Deutsch-Yozhi algoritm

Deutsch-Joja-algoritmen (även kallad Deutsch-Joza-algoritmen ) är en kvantalgoritm som föreslagits av David Deutsch och Richard Joja 1992 , och en av de första kvantalgoritmerna . Algoritmen är baserad på fenomenet kvantentanglement och superpositionsprincipen , på grund av vilken den visar kvantöverlägsenhet - mycket effektivare drift i jämförelse med kända klassiska algoritmer.

Deutschs algoritm är den första versionen av algoritmen utvecklad av Deutsch 1985 ; den betraktar en funktionav en variabel. $f(x_{1})$

Utmana

Det är känt att en boolesk funktion är konstant (den tar samma värde för alla argumentuppsättningar) eller balanserad (för hälften av argumentuppsättningarna tar den värdet , för den andra halvan tar den ). Det är nödvändigt att bestämma typen av funktionen genom att referera till oraklet som utvärderar funktionen så få gånger som möjligt. Vidare, för korthetens skull, kan hela uppsättningen också betecknas med ett tal från till med motsvarande binära notation . $f(x_{1},x_{2},\dots ,x_{n})$ $0$ $ett$ $x_{1},x_{2},\dots ,x_{n}$ $0$ $2^{n}-1$

För att få ett exakt svar behöver varje klassisk deterministisk algoritm i värsta fall göra anrop till oraklet, eftersom de första beräkningarna kan ge samma värde, trots att funktionen är balanserad. Den klassiska probabilistiska algoritmen kommer att kräva färre beräkningar för att garantera en hög sannolikhet att få rätt svar, men den kommer också att nå enhet först efter inte mindre än beräkningar. $2^{{n-1}}+1$ $2^{{n-1}}$ $2^{{n-1}}+1$

I kvantinställningen sker beräkningen av en funktion i form av ett anrop till ett kvantorakel , vilket ger en enhetlig transformation som verkar på en uppsättning qubits som fungerar som argument för funktionen, såväl som en mål-qubit , på som beräkningarna kommer att återspeglas. Resultatet av en sådan transformation för varje egentillstånd är mängden , där är beteckningen för det exklusiva "eller" , motsvarande resultatet av driften av kontrollerad negation av en qubit med hjälp av en qubit . Eftersom enhetstransformationer är linjära definieras resultatet av en given transformation för en superposition av egentillstånd som $U_{f}$ $|x_{1}x_{2}\dots x_{n}\rangle |y\rangle =|x\rangle |y\rangle$ $n$ $x_{1},x_{2},\dots ,x_{n}$ $y$ $|x\rangle$ $|x\rangle |y\oplus f(x)\rangle$ $\ plus$ $|y\rangle$ $|f(x)\rangle$ $|x\rangle =\alpha _{0}|0\rangle +\ldots +\alpha _{2^{n}-1}|2^{n}-1\rangle$ $U_{f}(|x\rangle |y\rangle )=\alpha _{0}|0\rangle |y\oplus f(0)\rangle +\ldots +\alpha _{2^{n }-1}|{2^{n}-1}\rangle |y\oplus f(2^{n}-1)\rangle .$

För Deutsch-Jozhi-algoritmen räcker ett enda anrop till kvantorakelet för att tillförlitligt lösa problemet.

Algoritm

Algoritmen är baserad på Hadamard-transformen , som resulterar i superpositioner av qubit -egentillstånd ${\textstyle H}$

|+\rangle =H|0\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle +|1\rangle {\big )},

|-\rangle =H|1\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}.

Om, vid åtkomst till oraklet, mål-qubiten är i tillståndet , implementerar oraklet den så kallade fasfrågan, vars resultat för egentillstånd är att multiplicera hela tillståndet med [1] : $|-\rangle$ ${\displaystyle (-1)^{f(x)))$

U_{f}{\big (}|x\rangle |-\rangle {\big )}={\frac {1}{\sqrt {2))}|x\rangle {\big (}| f(x)\rangle -|1\oplus f(x)\rangle {\big )}=(-1)^{f(x)}|x\rangle |-\rangle .

