Quantum algorithms for shifted subset problems
arXiv:0806.3362
Abstract
We consider a recently proposed generalisation of the abelian hidden subgroup problem: the shifted subset problem. The problem is to determine a subset S of some abelian group, given access to quantum states of the form |S+x>, for some unknown shift x. We give quantum algorithms to find Hamming spheres and other subsets of the boolean cube {0,1}^n. The algorithms have time complexity polynomial in n and give rise to exponential separations from classical computation.
15 pages; v3: simplified proof of main result
References in corpus (6)
- Reversing quantum dynamics with near-optimal quantum and classical fidelity
- An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
- Quantum factoring, discrete logarithms and the hidden subgroup problem
- Quantum algorithms for hidden nonlinear structures
- How many copies are needed for state discrimination?
- Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs