Quantum mechanical algorithms for the nonabelian hidden subgroup problem
The hidden subgroup problem is at present the keystone problem in quantum computations. In particular, two famous examples of the exponential quantum speedup, the discrete logarithm and factoring problems, are the partial cases of the abelian hidden subgroup problem. In general, the abelian hidden subgroup can be effectively found with a quantum computer by repetition of coset state preparation and Fourier sampling. At the same time many of the basic computational problems can be reduced to the nonabelian hidden subgroup problem, which remains open. It is natural to generalize the Fourier transform method to the case of nonabelian groups. Considering this way authors obtain the negative results: with respect to a random choice of basis the Fourier sampling reveal, in general, an exponentially small amount of information about the hidden subgroup. On the positive side, there were obtained effective solutions for several important special cases of the nonabelian hidden subgroup problem. These solutions are discussed in the paper.
- The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups
- On quantum algorithms for noncommutative hidden subgroups
- The Hidden Subgroup Problem and Quantum Computation Using Group Representations
- scientific article; zbMATH DE number 1304334
- EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
- Quantum algorithm design: techniques and applications
- Query complexity of generalized Simon's problem
- Deterministic algorithms for the hidden subgroup problem
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- The quantum query complexity of the abelian hidden subgroup problem
- Sample complexity of hidden subgroup problem
- Quantum algorithms for algebraic problems
- Extending the Promise of the Deutsch–Jozsa–Høyer Algorithm for Finite Groups
- On the Complexity of the Hidden Subgroup Problem
- Hidden symmetry detection on a quantum computer
- scientific article; zbMATH DE number 5320411 (Why is no real title available?)
- How a Clebsch-Gordan transform helps to solve the Heisenberg hidden subgroup problem
- On statistics, computation and scalability
- scientific article; zbMATH DE number 1304334 (Why is no real title available?)
- Computational indistinguishability between quantum states and its cryptographic application
- Exhaustion 2-subsets in dihedral groups of order 2 p
- The Hidden Subgroup Problem and Quantum Computation Using Group Representations
- scientific article; zbMATH DE number 1406124 (Why is no real title available?)
- On the complexity of the hidden subgroup problem
- Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups
- The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups
- EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
- Automata, Languages and Programming
- Efficient distributed approximation algorithms via probabilistic tree embeddings
- On quantum algorithms for noncommutative hidden subgroups
- Experiments with LAGRASP heuristic for set \(k\)-covering
- Complexity classes of equivalence problems revisited
- Random measurement bases, quantum state distinction and applications to the hidden subgroup problem
- Structural identifiability in low-rank matrix factorization
- Quantum mechanics on finite groups
This page was built for publication: Quantum mechanical algorithms for the nonabelian hidden subgroup problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705722)
