Kvantkomplexitetsteori

Kvantkomplexitetsteori  är en del av teorin om beräkningskomplexitet inom teoretisk datavetenskap . Han studerar komplexitetsklasserna som definieras med hjälp av kvantdatorer och kvantinformation , såväl som problemen förknippade med dessa komplexitetsklasser, och förhållandet mellan kvantkomplexitetsklasser och klassiska (icke-kvant) komplexitetsklasser.

Översikt

En komplexitetsklass är en uppsättning problem som kan lösas med hjälp av någon beräkningsmodell under begränsade resurser. Till exempel definieras komplexitetsklassen P som den uppsättning problem som kan lösas av en Turing-maskin i polynomtid . På samma sätt kan man definiera en klass av kvantkomplexitet med hjälp av en kvantmodell av beräkning som en vanlig kvantdator eller en kvantturingmaskin . Således definieras BQP-komplexitetsklassen som en uppsättning problem som kan lösas av en kvantdator i polynomtid med begränsat fel.

Två viktiga kvantkomplexitetsklasser är BQP och QMA , som är kvantmotsvarigheter till P- och NP- komplexitetsklasserna med begränsat fel. Ett av huvudmålen med kvantkomplexitetsteorin är att ta reda på var dessa klasser är i förhållande till klassiska komplexitetsklasser som P, NP, PP , PSPACE och andra.

Quantum query komplexitet

I frågekomplexitetsmodellen ges indata som ett orakel ("svart låda"). Algoritmen erhåller information om indata endast genom att fråga oraklet. Algoritmen körs i något fast kvanttillstånd , som ändras vid tidpunkten för begäran.

Kvantkomplexiteten för en fråga är det minsta antalet frågor till oraklet som krävs för att beräkna en funktion. Detta gör att kvantfrågans komplexitet blir en lägre gräns för funktionens totala tidskomplexitet.

Ett exempel som illustrerar möjligheterna med kvantberäkning är Grover-algoritmen (även GSA från engelskan.  Grover search algorithm ) för att lösa uppräkningsproblemet, det vill säga att hitta en lösning på ekvationen

där är en boolesk funktion av n variabler [1] . Kvantfrågekomplexiteten för en algoritm  är en kvadratisk förbättring jämfört med bästa möjliga klassiska frågekomplexitet (det vill säga linjär sökning ).

Se även

Anteckningar

  1. ↑ GSA kallas ibland felaktigt för en databasuppslagning .

Litteratur