Grovers sökalgoritm

Slutförd

I de föregående enheterna lärde du dig om sökproblemet och att implementera dess instanser som kvantoraklar.

Förberedelser är över! Förbered dig för ditt första verkliga uppdrag! I den här enheten implementerar du Grovers sökalgoritm. Det är inte nödvändigt att gå in närmare på implementeringsdetaljerna på grindnivå, men du fokuserar diskussionen på den avancerade logiken i stället.

För att göra det effektivt måste du se till att två anslutna stationer inte använder samma bandbredd.

Algoritmens kontur

Vi börjar med en översikt över algoritmen och diskuterar sedan varje steg i detalj.

  1. Vi börjar med att förbereda en lika stor superposition för alla grundtillstånd.
    Det här är ett vanligt första steg för kvantalgoritmer i allmänhet.

  2. Huvuddelen av algoritmen upprepar en sekvens av steg. Den här sekvensen kallas Grovers iteration och består av två steg:

    • Använd kvantoraklet – den här åtgärden multiplicerar faserna i alla tillstånd som är lösningar på vårt problem med $-1$, som vi såg tidigare i den här modulen. Observera att det här är det enda steget som använder informationen om vårt problem.

    • Använd den så kallade ”diffusionsoperatorn” – den här operatorn byter ut amplituderna för grundtillstånden enligt följande: de amplituder som är större än genomsnittet för amplituderna blir mindre och de amplituder som är mindre än genomsnittet blir större. Det här steget är inte beroende av vårt problem.

    Generellt minskar en iteration amplituderna för grund tillstånden som inte är lösningar på vårt problem och ökar amplituderna för de grund tillstånd som är lösningar, samtidigt som båda typerna av amplituder är positiva.

  3. Slutligen mäter vi systemets tillstånd. Upprepning av iterationen flera gånger introducerar betydande skillnader mellan de två typerna av amplituder, så att mätningen ger svar med hög sannolikhet.

Visualisering av algoritmen

Nu ska vi ta en titt på Grovers algoritm från en något annorlunda vinkel och visualisera systemtillstånden i varje steg.

Anta att vårt sökområde (vilket innebär alla möjliga värden som våra variabler kan ha) har $N$-element och att $M$ av dem är lösningar på vårt problem.

Vi definierar två tillståndsvektorer:

  • En lika stor superposition av $M$ ”bra” grundtillstånd (tillstånd som är lösningar på vårt problem)

    $$|\textrm{good}\rangle = \frac{1}{\sqrt{M}} \sum_{x : f(x) = 1} |x\rangle$$

  • En lika stor superposition av $N - M$ ”dåligt” grundtillstånd (tillstånd som inte är lösningar på vårt problem)

    $$|\textrm{bad}\rangle = \frac{1}{\sqrt{N-M}} \sum_{x : f(x) = 0} |x\rangle$$

Algoritmen skiljer sig aldrig från olika ”bra” och ”dåliga” tillstånd till den slutliga mätningen, så alla amplituder med ”bra” tillstånd är lika med varandra, och alla amplituder av ”dåliga” tillstånd är lika med varandra. Det innebär att vi alltid kan representera det övergripande systemtillståndet som en superposition i tillstånden $|\textrm{good}\rangle$ och $|\textrm{bad}\rangle$.

  1. Vi börjar med en lika stor superposition för alla grundtillstånd, både ”bra” och ”dåliga”. Det här tillståndet representeras på följande sätt:

    $$|\textrm{all}\rangle = \sqrt{\frac{M}{N}} |\textrm{good}\rangle + \sqrt{\frac{N-M}{N}} |\textrm{bad}\rangle$$

    Om vi föreställer oss ett plan där vektorerna $|\textrm{good}\rangle$ och $|\textrm{bad}\rangle$ motsvarar de lodräta och vågräta axlarna, kan vi rita upp det här tillståndet så här:

    Bild som visar en cirkel som illustrerar superpositionen för alla tillstånd.

    Vinkeln $\theta$ beror på procentandelen av ”bra” tillstånd bland alla grundtillstånd: $\sin \theta = \sqrt{\frac{M}{N}}$.

  2. Härnäst tillämpar vi oraklet. Kom ihåg att den här åtgärden multiplicerar amplituderna i ”bra” tillstånd med $-1$. I cirkeldiagrammet lämnar denna omvandling den vågräta komponenten i tillståndsvektorn oförändrad och kastar om dess lodräta komponent. Den här åtgärden är med andra ord en reflektion längs den vågräta axeln:

    Bild som visar en cirkel som illustrerar resultatet av den första reflektionen.

  3. Nu ska vi tillämpa diffusionsoperatorn. Dess inverkan är en annan reflektion, den här gången längs vektorn $|\textrm{all}\rangle$:

    Bild som visar cirkel som illustrerar resultatet av den andra reflektionen.

    Observera hur denna sekvens av två reflektioner blir en moturs rotation med en vinkel på $2\theta$. Om vi upprepar denna sekvens, som återspeglar det nya läget först utmed den vågräta axeln och sedan utmed vektorn $|\textrm{all}\rangle$, utför den en rotation med $2\theta$ igen. Rotationsvinkeln är bara beroende av vinkeln mellan reflektionsaxlarna och inte i det tillstånd som vi återspeglar.

  4. Om varje iteration vi gör roterar vår tillståndsvektor $2\theta$ moturs, när bör vi utföra mätningen?

    Sannolikheten för att få ett visst grundtillstånd när mätresultatet är lika med kvadratamplituden för detta tillstånd i superpositionen. Ju större amplitud, desto högre chans att få motsvarande tillstånd när du utför mätningen.

    Eftersom vårt mål är att få ett av de ”bra” tillstånden med en så hög sannolikhet som möjligt, måste vi öka amplituden för ”bra” tillstånd så mycket vi kan (och minska amplituderna för ”dåliga” tillstånd på motsvarande sätt). Detta innebär att vi vill rotera vår tillståndsvektor så nära den lodräta axeln som möjligt.

    Bild som visar en cirkel som illustrerar flera rotationer.

    Om vi väljer rätt antal iterationer kommer vi till det tillfälle då mätningen kommer att skapa ett korrekt svar med tillräckligt hög sannolikhet.

