Kvantealgoritme

En kvantealgoritme  er en algoritme designet til at køre på en kvantecomputer .

Grundlæggende principper

En kvantealgoritme er en klassisk algoritme, der specificerer en sekvens af enhedsoperationer (gates eller porte) med en indikation af, hvilke qubits de skal udføres på. En kvantealgoritme specificeres enten i form af en verbal beskrivelse af sådanne kommandoer eller ved hjælp af deres grafiske notation i form af et system af porte (kvanteportarray).

Resultatet af kvantealgoritmen er sandsynliggjort [1] . På grund af en lille stigning i antallet af operationer i algoritmen, kan man vilkårligt bringe sandsynligheden for at opnå det korrekte resultat til én.

De sæt af problemer, der kan løses på en kvantecomputer og på en klassisk, er sammenfaldende. En kvantecomputer øger således ikke antallet af algoritmisk løselige problemer. Hele pointen med at bruge en kvantecomputer er, at den kan løse nogle problemer meget hurtigere end nogen af ​​de klassiske. For at gøre dette skal kvantealgoritmen generere og bruge sammenfiltrede kvantetilstande under beregningen (se Kvantesuperposition og kvantesammenfiltring ).

Ethvert problem, der løses af en kvantealgoritme, kan også løses af en klassisk computer ved direkte at beregne enhedsmatricer af eksponentiel dimension og opnå en eksplicit form for kvantetilstande. Især problemer, der er uløselige på klassiske computere (såsom stopproblemet ) forbliver også uløselige på kvantecomputere. Men sådan direkte simulering kræver eksponentiel tid, og derfor bliver det muligt ved hjælp af kvanteparallelisme at accelerere nogle klassiske algoritmer på en kvantecomputer [2] .

Acceleration på en kvantecomputer er ikke relateret til processorens clockhastighed. Den er baseret på kvanteparallelisme. Et trin af kvanteberegning gør meget mere arbejde end et trin i klassisk computing. Det ville dog være en fejl at sætte lighedstegn mellem kvanteberegning og paralleliseret klassisk beregning. For eksempel kan en kvantecomputer ikke løse optællingsproblemet hurtigere end hvor  er køretiden for en deterministisk klassisk optællingsalgoritme (se [3] ), mens en ikke-deterministisk klassisk algoritme løser det i tid . Men en ikke-deterministisk klassisk algoritme kræver en eksponentiel hukommelsesressource, det vil sige, at den ikke er fysisk gennemførlig, mens en kvantealgoritme ikke modsiger de kendte naturlove.

Quantum computing er en proces af en særlig art. Den bruger en speciel fysisk ressource: kvantesammenfiltrede tilstande , som i nogle tilfælde gør det muligt at opnå fantastiske gevinster i tide. Sådanne tilfælde kaldes kvanteacceleration af klassisk databehandling.

Tilfælde af kvanteacceleration, på baggrund af den generelle masse af klassiske algoritmer, er meget sjældne (se [4] ). Dette forringer dog ikke den grundlæggende betydning af kvanteberegning, fordi de er i stand til fundamentalt at accelerere udførelsen af ​​brute-force opgaver.

Grundlæggende kvanteaccelerationsskemaer

Den vigtigste type problemer, der fremskyndes af kvantealgoritmer, er brute-force-problemer. De kan opdeles i 2 hovedgrupper:

1. Problemer med at modellere dynamikken i komplekse systemer (Feynmans oprindelige idé) og
2. Matematiske opgaver, der koger ned til opremsning af muligheder:
   1. Generel opregningstilfælde: Grovers ordning og dens varianter, samt
   2. Problemer med at søge efter skjulte perioder: Shors skema med at bruge den hurtige kvante Fourier-transformation og dens analoger.

Type 1) er repræsenteret af Zalka-Wiesner-algoritmen til modellering af enhedsdynamikken i kvantesystemer af partikler i næsten realtid og med lineær hukommelse. Denne algoritme bruger Shor-skemaet for kvante-Fourier-transformationen.

Type 2) præsenteret:

• Grovers algoritme for det generelle søgeproblem og dets kontinuerlige og adiabatiske varianter, samt algoritmer, der anvender Grovers skema: strukturel søgning (Fari, Gutman), ekstremum søgealgoritme (Hoyer osv.) og søgning efter matchende rækker i databasen (Ambainis) ,
• Shors algoritme til faktorisering af heltal, Abrams-Lloyds algoritme til periodedetektering, Kitaevs algoritme til bestemmelse af skjulte undergrupper osv.

Type 1) er af den største interesse med hensyn til yderligere anvendelser af en kvantecomputer.

Klassifikation

Klassificeringen af ​​kvantealgoritmer kan udføres i henhold til typen af ​​kvantetransformationer, der anvendes af algoritmen. Almindeligt anvendte transformationer omfatter: en:fase kick-back , faseestimering , en:quantum Fourier transform , en:quantum walk , en:amplitude amplification , en:topologisk kvantefeltteori . Det er også muligt at gruppere kvantealgoritmer efter den type problemer, de løser. [5]

Velkendte algoritmer

• Shors algoritme
• Grovers algoritme
• Deutsch-Yozhi algoritme

Se også

• kvantecomputer
• kvanteprogrammering
• Tidslinje for kvanteberegning
• Kvantenøglefordeling
• Liste over algoritmer
• BQP klasse

Noter

1. ↑ "Randomness as a Computational Resource" Arkiveret 29. oktober 2017 på Computerra Wayback Machine nr. 10 af 18. marts 2002 "Kvantealgoritmer ligner probabilistiske. Først og fremmest usikkerheden på resultatet.
2. ↑ "Quantum computers", PhD L. Fedichkin, FTI RAS. Nizh, 2001 nr. 01 "Introduktionen af ​​kvantecomputere vil ikke føre til løsningen af ​​algoritmisk uløselige klassiske problemer, men vil kun fremskynde nogle beregninger"
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. Kvantealgoritmer til algebraiske problemer  (neopr.)  // 0812.0380. - 2008. - 2. december.

Links

• Stephen Jordan, algebraiske og talteoretiske algoritmer  - omfattende katalog over kvantealgoritmer, NIST, 2013

Ordbøger og encyklopædier	stor kinesisk