Kvantoptimeringsalgoritmer

Kvantoptimeringsalgoritmer är kvantalgoritmer som används för att lösa optimeringsproblem. Matematisk optimering handlar om att hitta den bästa lösningen på ett problem (enligt vissa kriterier) från en uppsättning möjliga lösningar. Oftast är optimeringsproblemet formulerat som ett minimeringsproblem, där man försöker minimera ett fel som beror på lösningen: den optimala lösningen har det minimala felet. Olika optimeringstekniker tillämpas inom olika områden som mekanik , ekonomi och ingenjörskonst , och när komplexiteten och mängden data ökar behövs effektivare sätt att lösa optimeringsproblem. Kraften i kvantberäkning kan tillåta att problem som inte är praktiskt genomförbara på klassiska datorer kan lösas, eller föreslå en avsevärd hastighet upp med avseende på den mest kända klassiska algoritmen.

Kvantdataanpassning

Dataanpassning är en process för att konstruera en matematisk funktion som bäst passar en uppsättning datapunkter. Passformens kvalitet mäts med vissa kriterier, vanligtvis avståndet mellan funktionen och datapunkterna.

Anpassning för minsta kvantum

En av de vanligaste typerna av dataanpassning är att lösa minsta kvadratproblemet , minimera summan av kvadraterna av skillnader mellan datapunkterna och den anpassade funktionen.

Algoritmen ges som indata $N$ datapunkter $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})$ och $M$ kontinuerliga funktioner $f_{1},f_{2},...,f_{M}$ . Algoritmen hittar och ger som utdata en kontinuerlig funktion $f_{\vec {\lambda }}$ som är en linjär kombination av $f_{j}$ :

f_{\vec {\lambda }}(x)=\summa _{j=1}^{M}f_{j }(x)\lambda _{j}

Algoritmen hittar med andra ord de komplexa koefficienterna $\lambda _{j}$ , och finner därmed vektorn ${\ vec {\lambda }}=(\lambda _{1},\lambda _{2},...,\lambda _{M})$ .

Algoritmen syftar till att minimera felet, vilket ges av:

E=\sum _{i=1}^{N}\left\vert f_{\vec {\lambda }}(x_{i})-y_{i}\right\vert ^{2} =\summa _{i=1}^{N}\left\vert \sum _{j=1}^{M}f_{j}(x_{i})\lambda _{j}-y_{i} \right\vert ^{2}=\left\vert F{\vec {\lambda }}-{\vec {y}}\right\vert ^{2}

där vi definierar $F$ som följande matris:

{ F}={\begin{pmatrix}f_{1}(x_{1})&\cdots &f_{M}(x_{1})\\f_{1}(x_{2})&\cdots &f_{M }(x_{2})\\\vdots &\ddots &\vdots \\f_{1}(x_{N})&\cdots &f_{M}(x_{N})\\\end{pmatrix}}

Anpassningsalgoritmen för minsta kvantum använder sig av en version av Harrow, Hassidim och Lloyds kvantalgoritm för linjära ekvationssystem ( HHL), och matar ut koefficienterna $\lambda _{j}$ och passningskvaliteten uppskattning $E$ . Den består av tre subrutiner: en algoritm för att utföra en pseudo- invers operation, en rutin för uppskattning av passningskvaliteten och en algoritm för att lära in passningsparametrarna.

Eftersom kvantalgoritmen huvudsakligen är baserad på HHL-algoritmen, föreslår den en exponentiell förbättring i fallet där $F$ är sparsamt och villkorsnumret (nämligen förhållandet mellan de största och de minsta egenvärdena ) för både $FF^{\dolk }$ och $F^{\dolk }F$ är liten.

Quantum semidefinite programmering

Semidefinite programmering (SDP) är ett optimeringsunderfält som handlar om optimering av en linjär objektivfunktion (en användarspecificerad funktion som ska minimeras eller maximeras), över skärningspunkten mellan konen av positiva semidefinita matriser med ett affint utrymme . Objektivfunktionen är en inre produkt av en matris $C$ (given som indata) med variabeln $X$ . Beteckna med $\mathbb {S} ^{n}$ utrymmet för alla $n\ gånger n$ symmetriska matriser. Variabeln $X$ måste ligga i den (slutna konvexa) konen av positiva semidefinita symmetriska matriser $\mathbb {S} _{+}^{n}$ . Den inre produkten av två matriser definieras som:

$\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\summa _{i=1,j=1 }^{n}A_{ij}B_{ij}.$

Problemet kan ha ytterligare begränsningar (givna som input), också vanligtvis formulerade som inre produkter. Varje begränsning tvingar den inre produkten av matriserna $A_{k}$ (given som en indata) med optimeringsvariabeln $X$ att vara mindre än ett specificerat värde $b_{k }$ (givs som indata). Slutligen kan SDP-problemet skrivas som:

{\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{med förbehåll för}}&\ langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}