Således, i fallet med överlagring av tillstånd, inverterar fasfrågan fasen för alla tillstånd som motsvarar , och lämnar tillstånden som motsvarar oförändrade . Som ett fasfrågeargument använder Deutsch-Joji-algoritmen tillståndet $x$ $f(x)=1$ $f(x)=0$

H^{\otimes n}|0\rangle ^{\otimes n}=|+\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n)))) \sum \limits _{x\in \{0,1\}^{n}}|x\rangle ,

som är en enhetlig överlagring av alla egentillstånd för en uppsättning qubits. Här betecknar exponentiering genom en tensor (Kronecker) produkt . Resultatet av att tillämpa en fasfråga på ett sådant tillstånd är $n$ $\otimes n$ $n$

U_{f}{\big (}|+\rangle ^{\otimes n}|-\rangle {\big )}={\frac {1}{\sqrt {2^{n)))) \sum \limits _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle |-\rangle .

Efter återapplicering av transformationen på de första kvantbitarna kommer tillståndsamplituden att vara lika med ${\displaystyle H^{\otimes n))$ $n$ ${\displaystyle |0\rangle ^{\otimes n))$

{\frac {1}{2^{n}}}\summa \limits _{x\in \{0,1\}^{n}}(-1)^{f(x)},

det vill säga med eller med , eller om funktionen är balanserad. Att kontrollera balansen för en funktion är alltså likvärdigt med att kontrollera att alla qubits är i tillståndet i slutet av algoritmen. $ett$ $f(x)=0$ $-ett$ $f(x)=1$ $0$ $|0\intervall$

Algoritmen är med andra ord tillämpningen av operatorn på nollvektorn och mätningen av registrets tillstånd. Om alla registerbitar är lika beror värdet på funktionen inte på , annars är funktionen balanserad. ${\displaystyle |0\rangle ^{\otimes n))$ ${\displaystyle H^{\otimes n}U_{f}H^{\otimes n))$ $0$ $f(x)$ $x$

Om funktionen är obalanserad kan algoritmen ge svaret "konstant" med en sannolikhet som växer med ökningen av skillnaden mellan antalet "0" och "1" [2] . $f$

Funktionen av algoritmen på exemplet med Deutsch-problemet

Indata till algoritmen är en boolesk funktion av en variabel . Det finns fyra sådana funktioner [1] : $f(x)$

Nej.	$f(0)$	$f(1)$
ett	0	0	$f(x) \ekvivalent 0$
2	ett	ett	$f(x)\ekvivalent 1$
3	0	ett	$f(x) = x$
fyra	ett	0	$f(x)=\neg x$

Funktionerna 1 och 2 är konstanta och funktionerna 3 och 4 är balanserade.

I det första steget ges qubiten ett nolltillstånd:

|\varphi \rangle =1\cdot |0\rangle +0\cdot |1\rangle .

Att tillämpa Hadamard-transformen ger

|\varphi \rangle ={\frac {1}{\sqrt {2}}}\cdot |0\rangle +{\frac {1}{\sqrt {2}}}\cdot |1\rangle .

I princip skulle det vara möjligt att omedelbart tilldela ett sådant tillstånd till en qubit, men tekniskt sett är det lättare att först ställa in nolltillståndet och sedan transformera det med hjälp av enhetstransformationer till önskad form.

Ett fasanrop till en funktion ger följande tillstånd: ${\displaystyle O_{f))$ $f$

|\varphi \rangle =(-1)^{f(0)}\cdot {\frac {1}{\sqrt {2))}\cdot |0\rangle +(-1)^{f (1)}\cdot {\frac {1}{\sqrt {2))}\cdot |1\rangle .

Den andra Hadamard-transformationen leder till följande tillstånd:

|\varphi \rangle =(-1)^{f(0)}\cdot {\frac {1}{2))\cdot {\big (}|0\rangle +|1\rangle {\ big )}+(-1)^{f(1)}\cdot {\frac {1}{2}}\cdot {\big (}|0\rangle -|1\rangle {\big )}=

=\left((-1)^{f(0)}+(-1)^{f(1)}\right)\cdot {\frac {1}{2))\cdot |0\ rangle +\left((-1)^{f(0)}-(-1)^{f(1)}\right)\cdot {\frac {1}{2))\cdot |1\rangle .

