Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
We establish a $\Omega(\sqrt{\min\{n,M\}})$ lower bound on the number of quantum state copies required for $M$ adaptive Pauli predictions on $n$ qubits at fixed accuracy, proving that published upper bounds are tight for $M \le n$. This demonstrates that adaptive prediction incurs a significant statistical cost compared to fixed prediction, which scales logarithmically with the number of copies. The lower bound is derived using diagonal states and commuting observables, highlighting the inherent cost of adaptation and quantifying its increase with desired precision.
Adaptive quantum predictions on $n$ qubits require $\Theta(\sqrt{n})$ state copies, a stark contrast to the $O(\log n)$ copies needed for fixed predictions.
Can quantum data reliably answer questions chosen from earlier results? We prove that $M$ adaptive Pauli predictions on $n$ qubits require $Ω(\sqrt{\min\{n,M\}})$ copies at fixed accuracy. Published upper bounds make this tight for $M\le n$. Thus $n$ adaptive predictions cost $Θ(\sqrt n)$ copies, whereas a fixed list costs only $O(\log n)$. The lower bound uses diagonal states and commuting observables, identifying a statistical cost of adaptation. We also quantify how this cost increases with precision.