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. 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. 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, 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.
Research manuscript with PDF, LaTeX and review records. An algorithm exactly recovers every k-Fourier-sparse Boolean function with success at least 2/3 using O(k log^3(2k)) independent supplied uniform quantum examples and fixed-polynomial total computation and live space. Fresh residual estimates construct a queryable sign-majority hypothesis; known-function Fourier search and original-target certification contract missing Fourier energy. The theorem uses no target membership query or state-preparation inverse. All samples, adaptive refits and exact rational bit costs are charged. This complements Ye's smaller sample bound with a polynomial computational guarantee. No optimal logarithmic factor, practical implementation, noise robustness, exhaustive novelty, independent peer review, formal certification or BPP/BQP result is claimed. OpenAI Codex assisted derivation, source comparison, drafting and internal checking. Separate model reviews were obtained through Grok, Claude and AGY (configured with Gemini), with findings dispositioned in the archive. These are AI reviews, not independent human peer review.
When does a noisy quantum sampler yield an end-to-end polynomial-time optimization algorithm with performance guarantees? Building on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA, we show that inverse-polynomial ideal probability on the optimal set, together with independent sampling, polynomial-time feasibility repair, and scoring, produces an exact-hit fully polynomial randomized approximation scheme, which we call an FPRASq.
This guarantee survives device noise within an instance-dependent window. For effective circuit depth linear in the product of layer count and problem size, preserving an inverse-depth fraction of the ideal optimal mass increases the required shot complexity by one power of the problem size. Beyond this window, deterministic repair guarantees feasibility and provides an instance-dependent approximation guarantee whenever the induced objective inflation is controlled.
The resulting NP-HQ algorithm fits the Chen-Cotler-Huang-Li oracle model. On any NP-hard kernel-admissible promise family, reproducing its inverse-polynomial optimal overlap with a polynomial-time classical sampler would imply that NP is contained in BPP, even with identical repair and perfect access to the constraint structure. Thus, the separation lies in generating the sampling distribution.
We further introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size. Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables and match or improve every tested QOptlib reference tour.
This preprint studies readout-dependent prediction in a specified classical-quantum continuous-time model with an autonomous classical source and a driven qubit memory. A dynamic model (D) is compared with a scalar-contact model (MATCH) reconstructed to match stationary contact occupancy and both directional switching fluxes. The predictor observes only the qubit memory and the declared classical record j; the target is a future binary signal at an independent exponential horizon. Two distinct results are established by exact interval certificates. At B04, (s,u,v,Omega)=(-1/16,0,0,1), D has lower Brier loss under fixed-Z readout by at least 1/5,000,000, but higher loss under each model's optimal quantum readout by at least 1/2,000,000. This is a commuting conditional-state example. Separately, at nine D-only points with u=1/8, v=0, s in {-1/16,0,1/16}, and Omega in {1/16,1/4,1}, both j sectors have squared normalized commutator norm greater than 10^-8, and the same state's gain over fixed-Z readout is greater than 10^-3. These shared nine-point bounds were extracted after certification. The standard Sylvester readout construction is explicitly attributed. The results are fixed-point statements; they do not establish a continuous parameter region, an unrestricted classical-resource advantage, a causal role of noncommutativity in the B04 reversal, or equal thermodynamic costs. Exact evidence and editable source accompany the preprint in a separate Dataset item. OpenAI ChatGPT/Codex and Anthropic Claude systems assisted the work. Their roles and the limitations of the archived checks are disclosed. AI checks are not human or institutional independent validation. This preprint is not a peer-reviewed journal article. Companion evidence and editable source: https://doi.org/10.6084/m9.figshare.33756607
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.