© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2605.21380

Modeling and Resource Optimization for Quantum Oracles

Zhihang Li, Bo Zhao, Chuanbing Han, Jie Zhao, Jinchen Xu, Guoqiang Shu, Yimin Gao, Woji He, Zheng Shan

quant-phSubmitted May 20, 2026• Announced May 21, 2026• 0 citations• Revised Aug 30, 2026 (v2)

v1 · May 20, 2026 v2 · Aug 30, 2026

Abstract

Quantum oracles are fundamental building blocks of many quantum algorithms, and their resource consumption directly affects performance, yet structured description and complexity analysis for their composition are still lacking. In this paper, we introduce the Framework for Oracle Recursion Modeling (FORM), a unified formal abstraction of multi-function composition in quantum oracles: it provides a structured description of the composition layer, makes its gate complexity exactly computable, and turns oracle design into an optimizable tree-construction problem. Based on this model, we propose the ShallowGrow algorithm, which constructs an oracle structure under a given ancilla budget and provably minimizes the number of function evaluations. On Boolean quadratic equation systems, ShallowGrow reduces Qiskit-measured circuit depth by 54.1% on average relative to the state-of-the-art W-cycle construction, with consistent reductions on the EPFL and ISCAS85 combinational logic networks under scarce ancilla budgets. Furthermore, pebbling-based syntheses trade space against time within the logic network of a function; ShallowGrow extends this trade-off across functions, and integrated with their published circuits it reduces the ancillary qubits of a complete oracle from one per constraint function to logarithmically many. With half as many ancillas as constraint functions, the T-count falls by a factor of 7.9 to 32 relative to the W-cycle-based construction.

Comments: v2: substantial revision. Renamed HRSE model to FORM (Framework for Oracle Recursion Modeling) and ASDT algorithm to ShallowGrow. Expanded experiments to EPFL and ISCAS85 combinational benchmarks and to complete oracle construction with pebbling-based leaf syntheses (LHRS, Zhang et al.). Rewrote Section V with new tables and figures. 14 pages, 6 figures, 5 tables

Related papers

A Divide-And-Conquer Pebbling Strategy for Oracle Synthesis in Quantum Computing

Kezhen Zhang, Riling Li, Mingsheng Ying

Quantum oracles are quantum circuits that implement classical Boolean functions, frequently used as independent black boxes in quantum algorithm design. The hierarchical reversible logic synthesis approach, a scalable method for large-scale oracle synthesis, relies on ancilla qubits to store intermediate results. The sequence in which these results are computed and uncomputed, governed by the reversible pebble game, greatly affects both qubit usage and circuit gate count. This paper introduces a novel divide-and-conquer pebbling strategy that reduces qubit count while maintaining a reasonable circuit gate count. Experimental results show up to a 90% reduction in qubits compared to the most commonly-used strategy, with an average increase of 3 to 4 times in quantum operations, all achieved within a reasonable runtime. In qubit-constrained tasks, our method achieves over 90% reduction in T-count. Additionally, we have incorporated our strategy into the hierarchical synthesis method and implemented it as a potential synthesizer for Qiskit, with experiments demonstrating that it outperforms the default synthesizer. The proposed approach shows promise in optimizing both qubit usage and circuit gate count for large-scale oracle synthesis problems.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 15, 2025•0 citations

From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the FORM Model

Zhihang Li, Wei Zi, Shuai Yang +7 more

Quantum oracles play a fundamental role in many quantum algorithms, such as Grover's search and quantum counting. In oracle synthesis, reducing the circuit depth under a limited number of ancilla qubits is essential, given the constraints of current quantum devices. However, for satisfiability oracles (SAT-oracles) under a limited ancilla budget, existing synthesis methods fail to fully exploit clause-level parallelism, leading to deep circuits. In practice, evaluating clauses in parallel can quickly exhaust the ancilla budget. To address this issue, we introduce the Clustered Synthesis Tree (CST), a depth-oriented SAT-oracle synthesis framework that exploits clause-level parallelism while respecting the ancilla budget. CST leverages a recursive synthesis tree as the backbone for scheduling clause evaluations and groups its clause leaves into clusters, whose clauses are evaluated in parallel by a reversible oracle called ClausePack. To form the clusters, CST introduces a polynomial-time heuristic called SeedGrow for the NP-hard clause-grouping problem, and the resulting tree is compiled into an executable circuit by CST-Map. Compared with the depth-oriented pAND baseline, CST can reduce the circuit depth by an average of 10.2x and 8.8x-11.0x on SATLIB and random 4-CNF benchmarks, respectively, under the same ancilla budgets, while also outperforming the width-oriented pAND, clause-storing, and qSAT baselines.

quant-pharXiv:2607.11401•Jul 14, 2026•0 citations

