Abstract The construction of quantum computers is based on the synthesis of low-cost quantum circuits. The quantum circuit of any Boolean function expressed in a Positive Polarity Reed-Muller (PPRM) expansion can be synthesized using Multiple-Control Toffoli (MCT) gates. This paper proposes two algorithms to construct a quantum circuit for any Boolean function expressed in a PPRM expansion. The Boolean function can be expressed with various algebraic forms, so there are different quantum circuits can be synthesized for the Boolean function based on its algebraic form. The proposed algorithms aim to map the MCT gates into the NCV gates for any quantum circuit by generating a simple algebraic form for the Boolean function. The first algorithm generates a special algebraic form for any Boolean function by rearrangement of terms of the Boolean function according to a predefined degree of term d term , then synthesizes the corresponding quantum circuit. The second algorithm applies the decomposition methods to decompose MCT circuit into its elementary gates followed by applying a set of simplification rules to simplify and optimize the synthesized quantum circuit. The proposed algorithms achieve a reduction in the quantum cost of synthesized quantum circuits when compared with relevant work in the literature. The proposed algorithms synthesize quantum circuits that can applied on IBM quantum computer.
Abstract The construction of quantum computers is based on the synthesis of low-cost quantum circuits. The quantum circuit of any Boolean function expressed in a Positive Polarity Reed-Muller (PPRM) expansion can be synthesized using Multiple-Control Toffoli (MCT) gates. This paper proposes two algorithms to construct a quantum circuit for any Boolean function expressed in a PPRM expansion. The Boolean function can be expressed with various algebraic forms, so there are different quantum circuits can be synthesized for the Boolean function based on its algebraic form. The proposed algorithms aim to map the MCT gates into the NCV gates for any quantum circuit by generating a simple algebraic form for the Boolean function. The first algorithm generates a special algebraic form for any Boolean function by rearrangement of terms of the Boolean function according to a predefined degree of term d term , then synthesizes the corresponding quantum circuit. The second algorithm applies the decomposition methods to decompose MCT circuit into its elementary gates followed by applying a set of simplification rules to simplify and optimize the synthesized quantum circuit. The proposed algorithms achieve a reduction in the quantum cost of synthesized quantum circuits when compared with relevant work in the literature. The proposed algorithms synthesize quantum circuits that can applied on IBM quantum computer.
State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.
This paper introduces a new logic structure for reversible quantum circuit synthesis. Our synthesis method aims to minimize the quantum cost of reversible quantum circuits with decoders. In this method, multi-valued input, binary output (MVI) functions are utilized as a mathematical concept only, but the circuits are binary. We introduce the new concept of ``Multi-Valued Input Fixed Polarity Reed-Muller (MVI-RM)" forms. Our decoder-based circuit uses three logical levels in contrast to commonly-used methods based on Exclusive-or Sum of Products (ESOP) with two levels (AND-XOR expressions), realized by Toffoli gates. In general, the high number of input qubits in the resulting Toffoli gates is a problem that greatly impacts the quantum cost. Using decoders decreases the number of input qubits in these Toffoli gates. We present two practical algorithms for three-level circuit synthesis by finding the MVI-FPRM: products-matching and the newly developed butterfly diagrams. The best MVI-FPRM forms are factorized and reduced to approximate Multi-Valued Input Generalized Reed-Muller (MVI-GRM) forms.
Abstract Boolean matrices and operations on Boolean matrices have become increasingly popular in quantum computing and quantum information because they can be used to represent quantum states and the corresponding operations. In this paper, we first give a quantum circuit direct synthesis of general Boolean matrix multiplication using Toffoli gates. We assign a qubit to each element of the matrix and add Toffoli gates at the corresponding positions where the matrix elements are multiplied according to the arithmetic of matrix multiplication. For n × p dimensional matrix A multiplied by p × m dimensional matrix B, np + pm + nm qubits and at most pmn Toffoli gates are used in total. Then, an improved heuristic algorithm based on matrix Hamming distance selection of CNOT gate is proposed to synthesize the quantum circuit of a matrix, without using wire switching and SWAP gates, using only CNOT gates. The results show that our method is as good as or better than the classical synthesis. Finally, the quantum circuit of Boolean matrix multiplication with at least one invertible or full-rank matrix using only CNOT gates is given, which is divided into five cases for discussion and analysis. For n × n dimensional invertible matrix A multiplied by n × m dimensional matrix B, nm qubits and at most mn 2 CNOT gates are used in total. For n × p dimensional column full-rank matrix A multiplied by p × m dimensional matrix B, nm qubits and at most pmn CNOT gates are used in total. The results show that this method uses less quantum resources to synthesize the quantum circuit of Boolean matrix multiplication. The correctness of the quantum circuits was verified by the Aer simulator of the IBM Quantum platform.
The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing. While standard libraries often treat the Toffoli gate as an atomic unit, its realization in the NCV library requires decomposition into 5 elementary gates. In this work, we propose a novel, systematic four-phase optimization methodology. First, we generate an optimal circuit in the strict NCT library (NOT, CNOT, Toffoli) using automated synthesis. Second, we replace each Toffoli gate with a specific NCV decomposition, permuting the control lines such that the final internal CNOT gate matches the subsequent linear gate in the circuit, allowing us to apply a cancellation rule (X ·X = I). Finally, post-synthesis local searches are applied using Mixed- Integer Non-Linear Programming (MINLP) techniques to further reduce the total gate count. Applying this method to the MIG, TSG, and MKG gates, we achieve Quantum Costs of 7, 14, and 12 respectively, matching or beating the best-known literature benchmarks.
Abstract In this paper, we present a generic construction for synthesizing an optimal T-depth quantum circuit for any arbitrary n -input, m -output Boolean function f : {0, 1 } n → {0, 1} m with algebraic degree k ≤ n , achieving an exact Toffoli (consequently T) depth of ⌈log 2 k ⌉. This broadly generalizes the recent result establishing the optimal Toffoli (and T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). The optimality of T-depth in this initiative is considered in the context of implementing an n -MCT, assuming the decomposition via Clifford plus Toffoli gates. The key technique involves inspecting the Algebraic Normal Form (ANF) of the Boolean function. Obtaining a benchmark for the minimum T-depth of such circuits is crucial for the 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 broader implications of our results include a provable lower bounds on T-depth for S-box and block cipher implementations, such as AES. Finally, we also explain the impact of our result in identifying the T-depth for the generic cryptanalysis of block ciphers using Grover’s algorithm.
Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.