Deutsch-Jozsa malinteso

Question

Non riesco a capire l'algoritmo Deutsch-Jozsa. Come suggerisce wikipedia:${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$. La funzione accetta valori binari di n cifre come input e produce uno 0 o un 1 come output per ciascuno di questi valori. Ci viene promesso che la funzione è costante (0 su tutte le uscite o 1 su tutte le uscite) o bilanciata (restituisce 1 per metà del dominio di input e 0 per l'altra metà). Il compito quindi è determinare se {\ displaystyle f} f è costante o bilanciato usando l'oracolo.

Domanda 1: Se utilizzo l'algoritmo probabilistico su un normale computer, non posso inserire una sola volta un singolo 0 in Oracle, quindi inserire una volta un singolo 1. E ho finito.

Ho letto anche qui: http://www.diva-portal.org/smash/get/diva2:840938/FULLTEXT01.pdf: Considera che Bob genera un elenco di lunghezza arbitraria da una funzione bilanciata. Quindi l'elenco conterrà ugualmente molti zeri e uno, quindi se Alice disegna un elemento casuale nell'elenco sarà uno zero o uno con una probabilità di 1/2. Se disegna due elementi. quindi può ottenere i risultati "00", "01", "10" e "11", ciascuno con una probabilità uguale di 1/4. Se Alice ora deve indovinare se la funzione era costante o bilanciata, indovinerà correttamente la metà delle volte. Se invece disegna un terzo elemento, il risultato sarà una distribuzione di probabilità uniforme sui seguenti possibili risultati "000", "001", "010", "011", "100", "101", "110" e "111 ". Alice ora indovinerà correttamente sei volte su otto.

Domanda 2: Quindi se lei ha "001" (o vigilia "01" / "10") non è già una funzione bilanciata?

Answer 1

Per quanto riguarda la tua prima domanda, ci sono $n$ input a $f$ e il compito è determinare se $f$è costante o equilibrato (sotto la promessa che è l'uno o l'altro); puoi farlo su un computer quantistico con una singola query a$f$. Se$n=1$, quindi classicamente puoi fare come suggerisci, input $0$ per una query e input $1$ per un'altra query, per un totale di due query, ma il computer quantistico vince ancora con una sola query.

Per quanto riguarda la tua seconda domanda, sì, hai ragione; se mai classicamente ottieni due uscite che differiscono, allora (sotto la promessa) puoi essere sicuro che la funzione è bilanciata. Tuttavia, Deutsch-Josza osserva che puoi garantire che sia bilanciato con una sola query.

Classicamente ne servono almeno due e fino a $2^{n-1}+1$, query, ma dal punto di vista quantistico è sufficiente una singola query.

Answer 2

Se non l'hai già fatto, inizia dando un'occhiata all'algoritmo di Deutsch, che è la versione a qubit singolo dell'algoritmo Deutsch-Jozsa che stai guardando.

Ecco alcune risorse veloci:

• http://www.cs.xu.edu/~kinne/quantum/deutche.html
• https://www.youtube.com/watch?v=5xsyx-aNClM

È più semplice di Deutsch-Jozsa e un buon trampolino di lancio.