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

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
v1 · May 20, 2026v2 · Aug 30, 2026
arXivHTMLPDF

Abstract

Quantum computing has demonstrated its significant advantage over supercomputing for specific applications and shown promising prospect, such as machine learning, cryptography, finance, etc.. Quantum oracles are very common in many quantum algorithms and oracle resource consumption directly affects algorithm performance. However, existing oracle designs often exhibit high resource overhead and limited compatibility. Moreover, structured description tools and complexity analysis methods are lacked. In this work, we introduces a Hierarchical Recursive Synthesis-Evaluation (HRSE) model, enabling formal description and precise quantum gate complexity analysis of oracles. Based on this model, we propose an Adaptive Space-depth Trade-off (ASDT) algorithm for generating oracle structures under a fixed qubit constraint. We provide a theoretical proof showing that the ASDT algorithm achieves the optimal gate count for a given number of qubits. Experimental results show that the ASDT algorithm reduces the average quantum circuit depth by 53.99% compared with the W-cycle approach, with the number of variables being 10, 15, and 20, respectively.

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 computing has demonstrated its significant advantage over supercomputing for specific applications and shown promising prospect, such as machine learning, cryptography, finance, etc.. Quantum oracles are very common in many quantum algorithms and oracle resource consumption directly affects algorithm performance. However, existing oracle designs often exhibit high resource overhead and limited compatibility. Moreover, structured description tools and complexity analysis methods are lacked. In this work, we introduces a Hierarchical Recursive Synthesis-Evaluation (HRSE) model, enabling formal description and precise quantum gate complexity analysis of oracles. Based on this model, we propose an Adaptive Space-depth Trade-off (ASDT) algorithm for generating oracle structures under a fixed qubit constraint. We provide a theoretical proof showing that the ASDT algorithm achieves the optimal gate count for a given number of qubits. Experimental results show that the ASDT algorithm reduces the average quantum circuit depth by 53.99% compared with the W-cycle approach, with the number of variables being 10, 15, and 20, respectively.
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 bbb: with 1≤m≤Θ(2nn)1\le m\leΘ\left(\frac{2^n}{n}\right)1≤m≤Θ(n2n​) ancilla, size O(b2nlog⁡(n+m))\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)O(log(n+m)b2n​), depth O(b2nn+m)\mathcal{O}\left(\frac{b2^n}{n+m}\right)O(n+mb2n​); partial Boolean functions of effective support size ddd and output size bbb: with Θ(log⁡d)≤m≤Θ(d)Θ\left(\log d\right)\le m\le Θ\left(d\right)Θ(logd)≤m≤Θ(d) ancilla, size O(nlog⁡d+bd)\mathcal{O}\left(n\log d+bd\right)O(nlogd+bd), depth O(nlog⁡nlog⁡dn+m+log⁡n+d(log⁡d+blog⁡m)m)\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)O(n+mnlognlogd​+logn+md(logd+blogm)​); sparse Boolean functions of true input size ddd: with Θ(log⁡n+log⁡d)≤m≤Θ(ndlog⁡d)Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)Θ(logn+logd)≤m≤Θ(logdnd​) ancilla, size O(n2log⁡d+ndlog⁡(log⁡d+m/n))\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)O(n2logd+log(logd+m/n)nd​), depth O(n2log⁡nlog⁡dn+m+log⁡n+ndm)\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)O(n+mn2lognlogd​+logn+mnd​). 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 provableO(n)\mathcal{O}(n)O(n)reduction in the minimum Toffoli gate count - a key cost metric in FTQC - for constructing annnn-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 anmmm-clause SAT-oracle necessitates2m−12m-12m−1ancillary 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 toO~(log⁡m)\tilde {O}(\log m)O~(logm)usingmmmancillary 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 TTT-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.