Partial oracles quantum algorithm framework Part I: Analysis of in-place operations
Fintan Bolton · 2026
Read Partial oracles quantum algorithm framework Part I: Analysis of in-place operations by Fintan Bolton (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21788.txt.
Introduction
Bolton supplies the missing construction for the partial oracles quantum search framework, for oracle functions built only from in-place operations. The framework could beat Grover's quadratic speedup, up to an exponential maximum, but it lacked an explicit search-iteration operator. The new construction defines a reciprocal transform applied to the oracle function, which obeys a chain rule for breaking complex transforms into simple steps. Applications cover SHA-256 operations, and a QFrame Python library automates circuit construction. In-place-only oracles remain classically reversible, so quantum advantage awaits part II.
Catalog record
| CREATOR | Fintan Bolton |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93359 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.21788
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Partial oracles quantum algorithm framework Part I: Analysis of in-place operations Fintan Bolton 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 2^{n} , the M a j ( a , b , c ) Maj(a,b,c) function, the C h ( a , b , c ) 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. I Introduction The number of fundamental quantum algorithms we have at our disposal is relatively small and many of these are tied to solving a specific problem (for example, Shor’s algorithm for prime number factorization). Among these algorithms, however, Grover’s search algorithm stands out for its unmatched flexibility, and many applications of quantum computing rely on it as a fundamental building block to deliver quantum advantage. But the quadratic computational speedup offered by Grover’s algorithm (locating a solution in a search space of size N using only \mathcal{O}(\sqrt{N}) oracle queries) might not actually be of practical use in the real world. In a recent paper Hoefler et al. 2023 , Hoefler, Häner and Troyer made a performance comparison between a contemporary GPU processor (state-of-the art as of 2023) and a highly optimistic future projection of a quantum processor with 10,000 error-corrected qubits. Taking a two-week computation time as the cutoff to define a limit on the size of the problem considered, they found that a quadratic speedup was of no practical use (at the threshhold of quantum advantage, an oracle function would be limited to performing less than 0.2 of a single 16-bit floating point operation). Stoudenmire and Waintal Stoudenmire and Waintal 2023 ; Stoudenmire and Waintal 2024 have also made a detailed study of the practicality of Grover’s algorithm and come to similar conclusions. Both of these studies underscore the importance of developing quantum algorithms that can deliver an exponential speedup, as this is the class of algorithms that can be relied upon to deliver a decisive quantum advantage. The partial oracles algorithm (still under development) is a line of research that was devised specifically to tackle the limitations of Grover search. In a previous paper Bolton 2024 , we demonstrated that the theoretical upper limit (not necessarily achievable) on the speedup provided by the partial oracles approach is exponential. This does not contradict the well-known result that Grover’s search is optimal Galindo and Martin-Delgado 2000 , because the partial oracles approach starts from a different premise: instead of a single-bit oracle function f(x):\{0,1\}^{n}\rightarrow\{0,1\} which returns 0 for the solution value x_{s} (zero-matching convention), the partial oracles algorithm employs a multi-bit oracle function f(x):\{0,1\}^{n}\rightarrow\{0,1\}^{n} which indicates a full match only if every returned bit is zero—-that is, f_{0}(x)=0,f_{1}(x)=0,\ldots,f_{n-1}(x)=0 indicates the solution has been found (assuming a zero-matching convention). The particular difficulty faced by the partial oracles approach, however, is that the the second Grover operator can no longer be used to perform intermediate iterations of the search and a new type of operator is required. Consider how the Grover operators are conventionally defined. Given an n -qubit index register \ket{x}=\ket{x_{n-1}\ldots x_{0}} , we define the initial state \ket{S}=(1/\sqrt{2^{n}})\sum_{x}\ket{x} and the sought-after solution state \ket{x_{s}} that satisfies f(x_{s})=0 . We can then define the first Grover operator G^{I}=\mathbf{I}-2\ket{x_{s}}\bra{x_{s}} as a reflection in the hyperplane perpendicular to \ket{x_{s}} ; and the second Grover operator G^{II}=\mathbf{I}-2\ket{S}\bra{S} as a reflection in the hyperplane perpendicular to the initial state \ket{S} . A single Grover iteration is then defined as the product G^{II}G^{I} of these two reflection operators: -\big(\mathbf{I}-2\ket{S}\bra{S}\big)\,\,\big(\mathbf{I}-2\ket{x_{s}}\bra{x_{s}}\big) (1) When we consider that the initial state \ket{S} can be written as H^{\otimes n}\,\ket{0} (applying a Walsh-Hadamard transformation to the n -qubit zero state) and the fact that H^{\otimes n} is its own inverse, we can also write the Grover iteration in the form: -\underbrace{H^{\otimes n}\,\big(\mathbf{I}-2\ket{0}\bra{0}\big)\,H^{\otimes n}}_{\text{2\textsuperscript{nd} Grover operator}}\,\,\underbrace{\big(\mathbf{I}-2\ket{x_{s}}\bra{x_{s}}\big)}_{\textrm{1\textsuperscript{st} Grover operator}} (2) From this perspective, we can break the 2 nd Grover operator into three parts: 1. The Walsh-Hadamard transformation H^{\otimes n} maps states from direct space \ket{x} to reciprocal space \ket{k} , where the basis vectors \ket{k} represent the Walsh functions \{W_{k}(x)\} for k=0\ldots(2^{n}-1) . 2. In reciprocal space, the operator performs a reflection in the hyperplane perpendicular to the \ket{k=0} reciprocal state (which represents the W_{0}(x) Walsh function). 3. The Walsh-Hadamard transformation H^{\otimes n} maps states from reciprocal space \ket{k} back to direct space \ket{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 two H^{\otimes n} operators) that implements the appropriate type of search iteration for the partial oracles approach. The requisite operator is constructed by performing what we call a reciprocal transform R[f^{\sigma}(x^{\mu})] of the oracle function (section III.3 ). The corresponding partial oracle iteration operator is then given by equation 20 (or in parallelized form, by equation 24 ). This is the key result of this paper. Note, however, that this result has so far only been proved for in-place operations, not out-of-place operations. Given an n -qubit index register x , the distinction between in-place operations and out-of-place operations can be described, as follows: • In-place operations —the oracle function can be computed in such a way that it is only necessary to test qubits x_{n-1},\ldots,x_{0} from the index register x when applying a phase marker. • Out-of-place operations —the oracle function must be computed using out-of-place qubits (that is, not part of the index x ) in such a way that it is necessary to test out-of-place qubits when applying a phase marker. The difference between these two cases is stark: an oracle function calculated using in-place operations is always classically reversible; whereas reversing an oracle function calculated using out-of-place operations can be very non-trivial and hard to compute. A typical example of an out-of-place operation is integer multiplication. Given two