The Hidden Subgroup Problem - Review and Open Problems

Abstract

An overview of quantum computing and in particular the Hidden Subgroup Problem are presented from a mathematical viewpoint. Detailed proofs are supplied for many important results from the literature, and notation is unified, making it easier to absorb the background necessary to begin research on the Hidden Subgroup Problem. Proofs are provided which give very concrete algorithms and bounds for the finite abelian case with little outside references, and future directions are provided for the nonabelian case. This summary is current as of October 2004.

A thorough introduction to the HSP, with detailed proofs for many results, and an overview of the research literature through 2004. This is designed to bring more people to bear on the problem. 83 pages

References in corpus (25)

• Elementary gates for quantum computation
• Good Quantum Error-Correcting Codes Exist
• Strengths and Weaknesses of Quantum Computing
• Quantum Amplitude Amplification and Estimation
• Quantum Algorithms Revisited
• Quantum Error Correction and Orthogonal Geometry
• Semiclassical Fourier Transform for Quantum Computation
• A Quantum Algorithm for Finding the Minimum
• Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
• The quantum query complexity of the hidden subgroup problem is polynomial
• Quantum factoring, discrete logarithms and the hidden subgroup problem
• Quantum Random Walks Hit Exponentially Faster
• An Introduction to Quantum Complexity Theory
• Introduction to Quantum Algorithms
• Efficient Quantum Transforms
• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
• Quantum convolution and quantum correlation algorithms are physically impossible
• A Quantum Observable for the Graph Isomorphism Problem
• Hidden Subgroup States are Almost Orthogonal
• Efficient Quantum Algorithms for Shifted Quadratic Character Problems
• The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
• Quantum searching with continuous variables
• Countinuous Quantum Hidden Subgroup Algorithms
• Quantum State Detection Via Elimination
• A quantum Fourier transform algorithm

Cited by in corpus (22)

• A random walk approach to quantum algorithms
• qHiPSTER: The Quantum High Performance Software Testing Environment
• Quantum walks on quotient graphs
• Quantum Computation Beyond the Circuit Model
• Period Finding with Adiabatic Quantum Computation
• Obtaining the Quantum Fourier Transform from the Classical FFT with QR Decomposition
• The Optimal Single Copy Measurement for the Hidden Subgroup Problem
• The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks
• Normalizer Circuits and Quantum Computation
• Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems
• Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups
• Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups
• The central nature of the Hidden Subgroup problem
• Abelian Hypergroups and Quantum Computation
• Classical simulations of Abelian-group normalizer circuits with intermediate measurements
• An Improved Query for the Hidden Subgroup Problem
• The Study of Entangled States in Quantum Computation and Quantum Information Science
• Simon's Algorithm, Clebsch-Gordan Sieves, and Hidden Symmetries of Multiple Squares
• Recursive Path-Summing Simulation of Quantum Computation
• Quantum collision finding for homomorphic hash functions
• Quantum Property Testing for Solvable Groups
• Towards a Group Theoretic Quantum Encryption Scheme Based on Generalized Hidden Subgroup Problem