On the Power of Quantum Computation: Oracles

• Quantum computation solve some computational problems faster than the best-known alternative in classical computation. The evidence for this consists of examples where a quantum algorithm outperforms the best-known classical algorithm. A large body of these examples relies on oracle query complexity, where the performance (complexity) of the algorithms is measured by the number of times they need to access an oracle. Here, an oracle is usually considered to be a black box that computes a specific function at unit cost.However, the quantum algorithm is given access to an oracle with more structure than the classical algorithm. This thesis argues that the two oracles are so vastly different that comparing quantum and classical query complexity should not be considered evidence, but merely hints for a quantum advantage.The approach used is based on a model that can be seen as an approximation of quantum theory, but can be efficiently simulated on a classical computer. This model solves several oracular problems with the same performance as their quantum counterparts, showing that there is no genuine quantum advantage for these problems. This approach also clarifies the assumptions made in quantum computation, and which properties that can be seen as resources in these algorithms.

• Med en kvantdator antas vi kunna lösa vissa beräkningsproblem snabbare än dom bästa lösningarna tillgängliga för en vanlig klassisk dator. Bevisen för detta bygger på flertalet exempel där man har en kvantalgoritm som överträffar den bästa kända klassiska algoritmen. En stor andel av dessa exempel bygger på vad man kallar anrops-komplexitet, där man låter antalet anrop till ett orakel vara måttet på hur bra algoritmerna presterar. Här anses ett orakel vara en svart låda som beräknar en funktion under endast ett tidssteg.Kvantalgoritmen ges emellertid tillgång till ett orakel med mer struktur än det orakel som den klassiska algoritmen får tillgång till. Denna avhandling argumenterar för att dessa två orakel är så pass olika att en jämförelse mellan kvantalgoritmen och den klassiska algoritmen inte kan ses som bevis för kvantdatorns fördelar.Metoden vi använt är att konstruera en modell som kan anses vara en approximation av kvantteori, men kan simuleras effektivt på en klassisk dator. Denna modell löser flera orakelproblem med samma prestanda som motsvarande kvantalgoritmer, vilket visar att det inte finns någon äkta kvantfördel för dessa problem. Metoden klargör också vilka villkoren är för en kvantdator och vilka egenskaper som kan anses vara resurser i dessa algoritmer.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Publikations- och innehållstyp

vet (ämneskategori)

lic (ämneskategori)