Nearly optimal quantum circuits for Boolean oracles

Junhong Nie, Wei Zi

Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size $b$: with $1\le m\leΘ\left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)$, depth $\mathcal{O}\left(\frac{b2^n}{n+m}\right)$; partial Boolean functions of effective support size $d$ and output size $b$: with $Θ\left(\log d\right)\le m\le Θ\left(d\right)$ ancilla, size $\mathcal{O}\left(n\log d+bd\right)$, depth $\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)$; sparse Boolean functions of true input size $d$: with $Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)$ ancilla, size $\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)$, depth $\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)$. All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.

quant-pharXiv:2607.28402•Jul 31, 2026•0 citations

A New Perspective of Constructing Resource-Efficient Data-Lookup Quantum Oracles

Mingfei Yu, Mathias Soeken, Giovanni De Micheli

Quantum oracles are essential components in quantum algorithms, enabling the efficient evaluation of Boolean functions. This paper presents a novel approach to constructing resource-efficient data-lookup quantum oracles for fault-tolerant quantum computing (FTQC) systems. By leveraging the algebraic normal form (ANF) of Boolean functions, rather than the truth tables used in existing approaches, we achieve a provable$\mathcal{O}(n)$reduction in the minimum Toffoli gate count - a key cost metric in FTQC - for constructing an$n$-variable data-lookup oracle. Additionally, exploiting ANF product terms allows for the exploration of space-time trade-offs, enabling the design of data-lookup oracles with distinct resource requirements that can adapt to varying system constraints - flexibility that current methods do not offer. Based on the target quantum system's requirements, our approach offers the ability to tailor oracle designs to minimize either Toffoli count and depth, or ancillary qubit usage.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit

Shuai Yang, Wei Zi, Bujiao Wu +3 more

One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of an$m$-clause SAT-oracle necessitates$2m-1$ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle to$\tilde {O}(\log m)$using$m$ancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.

arXiv:2101.05430•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 19, 2023•3 citations

The Role of Multiplicative Complexity in Compiling Low $T$-count Oracle Circuits

Giulia Meuli, Mathias Soeken, Earl T. Campbell +2 more

We present a constructive method to create quantum circuits that implement oracles |x〉|y〉|0〉k→|x〉|y⊕f(x)〉|0〉kfor n-variable Boolean functions f with low T-count. In our method f is given as a 2-regular Boolean logic network over the gate basis {∧, ⊕, 1}. Our construction leads to circuits with a T-count that is at most four times the number of AND nodes in the network. In addition, we propose a SAT-based method that allows us to trade qubits for T gates, and explore the space/complexity trade-off of quantum circuits. Our constructive method suggests a new upper bound for the number of T gates and ancilla qubits based on the multiplicative complexity c∧(f) of the oracle function f, which is the minimum number of AND gates that is required to realize f over the gate basis {∧, ⊕, 1}. There exists a quantum circuit computing f with at most 4c∧(f)T gates using k=c∧(f) ancillae. Results known for the multiplicative complexity of Boolean functions can be transferred. We verify our method by comparing it to different state-of-the-art compilers. Finally, we present our synthesis results for Boolean functions used in quantum cryptoanalysis.

arXiv:1908.01609•Nov 1, 2019•29 citations

Quantum oracles are fundamental building blocks of many quantum algorithms, and their resource consumption directly affects performance, yet structured description and complexity analysis for their composition are still lacking. In this paper, we introduce the Framework for Oracle Recursion Modeling (FORM), a unified formal abstraction of multi-function composition in quantum oracles: it provides a structured description of the composition layer, makes its gate complexity exactly computable, and turns oracle design into an optimizable tree-construction problem. Based on this model, we propose the ShallowGrow algorithm, which constructs an oracle structure under a given ancilla budget and provably minimizes the number of function evaluations. On Boolean quadratic equation systems, ShallowGrow reduces Qiskit-measured circuit depth by 54.1% on average relative to the state-of-the-art W-cycle construction, with consistent reductions on the EPFL and ISCAS85 combinational logic networks under scarce ancilla budgets. Furthermore, pebbling-based syntheses trade space against time within the logic network of a function; ShallowGrow extends this trade-off across functions, and integrated with their published circuits it reduces the ancillary qubits of a complete oracle from one per constraint function to logarithmically many. With half as many ancillas as constraint functions, the T-count falls by a factor of 7.9 to 32 relative to the W-cycle-based construction.

