A Resource for Quantum Computation

• In this thesis we address the question, what is the resource, or property, that enables the advantage of quantum computers? The theory of quantum computers dates back to the eighties, so one would think there already is an answer to this question. There are several proposed solutions, but to this date, there is no consensus on an answer. Primarily, the advantage of quantum computers is characterized by a speedup for certain computational problems. This speedup is measured by comparing quantum algorithms with the best-known classical algorithms. For some algorithms we assume access to an object called oracle. The oracle computes a function, and the complexity of the oracle is of no concern. Instead, we count the number of queries to the oracle needed to solve the problem. Informally, the question we ask using an oracle is: if we can compute this function efficiently, what else could we then compute. However, using oracles while measuring a quantum speedup, we assume access to vastly different oracles residing in different models of computation.For our investigation of the speedup, we introduce a classical simulation framework that imitates quantum algorithms. The simulation suggests that the property enabling the potential quantum speedup is the ability to store, process, and retrieve information in an additional degree of freedom. We then theoretically verified that this is true for all problems that can be efficiently solved with a quantum computer.In parallel to this, we also see that quantum oracles sharply specify the information we can retrieve from the additional degree of freedom, while regular oracles do not. A regular oracle does not even allow for an extra degree of freedom. We conclude that comparing quantum with classical oracle query complexity bounds does not provide conclusive evidence for a quantum advantage.  

• I denna avhandling behandlar vi frågan, vad är resursen eller egenskapen som möjliggör fördelen hos kvantdatorer. Teorin bakom kvantdatorer daterar tillbaka till åttiotalet, så man skulle kunna tro att det redan finns ett svar på frågan. Det finns flera föreslagna lösningar, men hittills råder det ingen enighet kring ett svar.       Fördelen hos kvantdatorer kännetecknas främst av en uppsnabbning för vissa beräkningsproblem. Denna uppsnabbning mäts genom att man jämför kvantalgoritmer med de bästa klassiska algoritmerna som vi känner till. För vissa algoritmer så antas att man har tillgång till ett objekt som kallas orakel. Ett orakel beräknar en funktion och vi bryr oss inte om komplexiteten hos oraklet. Istället så räknar vi antalet annrop man behöver göra till oraklet för att lösa problemet. Informellt så kan man säga att när man använder ett orakel så ställer vi frågan: om vi kan beräkna den här funktionen effektivt, vad kan vi då beräkna? Men när man använder orakel för att mäta en kvantuppsnabbning så antar vi att man har tillgång till väldigt olika orakel i olika beräkningsmodeller.       För vår undersökning av kvantuppsnabbningen introducerar vi ett klassiskt simuleringsramverk som imiterar kvantalgoritmer. Simuleringen antyder att egenskapen som möjliggör den potentiella kvantuppsnabbningen är förmågan att lagra, bearbeta och hämta information i en extra frihetsgrad. Vi verifierar sedan teoretiskt att detta är sant för alla problem som effektivt kan lösas med en kvantdator.       Parallellt med detta ser vi att kvantorakel entydigt specificerar den information vi kan hämta ur den extra frihetsgraden, medan vanliga orakel inte gör det. Ett vanligt orakel tillåter inte ens en extra frihetsgrad. Från detta drar vi slutsatsen att jämförelser mellan kvantmekanisk och klassisk anropskomplexitet inte kan ge övertygande bevis för en kvantfördel. 

Ämnesord

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

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

Publikations- och innehållstyp

vet (ämneskategori)

dok (ämneskategori)