arXiv:2610.08890
Quantum Readout Complexity for Normalized Linear Functionals
Roi Vence-Nogueira
Abstract
Quantum numerical algorithms often encode a positive solution $q$ in the amplitudes of a quantum state, while the required scientific output is a normalized linear functional of $q$. Basis measurements produce probabilities determined by squared solution values, while the functional uses the solution values themselves. We study the complexity of this output-interface problem for $F_φ(q)=\intφq\,\mathrm dν/\int q\,\mathrm dν$ and identify a target-dependent susceptibility $χ_φ$ that governs the amount of copies of the solution state needed. For a fixed positive reference state and a neighborhood around it, the optimal number of unknown-state copies is $Θ\!\left(χ_0\varepsilon^{-2}\log(1/β)\right)$, where $\varepsilon$ is the absolute error tolerance and $β$ is the allowed failure probability. We show that two fixed single-copy measurements attain the same rate. We then analyze how this baseline changes when the interface retains classical information, uses adaptive allocation, supplies coherent access, or restricts the allowed solution family. Therefore $χ_φ$ quantifies a central cost of using a solution encoded in an $L^2$-normalized quantum state to estimate an $L^1$-normalized linear observable.
AI Summary
Quantum numerical algorithms may encode a positive solution $q$ in amplitudes proportional to $q$, while the desired output is $F_\phi(q)=\int\phi q\,d\nu/\int q\,d\nu$. Basis measurements instead sample squared amplitudes. This paper characterizes readout complexity when only independent solution-state copies, the measure, and the bounded observable $\phi$ are supplied. The central quantity is $\chi_\phi(q)=(\int q^2\,d\nu)/(\int q\,d\nu)^2\int(\phi-F_\phi(q))^2\,d\nu$. Around a fixed positive reference state, in a state-norm ball of radius $\kappa_0/4$, where $\kappa_0=\int q_0/\sqrt{\nu(\Omega)\int q_0^2}$, the minimax copy complexity is $\Theta(\chi_0\varepsilon^{-2}\log(1/\beta))$ for $\varepsilon\leq\kappa_0\sqrt{\chi_0}/12$ and $\beta\leq1/3$. Two fixed single-copy measurements attain this rate using a ratio estimator and median amplification. The converse constructs positive, target-separated states with fidelity divergence $O(\varepsilon^2/\chi_0)$ and applies quantum binary testing, covering biased estimators and collective measurements. A near-uniform example requires $\Omega(\sqrt D)$ basis samples at fixed accuracy, versus dimension-independent copies with these measurements. Extensions give coherent query complexity $\Theta(\sqrt{\chi_0}/\varepsilon)$ at constant confidence, adaptive allocation, and susceptibility reduction through retained classical moments. Consistent discretization preserves susceptibility; a transport pulse family exhibits inverse-width copy cost. The guarantees concern copy count, not measurement implementation or end-to-end solver cost. Lower bounds for restricted solution families require admissible hard pairs: large susceptibility alone is insufficient. Classical records or coherent preparation can change the cost. Finite measure is essential to the neighborhood guarantee, and the principal theorem is local with a restricted accuracy range.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 20 pages, 1 table