Quantum oracles are quantum circuits that implement classical Boolean functions, frequently used as independent black boxes in quantum algorithm design. The hierarchical reversible logic synthesis approach, a scalable method for large-scale oracle synthesis, relies on ancilla qubits to store intermediate results. The sequence in which these results are computed and uncomputed, governed by the reversible pebble game, greatly affects both qubit usage and circuit gate count. This paper introduces a novel divide-and-conquer pebbling strategy that reduces qubit count while maintaining a reasonable circuit gate count. Experimental results show up to a 90% reduction in qubits compared to the most commonly-used strategy, with an average increase of 3 to 4 times in quantum operations, all achieved within a reasonable runtime. In qubit-constrained tasks, our method achieves over 90% reduction in T-count. Additionally, we have incorporated our strategy into the hierarchical synthesis method and implemented it as a potential synthesizer for Qiskit, with experiments demonstrating that it outperforms the default synthesizer. The proposed approach shows promise in optimizing both qubit usage and circuit gate count for large-scale oracle synthesis problems.

Quantum oracles play a fundamental role in many quantum algorithms, such as Grover's search and quantum counting. In oracle synthesis, reducing the circuit depth under a limited number of ancilla qubits is essential, given the constraints of current quantum devices. However, for satisfiability oracles (SAT-oracles) under a limited ancilla budget, existing synthesis methods fail to fully exploit clause-level parallelism, leading to deep circuits. In practice, evaluating clauses in parallel can quickly exhaust the ancilla budget. To address this issue, we introduce the Clustered Synthesis Tree (CST), a depth-oriented SAT-oracle synthesis framework that exploits clause-level parallelism while respecting the ancilla budget. CST leverages a recursive synthesis tree as the backbone for scheduling clause evaluations and groups its clause leaves into clusters, whose clauses are evaluated in parallel by a reversible oracle called ClausePack. To form the clusters, CST introduces a polynomial-time heuristic called SeedGrow for the NP-hard clause-grouping problem, and the resulting tree is compiled into an executable circuit by CST-Map. Compared with the depth-oriented pAND baseline, CST can reduce the circuit depth by an average of 10.2x and 8.8x-11.0x on SATLIB and random 4-CNF benchmarks, respectively, under the same ancilla budgets, while also outperforming the width-oriented pAND, clause-storing, and qSAT baselines.

Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size

b

: with

1\le m\leΘ\left(\frac{2^n}{n}\right)

ancilla, size

\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)

, depth

\mathcal{O}\left(\frac{b2^n}{n+m}\right)

; partial Boolean functions of effective support size

d

and output size

b

: with

Θ\left(\log d\right)\le m\le Θ\left(d\right)

ancilla, size

\mathcal{O}\left(n\log d+bd\right)

, depth

\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)

; sparse Boolean functions of true input size

d

: with

Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)

ancilla, size

\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)

, depth

\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)

. All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.

Quantum oracles are essential components in quantum algorithms, enabling the efficient evaluation of Boolean functions. This paper presents a novel approach to constructing resource-efficient data-lookup quantum oracles for fault-tolerant quantum computing (FTQC) systems. By leveraging the algebraic normal form (ANF) of Boolean functions, rather than the truth tables used in existing approaches, we achieve a provable

\mathcal{O}(n)

reduction in the minimum Toffoli gate count - a key cost metric in FTQC - for constructing an

n

-variable data-lookup oracle. Additionally, exploiting ANF product terms allows for the exploration of space-time trade-offs, enabling the design of data-lookup oracles with distinct resource requirements that can adapt to varying system constraints - flexibility that current methods do not offer. Based on the target quantum system's requirements, our approach offers the ability to tailor oracle designs to minimize either Toffoli count and depth, or ancillary qubit usage.

One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of an

m

-clause SAT-oracle necessitates

2m-1

ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle to

\tilde {O}(\log m)

using

m

ancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.

The Role of Multiplicative Complexity in Compiling Low

T

-count Oracle Circuits

We present a constructive method to create quantum circuits that implement oracles |x〉|y〉|0〉k→|x〉|y⊕f(x)〉|0〉kfor n-variable Boolean functions f with low T-count. In our method f is given as a 2-regular Boolean logic network over the gate basis {∧, ⊕, 1}. Our construction leads to circuits with a T-count that is at most four times the number of AND nodes in the network. In addition, we propose a SAT-based method that allows us to trade qubits for T gates, and explore the space/complexity trade-off of quantum circuits. Our constructive method suggests a new upper bound for the number of T gates and ancilla qubits based on the multiplicative complexity c∧(f) of the oracle function f, which is the minimum number of AND gates that is required to realize f over the gate basis {∧, ⊕, 1}. There exists a quantum circuit computing f with at most 4c∧(f)T gates using k=c∧(f) ancillae. Results known for the multiplicative complexity of Boolean functions can be transferred. We verify our method by comparing it to different state-of-the-art compilers. Finally, we present our synthesis results for Boolean functions used in quantum cryptoanalysis.