Algoritmanalys

Grovers sökalgoritm har flera viktiga egenskaper som är värda att lyftas fram explicit.

Grover-algoritmen är probabilistisk

Den slutliga mätningen ger ett resultat som löser vårt problem med hög sannolikhet, men vanligtvis inte med absolut säkerhet. I de flesta fall finns det fortfarande en liten sannolikhet för ett fel.

Vi måste ta itu med eventuella fel på samma sätt som vi hanterar klassiska slumpmässiga algoritmer: kontrollera om resultatet vi fick är en lösning på vårt problem och om det inte är det, köra om algoritmen från början. Tyvärr finns det inget sätt att använda resultatet som vi fick för att förbättra chansen att lyckas för nästa försök. Det genomsnittliga antalet gånger som algoritmen körs igen är dock inte beroende av problemets storlek.

Fler iterationer är inte nödvändigtvis bättre!

För många iterativa klassiska algoritmer går det långsamt att köra extra iterationer, men det reducerar inte nödvändigtvis sannolikheten att algoritmen lyckas. Grover-sökningen har en speciell ”nyckelpunkt” – antalet iterationer som ger högsta möjliga sannolikhet. Om vårt problem har $N$ möjliga variabeltilldelningar och $M$ av dem är lösningar på problemet, är det optimala antalet iterationer

$$R_{opt} \approx \frac{\pi}{4} \sqrt{\frac{N}{M}}$$

Att fortsätta att iterera förbi det antalet börjar minska sannolikheten tills vi når nästan noll lyckade sannolikheter för iteration $2 R_{opt}$. Därefter växer sannolikheten igen och närmar sig 100 % vid iteration $3 R_{opt}$ och så vidare.

Anteckning

För att förstå det här beteendet kan du tänka på cirkelvisualiseringen.

Efter $k$ iterationer, är vinkeln mellan den vågräta axeln och tillståndsvektorn lika med $2k+1$ och vi vill att den ska komma så nära $\frac{\pi}{2}$ som möjligt. För de flesta tillämpningar är $M$ mycket mindre än $N$, så vi kan uppskatta $\theta \approx \sin \theta = \sqrt{\frac{M}{N}}$. Detta gör det möjligt för oss att uppskatta det optimala antalet iterationer.

Det periodiska beteendet för lyckad sannolikhet kan förklaras med samma visualisering. Varje iteration är en rotation i samma riktning enligt en fast vinkel. Om vi fortsätter att iterera, kommer vi att överrotera vårt tillstånd, vilket startar länge och längre bort från den vertikala axeln, vilket minskar lyckad sannolikhet.

Bild som visar cirkel som illustrerar överrotation.

När tillståndet passerar den vågräta axeln för ytterligare rotationer den närmare den lodräta axeln från motsatt riktning, vilket ökar vår lyckade sannolikhet igen. (Kom ihåg att mätsannolikheter definieras av kvadrater av amplituder, inte bara amplituder.)

Men jag vet inte hur många lösningar mitt problem har!

I det här exemplet har du ett litet och lättanalysat problem, så du kan beräkna antalet lösningar för hand. I praktiska tillämpningar vet du normalt inte hur många lösningar ditt problem har innan du löser det.

För att hantera det här problemet kan du välja ett litet antal, köra algoritmen med så många iterationer, och om det inte ger ett svar kan du försöka igen med ett annat, större antal iterationer. En effektiv strategi för gradvis ökande upprepningsantal kommer fortfarande att hitta lösningen med ett genomsnittligt antal iterationer runt $\sqrt{\frac{N}{M}}$.

I nästa enhet implementerar du Grovers algoritm i Q# och kör den för att lösa hörnfärgningsproblem för utrymmeskommunikationsproblemet!