A quantum computer applies the axioms of quantum mechanics to efficiently run quantum algorithms, thereby performing calculations which, we speculate, would demand exponential time or memory on a classical computer. This thesis focuses on deriving better explanations of, and in the process improving upon, quantum algorithms and models of (a sub-theory of) the quantum mechanical foundations that dictate how quantum computers operate. Our contributions consist of three parts.

First, we construct an efficient Einstein-Podolsky-Rosen(EPR)-complete hidden-variable model of the sub-theory of quantum mechanics given by the stabilizer formalism. Being EPR-complete means every element of physical reality is contained in the model.

Next, we create a single-qubit rotation algorithm using the universal Toffoli gate. Our circuit requires only a logarithmic gate depth (and so a loga-rithmic number of Toffolis), substantially improving on previous algorithms. The circuit admits an efficient construction, that uses a comparison with a constant obtained through a trigonometric expression, and so the gate array can be constructed in polynomial time. We perform quantum state and process tomography on our algorithm when run on both a simulated and a real quantum computer, and analyze the results, attaining good estimates of our algorithm’s performance under various (both simulated and real) noise levels.

Finally, we study Recursive Fourier Sampling (RFS): The quantum algorithm solving RFS is one of the first such appearing to give an advantage over any classical algorithm. By reformulating RFS in terms of which information its oracles write into the phase of the qubits, we show that the quantum algorithm solving RFS relies on the quantum computational resource of phase kickback, strengthening similar arguments made in related work. We show that this algorithm cannot be improved as the calculations carried out by the oracles must be uncomputed, lest random information gets written into the phase.

En kvantdator tillämpar kvantmekanikens axiom för att effektivt köra kvantalgoritmer, vilka utför beräkningar som, enligt rådande hypotes, kräver exponentiella resurser (tid eller minne) på en klassisk dator. Denna avhandling fokuserar på att förbättra vår förståelse, och därmed vår implementation, av kvantalgoritmer och modeller av (en delteori av) de kvantmekaniska grunderna vilka bestämmer hur kvantdatorer fungerar. Våra bidrag består av tre delar.

Först konstruerar vi en effektiv Einstein-Podolsky-Rosen(EPR)-komplett gömd-variabel-modell av del-teorin av kvantmekanik som ges av stabilisatorformalismen. Att vara EPR-komplett innebär att varje verklig storhet inryms i modellen.

Därefter skapar vi en rotations-algoritm för en kvantbit användandes den universella Toffoli-grinden. Vår konstruktion har ett logaritmiskt grinddjup, och därmed som mest ett logaritmiskt antal Toffolis, vilket är en kraftig förbättring jämfört med existerande algoritmer. Kretsen medger en effektiv konstruktion, som nyttjar en jämförelse med en konstant vilken fås genom ett trigonometriskt uttryck, och därmed kan grindnätet konstrueras i polynomiell tid. Vi utför tillstånds- och processtomografi på vår algoritm körandes på en simulerad såväl som en riktig kvantdator, och analyserar resultaten, därvidlag erhållandes goda uppskattningar av vår algoritms prestanda under varierande (båda simulerade och verkliga) brusnivåer.

Slutligen studerar vi Rekursiv Fourier-Sampling (RFS): Kvantalgoritmen som löser RFS är en av de första sådana som verkar ge ett övertag över klassiska algoritmer. Genom att omformulera RFS i termer av den information dess orakel skriver in i kvantbitarnas fas, visar vi att kvantalgoritmen som löser RFS utnyttjar kvantberäkningsresursen känd som fasrekyl, stärkandes liknande argument i relaterade arbeten. Vi visar även att algoritmen inte kan förbättras: Beräkningarna utförda av dess orakel måste göras ogjorda, enär slumpmässig information skrivs in i fasen.