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.
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.
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.
Although with some yet severe limitations, Physical working Quantum Computers are becoming available for end users. Such devices are based on the rules of Quantum Mechanics, which state that physical systems evolve through unitary transformations. However, as in the classical case, in order to have a model of computation, such unitary evolutions are expressed/approximated inside Quantum Computers in terms of a finite set of one/two qubit operations (i.e., through a universal set of gates). Single qubit gates are fault-tolerant, while the same cannot be said for two qubit gates. Hence, unitary matrices adopted in Quantum Algorithms must be synthesized in terms of this universal set of operations to obtain a quantum circuit. In such synthesis procedure we prefer circuits with minimum number of qubits and with minimum circuit depth. Clifford+T universal set is one of the most adopted in the literature for synthesis. In such set we have 3 single qubit gates and the CNOT, which is a two qubit gate. Many efforts have been directed to devise algorithms that synthesize general unitary matrices into Clifford+T circuits. These algorithms usually tend to optimize circuit depth or eventually the number of T gates. Since two qubit gates are not fault tolerant, in this work we propose an ASP based technique to minimize the number of CNOT gates inside a Clifford+T circuit. Moreover, in real world quantum computers, qubit are usually connected to each other according to some particular topology, thus providing further constraints. Two qubit gates —hence, CNOT gate— can be directly applied only to pair of gates that are connected. Such constraint has to be taken into account during the synthesis of CNOT minimal circuits. We propose an ASP model to solve the problem of synthesizing CNOT minimal circuits under topological constraints. We provide experimental evidence of the scalability of our proposal.
Quantum computation has extraordinary capabilities for solving complicated problems. As quantum computations are reversible by nature, reversible circuits are important for the development of quantum computation techniques. Designing an effective and efficient method for synthesizing reversible circuits to reduce costs and stabilize circuit efficiency is crucial. The traditional synthesis methods of solving reversible circuits focus on the conversion efficiency rather than discussing the properties of the reversible function. Thus, this paper aims to propose a novel synthesis method that directly and efficiently optimizes reversible circuit synthesis with the properties of the reversible circuit. The proposed method converts the reversible function into a hypercube, allowing visual observations of the overall circuit. Two new indicators, the adjacent Hamming distance (AHD) and total cycle distance (TCD), aid in effective decision-making, generating shorter circuits. Furthermore, we use the generalized Toffoli gate set, which without requiring any additional ancilla bits and has applications in error correction and fault tolerance. The experimental results show that our method can find better solutions than traditional methods, significantly reducing the gate count, while the hypercube assists in synthesizing the reversible circuit.
The quantum circuit synthesis problem bridges quantum algorithm design and quantum hardware implementation in the Noisy Intermediate-Scale Quantum (NISQ) era. In quantum circuit synthesis problems, diagonal unitary synthesis plays a crucial role due to its fundamental and versatile nature. Meanwhile, experimental results have shown that moderately approximating the original algorithm to conserve quantum resources can improve the fidelity of algorithms during quantum execution. Building on this insight, we propose a quantum circuit synthesis algorithm to design diagonal unitary implementations based on specified quantum resource limits. Our algorithm can synthesize diagonal unitary for quantum circuits with up to 15 qubits on an ordinary laptop. In algorithm efficiency, synthesizing an n-qubit unitary matrix with an exact algorithm requires 2n CNOT gates as a baseline. Within the algorithm error $\varepsilon $ range of interest (0\%-12\%), our algorithm achieves a $3.2\varepsilon $ reduction in CNOT gates on average. In runtime, the algorithm efficiently performs, synthesizing 12-qubit diagonal unitary in an average of 6.57 seconds and 15-qubit in approximately 561.71 seconds.
In the last year, physical working Quantum Computers have been built and made available for the end users. Such devices, working under the rules of Quantum Mechanics, can only apply a finite set of one/two qubit operations that form a universal set of gates. Single qubit gates are fault-tolerant, while the same cannot be said for two qubit gates. Hence, unitary matrices adopted in Quantum Algorithms must be synthesized in terms of this universal set of operations to obtain a quantum circuit. This synthesis procedure, however, is not constraint-free. In fact, we prefer circuits with minimum number of qubits and with minimum circuit depth. Clifford+T universal set is one of the most adopted in the literature for synthesis. In such set we have 3 single qubit gates and the CNOT, which is a two qubit gate. Many efforts have been directed to devise algorithms that synthesize general unitary matrices into Clifford+T circuits. These algorithms usually tend to optimize circuit depth or eventually the number of T gates. Since two qubit gates are not fault tolerant, in this work we propose an ASP based technique to minimize the number of CNOT gates inside a Clifford+T circuit. We start from a SAT encoding of the problem, and we translate it into an ASP model over a graph, by first working with a generic graph, and then by adopting the structure of a layered DAG. We provide experimental evidence of the scalability of our proposal.