Partial oracles quantum algorithm framework — Part I: Analysis of in-place operations

Fintan Bolton (Bradan Quantum) · arXiv:2604.21788 · submitted 2026-04-24 · score 8/10

Abstract

The partial oracles framework is a quantum search algorithm that has the potential to exceed the quadratic speedup of Grover's algorithm, up to a theoretical maximum of an exponential speedup. Until now, however, the framework has lacked an explicit method for constructing the operator that represents the search iteration. In this paper, we provide the missing construction, for the special case of an oracle function definable using only in-place operations (that is, where the calculated result of the oracle function can be read just from the qubits in the search index). The restriction to in-place operations means that the current work does not yet exhibit quantum advantage: oracle functions constructed using only in-place operations are always classically reversible. To demonstrate quantum advantage, it will be necessary to extend this construction method to include out-of-place operations (part II). As part of the construction of the search iteration operator, we define a new type of transform, the reciprocal transform, which is applied to the oracle function. We show that the reciprocal transform obeys a chain rule, which makes it possible to break down complex transforms into simple steps. To illustrate the practical application of this search method, we apply the reciprocal transform to elementary operations from the SHA-256 hash algorithm: addition modulo 2ⁿ, the Maj(a,b,c) function, the Ch(a,b,c) function, and the bit shift functions. We also introduce the QFrame python library, which is used to automate the construction of quantum circuits that represent reciprocal transforms.

Executive summary

This paper develops a Grover-style search framework — the partial oracles algorithm — in which the oracle outputs an n-bit vector f(x)∈{0,1}ⁿ and the solution is defined by f₀(x)=⋯=f_n−1(x)=0. The usual second Grover reflection is replaced by a new unitary built from a reciprocal transform R[f(x)] of the oracle. The paper gives the first explicit circuit construction of this operator for the restricted (but important) class of in-place oracles, proves a chain rule that composes complex oracles from primitives, and demonstrates the construction on SHA-256 primitives (modular addition, Maj, Ch, bit-rotations). The framework targets an eventual exponential speedup — Bolton previously (arXiv:2024 paper) showed exponential is the upper bound — but in-place alone is classically reversible, so this paper is Part I of a two-part programme; Part II will tackle out-of-place operations (e.g., integer multiplication) where quantum advantage is expected to emerge. For Yuan this is relevant because it sits in the same regime as Y4: Grover-family algorithms over structured feasible spaces, aiming at super-quadratic speedups.

Main contribution

