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

IEEE International Conference on Quantum Computing and Engineering (QCE)

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

Mingfei Yu, Mathias Soeken, Giovanni De Micheli

Published Aug 30, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/qce65121.2025.00063

Related papers

Modeling and Resource Optimization for Quantum Oracles

Zhihang Li, Bo Zhao, Chuanbing Han +6 more

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.

quant-pharXiv:2605.21380•May 21, 2026•0 citations

Unified architecture for quantum lookup tables

Shuchen Zhu, Aarthi Sundaram, Guang Hao Low

Quantum access to arbitrary classical data encoded in unitary black-box oracles underlies interesting data-intensive quantum algorithms, such as machine learning or electronic structure simulation. The feasibility of these applications depends crucially on gate-efficient implementations of these oracles, which are commonly some reversible versions of the boolean circuit for a classical lookup table. We present a general parametrized architecture for quantum circuits implementing a lookup table that encompasses all prior work in realizing a continuum of optimal trade-offs between qubits, non-Clifford gates, and error resilience, up to logarithmic factors. Our architecture assumes only local 2D connectivity, yet recovers results, with the appropriate parameters, polylogarithmic error scaling. We also identify regimes, such as simultaneous sublinear scaling, in all parameters. These results enable tailoring implementations of the commonly used lookup table primitive to any given quantum device with constrained resources.

arXiv:2406.18030•Physical Review Research•Dec 1, 2025•2 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

Tableau-Based Framework for Efficient Logical Quantum Compilation

Meng Wang, Liu, Chenxu, Sean R. Garner +4 more

Quantum computing holds the promise of solving problems intractable for classical computers, but practical large-scale quantum computation requires error correction to protect against errors. Fault-tolerant quantum computing (FTQC) enables reliable execution of quantum algorithms, yet they often demand substantial physical qubit overhead. Resource-efficient FTQC architectures minimize the number of physical qubits required, saving more than half compared to other architectures, but impose constraints that introduce up to 4.7$\times$ higher runtime overhead. In this paper, we present TQC, a \underline{T}ableau-based \underline{Q}uantum \underline{C}ompiler framework that minimizes FTQC runtime overhead without requiring additional physical qubits. By leveraging operation reorderability and latency hiding through parallel execution, TQC reduces FTQC runtime overhead by \textbf{2.57$\times$} on average. Furthermore, FTQC circuits often contain millions of gates, leading to substantial compilation overhead. To address this, we optimize the core data structure, the tableau, used in stabilizer formalism. We provide two tailored versions of the Tableau data type, each designed for different usage scenarios. These optimizations yield an overall performance improvement of more than \textbf{1000$\times$} compared to state-of-the-art FTQC optimization tools.

arXiv:2509.02721•Sep 2, 2025•0 citations

Performance Gains in Quantum SAT Solvers Using ESOP Encoding

Majd Assaad, Abhoy Kole, Rolf Drechsler

The Boolean Satisfiability (SAT) problem is a canonical NP-complete problem and a natural candidate for quantum acceleration via search-based algorithms. In Grover-based quantum SAT solvers, the dominant computational cost stems from the construction of a reversible oracle that evaluates the Boolean formula, rendering the choice of SAT encoding crucial for overall quantum resource efficiency. Although SAT instances are conventionally expressed in Conjunctive Normal Form (CNF), such encodings typically translate into quantum circuits with significant qubit overhead and high non-Clifford gate complexity. In this work, we investigate an Exclusive-Sum-of-Products (ESOP)-based CNF (e-CNF) representation tailored for quantum SAT solving and analyze its impact on oracle construction. We derive tighter upper bounds on qubit requirements and Clifford+$T$ gate counts for Grover-based SAT solvers when e-CNF encodings are employed in place of standard CNF. In addition, we propose a scalable transformation from Boolean formulas to e-CNF and present a systematic procedure for interpreting e-CNF representations as reversible quantum circuits suitable for oracle implementation. Experimental evaluation on representative SAT benchmarks demonstrates that the proposed e-CNF-based approach yields substantial and consistent reductions in quantum resources, including qubit count, T-gate complexity, and circuit depth, when compared to CNF-based oracle constructions. These results establish e-CNF as an effective quantum-aware SAT encoding that significantly improves the practicality of oracle-based quantum SAT solving.

quant-pharXiv:2605.16202•May 18, 2026•0 citations

Optimal T depth quantum circuits for implementing arbitrary Boolean functions

