Extendi's Logo (Dark)

2min read

Abbiamo provato il Quantum Computing di IBM utilizzando l'algoritmo di Grover con Qiskit

Ho provato Quantum Experience di IBM: sono qui per condividere la mia esperienza con questa nuova tecnologia e darti le istruzioni per provarla! Come hai letto nel mio primo articolo, il Quantum Computing è sensibilmente più veloce dei computing tradizionale. Qui lo dimostreremo attraverso l'algoritmo di Grover tramite Qiskit.

Duccio Giovannelli

By Duccio Giovannelli

Founder

13 May 2021

IBM Quantum Computer - image abstract

Introduzione

L'idea alla base dei computer quantistici è che la loro capacità di calcolo è esponenzialmente maggiore rispetto ai classici hardware. Un algoritmo quantistico in esecuzione su un computer quantistico beneficia delle cosiddette proprietà quantistiche: superposition, entanglement e interference.

La superposition è il fenomeno quantistico in cui un sistema quantistico può esistere in più stati o posti contemporaneamente.

L'entanglement è una forte correlazione esistente tra due o più particelle quantistiche.

L'interference consente la misurazione di un qubit verso uno stato o un insieme di stati desiderati.

Il fatto che il Quantum Computing sia più veloce del computing tradizionale può essere dimostrato attraverso l'algoritmo di Grover tramite Qiskit, un framework open source per il quantum development che fornisce strumenti per creare e manipolare programmi quantistici su IBM Quantum Experience (la piattaforma online che consente l'accesso pubblico ai servizi di calcolo quantistico di IBM).

Dimostrazione dell'algoritmo di Grover con Qiskit

Il secondo algoritmo quantistico più famoso che dimostra come un computer quantistico supera un computer classico è l'algoritmo di Grover, che si concentra sulla ricerca di un elemento in un elenco non ordinato, quadraticamente più veloce del miglior algoritmo classico. Puoi trovare l'esempio completo qui, ma proviamo a ricapitolare i suoi concetti principali.

Supponiamo di avere un elenco di N elementi non ordinati e di dover cercare la posizione di un elemento. Con un algoritmo classico, dovresti controllare in media N/2 elementi per trovare l'elemento che stai cercando, nel peggiore dei casi -l'elemento è l'ultimo- l'intero elenco. Questa può essere considerata una complessità O(N). Con l'amplitude amplification di Grover sarebbe √N, un aumento di velocità quadratico!

L'implementazione di Grover è una funzione in cui dato un input restituisce il suo negativo se l'input è il vincitore.

La funzione Oracle

Oracle Function

nota: |ω⟩ è lo winning state (l'indice che stai cercando nella lista). |𝑥⟩ è la notazione Dirac per un generic input qubit.

Se consideriamo 2 qubit, in modo da poter rappresentare 4 stati di input (00, 01, 10, 11), se assumiamo 11 come winning state, l'oracle Uω restituisce -11.

Amplitude Amplification

Il risultato dell'oracle in sé non basta, bisogna applicare la riflessione per amplificare le probabilità di ottenere lo winning state.

Ecco una rappresentazione geometrica che aiuta a capire come funziona:

Amplitude Amplification

fonte: Wikipedia

Dove: |s⟩ è uniform superposition su tutti gli stati

Uniform superposition over all states

Per un qubit e 2 stati: 1/√2 |0⟩ + 1/√2 |1⟩

|ω⟩ e |s⟩ non sono del tutto perpendicolari perché |ω⟩ si trova nella superposition con ampiezza 1/√N

|s'⟩ = |s⟩ - |ω⟩ è perpendicolare a |ω⟩

UₛUω |s⟩ (diffusore di Grover) = 2 |s⟩⟨s| − I

La somma di oracle più riflessione è chiamata iterazione di Grover. Per ottenere i risultati l'iterazione viene ripetuta O(√N) volte.

Come testarlo nel Quantum Computer di IBM

Per testare il circuito di Grover su IBMQ, registrati qui e ottieni un token.

Ecco il codice per 2 qubit:

code for 2 qubits

La probabilità dello winning state è 0.949

Probability of the winning state

Share

About Author

Duccio Giovannelli

Duccio Giovannelli

Founder

Duccio is Extendi's mastermind for AI and Machine Learning. When he is not training algorithms you can find him diving on reefs, sailing, and taking beautiful pictures.

Iscriviti

Per saperne di più, iscriviti alla nostra newsletter e riceverai aggiornamenti periodici, i migliori approfondimenti e alcuni preziosi consigli.

Extendi logo

Enabling Digital Innovation

Newsletter

Language

Italiano

|

English

Copyright © 2022 · Privacy policy

P.iva 06304560482