Optimal Search with Accidentally Collapsing Measurements
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.
Authors
- Daniel Fredriksen
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-15
- DOI
- https://doi.org/10.5281/zenodo.24255781
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- preprint