Understanding the Speedup of Quantum Computation
Christoffer Hindlycke · Linköping studies in science and technology. Dissertations · 2024
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.