Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Certified Depth–Width Frontiers for Reversible SELECT Circuits: Exact four-target curves, an all-width eight-target lower bound, and DRAT-certified boundary instances

Daniel Martín

Published Aug 15, 2026• 0 citations
Publisher

Abstract

We determine the complete fixed-width depth curve of the four-target one-hot selector SELECT_X in a fully declared classical-reversible model: gate set {X, CNOT, Toffoli}, pairwise-disjoint-support layers, all-to-all connectivity, dirty data targets, and clean ancillae restored to zero. The curve is D∗_SELECT(4,Q) = infinity for Q < 6; 5 for Q = 6; and 4 for Q >= 7. The two finite values are exact by exhaustive meet-in-the-middle; the all-width statement rests on a lossless normal-form reduction of every depth-3 clean-ancilla circuit to an independently certified finite core. A causal argument gives D∗(2^k,Q) >= k+1 for every k and every width. We then prove a conditional parametric saturation obstruction: if the width-free k-layer frontier contains at most 2^(k-1) carriers of the top address monomial but fewer than 2^(k-1) distinct minterms, then D∗(2^k,Q) >= k+2 at every width. For k = 3, independent Python and C++ exhaustions produce byte-identical complete frontiers (57 and 18,215 canonical states) and establish the hypotheses, yielding the all-width theorem D∗(8,Q) >= 5 for every Q >= 11. An explicit four-layer construction gives C_4(4) >= 10 > 8, so this sufficient criterion does not induct to k = 4. The prospective k+2 law therefore remains open and requires a different lower-bound invariant. If workspace may be left dirty, pure-encoding UNSAT certificates at widths 10 and 11, together with a verified width-12 construction, show that the smallest width at which four-target selection reaches depth 3 is exactly 12; for every Q >= 12, workspace restoration costs exactly one layer at the same width. For ancilla-free dirty-target fan-out we compute the exact depths through seven targets and prove that 2^d - 1 targets require depth at least d+1, above the causal floor. At minimum width the threshold values are 2, 4, 4 for m = 2, 3, 4, and a pure-encoding DRAT certificate gives D∗_THR(5) >= 5; the nonlinear payload has exact depth D∗_carry(6) = 6. The decisive UNSAT formulas and proofs are fixed by SHA-256 and accepted by an independently compiled proof checker; constructions are verified symbolically or exhaustively. We make no priority claim: a systematic novelty search is incomplete, and no result is asserted as first or novel. This record is version 3 of the Zenodo preprint. Earlier versions remain permanently citable through their version-specific DOIs. Version 3 extends version 2 with: the exact closure of the arithmetic-payload depth (D∗_carry(6) = 6, DRAT-certified, and carry(7) in {5,6}); the DRAT-certified threshold bound D∗_THR(5) >= 5; the completed garbage-width curve (minimum width for depth 3 exactly 12, via pure-encoding DRAT exclusions at widths 10 and 11); the all-width eight-target lower bound D∗(8,Q) >= 5 for every valid width, via a conditional parametric saturation argument and independent, byte-identical Python and C++ enumerations of the width-free k=3 frontier; an explicit witness showing the k=3 carrier criterion does not induct to k=4; and restricted (architecture-specific) depth-5 exclusions, explicitly not claimed as general impossibilities. The general depth-5 question at L=8 and the prospective all-k law remain open; the latter appears only as a conjecture. The large DRAT certificate archive is being prepared as a separate, DOI-linked Zenodo dataset.

DOI
10.5281/zenodo.21957770

Related papers

A 44-gate, depth-6 Clifford circuit preparing the [[23,1,7]] Golay logical zero: a new point on the CNOT-count/depth frontier

Harish Santhanalakshmi Ganesan

