Feynmans algoritm

Feynmans algoritm är en algoritm som används för att simulera operationerna av en kvantdator på en klassisk dator . Den är baserad på Path-integralformuleringen av kvantmekaniken, som formulerades av Richard Feynman .

Översikt

En $n$ kvantdator tar in en kvantkrets $U$ som innehåller $m$ -grindar och ett ingångstillstånd $|0\rangle ^{n}$ . Den matar sedan ut en sträng av bitar $x\in \{0,1\}^{n}$ med sannolikheten $P(x_{m})=|\langle x_{m}|U|0\rangle ^{n}|^{2}$ .

I Schrödingers algoritm beräknas ${\displaystyle P(x_{m})} enkelt via$ matrismultiplikation . Det vill säga $P(x_{m})=|\langle x_{m}|U_{m}U_{m-1}U_{m-2}U_{m-3},...,U_{1 }|0\rangle ^{n}|^{2}$ . Systemets kvanttillstånd kan spåras under hela dess utveckling.

I Feynmans sökvägsalgoritm beräknas ${\displaystyle P(x_{m})} genom att summera bidragen av$ $(2^{n})^{m- 1}$ historik. Det vill säga $P(x_{m})=|\langle x_{m}|U|0\rangle ^{n}|^{2}=|\summa _{x_{1},x_{2}, x_{3},...,x_{m-1}\in \{0,1\}^{n}}\prod _{j=1}^{m}\langle x_{j}|U_{ j}|x_{j-1}\rangle |^{2}$ .

Schrödingers tar mindre tid att köra jämfört med Feynmans medan Feynmans tar mer tid och mindre utrymme. Mer exakt tar Schrödingers $\sim m2^{n}$ tid och $\sim 2^{n}$ utrymme medan Feynmans tar $\sim 4^ {m}$ tid och $\sim m+n$ mellanrum.

Exempel

Tänk på problemet med att skapa en Bell-tillstånd . Vad är sannolikheten att den resulterande mätningen blir $00$ ?

Eftersom kvantkretsen som genererar ett Bell-tillstånd är H ( Hadamard-porten )-grinden följt av CNOT-grinden , är enhetens enhet för denna krets $(H\otimes I)\times CNOT$ . I så fall är ${\displaystyle P(00)=|\langle 00|(H\otimes I)\times CNOT|00\rangle |^{2}={\frac {1}{2}}} med Schrödingers$ algoritm . Så sannolikheten för mätningen blir $00$ är ${\frac {1}{2}}$ .

Med hjälp av Feynmans algoritm innehåller Bell-tillståndskretsen $(2^{2})^{2-1}=4$ historiker: $00 ,01,10,11$ . Så $|\sum _{00,01,10,11}\prod _{j=1}^{2}\langle x_{j}|U_{j}|x_{j-1}\rangle | ^{2}$ = | $\langle 00|H\otimes I|00\rangle \times \langle 00|CNOT|00\rangle$ + $\langle 01|H\otimes I|00\rangle \times \langle 00|CNOT|01\rangle$ + $\langle 10|H\otimes I|00\rangle \times \langle 00|CNOT|10\rangle$ + $\langle 11|H\otimes I|00\rangle \times \langle 00|CNOT|11\rangle |^{2}=|{\frac {1}{\sqrt {2}} }+0+0+0|^{2}={\frac {1}{2}}$ .

Se även