Math
Una domanda, posta una volta sola
Una scatola nera calcola f da n bit a un bit, e la si può interrogare solo sugli ingressi. Essere certi se f sia costante o bilanciata costa classicamente mezza tabella più una chiamata. Hadamard su tutto, UNA chiamata con la risposta come segno, di nuovo Hadamard - e l'esito tutti zeri decide. La tabella di verità qui è cliccabile, quindi la promessa si può rompere a mano: per qualsiasi tabella la risposta esce con probabilità (1 − 2k/N)². E se la tabella risulta essere f(x) = s·x, quella sola chiamata restituisce s stessa.
Cosa succede
Una scatola nera calcola una funzione f da n bit a un bit. È promesso che sia costante oppure bilanciata - la stessa risposta ovunque, o una risposta su esattamente metà degli ingressi - e bisogna dire quale. Classicamente non c'è scorciatoia: metà tabella può concordare e la voce successiva rovinare tutto, quindi la certezza costa N/2 + 1 chiamate. Nove con sedici ingressi, trentatré con sessantaquattro. Ora la versione quantistica, ed è in tre righe. Hadamard su ogni qubit, così tutti gli N ingressi sono chiesti insieme. Chiama l'oracolo - che non risponde con un bit ma con un SEGNO: un meno su ogni ingresso dove f vale uno. Hadamard di nuovo su ogni qubit. Misura. Se tutti i qubit leggono zero, f era costante; qualunque altra cosa significa bilanciata, e il tutto è costato una chiamata. Questo modulo va oltre la dimostrazione perché la tabella in alto è cliccabile. Rompi la promessa: gira una cella e f non è né costante né bilanciata, e l'algoritmo non fallisce - degrada di una quantità che si può scrivere. Per QUALSIASI tabella l'esito tutti zeri ha probabilità (1 − 2k/N)², dove k conta gli uni della tabella. Costante è k = 0 e dà uno. Bilanciata è k = N/2 e dà esattamente zero. Una cella girata con sedici ingressi dà 4/256, un'esecuzione su sessantaquattro, e il pannello dice il numero prima che tu conti. Ecco quanto vale una promessa dentro un algoritmo, in cifre. Qui si nasconde una seconda cosa. Quando la tabella è lineare - f(x) = s·x mod 2 per una stringa nascosta s -, gli stessi tre passi non rispondono soltanto sì o no: l'esito È s, con probabilità uno, e ogni altro esito ha esattamente zero. Questo è Bernstein-Vazirani, e classicamente costa n chiamate, una per bit. Chiedi una volta, leggi tutta la stringa. Sotto entrambi i fatti c'è una formula: l'ampiezza dell'esito y è la trasformata di Walsh-Hadamard di (−1)^f, e il modulo la ricalcola direttamente dalla tabella per poterle tenere insieme.
Equazioni del modulo
Equazioni i tre passi: H su ogni qubit; una chiamata all'oracolo come segno, |x> -> (−1)^f(x) |x>; di nuovo H su ogni qubit ampiezza dell'esito y: (1/N) somma su x di (−1)^(f(x) + x·y) - la trasformata di Walsh-Hadamard di (−1)^f P(tutti zeri) = (1 − 2k/N)² dove k è il numero di uni della tabella di verità - ESATTAMENTE, per qualsiasi tabella costante (k = 0 o N): 1; bilanciata (k = N/2): 0; una cella di una tabella bilanciata invertita: 4/N² = 1/64 per N = 16 costo classico per essere CERTI: N/2 + 1 chiamate (3, 5, 9, 17, 33 per n = 2…6) contro 1 tabella lineare f(x) = s·x mod 2 (Bernstein-Vazirani): l'esito È s, probabilità 1, ogni altro esito esattamente 0; costo classico n chiamate, una per bit f = 1 ovunque dà esattamente le stesse probabilità di f = 0 ovunque - la differenza è un segno globale, e un segno globale non è misurabile conteggio, 2000 esecuzioni con n = 4: costante: 2000 su 2000 danno tutti zeri; nascosto s = 11: 2000 su 2000 danno 11; bilanciata: 0 danno tutti zeri; una cella invertita: 30 (esatto 31.25)
