Abstract Quantum computing has been studied over the past four decades based on two computational models of quantum circuits and quantum Turing machines. To capture quantum polynomial-time computability, a new recursion-theoretic approach was taken lately by Yamakami [J. Symb. Logic 80, pp. 1546–1587, 2020] by way of recursion schematic definition, which constitutes six initial quantum functions and three construction schemes of composition, branching, and multi-qubit quantum recursion. By taking a similar approach, we look into quantum polylogarithmic-time computability and further explore the expressing power of elementary schemes designed for such quantum computation. In particular, we introduce an elementary form of the quantum recursion, called the fast quantum recursion, and formulate
EQS (elementary quantum schemes) of “elementary” quantum functions. This class
EQS captures exactly quantum polylogarithmic-time computability, which forms the complexity class BQPOLYLOGTIME. We also demonstrate the separation of BQPOLYLOGTIME from NLOGTIME and PPOLYLOGTIME. As a natural extension of
EQS , we further consider an algorithmic procedural scheme that implements the well-known divide-and-conquer strategy. This divide-and-conquer scheme helps compute the parity function, but the scheme cannot be realized within our system
EQS .
We prove that constant-space-overhead fault-tolerant quantum computation can be achieved with provably strictly logarithmic time overhead, improving over the best known results with additional subpolylogarithmic factors. Our main construction uses polynomial-subrank transversal logical $\CCZ$ gates on good quantum locally testable codes to implement addressable universal computation by transferring batches of logical qubits between dense storage and active logical subspaces while reusing the same ancillary workspace. Logical $\CCZ$ gates are implemented directly by the transversal operation, so only stabilizer resource states require separate preparation. Furthermore, we give an alternative construction that also achieves purely logarithmic time overhead based on modifying the quantum Reed--Solomon magic-state distillation scheme of Nguyen and Pattison. Recursively applying a fixed distillation circuit protected by qLTCs of increasing block length eliminates the subpolylogarithmic time factor.
Many quantum programming languages have been recently introduced to create a new tool for expressing quantum algorithms. However, many have failed to formally express \nthemselves as a universal programming language for quantum computation. In this dissertation, the SequenceL language is shown to be universal in two models of quantum computation, the circuit and machine models. A SequenceL quantum interpreter is developed to show universality in the circuit model. A universal quantum Turing machine (UQTM) is introduced using non-recursive computational laws of the functional language, SequenceL with no explicit recursion. The SequenceL UQTM is implemented \nbased on the rules of Bernstein and Vasari’s UQTM. Bernstein and Vasari’s UQTM definition is expanded to include quantum Turing machine with arbitrary run times. \nFinally, postselection is introduced as a halting scheme for quantum Turing machines.