.png){kind=icon}
.png){kind=icon}
Return
Unbounded quantum-classical separation in sample complexity for sphere center finding
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ic.2025.105361.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Keywords:
Quantum algorithms
Sample complexity
Sphere center finding
Quantum walks