Optimal Search and Positive-Adversary Bounds with Accidentally Collapsing Measurements

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.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-15
DOI
https://doi.org/10.5281/zenodo.24261197
Primary Topic
Quantum Computing Algorithms and Architecture
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Optimal Search and Positive-Adversary Bounds with Accidentally Collapsing Measurements

Daniel Fredriksen
Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
preprint

Optimal Search and Positive-Adversary Bounds with Accidentally Collapsing Measurements

Daniel Fredriksen
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Optimal Search and Positive-Adversary Bounds with Accidentally Collapsing Measurements — Daniel Fredriksen · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS