We propose an exact method of synthesizing Nearest Neighbor Architecture (NNA) compliant networks of CNOT gates on 2-D architecture quantum computers using SMT solvers. To minimize noisy CNOT gates in the circuit, previous methods have employed SMT solvers and partitioning to obtain a lower CNOT gate count than contemporary methods. We observe that there is no need to fix the positions of T-gates relative to the source circuit; we can freely move them relative to the original, in turn enabling the gates that implement the logic feeding into them to be freely placed. In this paper, we introduce a set of constraints based around relaxing the constraints on the logic that acts on the T-gates in the circuit. Using these, we improve both the runtime and the quantum cost of the generated circuits. We compare our method to the method by Ding et al., and find a reduction 29.22% in the runtime and 58.11% in the quantum cost. We also find an advantage vs. IBM's SabreSwap.
We propose an exact method of synthesizing Nearest Neighbor Architecture (NNA) compliant networks of CNOT gates on 2-D architecture quantum computers using SMT solvers. To minimize noisy CNOT gates in the circuit, previous methods have employed SMT solvers and partitioning to obtain a lower CNOT gate count than contemporary methods. We observe that there is no need to fix the positions of T-gates relative to the source circuit; we can freely move them relative to the original, in turn enabling the gates that implement the logic feeding into them to be freely placed. In this paper, we introduce a set of constraints based around relaxing the constraints on the logic that acts on the T-gates in the circuit. Using these, we improve both the runtime and the quantum cost of the generated circuits. We compare our method to the method by Ding et al., and find a reduction 29.22% in the runtime and 58.11% in the quantum cost. We also find an advantage vs. IBM's SabreSwap.
It is natural to assume that we can perform quantum operations between only two adjacent physical qubits (quantum bits) to realize a quantum computer for both the current and possible future technologies. This restriction is called the Nearest Neighbor Architecture (NNA) restriction. This paper proposes an SMT-solver-based synthesis of quantum circuits consisting of CNOT, H, and T gates to satisfy the NNA restriction. Although the existing SMT-solver-based synthesis cannot treat H and T gates directly, our method treats the functionality of quantum-specific T and H gates carefully so that we can utilize an SMT-solver to minimize the number of CNOT gates; unlike the existing SMT-solver-based methods, our method considers "Don't Care" conditions in intermediate points of a quantum circuit by exploiting the property of T gates to reduce CNOT gates. Experimental results show that our approach can reduce the number of CNOT gates by 58.11% on average compared to the naive application of the existing method which does not consider the "Don't Care" condition.
In this paper, we propose an exact method of directly synthesizing a nearest neighbor compliant (NNC) quantum circuit with the smallest depth in 2-D architecture, given a reversible function. Our method maps the synthesis problem to a Boolean satisfiability (SAT) problem and uses a satisfiability modulo theories (SMT) solver to find an assignment of a network of allowed quantum gates. Since an SMT solver performs an exhaustive search, it can be ensured that on a specific qubit placement, the NNC quantum circuit synthesized by our method has the smallest number of quantum gates. However, the exhaustive search also makes our exact method not scale well. For that reason, we propose another method of applying our exact method in the local synthesis of large-scale circuits, to in parallel synthesize sub-NNC quantum circuits. From the experimental results, the quantum costs of the NNC quantum circuits synthesized by our methods are reduced by an average of 23.89%, when compared to an optimal heuristic method which determines the smallest number of SWAP gates in 2-D architecture.
Quantum circuits should comply with the Nearest Neighbor Architecture (NNA), which primarily supports only two-qubit operations between adjacent qubits. Typically, con-verting a quantum circuit to an NNA -compliant circuit involves the insertion of SWAP gates. However, employing Gaussian Elimination often results in a smaller NNA -compliant quantum circuit. If we fix the order of qubits to apply Gaussian Elimination (GE), it appears there is no room to improve the GE-based synthesis method. This paper reveals that we can enhance the GE-based method by inserting CNOT gates before and/or after a target circuit in many cases. As a result, we achieve a reduction of approximately 16% in the number of CNOT gates by inserting CNOT gates into the target circuits compared to the original GE-based method. Additionally, we utilize a Simulated Annealing (SA)-based method to achieve an optimal circuit, resulting in an 18% reduction in the number of CNOT gates by inserting CNOT gates, compared to the original GE-based method.
While mapping a quantum circuit to the physical layer one has to consider the numerous constraints imposed by the underlying hardware architecture. Connectivity of the physical qubits is one such constraint that restricts two-qubit operations, such as CNOT, to ``connected'' qubits. SWAP gates can be used to place the logical qubits on admissible physical qubits, but they entail a significant increase in CNOT-count. In this paper we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity constrained architectures, like noisy intermediate-scale quantum (NISQ) computing devices. We ``slice'' the circuit at the position of Hadamard gates and ``build'' the intermediate {CNOT,T} sub-circuits using Steiner trees, significantly improving on previous methods. We compared the performance of our algorithms while mapping different benchmark and random circuits to some well-known architectures such as 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5 and 20-qubit IBM Tokyo. Our methods give less CNOT-count compared to Qiskit transpiler as well as using SWAP gates. Assuming most of the errors in a NISQ circuit implementation are due to CNOT errors, then our method would allow circuits with few times more CNOT gates be reliably implemented than the previous methods would permit.
While mapping a quantum circuit to the physical layer one has to consider the numerous constraints imposed by the underlying hardware architecture. Connectivity of the physical qubits is one such constraint that restricts two-qubit operations, such as CNOT, to “connected” qubits. SWAP gates can be used to place the logical qubits on admissible physical qubits, but they entail a significant increase in CNOT-count. In this article, we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity-constrained architectures, like noisy intermediate-scale quantum (NISQ) computing devices. We “slice” the circuit at the position of Hadamard gates and “build” the intermediate{CNOT,T}subcircuits using Steiner trees, significantly improving on previous methods. We compared the performance of our algorithms while mapping different benchmark and random circuits to some well-known architectures, such as 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5, and 20-qubit IBM Tokyo. Our methods give less CNOT-count compared to Qiskit and TKET transpiler as well as using SWAP gates. Assuming most of the errors in an NISQ circuit implementation are due to CNOT errors, then our method would allow circuits with a few times more CNOT gates be reliably implemented than the previous methods would permit.
While mapping a quantum circuit to the physical layer one has to consider the numerous constraints imposed by the underlying hardware architecture. Connectivity of the physical qubits is one such constraint that restricts two-qubit operations, such as CNOT, to “connected’‘ qubits. SWAP gates can be used to place the logical qubits on admissible physical qubits, but they entail a significant increase in CNOT-count. In this paper we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity constrained architectures, like noisy intermediate-scale quantum (NISQ) computing devices. We “slice’‘ the circuit at the position of Hadamard gates and “build” the intermediate {CNOT,T} sub-circuits using Steiner trees, significantly improving on previous methods. We compared the performance of our algorithms while mapping different benchmark and random circuits to some well-known architectures such as 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5 and 20-qubit IBM Tokyo. Our methods give less CNOT-count compared to Qiskit transpiler as well as using SWAP gates. Assuming most of the errors in a NISQ circuit implementation are due to CNOT errors, then our method would allow circuits with few times more CNOT gates be reliably implemented than the previous methods would permit.