Abelian Hypergroups and Quantum Computation
arXiv:1509.05806
Abstract
Motivated by a connection, described here for the first time, between the hidden normal subgroup problem (HNSP) and abelian hypergroups (algebraic objects that model collisions of physical particles), we develop a stabilizer formalism using abelian hypergroups and an associated classical simulation theorem (a la Gottesman-Knill). Using these tools, we develop the first provably efficient quantum algorithm for finding hidden subhypergroups of nilpotent abelian hypergroups and, via the aforementioned connection, a new, hypergroup-based algorithm for the HNSP on nilpotent groups. We also give efficient methods for manipulating non-unitary, non-monomial stabilizers and an adaptive Fourier sampling technique of general interest.
arXiv comment41 pages + 6 pages appendices. Added references and corrected typos in this version (sections 1-2)
References in corpus (36)
- Fault-tolerant quantum computation by anyons
- Anyons in an exactly solved model and beyond
- Good Quantum Error-Correcting Codes Exist
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Improved Simulation of Stabilizer Circuits
- Quantum Error Correction and Orthogonal Geometry
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- Quantum algorithms for algebraic problems
- An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
- The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
- Quantum computation based on d-level cluster states
- The quantum query complexity of the hidden subgroup problem is polynomial
- Stabilizer states and Clifford operations for systems of arbitrary dimensions, and modular arithmetic
- From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
- Universal simulation of Hamiltonian dynamics for qudits
- On the hardness of classically simulating the one clean qubit model
- A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
- Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
- The Hidden Subgroup Problem - Review and Open Problems
- Protected gates for topological quantum field theories
- A Quantum Observable for the Graph Isomorphism Problem
- Quantum algorithms for spin models and simulable gate sets for quantum computation
- Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
- A linearized stabilizer formalism for systems of finite dimension
- The algebraic hyperstructure of elementary particles in physical theory
- A monomial matrix formalism to describe quantum many-body states
- The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
- Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups
- The computational power of normalizer circuits over black-box groups
- Quantum algorithms for problems in number theory, algebraic geometry, and group theory
- Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems
- Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups
- Quantum algorithms for solvable groups
- Hidden Subhypergroup Problem
- A quantum polylog algorithm for non-normal maximal cyclic hidden subgroups in the affine group of a finite field