The key object is the reciprocal transform: for a bijective oracle f^σ(x^μ), define the unitary R[f^σ(x^μ)] = (1/√(N_σN_μ)) Σ_κ,x,k e^{i2π(−κ·f(x)+x·k)} |κ⟩⟨k|. A single parallelized partial-oracle iteration H^⊗n R^†[f(x)] e^{iπ/2 Σ_ℓ κ_ℓ} R[f(x)] H^⊗n e^{iπ/2 Σ_ℓ f_ℓ(x)} takes the uniform superposition to the unique solution in one iteration (rather than Grover's √N iterations). The paper proves this explicitly by induction over partial-oracle conditions, proves a chain rule R[f∘g] = R[f]·R[g] that lets the reciprocal operator be composed piecewise, and instantiates circuits for the four primitives of SHA-256. The supporting Python library QFrame automates circuit synthesis from a classical Python specification of f.

Key theorems / lemmas / algorithms

Definition (reciprocal transform, §III.C, eq. 12): R[f^σ(x^μ)] = (1/√(N_σN_μ)) Σ_κ,x,k e^{i2π(−κ·f(x)+x·k)} |κ⟩⟨k| — represents the oracle in reciprocal (Hadamard/Fourier) space.
Partial oracle iteration (§III.D, eq. 17): Sequential form H^⊗n R^†[f] e^{iπ/2 κ_ℓ} R[f] H^⊗n e^{iπ/2 f_ℓ(x)} reduces the superposition over {x:f₀=…=f_ℓ−1=0} by one more condition at each step; parallelized form (eq. 18) solves the full problem in one shot.
Theorem 1 (chain rule, §III.G): R[f^σ(g^μ(x^ν))] = R[f^σ(y^μ)]·R[g^μ(x^ν)]. Proof via delta-function closure over the intermediate shape index.
Lemma (§IV.E, bit-shift reciprocal): For shift operators σ_μ of type (cyclic-rot-set)(bit-shift-set), the reciprocal transform decomposes into independent Walsh-wise phase factors.
SHA-256 primitives (§IV): Explicit reciprocal-transform circuits for (i) addition mod 2ⁿ, (ii) Maj(a,b,c), (iii) Ch(a,b,c), (iv) rotate-right/shift-right. Each is built from phase-gate layers plus Hadamard bracketing.
Simulation (§V): 4-bit "toy SHA" implementation — uniform superposition over 2²⁰ input states is collapsed to the target pre-image after a single partial-oracle iteration with 100% probability; equivalent Grover would require √(2²⁰)=1024 iterations.

Detailed walkthrough

Motivation (§II). Hoefler–Häner–Troyer (2023) and Stoudenmire–Waintal argued that Grover's quadratic speedup is unlikely to give real-world quantum advantage on practical problem sizes: when amortized over the cost of a single oracle query, the break-even threshold sits below <0.2 of a 16-bit floating-point op per query within a two-week budget even on an idealized 10k-logical-qubit machine. The partial-oracles framework is a direct response: build a search algorithm whose upper-bound speedup is exponential rather than quadratic, by enriching the oracle from f:{0,1}ⁿ→{0,1} to f:{0,1}ⁿ→{0,1}ⁿ.

Algorithmic geometry (§III.A–C). The author factors the standard Grover iteration as −H^⊗n(I−2|0⟩⟨0|)H^⊗n·(I−2|x_s⟩⟨x_s|) and identifies that the "reflection in reciprocal space" middle factor is the piece that must be replaced. The replacement must act independently on each κ_ℓ qubit in reciprocal space; the reciprocal transform R[f] constructed in eq. 12 is exactly the operator that diagonalizes the multi-bit oracle in κ-space. A related "bare" form B[f] (eq. 13) goes directly from direct to reciprocal space; R=BH^⊗n.

Inductive proof (§III.D). Define T_ℓ = {x : f₀(x)=…=f_ℓ−1(x)=0}. Starting from |T_ℓ⟩ = |T_ℓ|^−1/2 Σ_{x∈T_ℓ} |x⟩, apply e^{iπ/2 f_ℓ(x)}, then R[f]·H^⊗n. Using bijectivity, x=f⁻¹(y_n−1…y₀) and the amplitude factors cleanly per κ_j. For j<ℓ: κ_j stays uniform; for j=ℓ: κ_ℓ becomes (|0⟩−i|1⟩)/√2; for j>ℓ: κ_j=0 with certainty. Applying e^{iπ/2 κ_ℓ} flips the minus into a plus (returning κ_ℓ to uniform), then the adjoint H^⊗nR^†[f] completes the induction step, yielding |T_ℓ+1⟩. Parallelization (§III.E) applies the same logic to all ℓ simultaneously — since κ_ℓ qubits are independent, one iteration solves the full problem.

Chain rule (Theorem 1, §III.G). The proof collapses two nested reciprocal transforms by first identifying the shared intermediate shape-index (k'^μ↔κ^μ) via the Walsh delta function, then summing out κ^μ using δ(y^μ−g^μ(x^ν)). Net effect: R[f∘g]=R[f]·R[g], i.e., reciprocal-transform factorization mirrors function composition. This is the practical workhorse for SHA-style constructions: reciprocal transforms for primitive functions can be looked up, then composed to build the circuit for the full round function.

SHA primitives (§IV). For Maj(a,b,c)=a⊕((a⊕b)(a⊕c)), a 3-qubit circuit is given for the reciprocal gate using the identity 2·Maj(k_a,k_b,k_c)−1=⟨W_k,W_Maj⟩. The Ch(a,b,c)=(a∧b)⊕(¬a∧c) function yields an analogous gate. Modular addition mod 2ⁿ is handled by carry-chain decomposition whose reciprocal transform is built layer-wise via the chain rule. Bit-rotations have a particularly clean reciprocal structure: they commute with Hadamard transforms up to reindexing.

QFrame library and simulation (§V). The QFrame Python library (layered on Eclipse Qrisp) exposes a QFrameUInt abstract register with in-place +=, maj, ch, Rotr operators. Given a classical Python specification of g(x), QFrame auto-generates (i) the classical forward computation, (ii) the oracle circuit apply_oracle_gate, (iii) the reciprocal-oracle circuit apply_recip_oracle_gate. The toy SHA demonstrator uses 4-qubit registers a,b,c,d,W₀ through four rounds; the reported run inverts the function from a uniform superposition over 2²⁰ inputs to the preimage of a target 20-bit output in 1 iteration, 100% probability. The author notes this is not yet "hash inversion" because the problem constrains only the output, not both input and output — that would require out-of-place operations, deferred to Part II.

Scope of the restriction (§I, VI). In-place operations are those where the oracle can test only the index qubits (no out-of-place ancilla dependencies). Such oracles are classically reversible, which means they cannot actually deliver quantum advantage — an out-of-place function like integer multiplication is needed for Shor-class problems. Thus Part I is a foundation: it proves the framework works where the classical problem is easy; Part II must extend it to where the problem is hard.

Figures

Figure 1. Overview of partial-oracle iterations. At each iteration stage j, a search returns the index values x satisfying partial-oracle condition f_j(x)=0; the effect is cumulative, so the final state satisfies all conditions {f_j(x)=0}. Each of the n searches is implemented by a (modified) Grover-Long iteration; when f_j(x)=0 is satisfied by 50% of index states, a single iteration suffices.

Figure 2. First partial-oracle iteration: (a) initial equal superposition; (b) relative phase e^iπ/2 between matching and non-matching states; (c) horizontal/vertical decomposition; (d) reciprocal space after Walsh-Hadamard; (e) after applying the phase to the W₀(x) Walsh state; (f) transform back to direct space.

Figure 3. Second (and subsequent) partial-oracle iteration: (a) remaining states after iteration 1; (b) relative phase of e^iπ/2; (c) horizontal/vertical components; (d) reciprocal space after Walsh-Hadamard; (e) rearranged by the reciprocal transform; (f) phase on W₀(x); (g) rearranged by the adjoint reciprocal transform; (h) transform back to direct space.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y4 (Grover-based cardinality-constrained BO, arXiv:2603.14744) — strong method overlap. Y4 uses Grover search with O(√(C(n,k)/M)) rotations (quadratic speedup, structured feasible space). The partial-oracles framework generalizes Grover differently — by replacing single-bit with multi-bit oracles — and targets an exponential upper bound on speedup. The two approaches are complementary: Y4 exploits structure in the feasible set; Bolton exploits structure in the oracle output. A combined scheme (multi-bit oracle over a cardinality-constrained feasible space) is a natural research thread.
Y5 (GW via Gibbs states + Pauli sparsity, arXiv:2510.08292) — weak/indirect. Both papers target exponential-speedup pipelines over classical; Y5 achieves speedup via SDP relaxation + Pauli sparsity; Bolton via oracle-output structure. No direct technical overlap, but both sit in the "exponential advantage via structural exploitation" family.
Y1/Y2/Y3 — none. This is not a QAOA/variational paper.
Y6 — none. Foundations-testing paper, orthogonal.

Recommended action for Yuan

Read deeper; potentially cite in Y4 follow-ups. The reciprocal-transform idea is a generalization of the Grover reflection that Y4 already uses. Even if the current Part I doesn't demonstrate advantage, the reciprocal-transform + chain-rule machinery is a clean formalism for reasoning about multi-output oracles, which could inform discussions of oracle structure in cardinality-constrained settings.
Track Part II. The out-of-place extension is where actual quantum advantage would appear. If Part II materializes with a working construction, it becomes a required citation for any Grover-based optimization paper targeting super-quadratic improvement.
Low-priority for Y2/Y3. No immediate relevance to QAOA/portfolio work — skim only.