← Back to papers
On the Exponential Sample Complexity of the Quantum State Sign Estimation Problem
Arthur G. Rattew, Marco Pistoia·August 6, 2021
Computer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We demonstrate that the ability to estimate the relative sign of an arbitrary $n$-qubit quantum state (with real amplitudes), given only $k$ copies of that state, would yield a $kn$-query algorithm for unstructured search. Thus the quantum sample complexity of sign estimation must be exponential: $\Omega(2^{n/2}/n)$. In particular, we show that an efficient procedure for solving the sign estimation problem would allow for a polynomial time solution to the NP-complete problem 3-SAT.