Quantum Turing maskin

En kvantturingmaskin ( QTM ) eller universell kvantdator är en abstrakt maskin som används för att modellera effekterna av en kvantdator . Den tillhandahåller en enkel modell som fångar all kraft i kvantberäkning – det vill säga vilken kvantalgoritm som helst kan uttryckas formellt som en speciell kvantturingmaskin. Den beräkningsmässigt ekvivalenta kvantkretsen är dock en vanligare modell.

Quantum Turing-maskiner kan relateras till klassiska och probabilistiska Turing-maskiner i ett ramverk baserat på övergångsmatriser . Det vill säga en matris kan specificeras vars produkt med matrisen representerande en klassisk eller probabilistisk maskin tillhandahåller kvantsannolikhetsmatrisen som representerar kvantmaskinen. Detta visades av Lance Fortnow .

Informell skiss

Olöst problem i fysik :

Är en universell kvantdator tillräcklig för att effektivt simulera ett godtyckligt fysiskt system?

(fler olösta problem inom fysik)

Ett sätt att förstå kvantturingmaskinen (QTM) är att den generaliserar den klassiska Turingmaskinen (TM) på samma sätt som kvantfinita automaten (QFA) generaliserar den deterministiska finita automaten (DFA). I huvudsak ersätts de inre tillstånden i en klassisk TM av rena eller blandade tillstånd i ett Hilbert-rum ; övergångsfunktionen ersätts av en samling enhetliga matriser som mappar Hilbert-rummet till sig självt.

Det vill säga, en klassisk Turing-maskin beskrivs av en 7- tuppel $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ .

För en kvant-Turing-maskin med tre band (ett band som håller ingången, ett andra band med mellanliggande beräkningsresultat och ett tredje band som håller utgången):

• Uppsättningen av tillstånd $Q$ ersätts av ett Hilbert-mellanslag .
• Bandalfabetets symboler $\Gamma$ ersätts på samma sätt av ett Hilbertmellanslag (vanligtvis ett annat Hilbertmellanrum än tillståndsuppsättningen).
• Den tomma symbolen $b\in \Gamma$ är ett element i Hilbertutrymmet.
• Ingångs- och utmatningssymbolerna $\Sigma$ tas vanligtvis som en diskret mängd, som i det klassiska systemet; sålunda behöver varken input eller output till en kvantmaskin vara ett kvantsystem i sig.
• Övergångsfunktionen $Sigma \times Q\otimes \Gamma \times \{L,R\}}$ \ är en generalisering av en övergångsmonoid och förstås vara en samling enhetliga matriser som är automorfismer av Hilbert-rummet $Q$ .
• Det initiala tillståndet $q_{0}\in Q$ kan vara antingen ett blandat tillstånd eller ett rent tillstånd .
• Mängden $F$ av slutliga eller accepterande tillstånd är ett delrum av Hilbert-utrymmet $Q$ .

Ovanstående är bara en skiss av en kvant Turing-maskin, snarare än dess formella definition, eftersom den lämnar vaga flera viktiga detaljer: till exempel hur ofta en mätning utförs; se till exempel skillnaden mellan en mätning-en gång och en mätning-många QFA. Denna fråga om mätning påverkar sättet på vilket skrivningar till utgångsbandet definieras.

Historia

1980 och 1982 publicerade fysikern Paul Benioff artiklar som först beskrev en kvantmekanisk modell av Turing-maskiner . En artikel från 1985 skriven av fysikern vid Oxford University, David Deutsch , vidareutvecklade idén om kvantdatorer genom att antyda att kvantportar skulle kunna fungera på ett liknande sätt som traditionella digitala binära logiska grindar .

Iriyama, Ohya och Volovich har utvecklat en modell av en linjär kvantturingmaskin (LQTM). Detta är en generalisering av en klassisk QTM som har blandade tillstånd och som tillåter irreversibla övergångsfunktioner. Dessa tillåter representation av kvantmätningar utan klassiska utfall.

En kvantturingmaskin med postselektion definierades av Scott Aaronson , som visade att klassen av polynomtid på en sådan maskin ( PostBQP ) är lika med den klassiska komplexitetsklassen PP .

Se även

• Kvantsimulator § Lösa fysikproblem

Vidare läsning

•    Molina, Abel; Watrous, John (2018). "Återbesök simuleringen av kvant Turing-maskiner med kvantkretsar" . Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences . 475 (2226). arXiv : 1808.01701 . doi : 10.1098/rspa.2018.0767 . PMC 6598068 . PMID 31293355 .
• Iriyama, Satoshi; Ohya, Masanori; Volovich, Igor (2004). "Generaliserad Quantum Turing Machine och dess tillämpning på SAT Chaos Algorithm". arXiv : quant-ph/0405191 .
•     Deutsch, D. (1985). "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer". Proceedings of the Royal Society of London. Serie A, Matematiska och fysikaliska vetenskaper . 400 (1818): 97–117. Bibcode : 1985RSPSA.400...97D . CiteSeerX 10.1.1.41.2382 . doi : 10.1098/rspa.1985.0070 . JSTOR 2397601 . S2CID 1438116 .

externa länkar

• Kvantdatorn – historia