L'algoritmo di Grover su macchine classiche probabilistiche

Question

Come punto di partenza per questa domanda, mi sono imbattuto in Questa domanda , che AIUI sta citando una costruzione che mostra come simulare circuiti quantistici con una $ PP $ algoritmo, cioè implicando il calcolo quantico in generale è in $ PP $ .

Tuttavia, mi ha colpito come controintuitivo per dire che il modo solo per implementare un esempio specifico di QC, come l'algoritmo di Grover, sarebbe quello di farlo emulando un computer quantico e lo correre lì dentro . Ho quindi cercato di immaginare ciò che l'implementazione è più naturalmente potrebbe sembrare, ad es. Operazioni in termini di elementi elenchi direttamente piuttosto che trasformarli in un vettore di stato quantistico.

Per lo sfondo, capisco che non- $ BPP $ algoritmi in $ PP $ è permesso Sii arbitariamente vicino a caso, e quindi abbiamo potenzialmente bisogno di ripeterli esponenzialmente molte volte per arrivare a qualsiasi particolare fiducia nella loro risposta. Sono specificamente interessato a quale single iterazione (che quindi deve essere ripetuta esponenzialmente molte volte) di un algoritmo di Grover, sembra. Presumo, dal fatto che la traduzione nel thread collegata è 1-1, che questa singola iterazione dovrebbe prendere $ o (\ sqrt n) $ , Ma per favore fammi sapere se questa inferenza non è corretta.

(Sto anche presumendo che questo algoritmo simile a un grello è non in $ BPP $ , perché altrimenti la teoria della ricerca sarebbe molto diverso. Essere fuori $ BPP $ significa che stiamo parlando di un algoritmo di ricerca che in pratica prende $ o (2 ^ \ sqrt n) $ tempo, che non rivoluzionerà nulla.)

anche, poiché $ PP $ è generalmente definito in termini di problemi decisionali binari e l'algoritmo di Grover non è uno, ho dovuto estrapolare leggermente ciò che i criteri di successo Come in una classe $ PP $ anziché $ BQP $ contesto. I criteri che ho inventato in modo provviso è che l'algoritmo dovrebbe essere creato e scegliere da una distribuzione della probabilità sulla $ N $ elementi di un elenco, con la proprietà che la proprietà Probabilmente l'oggetto da selezionare è il (A, se più di uno) elemento contrassegnato dalla funzione Oracle, cioè ha la plurità, ma non necessariamente la maggioranza , della massa di probabilità.

che ha gli ovvi avvertimenti che perché l'elenco in generale contiene più di due elementi, non è più probabile che quell'articolo venga selezionato, solo che nessun oggetto singolo è più probabile. La differenza di probabilità tra la maggior parte e il secondo oggetto più probabile viene scelto è anche permesso di essere arbibarariamente piccolo. Un algoritmo che restituisce l'elemento contrassegnato da un elenco di $ N $ con probabilità $ \ frac {1} {n} + 2 ^ {- n} $ sarebbe permesso finché tutti gli altri oggetti erano meno probabili.

C'è qualche lavoro esistente su algoritmi che raggiungono il risultato corrispondente come gli algoritmi quantitativi specifici di Grover (o simili), ma in termini più diretti / naturali?

Answer 1

Let $ f $ Sii una funzione che mappa integevoli da $ 0 \ dots n-1 $ a $ \ {0, 1 \} $ . Vogliamo trovare $ x $ (che è promesso di essere univoco) tale che:

$$ f (x)= 1 $$

Ora prendiamo due numeri interi casuali $ A $ e $ B $ da $ 0 \ Dots N-1 $ e uscita:

.
1. $ B $ , se $ f (a)= 0 $
2. $ a $ , se $ f (a)= 1 $

per qualsiasi file fisso $ x $ e $ y $ Abbiamo:

$$ p_ {a= x}= p_ {b= x}= p_ {a= y}= p_ {b= y}=frac {1} {n } \\ P_ {a \ ne x}= p_ {b \ ne x}= p_ {a \ ne y}= p_ {b \ ne y}=frac {n-1} {n} $$ .

sapendo che $ a $ e $ B $ sono variabili casuali indipendenti, la probabilità che produciamo $ x $ è

$$ p_ {a= x \ lor a \ ne x \ Land b= x}= P_ {A= X} + P_ {A \ NE X} P_ {B= X}= \ frac {1} {n} + \ frac {n - 1} {n ^ 2} $$

E la probabilità che produciamo qualche altro valore $ y \ ne x $ è

$$ p_ {a \ ne x \ Land b= y}= p_ {a \ ne x} p_ {b= y}= \ frac {n - 1} {n ^ 2} <\ frac {1} {n} $$