Grovers algoritme

Grovers algoritme (også GSA fra engelsk.  Grover search algorithm ) er en kvantealgoritme til løsning af opregningsproblemet, det vil sige at finde en løsning på ligningen

hvor er en boolsk funktion af n variable. [1] Det blev foreslået af den amerikanske matematiker Lov Grover i 1996 .

Det antages, at funktionen er givet i form af en sort boks eller orakel , det vil sige, i løbet af løsningen kan du kun stille oraklet et spørgsmål som: "hvad er det lig på dette ?" , og brug svaret i yderligere beregninger. Det vil sige, at opgaven med at løse ligning (1) er en generel form for brute-force-problemet: her er det påkrævet at finde "adgangskoden til enheden ", som klassisk kræver en fuldstændig opregning af alle muligheder.

Grovers algoritme finder en rod af en ligning ved hjælp af funktionskald ved hjælp af qubits . [2]

Pointen med Grovers algoritme er at " øge amplituden " af måltilstanden ved at mindske amplituden af ​​alle andre tilstande. Geometrisk består Grovers algoritme i at rotere kvantecomputerens nuværende tilstandsvektor i retning nøjagtigt til måltilstanden (bevægelse langs den korteste vej sikrer optimaliteten af ​​Grovers algoritme). Hvert trin giver en drejning med en vinkel , hvor vinklen mellem og er . Yderligere fortsættelse af operatørens G 's iterationer vil give en fortsættelse af omsejlingen af ​​cirklen i det reelle plan genereret af disse vektorer.

Grovers "amplitudeforstærkning" ser ud til at være et grundlæggende fysisk fænomen i kvante-mangelegemeteorien. For eksempel er det nødvendigt at tage det i betragtning for at estimere sandsynligheden for begivenheder, der virker "sjældne". Processen, der implementerer Grover-algoritmen, fører til en eksplosiv vækst af en i starten ubetydelig amplitude, som hurtigt kan bringe den til virkelig observerbare værdier.

Grovers algoritme kan også bruges til at finde medianen og det aritmetiske middelværdi af en talserie. Derudover kan det bruges til at løse NP-komplette problemer ved at søge udtømmende blandt sættet af mulige løsninger. Dette kan resultere i betydelige hastighedsforøgelser i forhold til klassiske algoritmer, dog uden at give en " polynomiel løsning " i generelle vendinger.

Beskrivelse

Lad der være en enhedsoperator, der spejler Hilbert-rummet med hensyn til hyperplanet vinkelret på vektoren , er den tilstand, der svarer til roden af ​​ligning (1), er en ensartet superposition af alle tilstande.

Grovers algoritme består i at anvende operatoren på tilstanden et antal gange lig med heltalsdelen af ​​. Resultatet vil næsten matche staten . Ved at måle den opnåede tilstand får vi et svar med en sandsynlighed tæt på én.

Noter

Antag, at ligning (1) har rødder. Den klassiske algoritme til at løse et sådant problem ( lineær søgning ) kræver naturligvis opkald til for at løse problemet med sandsynlighed . Grovers algoritme giver dig mulighed for at løse søgeproblemet i tide , det vil sige rækkefølgen af ​​kvadratroden af ​​den klassiske, hvilket er en enorm speedup. Det er bevist, at Grovers algoritme er optimal i følgende henseender:

• Konstanten kan ikke forbedres [3] .
• Større kvanteacceleration end den kvadratiske kan ikke opnås [4] .

Grovers algoritme er et eksempel på et orakelafhængigt masseproblem . For mere specifikke problemer er det muligt at opnå en større kvanteacceleration. For eksempel giver Shor-faktoriseringsalgoritmen en eksponentiel forstærkning sammenlignet med de tilsvarende klassiske algoritmer.

Det faktum, at f er givet som en sort boks, påvirker ikke kompleksiteten af ​​både kvante- og klassiske algoritmer i det generelle tilfælde. Kendskab til "enheden" af funktionen f (for eksempel kendskab til kredsløbet, der definerer den fra funktionelle elementer) i det generelle tilfælde kan ikke hjælpe med at løse ligning (1). Søgning i en database refererer til at kalde en funktion, der tager en bestemt værdi, hvis x -argumentet matcher den søgte post i databasen.

Algoritmer, der bruger Grovers skema

• Algoritme til søgning efter ekstremum af en heltalsfunktion (P. Hoyer og andre). Leder efter den største værdi af funktionen . Kvantealgoritmen finder maksimum i f .
• Strukturel søgealgoritme (Farhi, Gutman). Løsningen af ​​ligning (1) søges under den yderligere betingelse , hvor er opdelingen af ​​strengen i to strenge af samme længde. Algoritmen har en kompleksitet af rækkefølgen af ​​kvadratroden af ​​klassisk tid.
• Algoritme til at finde matchende strenge i en database (Ambainis). Leder efter et par forskellige argumenter , hvor funktionen har samme værdi. Algoritmen kræver opkald til f .

Variationer og generaliseringer

• Lad Hamiltonian af et kvantesystem have formen , hvor og er operatorerne og hhv. Så fører den kontinuerlige enhedsudvikling med Hamiltonianeren , startende fra , naturligvis til . Kompleksiteten af ​​en sådan kontinuerlig analog af Grovers algoritme er nøjagtig den samme som for det diskrete tilfælde.
• En adiabatisk version af Grovers algoritme . Den langsomme udvikling af grundtilstanden af ​​typen under påvirkning af en Hamiltonianer afhængig af f , ifølge den adiabatiske sætning , over en ordenstid fører til tilstanden .

Noter

1. ↑ GSA omtales nogle gange unøjagtigt som et databaseopslag .
2. ↑ Algoritmens kompleksitet, for opgaven med oraklet kaldes også tidspunktet for dets arbejde, bestemmes af antallet af kald til oraklet.
3. ↑ Christof Zalka, Grovers kvantesøgningsalgoritme er optimal, Phys.Rev. A60 (1999) 2746-2751 [1]  (link ikke tilgængeligt)
4. ↑ Yuri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc. Roy. Soc. London. A455 (1999) 2165-2172 [2]

Links

• Grover L.K. Kvantemekanik hjælper med at finde en nål i en høstak (download)
• Loginov O. V. og Tsyganov A. V. Grover's Quantum Algorithm, St. Petersburg State University
• Kildetekster til en kvantecomputersimulator i C++ og implementeringer af Grovers algoritme med en detaljeret beskrivelse og diagrammer af kvanteporte