Unbounded quantum-classical separation in sample complexity for sphere center finding
arXiv:2401.14932 · doi:10.1016/j.ic.2025.105361
Abstract
Fast quantum algorithms can solve important computational problems more efficiently than classical algorithms. However, little is known about whether quantum computing can speed up solving geometric problems. This article explores quantum advantages for the problem of finding the center of a sphere in vector spaces over finite fields, given samples of random points on the sphere. We prove that any classical algorithm for this task requires approximately as many samples as the dimension of the vector space, by a reduction to an old and basic algebraic result -- Warning's second theorem. On the other hand, we propose a quantum algorithm based on quantum walks that needs only a constant number of samples to find the center. Thus, an unbounded quantum advantage is revealed for a natural and intuitive geometric problem, which highlights the power of quantum computing in solving geometric problems.
The title has been adjusted, but the main results have no change. This paper has been published in Information and Computation
References in corpus (11)
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- A rigorous and robust quantum speed-up in supervised machine learning
- Search via Quantum Walk
- Quantum walks can find a marked element on any graph
- Quantum algorithms for hidden nonlinear structures
- Exponential quantum speedup in simulating coupled classical oscillators
- Quantum Algorithms for Learning and Testing Juntas
- Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Optimal exact quantum algorithm for the promised element distinctness problem
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact