O întrebare despre efectuarea de calcule cuantice pe suprapoziții uniforme

Ai putea fugi Algoritmul lui Grover deasupra $n$ biți din registru pentru $2^{n/2}$ pași, dar acest lucru este probabil mai puțin eficient decât ați sperat.

Orice lucru mai bun decât Grover este puțin probabil să funcționeze (nu sunt sigur cât de departe are ca rezultat „Algoritmul de căutare cuantică al lui Grover este optim" se extinde în cele ce urmează). Un astfel de algoritm ar fi suficient pentru a inversa o permutare arbitrară $\mathbb F_2^n$ (și de aici orice permutare ca corolar). Pentru a vedea acest lucru presupunem că suntem înzestrați cu un circuit $U_\pi$ pentru a ne evalua permutarea misterului $\pi(x)$. Noi creăm statul $|\phi\rangle|0^n\rangle$ si aplica $U_\pi$ a obtine $|\psi\rangle:=\sum 2^{-n/2}|x\rangle|\pi(x)\rangle$. Rețineți că finala $n$ biții sunt în stare $|\phi\rangle$ deoarece $\pi$ este o permutare. Dacă schimbăm prima și a doua jumătate a registrelor, atunci avem $\sum 2^{-n/2}|x\rangle|\pi^{-1}(x)\rangle$ iar rularea algoritmului nostru presupus pentru problema dvs. ne va permite să calculăm $\pi^{-1}(x^*)$ pentru orice $x^*$. Restricționarea la caz $0^n$ face pentru a reduce puterea unui astfel de algoritm luând în considerare funcția (respectiv permutarea) $f(x\oplus x^*)$ (resp. $\pi(x)\oplus x^*$).