När vi mäter tillståndet för en qubit får vi 0 för konstanta funktioner och 1 för balanserade:

Nej.	$f(0)$	$f(1)$	qubit-tillstånd $\|\varphi \rangle$	Sannolikhet att få 0	Sannolikhet att få 1
ett	$0$	$0$	${\big (}(-1)^{0}+(-1)^{0}{\big )}\cdot {\frac {1}{2))\cdot \|0\rangle +{ \big (}(-1)^{0}-(-1)^{0}{\big )}\cdot {\frac {1}{2))\cdot \|1\rangle =1\cdot \|0 \rangle +0\cdot \|1\rangle$	$1^{2}=1$	$0$
2	$ett$	$ett$	${\big (}(-1)^{1}+(-1)^{1}{\big )}\cdot {\frac {1}{2))\cdot \|0\rangle +{ \big (}(-1)^{1}-(-1)^{1}{\big )}\cdot {\frac {1}{2))\cdot \|1\rangle =-1\cdot \| 0\rangle +0\cdot \|1\rangle$	$(-1)^{2}=1$	$0$
3	$0$	$ett$	$((-1)^{0}+(-1)^{1})\cdot {\frac {1}{2}}\cdot \vert 0\rangle +((-1)^{0}-( -1)^{1})\cdot {\frac {1}{2}}\cdot \vert 1\rangle =0\cdot \vert 0\rangle +1\cdot \vert 1\rangle$	$0$	$1^{{2}}=1$
fyra	$ett$	$0$	${\big (}(-1)^{1}+(-1)^{0}{\big )}\cdot {\frac {1}{2))\cdot \|0\rangle +{ \big (}(-1)^{1}-(-1)^{0}{\big )}\cdot {\frac {1}{2))\cdot \|1\rangle =0\cdot \|0 \rangle -1\cdot \|1\rangle$	$0$	$(-1)^{2}=1$

Litteratur

Wolf R. d. Quantum Computing (engelska) : Lecture Notes - 2019. - 176 sid. arXiv : 1907.09415

Anteckningar

↑ 1 2 M. Trögt . Quantum Algorithms: Opportunities and Limitations, Föreläsning 2 ( Arkiverad 10 juni 2011 på Wayback Machine ), sid. 12-13. - St. Petersburg, våren 2011.
↑ M. Trögt . Quantum Algorithms Lecture 2 Arkiverad 26 april 2013 på Wayback Machine .

Kvantalgoritmer
Shors algoritm Grovers algoritm Deutsch-Yozhi algoritm Feynman problem Zalka-Wiesner algoritm kvantglödgning

kvantinformatik

Allmänna begrepp

kvantkommunikation

kvantkanal
- kvantnät
kvantkryptografi
- Kvantnyckeldistribution
Teleportering av kvantenergi
kvantteleportering
Quantum ultra-tät kodning
LOCC
kvantdestillation

Kvantalgoritmer

kvantsimulator
Deutsch-Yozhi algoritm
Bernstein-Wazirani Algoritm
Grovers algoritm
Quantum Fourier Transform
Shors algoritm
Simons problem
Quantum Phase Estimation Algoritm
Quantum Computing Algoritm
kvantglödgning
Algoritmisk kylning
Kvantalgoritm för att lösa ett system av linjära ekvationer
Amplitudförstärkning

Kvantkomplexitetsteori

Turing kvantmaskin
EQP
BQP
QMA
PostBQP
QIP

Quantum Computing Models

kvantkrets
- kvantport
Ensidig kvantdator
- klunga
Adiabatisk kvantberäkning
Topologisk kvantdator

Förebyggande av dekoherens

Korrigering av kvantfel
Stabiliseringskoder
Stabiliseringsformalism
Quantum faltningskod

Fysiska implementeringar

kvantoptik	Kavitationskvantelektrodynamik Kontur kvantelektrodynamik Kvantberäkning baserad på linjär optik KLM-protokoll Bosonisk provtagning
superkalla atomer	Absorberad jon kvantdator Optiskt galler
ryggbaserad _	Kvantdator baserad på kärnmagnetisk resonans Kanes kvantdator Förlust kvantdator - DiVincenzo NV centrum
Supraledande kvantdatorer	ladda qubit strömmande qubit Fas qubit Transmon