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 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 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 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.
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.
This note records a self-contained exact reduction from every even-order symmetric matrix with binary nonnegative rational off-diagonal entries to a simple unweighted perfect-matching count, with polynomial encoding length, an explicit logarithmic integer-weight gadget, exact rational scaling, and weighted matching fibers. Citing the general-graph FPRAS of OpenAI, it derives a uniform rational hafnian FPRAS with exact zero detection and a rigorously specified bounded-bit total-variation approximate sampler. Logarithmic integer weight removal, binary rational weighted-to-unweighted equivalence, and counting self-reduction are established machinery and credited to earlier work, including Dell and collaborators, McQuillan, and Jerrum, Valiant, and Vazirani. The approximation breakthrough belongs to OpenAI. This is an attributed consequence and implementation note; no first-publication, new reduction, or independent solution of the base approximation problem is claimed. The supplement contains proofs, transparent code, exact finite enumeration and output-law checks, dependency and priority audits, and clean reproduction instructions. Finite checks do not certify the upstream FPRAS. The real upstream Lean statement was inspected, but no independent kernel rebuild was reproduced. Nonnegative rational inputs only; no signed or complex hafnian or unrestricted Gaussian-boson-sampling consequence. AI tools were used extensively in research, drafting and automated adversarial verification. The preprint has not undergone conventional human peer review or refereeing at publication. Automated reviews are not human peer review. Newly authored prose and data are CC BY 4.0; code is MIT as specified in the archive.
We study the two-weight decision version of quantum approximate counting: given oracle access to x∈{0,1}N, distinguish ∣x∣=M from ∣x∣=M+Δ with success probability 1/2+ζ. Using the multiplicative adversary method, we prove Ω(max{ζ(N−M)(M+Δ)/Δ,ζN/Δ}). The same parameter dependence follows from the polynomial-method characterization of the two-layer symmetric function by Podder, Yao, and Ye. Our contribution is a multiplicative-adversary derivation that tracks the progress produced by individual oracle queries. For the first term, after complementing the input if necessary, we assume M+Δ≤N−M. We use the Hamming-layer subspaces from the eigenspace method of Ambainis, Spalek, and de Wolf and compose their adjacent-layer unitary maps to relate the two nonadjacent promise layers. After fixing the queried coordinate, the analysis block-diagonalizes into four-dimensional subspaces. An exact calculation of the one-query progress ratio gives the first lower bound. The same estimate also implies (I−Πbad)∣ΨT⟩2=O(T2Δ2/((N−M)(M+Δ))) for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on n bits with success probability 1/2+ζ requires Ω(ζn) queries, and then reduce unique OR to the two-weight counting problem.