On the Exponential Sample Complexity of the Quantum State Sign Estimation Problem
2021
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
6
References
0
Citations
NaN
KQI