Normalizer Circuits and Quantum Computation

Abstract

(Abridged abstract.) In this thesis we introduce new models of quantum computation to study the emergence of quantum speed-up in quantum computer algorithms. Our first contribution is a formalism of restricted quantum operations, named normalizer circuit formalism, based on algebraic extensions of the qubit Clifford gates (CNOT, Hadamard and $\pi /4$-phase gates): a normalizer circuit consists of quantum Fourier transforms (QFTs), automorphism gates and quadratic phase gates associated to a set $G$, which is either an abelian group or abelian hypergroup. Though Clifford circuits are efficiently classically simulable, we show that normalizer circuit models encompass Shor's celebrated factoring algorithm and the quantum algorithms for abelian Hidden Subgroup Problems. We develop classical-simulation techniques to characterize under which scenarios normalizer circuits provide quantum speed-ups. Finally, we devise new quantum algorithms for finding hidden hyperstructures. The results offer new insights into the source of quantum speed-ups for several algebraic problems. Our second contribution is an algebraic (group- and hypergroup-theoretic) framework for describing quantum many-body states and classically simulating quantum circuits. Our framework extends Gottesman's Pauli Stabilizer Formalism (PSF), wherein quantum states are written as joint eigenspaces of stabilizer groups of commuting Pauli operators: while the PSF is valid for qubit/qudit systems, our formalism can be applied to discrete- and continuous-variable systems, hybrid settings, and anyonic systems. These results enlarge the known families of quantum processes that can be efficiently classically simulated. This thesis also establishes a precise connection between Shor's quantum algorithm and the stabilizer formalism, revealing a common mathematical structure in several quantum speed-ups and error-correcting codes.

PhD thesis, Technical University of Munich (2016). Please cite original papers if possible. Appendix E contains unpublished work on Gaussian unitaries. If you spot typos/omissions please email me at JLastNames at posteo dot net. Source: http://bit.ly/2gMdHn3. Related video talk: https://www.perimeterinstitute.ca/videos/toy-theory-quantum-speed-ups-based-stabilizer-formalism Posted on my birthday

References in corpus (26)

• Universal Quantum Computation with Continuous-Variable Cluster States
• Randomizing quantum states: Constructions and applications
• Bell Inequalities for Graph States
• Fast simulation of stabilizer circuits using a graph state representation
• NP-complete Problems and Physical Reality
• Effective fault-tolerant quantum computation with slow measurements
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Universal quantum computation with little entanglement
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• Efficient classical simulation of the semi-classical Quantum Fourier Transform
• The Hidden Subgroup Problem - Review and Open Problems
• Efficient classical simulation of the approximate quantum Fourier transform
• Approximation of real error channels by Clifford channels and Pauli measurements
• The quantum FFT can be classically simulated
• Efficient Quantum Algorithms for Estimating Gauss Sums
• Wigner function for a particle in an infinite lattice
• Several natural BQP-Complete problems
• The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
• Computation with Unitaries and One Pure Qubit
• Stabilizer Codes for Continuous-variable Quantum Error Correction
• The computational power of normalizer circuits over black-box groups
• Quantum Complexity: restrictions on algorithms and architectures
• Notes on the hidden subgroup problem on some semi-direct product groups
• Decomposition of phase space and classification of Heisenberg groups
• Efficiently contractable quantum circuits cannot produce much entanglement
• Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups