arxiv: 2604.21788 · v1 · submitted 2026-04-23 · 🪐 quant-ph

Recognition: unknown

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

Fintan M. Bolton

Authors on Pith no claims yet

Pith reviewed 2026-05-09 22:39 UTC · model grok-4.3

classification 🪐 quant-ph

keywords operationsfunctionquantumsearchalgorithmconstructionin-placeoracle

0 comments

The pith

The paper gives a construction for the partial-oracles search iteration operator restricted to in-place operations via a new reciprocal transform applied to SHA-256 building blocks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Quantum search algorithms like Grover's give a quadratic speedup over classical search. The partial oracles framework aims for something stronger, potentially exponential, by using a different kind of oracle. Until this work, no explicit way existed to build the operator that performs one full search iteration. The authors supply that construction when the oracle is made only from in-place operations, meaning the result can be read directly from the same qubits that hold the search index. They define a reciprocal transform that converts the oracle function into the needed operator and prove it obeys a chain rule so complex functions can be assembled from simpler pieces. As a demonstration they apply the method to the addition, majority, choice, and shift operations inside SHA-256. Because every in-place operation is classically reversible, the resulting circuits can be simulated classically and therefore do not yet show quantum advantage; that step is reserved for part II which will handle out-of-place operations.

Core claim

we provide the missing construction, for the special case of an oracle function definable using only in-place operations

Load-bearing premise

That the reciprocal transform, once defined for in-place operations, can be extended without loss of the claimed speedup properties to out-of-place operations in part II (the paper states this extension is required for quantum advantage but does not yet demonstrate it).

Figures

Figures reproduced from arXiv: 2604.21788 by Fintan M. Bolton.

