Oracle Synthesis Based on X-Map Decision Diagrams
Abstract
Quantum oracles act as reversible black-box operators that encode classical Boolean functions into quantum states, enabling efficient function evaluation in quantum superposition. The resource efficiency of oracle implementation is critical to the performance of numerous quantum algorithms. Most state-of-the-art oracle synthesis approaches rely on compact Boolean function representations such as exclusive-sum-of-products (ESOP), yet still suffer from excessive T-count and CX-count for large-scale functions. In this paper, we propose a novel compact representation named X-Map decision diagram (XMDD) for Boolean functions, which integrates local invertible maps and complement edges to achieve higher compression efficiency. Based on XMDD, we further develop an optimized quantum oracle synthesis algorithm. Extensive experimental results demonstrate that, for Boolean functions with more than seven input variables, our method outperforms the state-of-the-art ESOP-based approach and Qiskit in nearly all test cases, achieving simultaneous reduction in both T-count and CX-count without an obvious trade-off. Moreover, we show that the performance can be further boosted by employing more optimal variable orderings. The proposed XMDD-based framework provides a scalable and resource-efficient solution for practical oracle synthesis in near-term and fault-tolerant quantum computing.
Related
- State Synthesis with an NP oracle
- Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group
- Magic in Grover's Algorithm and the Role of Oracle Synthesis
- Random-Oracle Unitary Synthesis is Impossible
- From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the FORM Model
BibTeX
@misc{hong2026oracle,
title = {{Oracle Synthesis Based on X-Map Decision Diagrams}},
author = {Xin Hong and Kezhen Zhang and Aochu Dai and Sanjiang Li and Shenggang Ying and Mingsheng Ying},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20854},
eprint = {2609.20854},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20854},
}
RIS
TY - UNPB
TI - Oracle Synthesis Based on X-Map Decision Diagrams
AU - Xin Hong
AU - Kezhen Zhang
AU - Aochu Dai
AU - Sanjiang Li
AU - Shenggang Ying
AU - Mingsheng Ying
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.20854
UR - https://arxiv.org/abs/2609.20854
AB - Quantum oracles act as reversible black-box operators that encode classical Boolean functions into quantum states, enabling efficient function evaluation in quantum superposition. The resource efficiency of oracle implementation is critical to the performance of numerous quantum algorithms. Most state-of-the-art oracle synthesis approaches rely on compact Boolean function representations such as exclusive-sum-of-products (ESOP), yet still suffer from excessive T-count and CX-count for large-scale functions. In this paper, we propose a novel compact representation named X-Map decision diagram (XMDD) for Boolean functions, which integrates local invertible maps and complement edges to achieve higher compression efficiency. Based on XMDD, we further develop an optimized quantum oracle synthesis algorithm. Extensive experimental results demonstrate that, for Boolean functions with more than seven input variables, our method outperforms the state-of-the-art ESOP-based approach and Qiskit in nearly all test cases, achieving simultaneous reduction in both T-count and CX-count without an obvious trade-off. Moreover, we show that the performance can be further boosted by employing more optimal variable orderings. The proposed XMDD-based framework provides a scalable and resource-efficient solution for practical oracle synthesis in near-term and fault-tolerant quantum computing.
ER -