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.

arXiv commentPhD 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 (105)

• Fault-tolerant quantum computation by anyons
• Anyons in an exactly solved model and beyond
• Quantum information with continuous variables
• Gaussian Quantum Information
• Quantum secret sharing
• Good Quantum Error-Correcting Codes Exist
• Efficient classical simulation of slightly entangled quantum computations
• Persistent entanglement in arrays of interacting particles
• Encoding a qubit in an oscillator
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• How to share a quantum secret
• Quantum Error Correction for Quantum Memories
• Quantum Computing with Very Noisy Devices
• Quantum computation over continuous variables
• Universal Quantum Computation with Continuous-Variable Cluster States
• On the Power of One Bit of Quantum Information
• Quantum Error Correction and Orthogonal Geometry
• Contextuality supplies the magic for quantum computation
• On the Theory of Quantum Secret Sharing
• Squeezing as an irreducible resource
• The Resource Theory of Stabilizer Computation
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Simulating quantum computation by contracting tensor networks
• Positive Wigner functions render classical simulation of quantum computation efficient
• Efficient Classical Simulation of Continuous Variable Quantum Information Processes
• The Real Symplectic Groups in Quantum Mechanics and Optics
• Discrete phase space based on finite fields
• Overhead and noise threshold of fault-tolerant quantum error correction
• Fault-Tolerant Measurement-Based Quantum Computing with Continuous-Variable Cluster States
• Randomizing quantum states: Constructions and applications
• Quantum Computing with Continuous-Variable Clusters
• Quantum algorithms for algebraic problems
• Classical simulation of noninteracting-fermion quantum circuits
• Cluster States for Continuous-Variable Multipartite Entanglement
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• Bell Inequalities for Graph States
• Quantum memories at finite temperature
• Error correction for continuous quantum variables
• Protected gates for superconducting qubits
• The role of the rigged Hilbert space in Quantum Mechanics
• Nonlocality of cluster states of qubits
• Enhanced fault-tolerant quantum computing in $d$-level systems
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Instantaneous Quantum Computation
• Fast simulation of stabilizer circuits using a graph state representation
• Analog quantum error correction
• Quantum computation based on d-level cluster states
• NP-complete Problems and Physical Reality
• The quantum query complexity of the hidden subgroup problem is polynomial
• Effective fault-tolerant quantum computation with slow measurements
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Stabilizer states and Clifford operations for systems of arbitrary dimensions, and modular arithmetic
• Universal simulation of Hamiltonian dynamics for qudits
• Universal quantum computation with little entanglement
• Contextuality and Wigner function negativity in qubit quantum computation
• Qutrit Magic State Distillation
• On the hardness of classically simulating the one clean qubit model
• Feasibility of self-correcting quantum memory and thermal stability of topological order
• Efficient Decoders for Qudit Topological Codes
• Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• Efficient classical simulation of the semi-classical Quantum Fourier Transform
• Fermionic Linear Optics and Matchgates
• Classical computing, quantum computing, and Shor's factoring algorithm
• Efficient Classical Simulation of Optical Quantum Circuits
• Standard Form of Qudit Stabilizer Groups
• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
• 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
• Quantum interference as a resource for quantum speedup
• Protected gates for topological quantum field theories
• Orbital angular momentum in phase space
• A Quantum Observable for the Graph Isomorphism Problem
• Qudit Colour Codes and Gauge Colour Codes in All Spatial Dimensions
• The Power of Noisy Fermionic Quantum Computation
• The quantum FFT can be classically simulated
• Efficient Quantum Algorithms for Estimating Gauss Sums
• Quantum algorithms for spin models and simulable gate sets for quantum computation
• Testing integrability with a single bit of quantum information
• Wigner function for a particle in an infinite lattice
• Quantum computation of discrete logarithms in semigroups
• Several natural BQP-Complete problems
• A linearized stabilizer formalism for systems of finite dimension
• A monomial matrix formalism to describe quantum many-body states
• Non-negative Wigner functions for orbital angular momentum states
• 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
• Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups
• Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit
• 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
• Quantum Algorithm for Computing the Period Lattice of an Infrastructure
• Quantum algorithms for problems in number theory, algebraic geometry, and group theory
• Efficiently contractable quantum circuits cannot produce much entanglement
• Abelian Hypergroups and Quantum Computation
• Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups
• Classical and Quantum Algorithms for Testing Equivalence of Group Extensions
• A quantum polylog algorithm for non-normal maximal cyclic hidden subgroups in the affine group of a finite field
• Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem

Cited by in corpus (3)

• Robust encoding of a qubit in a molecule
• Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits
• The vacuum provides quantum advantage to otherwise simulatable architectures