Short note with the circuit, an independent verifier and the search records. For ancilla-free Clifford preparation of the logical zero |0_G> = 2^{-11/2} Σ_{c ∈ C^⊥} |c> of the [[23,1,7]] quantum Golay code (Open Problem Zoo op_c847b635f53b0812, after Paetznick and Reichardt 2012), the best documented circuits were 45 two-qubit gates at two-qubit depth 7 and 44 gates at depth 8 (Doherty et al., arXiv:2603.17743). We exhibit an explicit circuit with 44 two-qubit gates (all controlled-Z, i.e. CNOT up to free single-qubit Cliffords) in six disjoint two-qubit layers of sizes 9, 10, 7, 6, 7, 5, so g_G(D) ≤ 44 for every D ≥ 6; it dominates both previous Pareto points. The circuit is given in the cyclic coordinates of the Golay code (generator polynomial 1+x^2+x^4+x^5+x^6+x^10+x^11) and verified two independent ways: a stabilizer-tableau proof (the output stabilizer group is CSS with all + signs, its Z-code is a binary [23,12,7] code, hence the Golay code by uniqueness, and an explicit wire permutation is exhibited) and a full 2^23-amplitude statevector overlap of 1.0 with the target. The circuit was found by an autonomous AI research agent (the depositor's EVO discovery harness, Claude Sonnet 5.5 proposer) by a local search started from the published 44-gate depth-8 circuit: a bit-packed C tableau simulator, a cost equal to the number of qubits left entangled when the circuit is run backwards from the target, and a random walk among 44-gate circuits that penalises gates in layers beyond the target depth. The same searches did not find 43 gates at any depth or 44 gates at depth 5 (about 10^10 and 10^9 evaluations respectively; these are negative search outcomes, not bounds). Claim boundary: an upper bound g_G(6) ≤ 44 witnessed by an explicit, machine-checkable circuit; no optimality or priority claim. Files: the note (PDF + LaTeX), the circuit in three equivalent JSON forms (agent wire labels; cyclic coordinates; cyclic coordinates with CNOT as the only two-qubit gate), the verifier and relabeling finder, the agent's notes and search code, the task text, SHA-256 sums.

•Oct 20, 2026•0 citations

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

quant-pharXiv:2609.34659•Sep 29, 2026•1 citation

A parity obstruction to degree-optimal syndrome extraction in bivariate bicycle codes

Guangyi Li, Yu Gan, Zeguan Wu +3 more

Syndrome extraction for a CSS code has depth at least the Tanner-graph degree $Δ$, attained by edge colouring if gate order is ignored; correctness adds a parity constraint. We prove three general obstructions to depth-$Δ$ extraction and show that, for every two-block group-algebra code with weight-three polynomials whose checks overlap in at most two qubits, no correct single-round circuit with one ancilla per check and one CNOT per Tanner edge has depth six: the minimum is seven, so the seven-layer cycle of Bravyi \emph{et al.} is optimal for their seven bivariate bicycle codes. This is the first analytic, family-wide impossibility result, extending prior instance-specific solver-based infeasibility results. The hypothesis cannot be dropped: a single orbit of four-qubit overlaps with a collision element of even order and $2$-height at most eight makes depth six attainable, and a $[[72,8,6]]$ code of this kind has a verified six-layer circuit. The refutations carry DRAT certificates. As a further application of the same scheduling scheme, we construct Stab-QRAM, a quantum random access memory for affine Boolean data that uses only CNOT and $X$ gates and has the minimum depth possible for this gate set.

quant-pharXiv:2509.26494•Oct 1, 2025

Finite-Count Calibration of Ancilla-Orientation Safe Maps A Bell-Apparatus Bound and a Reference-Link Obstruction

Qingchun Zhang

An exact operational selector specifies which candidate maps are nonnegative on declared preparation and effect resources. This paper studies finite-count calibration of that resource-dependent question for a qubit apparatus with an inert qubit reference, an arbitrary complex physical preparation, and an arbitrary physical binary detector, relative to a trusted common calibration frame. Two preparation-stabilizer settings and six separable detector probes control the statistic of the affine family (1 − θ)id + θT, 0 ≤ θ ≤ 1, uniformly over all compatible state–effect pairs. The explicit radius is 3h + √(2s), where h is a simultaneous detector calibration width and s is a one-sided bound on Bell infidelity. It yields simultaneous inner and outer confidence sets for a one-parameter slice of the declared safe-map class. A fixed allocation of 200,000 trials per calibration setting, totaling 1,600,000 calibration trials, gives false-implication probability at most 0.005 and transpose-exclusion power at least 0.996 at the specified physical alternative. The calibration confidence budgets are 0.001 for preparation and 0.004 for the detector. This exclusion calculation uses no target stream; the acquired calibration circuits can use identity wiring. Coverage and prospective power remain separate statements. The acquisition contract uses fixed-length iid Bernoulli streams with their stated physical means and permits coupling between whole streams. The numerical example sets external-reference systematic errors to zero, and its trial budget excludes establishing reference trust and accuracy. If the preparation and detector references are not linked, the paper constructs two physical identity-wired apparatus worlds with identical complete record laws under the specified independent acquisition construction but different safety conclusions on the fixed target cone pair. A secondary nearest-center theorem supplies unconditional error control for the joint event of a wrong and nonabstaining candidate label under an additional finite-context target-law contract. Its nonidentity candidates are not completely positive maps, and their ideal probabilities lie below the nominal detector’s ordinary positive-output floor. That target law is an explicit model assumption; the label theorem is not a conditional-correctness or posterior statement. The results are analytic and prospective. The number of settings and trial allocations are sufficient constructions, with no empirical success-rate, minimality, optimal sample-complexity, or general certified count-to-feasibility implementation claim. The scope is one declared qubit apparatus, target preparation ray and binary effect cone, and affine map slice. The common complex operator description, trusted reference relationship and physical calibration probability law are assumptions. Exact finite checks and an assessed supporting Lean subset accompany the manuscript. That subset covers 326 audited named declarations: 240 theorems and 86 definition/type interfaces. Analytic binomial coverage, concentration and acquisition bridges, independent-product-law construction and normalization, and the complete noisy-power chain remain outside the accepted Lean subset. That subset does not establish a certified numerical feasibility evaluator, a complete physical two-sector implementation, or an ordinary-channel realization. AI assistance and the dated review/correction provenance are disclosed in the manuscript and companion records. No experimental dataset, external human peer review, or end-to-end formal verification is claimed.

•Nov 8, 2026•0 citations

SAT-Guided Conversion of Boolean Functions into Reversible Quantum Logic: Minimal Embedding, Exact Synthesis, and Cost-Aware Mapping

Chandan Bandyopadhyay, Saibal Majumder, Haresh Kumar Sharma

A classical Boolean specification need not be one-to-one, whereas every reversible quantum network must preserve distinctions between basis states. SAT-Embed-Q handles this mismatch by first constructing a partial reversible embedding from output-preimage multiplicities and then searching for a compatible mixed-polarity Toffoli network. We implemented two bounded satisfiability encodings, one tracking complete intermediate states and the other tracking individual line values, and evaluated both with a deterministic reference DPLL solver. On the four-line example F(a,b,c)=ab¯∨bc, the minimum-depth CNF contains 42,234 clauses in the direct encoding and 34,194 in the bit-level encoding. The smaller clause set did not translate into faster execution: the direct representation required less time in our solver. A separate exhaustive study of the target-preserving oracle class covers every single-output function of two and three inputs. Within that restricted class, allowing negative controls lowers the summed minimum target-gate count by 34.38% and 46.39%, respectively. We also examine two four-input functions from RevLib, for which fixing the input-preserving oracle structure leads to different gate counts from embedding-optimized benchmark circuits. These experiments characterize bounded synthesis and control-polarity choices for small functions; fault-tolerant resource optimization and large-network scalability remain outside their scope.

Quantum Reports•Oct 26, 2026•0 citations

Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems

Nishant Shukla

Coherent quantum rollout for sequential decision problems requires a unitary simulator: randomness must live in explicit quantum registers, and basis-state selectors must be mapped to actions reversibly. With branch-dependent valid actions, this mapping is totalized coherent rank-select over an entangled $N$-bit validity mask: return the position of the $r$-th valid bit, or a sentinel if $r$ is out of range. We give the first reversible-circuit complexity analysis of this primitive. For selector width $w = \lceil \log_2(N+1) \rceil$, rank-select admits an $O(Nw)$-gate low-ancilla bounded-span scan, proved gate-optimal in its model, and an $O(N\log w)$-gate low-ancilla blocked construction when long-range gates are available; across all bounded-fan-in layouts, the unconditional gate lower bound is $Ω(N)$. Composing rank-select with reversible transition and predicate-evaluation circuits gives an explicit polynomial-size coherent rollout oracle for finite-horizon planning problems satisfying these primitive assumptions. The resulting oracle satisfies the access model of the best-arm pipeline of Wang et al., yielding $\widetilde{O}(\sqrt{k}/\varepsilon)$ coherent oracle calls against the standard classical $Ω(k/\varepsilon^2)$ arm-pull lower bound. We give a bounded-influence lifting theorem that extends this lower-bound construction from a base configuration to an exponential family of configurations. We instantiate the construction on SIR epidemic intervention, with a stochastic placement-game sanity check, and machine-check the main results in Lean 4. Code and proofs: https://github.com/BinRoot/b01t/tree/main/demos/rollout.

quant-pharXiv:2604.25962•Apr 29, 2026•1 citation
We determine the complete fixed-width depth curve of the four-target one-hot selector SELECT_X in a fully declared classical-reversible model: gate set {X, CNOT, Toffoli}, pairwise-disjoint-support layers, all-to-all connectivity, dirty data targets, and clean ancillae restored to zero. The curve is D∗_SELECT(4,Q) = infinity for Q < 6; 5 for Q = 6; and 4 for Q >= 7. The two finite values are exact by exhaustive meet-in-the-middle; the all-width statement rests on a lossless normal-form reduction of every depth-3 clean-ancilla circuit to an independently certified finite core. A causal argument gives D∗(2^k,Q) >= k+1 for every k and every width. We then prove a conditional parametric saturation obstruction: if the width-free k-layer frontier contains at most 2^(k-1) carriers of the top address monomial but fewer than 2^(k-1) distinct minterms, then D∗(2^k,Q) >= k+2 at every width. For k = 3, independent Python and C++ exhaustions produce byte-identical complete frontiers (57 and 18,215 canonical states) and establish the hypotheses, yielding the all-width theorem D∗(8,Q) >= 5 for every Q >= 11. An explicit four-layer construction gives C_4(4) >= 10 > 8, so this sufficient criterion does not induct to k = 4. The prospective k+2 law therefore remains open and requires a different lower-bound invariant. If workspace may be left dirty, pure-encoding UNSAT certificates at widths 10 and 11, together with a verified width-12 construction, show that the smallest width at which four-target selection reaches depth 3 is exactly 12; for every Q >= 12, workspace restoration costs exactly one layer at the same width. For ancilla-free dirty-target fan-out we compute the exact depths through seven targets and prove that 2^d - 1 targets require depth at least d+1, above the causal floor. At minimum width the threshold values are 2, 4, 4 for m = 2, 3, 4, and a pure-encoding DRAT certificate gives D∗_THR(5) >= 5; the nonlinear payload has exact depth D∗_carry(6) = 6. The decisive UNSAT formulas and proofs are fixed by SHA-256 and accepted by an independently compiled proof checker; constructions are verified symbolically or exhaustively. We make no priority claim: a systematic novelty search is incomplete, and no result is asserted as first or novel. This record is version 3 of the Zenodo preprint. Earlier versions remain permanently citable through their version-specific DOIs. Version 3 extends version 2 with: the exact closure of the arithmetic-payload depth (D∗_carry(6) = 6, DRAT-certified, and carry(7) in {5,6}); the DRAT-certified threshold bound D∗_THR(5) >= 5; the completed garbage-width curve (minimum width for depth 3 exactly 12, via pure-encoding DRAT exclusions at widths 10 and 11); the all-width eight-target lower bound D∗(8,Q) >= 5 for every valid width, via a conditional parametric saturation argument and independent, byte-identical Python and C++ enumerations of the width-free k=3 frontier; an explicit witness showing the k=3 carrier criterion does not induct to k=4; and restricted (architecture-specific) depth-5 exclusions, explicitly not claimed as general impossibilities. The general depth-5 question at L=8 and the prospective all-k law remain open; the latter appears only as a conjecture. The large DRAT certificate archive is being prepared as a separate, DOI-linked Zenodo dataset.
Short note with the circuit, an independent verifier and the search records. For ancilla-free Clifford preparation of the logical zero |0_G> = 2^{-11/2} Σ_{c ∈ C^⊥} |c> of the [[23,1,7]] quantum Golay code (Open Problem Zoo op_c847b635f53b0812, after Paetznick and Reichardt 2012), the best documented circuits were 45 two-qubit gates at two-qubit depth 7 and 44 gates at depth 8 (Doherty et al., arXiv:2603.17743). We exhibit an explicit circuit with 44 two-qubit gates (all controlled-Z, i.e. CNOT up to free single-qubit Cliffords) in six disjoint two-qubit layers of sizes 9, 10, 7, 6, 7, 5, so g_G(D) ≤ 44 for every D ≥ 6; it dominates both previous Pareto points. The circuit is given in the cyclic coordinates of the Golay code (generator polynomial 1+x^2+x^4+x^5+x^6+x^10+x^11) and verified two independent ways: a stabilizer-tableau proof (the output stabilizer group is CSS with all + signs, its Z-code is a binary [23,12,7] code, hence the Golay code by uniqueness, and an explicit wire permutation is exhibited) and a full 2^23-amplitude statevector overlap of 1.0 with the target. The circuit was found by an autonomous AI research agent (the depositor's EVO discovery harness, Claude Sonnet 5.5 proposer) by a local search started from the published 44-gate depth-8 circuit: a bit-packed C tableau simulator, a cost equal to the number of qubits left entangled when the circuit is run backwards from the target, and a random walk among 44-gate circuits that penalises gates in layers beyond the target depth. The same searches did not find 43 gates at any depth or 44 gates at depth 5 (about 10^10 and 10^9 evaluations respectively; these are negative search outcomes, not bounds). Claim boundary: an upper bound g_G(6) ≤ 44 witnessed by an explicit, machine-checkable circuit; no optimality or priority claim. Files: the note (PDF + LaTeX), the circuit in three equivalent JSON forms (agent wire labels; cyclic coordinates; cyclic coordinates with CNOT as the only two-qubit gate), the verifier and relabeling finder, the agent's notes and search code, the task text, SHA-256 sums.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0δ>0δ>0, it ε\varepsilonε-approximates an arbitrary single-qubit gate using O(log⁡1+δ(1/ε))O(\log^{1+δ}(1/\varepsilon))O(log1+δ(1/ε)) clean ancillae, Hadamard and TTT single-qubit gates, O(log⁡(1/ε))O(\log(1/\varepsilon))O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, TTT, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon))O(loglog(1/ε)), and we prove a matching Ω(log⁡log⁡(1/ε))Ω(\log\log(1/\varepsilon))Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(log⁡log⁡(1/ε))Θ(\log\log(1/\varepsilon))Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-ddd QAC circuit can be simulated in depth O(d)O(d)O(d) using only Hadamard, XXX, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∉\notin∈/QAC0^00 to proving a Parity lower bound against circuits consisting only of Hadamard, XXX, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
Syndrome extraction for a CSS code has depth at least the Tanner-graph degree ΔΔΔ, attained by edge colouring if gate order is ignored; correctness adds a parity constraint. We prove three general obstructions to depth-ΔΔΔ extraction and show that, for every two-block group-algebra code with weight-three polynomials whose checks overlap in at most two qubits, no correct single-round circuit with one ancilla per check and one CNOT per Tanner edge has depth six: the minimum is seven, so the seven-layer cycle of Bravyi \emph{et al.} is optimal for their seven bivariate bicycle codes. This is the first analytic, family-wide impossibility result, extending prior instance-specific solver-based infeasibility results. The hypothesis cannot be dropped: a single orbit of four-qubit overlaps with a collision element of even order and 222-height at most eight makes depth six attainable, and a [[72,8,6]][[72,8,6]][[72,8,6]] code of this kind has a verified six-layer circuit. The refutations carry DRAT certificates. As a further application of the same scheduling scheme, we construct Stab-QRAM, a quantum random access memory for affine Boolean data that uses only CNOT and XXX gates and has the minimum depth possible for this gate set.
An exact operational selector specifies which candidate maps are nonnegative on declared preparation and effect resources. This paper studies finite-count calibration of that resource-dependent question for a qubit apparatus with an inert qubit reference, an arbitrary complex physical preparation, and an arbitrary physical binary detector, relative to a trusted common calibration frame. Two preparation-stabilizer settings and six separable detector probes control the statistic of the affine family (1 − θ)id + θT, 0 ≤ θ ≤ 1, uniformly over all compatible state–effect pairs. The explicit radius is 3h + √(2s), where h is a simultaneous detector calibration width and s is a one-sided bound on Bell infidelity. It yields simultaneous inner and outer confidence sets for a one-parameter slice of the declared safe-map class. A fixed allocation of 200,000 trials per calibration setting, totaling 1,600,000 calibration trials, gives false-implication probability at most 0.005 and transpose-exclusion power at least 0.996 at the specified physical alternative. The calibration confidence budgets are 0.001 for preparation and 0.004 for the detector. This exclusion calculation uses no target stream; the acquired calibration circuits can use identity wiring. Coverage and prospective power remain separate statements. The acquisition contract uses fixed-length iid Bernoulli streams with their stated physical means and permits coupling between whole streams. The numerical example sets external-reference systematic errors to zero, and its trial budget excludes establishing reference trust and accuracy. If the preparation and detector references are not linked, the paper constructs two physical identity-wired apparatus worlds with identical complete record laws under the specified independent acquisition construction but different safety conclusions on the fixed target cone pair. A secondary nearest-center theorem supplies unconditional error control for the joint event of a wrong and nonabstaining candidate label under an additional finite-context target-law contract. Its nonidentity candidates are not completely positive maps, and their ideal probabilities lie below the nominal detector’s ordinary positive-output floor. That target law is an explicit model assumption; the label theorem is not a conditional-correctness or posterior statement. The results are analytic and prospective. The number of settings and trial allocations are sufficient constructions, with no empirical success-rate, minimality, optimal sample-complexity, or general certified count-to-feasibility implementation claim. The scope is one declared qubit apparatus, target preparation ray and binary effect cone, and affine map slice. The common complex operator description, trusted reference relationship and physical calibration probability law are assumptions. Exact finite checks and an assessed supporting Lean subset accompany the manuscript. That subset covers 326 audited named declarations: 240 theorems and 86 definition/type interfaces. Analytic binomial coverage, concentration and acquisition bridges, independent-product-law construction and normalization, and the complete noisy-power chain remain outside the accepted Lean subset. That subset does not establish a certified numerical feasibility evaluator, a complete physical two-sector implementation, or an ordinary-channel realization. AI assistance and the dated review/correction provenance are disclosed in the manuscript and companion records. No experimental dataset, external human peer review, or end-to-end formal verification is claimed.
A classical Boolean specification need not be one-to-one, whereas every reversible quantum network must preserve distinctions between basis states. SAT-Embed-Q handles this mismatch by first constructing a partial reversible embedding from output-preimage multiplicities and then searching for a compatible mixed-polarity Toffoli network. We implemented two bounded satisfiability encodings, one tracking complete intermediate states and the other tracking individual line values, and evaluated both with a deterministic reference DPLL solver. On the four-line example F(a,b,c)=ab¯∨bc, the minimum-depth CNF contains 42,234 clauses in the direct encoding and 34,194 in the bit-level encoding. The smaller clause set did not translate into faster execution: the direct representation required less time in our solver. A separate exhaustive study of the target-preserving oracle class covers every single-output function of two and three inputs. Within that restricted class, allowing negative controls lowers the summed minimum target-gate count by 34.38% and 46.39%, respectively. We also examine two four-input functions from RevLib, for which fixing the input-preserving oracle structure leads to different gate counts from embedding-optimized benchmark circuits. These experiments characterize bounded synthesis and control-polarity choices for small functions; fault-tolerant resource optimization and large-network scalability remain outside their scope.
Coherent quantum rollout for sequential decision problems requires a unitary simulator: randomness must live in explicit quantum registers, and basis-state selectors must be mapped to actions reversibly. With branch-dependent valid actions, this mapping is totalized coherent rank-select over an entangled NNN-bit validity mask: return the position of the rrr-th valid bit, or a sentinel if rrr is out of range. We give the first reversible-circuit complexity analysis of this primitive. For selector width w=⌈log⁡2(N+1)⌉w = \lceil \log_2(N+1) \rceilw=⌈log2​(N+1)⌉, rank-select admits an O(Nw)O(Nw)O(Nw)-gate low-ancilla bounded-span scan, proved gate-optimal in its model, and an O(Nlog⁡w)O(N\log w)O(Nlogw)-gate low-ancilla blocked construction when long-range gates are available; across all bounded-fan-in layouts, the unconditional gate lower bound is Ω(N)Ω(N)Ω(N). Composing rank-select with reversible transition and predicate-evaluation circuits gives an explicit polynomial-size coherent rollout oracle for finite-horizon planning problems satisfying these primitive assumptions. The resulting oracle satisfies the access model of the best-arm pipeline of Wang et al., yielding O~(k/ε)\widetilde{O}(\sqrt{k}/\varepsilon)O(k​/ε) coherent oracle calls against the standard classical Ω(k/ε2)Ω(k/\varepsilon^2)Ω(k/ε2) arm-pull lower bound. We give a bounded-influence lifting theorem that extends this lower-bound construction from a base configuration to an exponential family of configurations. We instantiate the construction on SIR epidemic intervention, with a stochastic placement-game sanity check, and machine-check the main results in Lean 4. Code and proofs: https://github.com/BinRoot/b01t/tree/main/demos/rollout.