Research preprint. For unique-item search with a noiseless oracle and a Born sampler that independently projects its sampled register with probability epsilon, with immediate outcome/flag feedback on the same persistent state, the optimal total query/readout/preparation/ordinary-measurement cost is Theta(N^(1/3)+sqrt(epsilon N)). A fixed-power conditional-history fidelity argument gives the matching lower bound despite arbitrary entangled workspace and partial measurements. The deferred ideal endpoint, conditional-copy framework and repeated-sampling template are attributed to prior work, including ABFL, Miloschewsky--Podder and prior imperfect-readout robustness by Abbas et al. This is a specified hypothetical postquantum model, not physical noisy hardware, a classification of all noisy PDQP or an ordinary BPP/BQP result. OpenAI Codex assisted derivation, literature comparison, drafting and internal checking. Separate provider CLI AI-review reports and their dispositions are recorded in the archive. No independent human peer review or formal certification has occurred. The revision extends the lower bound by finite-tree induction and query-frontier alignment to adaptive control; at epsilon=0 it addresses the cited persistent CQP search question under charged-call accounting.
Research preprint. For unique-item search with a noiseless oracle and a Born sampler that independently projects its sampled register with probability epsilon, with immediate outcome/flag feedback on the same persistent state, the optimal total query/readout/preparation/ordinary-measurement cost is Theta(N^(1/3)+sqrt(epsilon N)). A fixed-power conditional-history fidelity argument gives the matching lower bound despite arbitrary entangled workspace and partial measurements. The deferred ideal endpoint, conditional-copy framework and repeated-sampling template are attributed to prior work, including ABFL, Miloschewsky--Podder and prior imperfect-readout robustness by Abbas et al. This is a specified hypothetical postquantum model, not physical noisy hardware, a classification of all noisy PDQP or an ordinary BPP/BQP result. OpenAI Codex assisted derivation, literature comparison, drafting and internal checking. Separate provider CLI AI-review reports and their dispositions are recorded in the archive. No independent human peer review or formal certification has occurred. The revision extends the lower bound by finite-tree induction and query-frontier alignment to adaptive control; at epsilon=0 it addresses the cited persistent CQP search question under charged-call accounting.
Research preprint. For unique-item search with a noiseless oracle and a Born sampler that independently projects its sampled register with probability epsilon, with outcomes and flags deferred until the circuit ends, the optimal total query/readout/preparation/ordinary-measurement cost is Theta(N^(1/3)+sqrt(epsilon N)). A fixed-power conditional-history fidelity argument gives the matching lower bound despite arbitrary entangled workspace and partial measurements. The ideal endpoint, conditional-copy framework and repeated-sampling template are attributed to prior work, including ABFL, Miloschewsky--Podder and prior imperfect-readout robustness by Abbas et al. This is a specified hypothetical postquantum model, not physical noisy hardware, a classification of all noisy PDQP or an ordinary BPP/BQP result. OpenAI Codex assisted derivation, literature comparison, drafting and internal checking. Separate provider CLI AI-review reports and their dispositions are recorded in the archive. No independent human peer review or formal certification has occurred.
Research preprint, version 0.3.0. We study a hypothetical Born sampler that independently projects its sampled register with probability epsilon, with immediate outcome/flag feedback on the same persistent state and a noiseless input oracle. Constant-success unique-item search has optimal total query/readout/preparation/ordinary-measurement cost Theta(N^(1/3)+sqrt(epsilon N)), with separately paid gates, classical work, space, transcript bits and precision. The revision adds a second main theorem: every finite Boolean promise problem with success at least 2/3 satisfies Q min{P+1,ceil(1/epsilon)} >= Adv_+(f)/36, using P+1 at epsilon=0. Adv_+ is the entrywise-nonnegative spectral adversary. A complete-history spectral query charge covers entangled workspace, partial measurements, permitted resets, feedback and unequal stopping without a history-count factor. Fixed and decreasing powers are proved separately. The parity application gives Omega(n) queries at any fixed positive collapse rate. The sharper search theorem is retained. The algorithmic template, ideal endpoint and conditional-copy framework are attributed to ABFL and Miloschewsky--Podder; prior imperfect-readout robustness to Abbas et al.; positive weighted/spectral adversary machinery to the established literature including Miloschewsky--Podder and Spalek--Szegedy. Certificates may be exponentially large analytical objects. No signed-adversary extension, efficient certificate discovery, physical implementation, classification of all noisy PDQP or ordinary BPP/BQP result is claimed. OpenAI Codex assisted derivation, literature comparison, drafting and internal checking. Separate provider CLI AI-review reports and dispositions are archived; no independent human peer review or formal certification has occurred.
This theoretical and computational preprint integrates standard QND measurement and posterior-martingale results with finite-confidence decisions and physically retained observer records. Under a declared quantum instrument and its standard outcome probabilities, the posterior is a bounded martingale on an increasing observation filtration. A precise sufficient identification condition yields asymptotic terminal weights; a binary Gaussian benchmark gives exact mean stopping times, finite-threshold latch probabilities, and a controlled population-transfer bias bound. Version 2.3 is the first public release. It distinguishes accumulated observations from lossy current memory; assumed Born/instrument probabilities from derived consistency results; expected entropy from pathwise ambiguity; continuous confidence endpoints from discrete overshoot and unresolved runs; and Kramers first escape from endpoint readout error. It also clarifies the conditional D18/D19 persistence-selector interface and the separate D1092 finite-resource ledger, with direct attribution to established QND convergence and filtering literature. The companion archive includes the editable manuscript, PDF, equation sources, a fixed validation protocol, executable independent checks, numerical results, a revision ledger, and unchanged historical inputs. Historical simulation summaries are explicitly distinguished from new executions; some older executable sources were unavailable. The new audit includes exact finite-kernel and stopped-posterior checks, Gaussian likelihood-mixture calculations, five neutral and four population-transfer boundary-value cases, and retention/accounting controls. All examples are analytic or synthetic. No laboratory measurements, independent Born-rule derivation, measurement-problem solution, universal physical selector, or new empirical anchor are claimed.
In quantum property estimation, an experimenter estimates Tr(Oρ) for a family of observables from independent copies of an unknown state ρ simultaneously to additive error ε. While quantum memory can dramatically reduce sample complexity, understanding the power of a modest register that remains coherent throughout an adaptive experiment has remained an open challenge because existing frameworks require optimizing over the infinite space of measurement trees. We overcome this barrier by developing a backward-induction framework based on operator resolvents. Rather than tracking path-dependent memory states across rounds, resolvent regularization cancels internal memory trajectories exactly, reducing the lower bound to an algebraic certificate computed directly from the target observables with sharp Ω(1/ε2) scaling. Our structural rule charges only the retained dimension K under arbitrary adaptive instruments and unrestricted memory lifetime. Via symmetry reductions, it yields polynomial-size linear programs that establish the optimal linear Ω(D/(Kε2)) trade-off for the D2−1 Paulis, eliminating the cubic loss in prior bounds. For growing weight-w Pauli strings (w=⌈log2n⌉) and quadratic Majorana cross-correlations, it proves lower bounds of Ω(3w/ε2) and Ω(n2/(ε2(1+lnn)2)) against an indefinitely persistent memory of dimension K=⌊n⌋. These bounds match memoryless or commuting estimators within polylogarithmic factors, demonstrating that rank constraints on the persistent register fundamentally throttle observable overlap and prevent a modest coherent memory from overcoming the sample complexity barrier.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most q oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model:
(i) (Unbiased) Phase estimation up to a precision ε requires Θ(qε21) queries;
(ii) (Unbiased) Amplitude estimation up to a precision ε requires Θ(qε2p(1−p)) queries;
(iii) Search among N items requires Θ(qN) queries;
(iv) Two level AND-OR tree (AND of m ORs, with n inputs to each OR) requires Θ(qnm) queries.
All of these bounds are optimal up to a constant factor, for all q from 1, corresponding to the classical complexity, to Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor.
Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability p>0 completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum O(n)-query algorithms in this setting, even for constant p. We show that, for all p≤0.99, the quantum noisy-query complexity of the unstructured search is Θ~(max{np,n}). The lower bound Ω(max{np,n}) holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.