Det är inte känt att den bästa klassiska algoritmen körs ovillkorligt i polynomtid . Motsvarande genomförbarhetsproblem är känt för att antingen ligga utanför föreningen av komplexitetsklasserna NP och co-NP, eller i skärningspunkten mellan NP och co-NP.

Kvantalgoritmen

Algoritmingångarna $A_{1}...A_{m},C,b_{1}...b_{m}$ och parametrar avseende lösningens spårning , precision och optimala värde (objektivfunktionens värde vid det optimala punkt).

Kvantalgoritmen består av flera iterationer. I varje iteration löser den ett genomförbarhetsproblem , nämligen att hitta vilken lösning som helst som uppfyller följande villkor (som ger ett tröskelvärde ${\displaystyle t} )$ :

{\begin{array}{lr}\langle C,X\rangle _ {\mathbb {S} ^{n}}\leq t\\\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1 ,\ldots ,m\\X\succeq 0\end{array}}

väljs ett annat tröskelvärde ${\displaystyle t} , och algoritmen matar ut antingen en lösning$ $X$ så att $\langle C,X\rangle _{\mathbb {S} ^{n}}\leq t$ (och de andra begränsningarna är också uppfyllda) eller en indikation på att ingen sådan lösning existerar. Algoritmen utför en binär sökning för att hitta den minimala tröskeln $t$ för vilken en lösning $X$ fortfarande finns: detta ger den minimala lösningen på SDP-problemet.

Kvantalgoritmen ger en kvadratisk förbättring jämfört med den bästa klassiska algoritmen i det allmänna fallet, och en exponentiell förbättring när inmatningsmatriserna är av låg rang .

Kvantkombinatorisk optimering

Det kombinatoriska optimeringsproblemet syftar till att hitta ett optimalt objekt från en ändlig uppsättning objekt. Problemet kan formuleras som en maximering av en objektiv funktion som är summan av booleska funktioner . Varje boolesk funktion $\,C_{\alpha }\colon \lbrace {0,1\rbrace }^{n}\högerpil \lbrace {0,1} \rbrace$ får som indata $n$ -bitsträngen $z=z_{1}z_{2}\ldots z_{n}$ och ger som utgång ett bit (0 eller 1). Det kombinatoriska optimeringsproblemet med $n$ bitar och $m$ satser är att hitta en $n$ -bitsträng $z$ som maximerar funktionen

C(z)=\summa _{\alpha =1}^{m}C_{\alpha }(z)

Ungefärlig optimering är ett sätt att hitta en ungefärlig lösning på ett optimeringsproblem, som ofta är NP-hårt . Den ungefärliga lösningen av det kombinatoriska optimeringsproblemet är en sträng $z$ som är nära att maximera $C(z)$ .

Quantum approximativ optimeringsalgoritm

För kombinatorisk optimering hade kvantapproximativ optimeringsalgoritm (QAOA) kortvarigt ett bättre approximationsförhållande än någon känd klassisk polynomtidsalgoritm (för ett visst problem), tills en mer effektiv klassisk algoritm föreslogs. Den relativa hastigheten för kvantalgoritmen är en öppen forskningsfråga.

Hjärtat i QAOA förlitar sig på användningen av enhetsoperatorer beroende på $2p$ vinklar , där $p>1$ är ett inmatat heltal. Dessa operatorer appliceras iterativt på ett tillstånd som är en likaviktad kvantöverlagring av alla möjliga tillstånd i beräkningsbasen. I varje iteration mäts tillståndet i beräkningsbasen och $C(z)$ uppskattas. Vinklarna uppdateras sedan klassiskt för att öka $C(z)$ . Efter att denna procedur har upprepats ett tillräckligt antal gånger är värdet på $C(z)$ nästan optimalt, och tillståndet som mäts är också nära att vara optimalt.

År 2020 visades det att QAOA uppvisar ett starkt beroende av förhållandet mellan ett problems begränsning och variabler (problemdensitet), vilket sätter en begränsande begränsning på algoritmens kapacitet att minimera en motsvarande objektiv funktion .

Det insågs snart att en generalisering av QAOA-processen i huvudsak är en alternerande tillämpning av en kontinuerlig kvantvandring på en underliggande graf följt av en kvalitetsberoende fasförskjutning som tillämpas på varje lösningstillstånd. Denna generaliserade QAOA kallades QWOA (Quantum Walk-based Optimization Algorithm).

I artikeln How many qubits are needed for quantum computational supremacy inlämnad till arXiv drar författarna slutsatsen att en QAOA-krets med 420 qubits och 500 begränsningar skulle kräva minst ett sekel för att simuleras med en klassisk simuleringsalgoritm som körs på state-of-the -art superdatorer så det skulle vara tillräckligt för kvantberäkningsöverlägsenhet .

En noggrann jämförelse av QAOA med klassiska algoritmer kan ge uppskattningar av djup $p$ och antal qubits som krävs för kvantfördelar. En studie av QAOA och MaxCut algoritm visar att $p>11$ krävs för skalbar fördel.

Se även