Implementera klassisk beräkning på en kvantdator

Slutförd

Nu när du förstår det klassiska problemet som du försöker lösa ska vi se hur du konverterar den här problembeskrivningen till en kvantåtgärd som kan användas av Grovers sökalgoritm och köras på en kvantdator.

Hur gör du beräkningar med ett superpositionstillstånd?

En av nyckelegenskaperna för kvantberäkning är möjligheten att utföra beräkningar som inte bara gäller för enskilda indata, utan även på superpositioner av indata. När vi arbetar med ett sökproblem och en speciell funktion $f(x)$ som beskriver instansen av ett sökproblem som vi försöker lösa, behöver vi kunna beräkna den här funktionen även på en superposition av indata.

Anteckning

Ett kvantorakel är en ”svartbox”-åtgärd som används som indata till en annan algoritm (i det här fallet Grover-algoritmen, men termen ”orakel” används i stor utsträckning även i klassisk databehandling). Vissa kvantalgoritmer beskrivs i termer av kvantorakel för att betona att de kan användas för många typer av problem, så länge som problemet kan implementeras effektivt som ett kvantorakel. För sådana algoritmer är deras körningsanalys vanligtvis antalet kvantanrop (det vill säga funktionsutvärderingar) i stället för de primitiva åtgärder som utförs av algoritmen.

När vi använder en algoritm som beskrivs i termer av kvantorakel för att lösa ett särskilt problem, måste vi implementera kvantoraklet för det här problemet. När det gäller Grover-algoritmen beräknar oraklet värdet för funktionen $f(x)$ som vi försöker invertera.

Det finns två vanliga sätt att koda effekterna av att använda en funktion för ett superpositionstillstånd – med hjälp av ett fasorakel eller med ett markeringsorakel.

Anta att vi vill implementera en kvantoperator $U$ som beräknar en funktion $f(x)$, som tar en enda bit som indata och skapar en enda bit som utdata. Vi börjar med ett superpositionstillstånd $a_0 |0\rangle + a_1 |1\rangle$.

  • Vi kan koda värdena $f(0)$ och $f(1)$ i relativa faser av grundtillstånd $|0\rangle$ och $|1\rangle$.
    I det här fallet konverterar operatorn $U_\textrm{phase}$ tillståndet $a_0 |0\rangle + a_1 |1\rangle$ till tillståndet $(-1)^{f(0)} a_0 |0\rangle + (-1)^{f(1)} a_1 |1\rangle$. Med andra ord ändrar operatorn $U_\textrm{phase}$ inte fasen i grundtillstånden som $f (x) = 0$, utan multiplicerar fasen i de grundtillstånd för vilka $f (x) = 1$ per $-1$.
    Operatorn $U_\textrm{phase}$ kallas för ett fasorakel.

  • Alternativt kan vi allokera en extra qubit $y$ och koda värdena $f(0)$ och $f(1)$ i tillståndet för denna kvantbit.
    I det här fallet delar vi upp det gemensamma tillståndet för våra datakvantbitar och den extra kvantbiten i en linjär kombination av grundtillstånd $a_{00} |0\rangle_x|0\rangle_y + a_{01} |0\rangle_x|1\rangle_y + a_{10} |1\rangle_x|0\rangle_y + a_{11} |1\rangle_x|1\rangle_y$ och tillämpar operatorn $U_\textrm{mark}$ för varje grundtillstånd separat. Den här operatorn transformerar ett grundtillstånd $|x\rangle|y\rangle$ till $|x\rangle|y \oplus f(x)\rangle$ ($\oplus$ är en addition av modulo 2). Med andra ord ändrar operatorn $U_\textrm{mark}$ inte grundtillstånden där $f(x) = 0$, och vänder tillståndet för den extra kvantbiten till de tillstånd där $f(x) = 1$. Den fullständiga påverkan på superpositionen kan härledas med det faktum att kvantoperatorer är linjära: det vill säga att vårt starttillstånd kommer att omvandlas till $a_{00} |0\rangle_x|f(0)\rangle_y + a_{01} |0\rangle_x|1 \oplus f(0)\rangle_y + a_{10} |1\rangle_x|f(1)\rangle_y + a_{11} |1\rangle_x|1 \oplus f(1)\rangle_y$. I det här fallet har den extra kvantbiten ofta sammanflätats med datakvantbitar.
    Operatorn $U_\textrm{mark}$ kallas för ett markeringsorakel.

Anteckning

Att utföra beräkningar på det här sättet är inte detsamma som att ”kunna utvärdera funktionen på alla indata samtidigt”! Kom ihåg att kvantmätningar begränsar mängden information som vi kan extrahera från ett kvantsystem, så i båda fallen kommer vi inte kunna extrahera alla funktionsvärden från en sådan beräkning. Vi behöver skapa en smart algoritm som drar nytta av att utföra beräkningen i superposition för att hitta svaret.

Det bästa sättet att representera klassiska beräkningar i en kvantalgoritm beror på målen:

  • Många kvantalgoritmer kräver att du använder den första metoden, att koda de klassiska funktionsvärdena i faser om grundtillstånd, eftersom den här metoden förenklar algoritmen.
  • Den andra metoden, att koda de klassiska funktionsvärdena i tillstånd av extra kvantbitar, gör det enklare att implementera de klassiska beräkningarna.
  • I praktiken ser vi ofta ett markeringsorakel som används för att implementera de klassiska beräkningarna och sedan konverteras till ett fasorakel som det sista steget innan åtgärden ansluts till resten av kvantalgoritmen.

En gren av klassisk datavetenskap som kallas reversibel databehandling ger oss de tekniker vi behöver för att implementera klassiska beräkningar på en kvantdator. I den sista enheten i den här modulen återvänder vi till frågan om att implementera kvantorakel effektivt när vi diskuterar de typer av problem som kan dra nytta av Grover-algoritmen.

I nästa enhet lär vi oss att implementera exempelproblemet med graffärgning som ett kvantorakel med hjälp av Q#.