Algoritmul Grover, publicat de Lov Grover în 1996, oferă o accelerare pătratică pentru căutarea nestructurată. Pentru un spațiu de căutare de N elemente, căutarea clasică necesită O(N) interogări, în timp ce algoritmul Grover necesită doar O(√N). Algoritmul funcționează prin aplicarea repetată a „operatorului de difuzie Grover” (care amplifică amplitudinea stării țintă, suprimându-le pe celelalte) printr-un proces numit amplificarea amplitudinii. După aproximativ π√N/4 iterații, măsurarea stării produce elementul țintă cu o probabilitate ridicată. Algoritmul Grover este demonstrabil optim. Niciun algoritm cuantic nu face mai bine pentru căutarea nestructurată. Aplicațiile includ căutarea în baze de date, rezolvarea problemelor NP-dificile și criptanaliza cuantică. HLQuantum include o implementare Grover integrată.
Termeni asociați
Circuit Cuantic
FundamentalsO secvență de porți cuantice aplicate unui registru de qubiți, urmată de măsurători.
Poarta Hadamard
GatesPoarta H: creează o suprapunere egală a lui |0⟩ și |1⟩ dintr-o stare de bază.
QFT
AlgorithmsQuantum Fourier Transform: analogul cuantic al transformatei Fourier discrete, exponențial mai rapid.
Algoritmul Deutsch-Jozsa
AlgorithmsUn algoritm cuantic timpuriu care determină dacă o funcție ascunsă este constantă sau echilibrată printr-o singură interogare, față de până la jumătate din intrările posibile clasic, important istoric ca prima dovadă că computerele cuantice pot oferi o accelerare exponențială.
Estimarea Amplitudinii
AlgorithmsUn algoritm cuantic care estimează amplitudinea de probabilitate a unui rezultat marcat, pătratic mai rapid decât eșantionarea Monte Carlo clasică, baza accelerărilor cuantice propuse în evaluarea instrumentelor derivate și analiza riscului.