**Figure 2.** Figure 2: FIG. 2. First partial oracle iteration showing: (a) the initial equal superposition state; (b) index [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3. Second (and subsequent) partial oracle iteration: (a) index states remaining after the [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4. Circuit for the majority function [PITH_FULL_IMAGE:figures/full_fig_p027_4.png] view at source ↗

**Figure 5.** Figure 5: FIG. 5. Circuit for the [PITH_FULL_IMAGE:figures/full_fig_p028_5.png] view at source ↗

**Figure 6.** Figure 6: FIG. 6. Reciprocal majority gate [PITH_FULL_IMAGE:figures/full_fig_p028_6.png] view at source ↗

**Figure 7.** Figure 7: shows the corresponding circuit for the choose function, which requires just two gates to implement. a b c f0 f1 f2 FIG. 7. Circuit for the choose function Ch(a, b, c) The inverse of the choose oracle function is given by: a = f0 (46) b = f2 + (1 − f0)f1 (47) c = f2 + f0f1 (48) From equation 17, the reciprocal transform of the choose gate is given by: R[f(a, b, c)] = 1 2 3 X κ X a,b,c X k e iπ (−(κ0f0+κ1f1… view at source ↗

**Figure 8.** Figure 8: FIG. 8. Reciprocal choose gate [PITH_FULL_IMAGE:figures/full_fig_p030_8.png] view at source ↗

**Figure 9.** Figure 9: FIG. 9. Sum gate [PITH_FULL_IMAGE:figures/full_fig_p031_9.png] view at source ↗

**Figure 10.** Figure 10: FIG. 10. Modulo adder gate [PITH_FULL_IMAGE:figures/full_fig_p031_10.png] view at source ↗

**Figure 11.** Figure 11: FIG. 11. Reciprocal sum gate [PITH_FULL_IMAGE:figures/full_fig_p033_11.png] view at source ↗

**Figure 12.** Figure 12: FIG. 12. Reciprocal modulo adder gate [PITH_FULL_IMAGE:figures/full_fig_p033_12.png] view at source ↗

**Figure 13.** Figure 13: FIG. 13. Reciprocal bit shifter gate for [PITH_FULL_IMAGE:figures/full_fig_p038_13.png] view at source ↗

read the original 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^n$, 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Bolton gives an explicit construction for the search iteration operator in the partial-oracles framework, but only for the reversible in-place case, so any exponential speedup remains deferred to part II.

read the letter

The paper's main contribution is the explicit construction of the iteration operator for oracles built only from in-place operations, using a new reciprocal transform that obeys a chain rule. This fills the gap the abstract mentions, and the author demonstrates it on concrete SHA-256 building blocks: modular addition, Maj, Ch, and bit shifts. The QFrame library that automates the resulting circuits is a practical addition; it turns the transform steps into inspectable quantum circuits rather than leaving them as diagrams on paper. Those pieces are useful for anyone who needs to compose reversible oracles systematically. The chain-rule property is the part that could make larger constructions tractable, and applying it to hash primitives shows the method is not purely abstract. The limitation is stated plainly: in-place operations are classically reversible, so this version cannot produce quantum advantage on its own. The speedup claim is postponed until out-of-place operations are handled in the follow-up paper. That deferral is honest, but it means the current work is preparatory rather than a completed algorithm. Without the full equations and circuit diagrams in front of me, I cannot check whether the reciprocal transform introduces hidden costs or whether the chain rule survives every composition the author intends. The SHA-256 examples are illustrative; they do not include a full search run or resource counts that would let a reader judge scaling. This paper is for people already working on quantum search variants or on reversible implementations of cryptographic functions. A reader who wants to build on the framework will find the construction and the library worth examining, but anyone looking for a demonstrated speedup will need part II. I would send it to referees. The explicit operator and the automation tool are concrete enough to merit detailed review, even if the larger claims are still conditional.

Referee Report

0 major / 3 minor

Summary. The paper claims to supply the missing explicit construction of the search iteration operator for the partial oracles quantum search framework when the oracle is restricted to in-place operations. It does so by defining a reciprocal transform on the oracle function, establishing that this transform obeys a chain rule, and using the rule to decompose complex oracles into elementary steps. The construction is illustrated on the addition-mod-2^n, Maj, Ch, and bit-shift primitives from SHA-256; a Python library (QFrame) is supplied to automate the resulting quantum circuits. The authors explicitly note that the in-place restriction keeps the oracles classically reversible and therefore defers any claim of quantum advantage to a planned Part II that will treat out-of-place operations.

Significance. If the reciprocal-transform construction and its chain-rule property are free of gaps, the work supplies a concrete, decomposable method for building the iteration operator of a search framework that the authors position as capable of super-quadratic (potentially exponential) speedup. The provision of an automated circuit-generation library and the explicit restriction of scope to reversible in-place functions are positive for reproducibility and for guiding future extensions. Immediate impact is limited by the absence of quantum advantage in the present part, but the framework could become a useful building block once the out-of-place case is completed.

minor comments (3)

The abstract states that the reciprocal transform 'obeys a chain rule' but does not indicate whether the proof is by direct verification on the elementary gates or by induction on circuit depth; a one-sentence pointer to the relevant lemma or section would help readers locate the argument.
The description of the QFrame library mentions automation of circuit construction but does not state whether the library outputs OpenQASM, Qiskit objects, or another standard format; adding this detail would improve usability for readers who wish to reproduce the SHA-256 examples.
Figure captions (or the text surrounding the SHA-256 examples) should explicitly note the qubit count and depth of the generated circuits so that the overhead of the reciprocal-transform construction can be compared with a direct Grover oracle implementation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, including its scope, the reciprocal-transform construction, the chain-rule property, the SHA-256 illustrations, and the explicit restriction to in-place operations. We also appreciate the recommendation for minor revision and the constructive framing of the work's potential once Part II is completed.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central construction rests on standard quantum-circuit axioms plus the newly introduced reciprocal transform; no free parameters or invented physical entities are visible in the abstract.

axioms (1)

standard math Standard axioms of quantum computation (unitary operators on qubits, reversible classical functions embeddable as quantum circuits)
Invoked implicitly when treating in-place operations as quantum circuits.

invented entities (2)

reciprocal transform no independent evidence
purpose: Converts an in-place oracle function into the search-iteration operator
Newly defined operator whose chain rule is claimed to allow decomposition of complex functions.
partial oracles framework no independent evidence
purpose: Quantum search algorithm claimed to exceed Grover quadratic speedup
The overarching framework whose iteration operator is constructed here.

pith-pipeline@v0.9.0 · 5568 in / 1446 out tokens · 24063 ms · 2026-05-09T22:39:37.133974+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

42 extracted references · 5 canonical work pages

[1]

(2 n −1)

The Walsh-Hadamard transformationH ⊗n maps states from direct space|x⟩to recip- rocal space|k⟩, where the basis vectors|k⟩represent the Walsh functions{W k(x)}for k= 0. . .(2 n −1)
[2]

In reciprocal space, the operator performs a reflection in the hyperplane perpendicular to the|k= 0⟩reciprocal state (which represents theW 0(x) Walsh function)
[3]

As already noted, we have found that the second Grover operator cannot be used in the context of the partial oracles approach

The Walsh-Hadamard transformationH ⊗n maps states from reciprocal space|k⟩back to direct space|x⟩. As already noted, we have found that the second Grover operator cannot be used in the context of the partial oracles approach. But it turns out that it is possible to define an operator in reciprocal space (sandwiched between the twoH ⊗n operators) that impl...
[4]

The quantum system is initialized in an equal superposition state|Ψ⟩= (1/N 1/2)P x |x⟩, where each|x⟩state has the amplitude +1/ √ N. 5
[5]

The first Grover operator uses the oracle functionf(x) to identify the solution state |xs⟩and marks it by applying the phase exp(iπ) =−1
[6]

In reciprocal space, the basis states are given by the Walsh functionsWk(x) = exp(i2π k·x), where we definek·x= (1/2) Pn−1 j=1 kjxj

A Walsh-Hadamard transformation is applied to the state|Ψ⟩ 7→H ⊗n |Ψ⟩, which transforms the state into reciprocal space. In reciprocal space, the basis states are given by the Walsh functionsWk(x) = exp(i2π k·x), where we definek·x= (1/2) Pn−1 j=1 kjxj. Most of the state’s amplitude is concentrated in the zero Walsh stateW 0(x) = const, while a small part...
[7]

The second Grover operator flips the zero Walsh stateW 0(x) (for example, using a multi-controlled gate to detect the all-zero state, and an ancillary phase oracle to flip the phase), so that its amplitude is negative and the components it represents are oriented parallel to the negative amplitude atx s
[8]

The (inverse) Walsh-Hadamard transformation is applied to the state, transforming from reciprocal space back to direct space. After this transformation, the amplitude from the zero Walsh function and the solution amplitude add constructively atx s, so that the ampltitude atx s increases from 1/ √ Nto approximately 2/ √ N
[9]

In the partial oracle approach [4], the single-bit oracle functionf(x) :{0,1} n → {0,1}is replaced by a multi-bit oracle functionf(x) :{0,1} n → {0,1} n

By repeating this procedure iteratively, the amplitude atx s increases—at first linearly and then more slowly—until all of the amplitude is in the|x s⟩state, after approxi- mately √ Niterations. In the partial oracle approach [4], the single-bit oracle functionf(x) :{0,1} n → {0,1}is replaced by a multi-bit oracle functionf(x) :{0,1} n → {0,1} n. Instead ...
[10]

We then divide thenqubits of the raw registerxintorregisters of sizes{m j}r j=1., wherem 1 +m 2 +· · ·m r =n

Registers in direct space The raw registerx∈ {0,1} n refers to the totality of qubits in the search index (but does not include, for example, any ancillary qubits that might be needed by circuit implementa- tions). We then divide thenqubits of the raw registerxintorregisters of sizes{m j}r j=1., wherem 1 +m 2 +· · ·m r =n. To identify each of therregister...
[11]

Given thereciprocal raw registerk, we can define the correspondingreciprocal qubit vectork µ: kµ = (k(1), k(2),

Registers in reciprocal space By analogy to the notation in direct space, we can also define the corresponding reg- ister notation in reciprocal space. Given thereciprocal raw registerk, we can define the correspondingreciprocal qubit vectork µ: kµ = (k(1), k(2), . . . , k(r)) With the corresponding qubit shape: µ= (m 1, m2, . . . , mr)
[12]

r, combining the qubit indices into a single range from 0

Hadamard-style dot product We define the Hadamard-style dot product between a qubit vectorx µ and a reciprocal qubit vectork µ as: 15 kµ ·x µ = 1 2 m1−1M ℓ1=0 k(1) ℓ1 x(1) ℓ1 ! ⊕ · · · ⊕ 1 2 mr−1M ℓr=0 k(r) ℓr x(r) ℓr ! (8) = 1 2 rM j=1 rM ℓj =1 k(j) ℓj x(j) ℓj (9) = 1 2 n−1M i=0 kixi (10) Equation 10 uses the indices of the underlying raw vectors, which ...
[13]

Hadamard transform with qubit shapes With the help of the dot product notation from the previous section, we can write the Hadamard transform for qubit vectors as: Hkµxµ = 1p Nµ X kµ X xµ e−i2π kµ·xµ |kµ⟩⟨xµ|(11) WhereN µ = 2 m1 . . .2 mr = 2 n and the sums overx µ andk µ use the following compact notation: X xµ = 2m1 −1X x(1)=0 · · · 2mr −1X x(r)=0 (12) ...
[14]

Reciprocal transform definition We are now ready to define the reciprocal transform, which plays a central role in the partial oracles algorithm

Delta function Note that, in the usual way, we can define a delta function by summing over the complete Walsh-Hadamard basis, that is: δxµ,0 = 1 Nµ X kµ e−i2π kµ·xµ (16) This can easily be proved for the case of the Hadamard-style dot product, as follows: 1 Nµ X kµ e−i2π kµ·xµ =  1 2 1X kn−1=0 e−iπ kn−1xn−1   · · · 1 2 1X k0=0 e−iπ k0x0 ! = δxn−1,0 · ...
[15]

Before you start, calculate the reciprocal transformR[f(x)] of the oracle function and figure out the quantum circuits needed to implement this operator (examples are given in section IV). 22
[16]

Initialize the index registerx∈ {0,1} n in a uniform superposition state, by applying the Walsh-Hadamard transformation: H ⊗n |0⟩
[17]

Calculate the value of the multi-qubit oracle function{f j(x)}n−1 0 (which typically requires using ancillary qubits, in addition to the index qubits)
[18]

In order to apply thee +i π 2 Pn−1 ℓ=0 fℓ(x) operator, execute the phase gate (S gate) on all of the oracle qubits{f j(x)}n−1 0 (that is, the qubits that contain the result of calculating the multi-qubit oracle)
[19]

Uncompute the multi-qubit oracle function{f j(x)}n−1 0
[20]

Map the index qubits to reciprocal space, by applying a Walsh-Hadamard transfor- mationH ⊗n
[21]

Apply the circuit that implements the reciprocal operatorR[f(x)] (using the circuit worked out in step 1)
[22]

In order to apply thee +i π 2 Pn−1 ℓ=0 κℓ operator, execute the phase gate (S gate) on all of the reciprocal space qubits{κ j}n−1 0
[23]

Uncompute the reciprocal operator, by applying its adjoint operatorR †[f(x)]
[24]

Map the index qubits from reciprocal space back to direct space, by applying a Walsh- Hadamard transformationH ⊗n to the index qubits
[25]

Measure the qubits from the index register to obtain the solutionx s that satisfies the oracle constraintf(x s) = 0. G. Chain rule theorem The reciprocal transform obeys a chain rule, which provides a powerful tool for decom- posing complex transforms. Theorem 1(Chain rule).Given the bijective nested functionf σ(gµ(xν)), the reciprocal transform of this n...
[26]

Hoefler, T

T. Hoefler, T. Haener, and M. Troyer, Disentangling hype from practicality: On realistically achieving quantum advantage (2023), arXiv:2307.00523 [quant-ph]

work page arXiv 2023
[27]

E. M. Stoudenmire and X. Waintal, Grover’s algorithm offers no quantum advantage, arXiv preprint arXiv.2303.11317 (2023)

work page arXiv 2023
[28]

E. M. Stoudenmire and X. Waintal, Opening the black box inside grover’s algorithm, Phys. Rev. X14, 041029 (2024)

2024
[29]

F. M. Bolton, Accelerated quantum search using partial oracles and grover’s algorithm (2024), arXiv:2403.13035 [quant-ph]

work page arXiv 2024
[30]

Galindo and M

A. Galindo and M. A. Martin-Delgado, Family of grover’s quantum-searching algorithms, Physical Review A62, 062303 (2000)

2000
[31]

L. K. Grover, A fast quantum mechanical algorithm for database search, inProceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96 (Association for Computing Machinery, New York, NY, USA, 1996) p. 212–219

1996
[32]

L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett.79, 325 (1997)

1997
[33]

G. L. Long, Grover algorithm with zero theoretical failure rate, Physical Review A64, 022307 (2001)

2001
[34]

National Institute of Standards and Technology, Secure Hash Standard (2015)

2015
[35]

S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, A new quantum ripple-carry addition circuit (2004), arXiv:quant-ph/0410184 [quant-ph]

work page Pith review arXiv 2004
[36]

R. L. Rivest, The invertibility of the XOR of rotations of a binary word, International Journal of Computer Mathematics88, 281 (2011), https://doi.org/10.1080/00207161003596708

work page doi:10.1080/00207161003596708 2011
[37]

S. S. Thomsen,Cryptographic Hash Functions, Phd thesis, Technical University of Denmark (2008)

2008
[38]

Peters, Reverse SHA-256 sigma0 function within complexity of O(n)? (2021)

O. Peters, Reverse SHA-256 sigma0 function within complexity of O(n)? (2021)

2021
[39]

Microsoft Research, Z3 prover,https://github.com/Z3Prover/z3(2026)

2026
[40]

Bolton, QFrame examples,https://github.com/bradan-quantum/ qframe-examples/(2026)

F. Bolton, QFrame examples,https://github.com/bradan-quantum/ qframe-examples/(2026)

2026
[41]

Bolton, QFrame source code,https://github.com/bradan-quantum/qframe/ 49 (2026)

F. Bolton, QFrame source code,https://github.com/bradan-quantum/qframe/ 49 (2026)

2026
[42]

Bolton, QFrame package,https://pypi.org/project/qframe/(2026)

F. Bolton, QFrame package,https://pypi.org/project/qframe/(2026). 50

2026