Grovers algoritm

Grovers algoritm (även GSA från engelska.  Grover search algorithm ) är en kvantalgoritm för att lösa uppräkningsproblemet, det vill säga hitta en lösning på ekvationen

där är en boolesk funktion av n variabler. [1] Det föreslogs av den amerikanske matematikern Lov Grover 1996 .

Det antas att funktionen ges i form av en svart låda , eller orakel , det vill säga under lösningen kan du bara ställa oraklet en fråga som: "vad är det lika med på detta ?" , och använd svaret i ytterligare beräkningar. Det vill säga uppgiften att lösa ekvation (1) är en allmän form av brute-force-problemet: här krävs det att hitta "lösenordet till enheten ", vilket klassiskt kräver en fullständig uppräkning av alla alternativ.

Grovers algoritm hittar någon rot av en ekvation med hjälp av funktionsanrop med hjälp av qubits . [2]

Poängen med Grovers algoritm är att " öka amplituden " för måltillståndet genom att minska amplituden för alla andra tillstånd. Geometriskt består Grovers algoritm i att rotera kvantdatorns nuvarande tillståndsvektor i riktning exakt mot måltillståndet (förflyttning längs den kortaste vägen säkerställer optimaliteten hos Grovers algoritm). Varje steg ger en rotation med en vinkel , där vinkeln mellan och är . Ytterligare fortsättning av iterationerna av operatören G kommer att ge en fortsättning på cirkelns omlopp i det verkliga planet som genereras av dessa vektorer.

Grovers "amplitudförstärkning" verkar vara ett fundamentalt fysiskt fenomen i kvantmångkroppsteorin. Till exempel är det nödvändigt att ta hänsyn till det för att uppskatta sannolikheterna för händelser som verkar "sällsynta". Processen som implementerar Grover-algoritmschemat leder till en explosiv tillväxt med en initialt försumbar amplitud, vilket snabbt kan föra den till riktigt observerbara värden.

Grovers algoritm kan också användas för att hitta medianen och det aritmetiska medelvärdet för en talserie. Dessutom kan den användas för att lösa NP-kompletta problem genom att uttömmande söka bland uppsättningen av möjliga lösningar. Detta kan resultera i betydande hastighetsvinster jämfört med klassiska algoritmer, dock utan att tillhandahålla en " polynomlösning " i allmänna termer.

Beskrivning

Låt det finnas en enhetlig operator som speglar Hilbert-utrymmet med avseende på hyperplanet vinkelrätt mot vektorn , är det tillstånd som motsvarar roten av ekvation (1), är en enhetlig överlagring av alla tillstånd.

Grovers algoritm består av att applicera operatören på tillståndet ett antal gånger lika med heltalsdelen av . Resultatet kommer nästan att matcha staten . Genom att mäta det erhållna tillståndet får vi ett svar med en sannolikhet nära ett.

Anteckningar

Antag att ekvation (1) har rötter. Den klassiska algoritmen för att lösa ett sådant problem ( linjär sökning ) kräver uppenbarligen anrop till för att lösa problemet med sannolikhet . Grovers algoritm låter dig lösa sökproblemet i tid , det vill säga ordningen på kvadratroten av den klassiska, vilket är en enorm snabbhet. Det är bevisat att Grovers algoritm är optimal i följande avseenden:

• Konstanten kan inte förbättras [3] .
• Större kvantacceleration än den kvadratiska kan inte erhållas [4] .

Grovers algoritm är ett exempel på ett orakelberoende massproblem . För mer speciella problem är det möjligt att få en större kvantacceleration. Till exempel ger Shor-faktoriseringsalgoritmen en exponentiell förstärkning jämfört med motsvarande klassiska algoritmer.

Det faktum att f ges som en svart låda påverkar inte komplexiteten hos både kvantalgoritmer och klassiska algoritmer i det allmänna fallet. Kunskap om "enheten" för funktionen f (till exempel kunskap om kretsen som definierar den från funktionella element) i det allmänna fallet kan inte hjälpa till att lösa ekvation (1). Att söka i en databas syftar på att anropa en funktion som tar ett visst värde om x -argumentet matchar den sökta posten i databasen.

Algoritmer som använder Grovers schema

• Algoritm för att söka efter extremumet av en heltalsfunktion (P. Hoyer och andra). Letar efter det största värdet av funktionen . Kvantalgoritmen hittar maximum i f .
• Strukturell sökalgoritm (Farhi, Gutman). Lösningen av ekvation (1) söks under det ytterligare villkoret , där är uppdelningen av strängen i två strängar av samma längd. Algoritmen har en komplexitet av ordningen av kvadratroten av klassisk tid.
• Algoritm för att hitta matchande strängar i en databas (Ambainis). Letar efter ett par olika argument , där funktionen har samma värde. Algoritmen kräver anrop till f .

Variationer och generaliseringar

• Låt Hamiltonian för ett kvantsystem ha formen , där och är operatorerna respektive . Sedan leder den kontinuerliga enhetliga utvecklingen med Hamiltonian , med början från , naturligtvis till . Komplexiteten hos en sådan kontinuerlig analog av Grovers algoritm är exakt densamma som för det diskreta fallet.
• En adiabatisk version av Grovers algoritm . Den långsamma utvecklingen av grundtillståndet av typen under inverkan av en Hamiltonian beroende på f , enligt den adiabatiska satsen , över en ordningstid leder till tillståndet .

Anteckningar

1. ↑ GSA kallas ibland felaktigt för en databasuppslagning .
2. ↑ Algoritmens komplexitet, för uppgiften med oraklet kallas också tiden för dess arbete, bestäms av antalet anrop till oraklet.
3. ↑ Christof Zalka, Grovers kvantsökningsalgoritm är optimal, Phys.Rev. A60 (1999) 2746-2751 [1]  (länk ej tillgänglig)
4. ↑ Yuri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc. Roy. Soc. London. A455 (1999) 2165-2172 [2]

Länkar

• Grover L.K. Quantum mechanics hjälper till att hitta en nål i en höstack (ladda ner)
• Loginov O. V. och Tsyganov A. V. Grover's Quantum Algorithm, St. Petersburg State University
• Källtexter för en kvantdatorsimulator i C++ och implementeringar av Grovers algoritm med en detaljerad beskrivning och diagram över kvantgrindar