Dutta, Suman, Bhaumik, Anik Basu, Anupam Chattopadhyay +1 more

In this paper we present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}^m$ having algebraic degree $k\leq n$, and it achieves an exact Toffoli (and T) depth of $\lceil \log_2 k \rceil$. This is a broader generalization of the recent result establishing the optimal Toffoli (and consequently T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function. Obtaining a benchmark for the minimum T depth of such circuits are of prime importance for efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations, for example AES.

arXiv:2506.01542•Jun 2, 2025•0 citations
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.
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 access to arbitrary classical data encoded in unitary black-box oracles underlies interesting data-intensive quantum algorithms, such as machine learning or electronic structure simulation. The feasibility of these applications depends crucially on gate-efficient implementations of these oracles, which are commonly some reversible versions of the boolean circuit for a classical lookup table. We present a general parametrized architecture for quantum circuits implementing a lookup table that encompasses all prior work in realizing a continuum of optimal trade-offs between qubits, non-Clifford gates, and error resilience, up to logarithmic factors. Our architecture assumes only local 2D connectivity, yet recovers results, with the appropriate parameters, polylogarithmic error scaling. We also identify regimes, such as simultaneous sublinear scaling, in all parameters. These results enable tailoring implementations of the commonly used lookup table primitive to any given quantum device with constrained resources.
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.
Quantum computing holds the promise of solving problems intractable for classical computers, but practical large-scale quantum computation requires error correction to protect against errors. Fault-tolerant quantum computing (FTQC) enables reliable execution of quantum algorithms, yet they often demand substantial physical qubit overhead. Resource-efficient FTQC architectures minimize the number of physical qubits required, saving more than half compared to other architectures, but impose constraints that introduce up to 4.7×\times× higher runtime overhead. In this paper, we present TQC, a \underline{T}ableau-based \underline{Q}uantum \underline{C}ompiler framework that minimizes FTQC runtime overhead without requiring additional physical qubits. By leveraging operation reorderability and latency hiding through parallel execution, TQC reduces FTQC runtime overhead by \textbf{2.57×\times×} on average. Furthermore, FTQC circuits often contain millions of gates, leading to substantial compilation overhead. To address this, we optimize the core data structure, the tableau, used in stabilizer formalism. We provide two tailored versions of the Tableau data type, each designed for different usage scenarios. These optimizations yield an overall performance improvement of more than \textbf{1000×\times×} compared to state-of-the-art FTQC optimization tools.
The Boolean Satisfiability (SAT) problem is a canonical NP-complete problem and a natural candidate for quantum acceleration via search-based algorithms. In Grover-based quantum SAT solvers, the dominant computational cost stems from the construction of a reversible oracle that evaluates the Boolean formula, rendering the choice of SAT encoding crucial for overall quantum resource efficiency. Although SAT instances are conventionally expressed in Conjunctive Normal Form (CNF), such encodings typically translate into quantum circuits with significant qubit overhead and high non-Clifford gate complexity. In this work, we investigate an Exclusive-Sum-of-Products (ESOP)-based CNF (e-CNF) representation tailored for quantum SAT solving and analyze its impact on oracle construction. We derive tighter upper bounds on qubit requirements and Clifford+TTT gate counts for Grover-based SAT solvers when e-CNF encodings are employed in place of standard CNF. In addition, we propose a scalable transformation from Boolean formulas to e-CNF and present a systematic procedure for interpreting e-CNF representations as reversible quantum circuits suitable for oracle implementation. Experimental evaluation on representative SAT benchmarks demonstrates that the proposed e-CNF-based approach yields substantial and consistent reductions in quantum resources, including qubit count, T-gate complexity, and circuit depth, when compared to CNF-based oracle constructions. These results establish e-CNF as an effective quantum-aware SAT encoding that significantly improves the practicality of oracle-based quantum SAT solving.
In this paper we present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary nnn-input mmm-output Boolean function f:{0,1}n→{0,1}mf: \{0,1\}^n \rightarrow \{0,1\}^mf:{0,1}n→{0,1}m having algebraic degree k≤nk\leq nk≤n, and it achieves an exact Toffoli (and T) depth of ⌈log⁡2k⌉\lceil \log_2 k \rceil⌈log2​k⌉. This is a broader generalization of the recent result establishing the optimal Toffoli (and consequently T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function. Obtaining a benchmark for the minimum T depth of such circuits are of prime importance for efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations, for example AES.