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.
We propose quantum cryptography based on an algorithm of determining a function. The security of our cryptography is based on the Ekert 1991 protocol, that is, we use an entangled state. Eve must destroy the entangled state. Consider a function. Alice knows all the mappings concerning the function. Bob knows none of them. His aim is of obtaining all of them without Eve's attack. In classical case, Bob needs some queries. In quantum case, Bob needs just a query. By measuring the single entangled state, which is sent by Alice, Bob can obtain all the mappings concerning the function, simultaneously. This is faster than classical cryptography.