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.
41 pages + 6 pages appendices. Added references and corrected typos in this version (sections 1-2)
References in corpus (9)
- Instantaneous non-local computation of low T-depth quantum circuits
- From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
- A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
- The Hidden Subgroup Problem - Review and Open Problems
- Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
- The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
- The computational power of normalizer circuits over black-box groups
- Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups
- Hidden Subhypergroup Problem