Kvantalgoritm

En kvantalgoritm  är en algoritm utformad för att köras på en kvantdator .

Grundläggande principer

En kvantalgoritm är en klassisk algoritm som specificerar en sekvens av enhetliga operationer (grindar eller grindar) med en indikation på vilka kvantbitar de behöver utföras på. En kvantalgoritm specificeras antingen i form av en verbal beskrivning av sådana kommandon, eller med hjälp av deras grafiska notation i form av ett system av grindar (quantum gate array).

Resultatet av kvantalgoritmen är probabilistiskt [1] . På grund av en liten ökning av antalet operationer i algoritmen kan man godtyckligt föra sannolikheten för att erhålla det korrekta resultatet till en.

Uppsättningarna av problem som kan lösas på en kvantdator och på en klassisk sammanfaller. En kvantdator ökar alltså inte antalet algoritmiskt lösbara problem. Hela poängen med att använda en kvantdator är att den kan lösa vissa problem mycket snabbare än någon av de klassiska. För att göra detta måste kvantalgoritmen generera och använda intrasslade kvanttillstånd under beräkningen (se Quantum superposition och Quantum entanglement ).

Alla problem som löses med en kvantalgoritm kan också lösas av en klassisk dator genom att direkt beräkna enhetsmatriser med exponentiell dimension, och erhålla en explicit form av kvanttillstånd. Speciellt problem som är olösliga på klassiska datorer (som stoppproblemet ) förblir olösliga även på kvantdatorer. Men sådan direkt simulering kräver exponentiell tid, och därför blir det möjligt att, med hjälp av kvantparallellism, accelerera några klassiska algoritmer på en kvantdator [2] .

Acceleration på en kvantdator är inte relaterad till processorns klockhastighet. Den bygger på kvantparallellism. Ett steg av kvantberäkning gör mycket mer arbete än ett steg av klassisk beräkning. Det skulle dock vara ett misstag att likställa kvantberäkning med parallelliserad klassisk beräkning. Till exempel kan en kvantdator inte lösa uppräkningsproblemet snabbare än var  är körtiden för en deterministisk klassisk uppräkningsalgoritm (se [3] ), medan en icke-deterministisk klassisk algoritm löser det i tid . Men en icke-deterministisk klassisk algoritm kräver en exponentiell minnesresurs, det vill säga den är inte fysiskt genomförbar, medan en kvantalgoritm inte motsäger de kända naturlagarna.

Quantum computing är en process av ett speciellt slag. Den använder en speciell fysisk resurs: kvantentangled states , som i vissa fall gör det möjligt att uppnå fantastiska vinster i tid. Sådana fall kallas kvantacceleration av klassisk beräkning.

Fall av kvantacceleration, mot bakgrund av den allmänna massan av klassiska algoritmer, är mycket sällsynta (se [4] ). Detta förtar dock inte den grundläggande betydelsen av kvantberäkning, eftersom de är kapabla att i grunden påskynda utförandet av brute-force-uppgifter.

Grundläggande kvantaccelerationsscheman

Den huvudsakliga typen av problem som accelereras av kvantalgoritmer är brute-force-problem. De kan delas in i 2 huvudgrupper:

1. Problem med att modellera dynamiken i komplexa system (Feynmans ursprungliga idé) och
2. Matematiska uppgifter som kokar ner till uppräkning av alternativ:
   1. Allmänt uppräkningsfall: Grovers schema och dess varianter, samt
   2. Problem med att söka efter dolda perioder: Shors schema för att använda den snabba kvantfouriertransformen och dess analoger.

Typ 1) representeras av Zalka-Wiesner-algoritmen för att modellera den enhetliga dynamiken hos kvantsystem av partiklar i nästan realtid och med linjärt minne. Denna algoritm använder Shor-schemat för kvant-Fourier-transformen.

Typ 2) presenteras:

• Grovers algoritm för det allmänna sökproblemet och dess kontinuerliga och adiabatiska varianter, samt algoritmer som använder Grovers schema: strukturell sökning (Fari, Gutman), extremum sökalgoritm (Hoyer, etc.) och sökning efter matchande rader i databasen (Ambainis) ,
• Shors algoritm för faktorisering av heltal, Abrams-Lloyds algoritm för perioddetektering, Kitaevs algoritm för att bestämma dolda undergrupper, etc.

Typ 1) är av största intresse ur synvinkeln av ytterligare tillämpningar av en kvantdator.

Klassificering

Klassificeringen av kvantalgoritmer kan utföras enligt den typ av kvantomvandlingar som används av algoritmen. Vanligt använda transformationer inkluderar: en:phase kick-back , phase estimering , en:quantum Fourier transform , en:quantum walk , en:amplitud amplification , en:topological quantum field theory . Det är också möjligt att gruppera kvantalgoritmer efter vilken typ av problem de löser. [5]

Välkända algoritmer

• Shors algoritm
• Grovers algoritm
• Deutsch-Yozhi algoritm

Se även

• kvantdator
• kvantprogrammering
• Tidslinje för kvantberäkning
• Kvantnyckeldistribution
• Lista över algoritmer
• BQP klass

Anteckningar

1. ↑ "Randomness as a Computational Resource" Arkiverad 29 oktober 2017 på Computerra Wayback Machine nr 10 av 18 mars 2002 "Kvantalgoritmer liknar probabilistiska sådana. Först och främst osäkerheten i resultatet.
2. ↑ "Quantum computers", PhD L. Fedichkin, FTI RAS. Nizh, 2001 nr 01 "Introduktionen av kvantdatorer kommer inte att leda till lösningen av algoritmiskt olösliga klassiska problem, utan kommer bara att påskynda vissa beräkningar"
3. ↑ Yuri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc. Roy. Soc. London. A455 (1999) 2165-2172 [1]
4. ↑ Yuri Ozhigov, Quantum Computers Speed ​​Up Classical with Probability Zero, Chaos Solitons Fractals 10 (1999) 1707-1714 [2]
5. ↑ Childs, Andrew M; Wim van Dam. Kvantalgoritmer för algebraiska problem  (neopr.)  // 0812.0380. - 2008. - 2 december.

Länkar

• Stephen Jordan, Algebraic and Number Theoretic Algorithms  - omfattande katalog över kvantalgoritmer, NIST, 2013

Ordböcker och uppslagsverk	stor kines