Abstract Current quantum computers are noisy intermediate-scale quantum (NISQ) devices. Execution of quantum algorithms, represented as quantum circuits in the quantum circuit model, on such hardware requires transformation of the original circuits to comply with the hardware’s physical constraints, a process known as transpilation. One of the main constraints is limited qubit connectivity. In this work, we present an algorithm that transforms a quantum hashing circuit to satisfy architectural connectivity constraints while minimizing the number of CNOT gates (CNOT cost). The considered algorithm constructs a mapping from logical qubits to physical qubits that minimizes the CNOT cost of the resulting circuit. We optimize circuits for IBM Quantum devices.
Abstract Current quantum computers are noisy intermediate-scale quantum (NISQ) devices. Execution of quantum algorithms, represented as quantum circuits in the quantum circuit model, on such hardware requires transformation of the original circuits to comply with the hardware’s physical constraints, a process known as transpilation. One of the main constraints is limited qubit connectivity. In this work, we present an algorithm that transforms a quantum hashing circuit to satisfy architectural connectivity constraints while minimizing the number of CNOT gates (CNOT cost). The considered algorithm constructs a mapping from logical qubits to physical qubits that minimizes the CNOT cost of the resulting circuit. We optimize circuits for IBM Quantum devices.
NISQ devices have inherent limitations in terms of connectivity and hardware noise. The synthesis of CNOT circuits considers the physical constraints and transforms quantum algorithms into low-level quantum circuits that can execute on physical chips correctly. In the current trend, quantum chip architectures without Hamiltonian paths are gradually replacing architectures with Hamiltonian paths due to their scalability and low-noise characteristics. To this end, this paper addresses the nearest neighbor synthesis of CNOT circuits in the architectures with and without Hamiltonian paths, aiming to enhance the fidelity of the circuits after execution. Firstly, a key-qubit priority mapping model for general quantum architectures is proposed. Secondly, the initial mapping is further improved by using tabu search to reduce the number of CNOT gates after circuit synthesis and enhance its fidelity. Finally, the noise-aware CNOT circuit nearest neighbor synthesis algorithm for the general architecture is proposed based on the key-qubit priority mapping model. The algorithm is demonstrated on several popular cloud quantum computing platforms and simulators, showing that it effectively optimizes the fidelity of CNOT circuits compared with mainstream methods. Moreover, the method can be extended to more general circuits, thereby improving the overall performance of quantum computing on NISQ devices.
One of the obstacles to the widespread adoption of quantum computing is the problem of efficient circuit synthesis. Current quantum hardware has limited connections between qubits, with each qubit connected to only a few others. This means that the circuit has to be transformed to accommodate this. In this paper, we present an algorithm that converts a circuit containing a sequence of CNOT gates into a form that is suitable for arbitrary quantum computer architectures. Although we demonstrate the algorithm only in the context of quantum fingerprinting, similar gate sequences are prevalent in quantum algorithms; for instance, they are present in the textbook quantum Fourier transform. We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting algorithm) for a quantum device with restrictions on the application of two-qubit gates that are expressed as a qubit connectivity graph. As an example of usage of the technique, we apply it to quantum finite automata recognizing the unary MODp={aℓ:ℓmodp=0} language, and the EQp={aℓbr:ℓ≡r(modp)} language. Given the enhancements that our algorithm provides~-- for instance, in one case it achieves a 16\%--17\% decrease in CNOT circuit cost~-- we believe it could also be useful in a broader quantum compilation context.
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.
In the era of noisy intermediate-scale quantum (NISQ), executing quantum algorithms on actual quantum devices faces unique challenges. One such challenge is that quantum devices in this era have restricted connectivity: quantum gates are allowed to act only on specific pairs of physical qubits. For this reason, a quantum circuit needs to go through a compiling process called qubit routing before it can be executed on a quantum computer. In this study, we propose a CNOT synthesis method called the token reduction method to solve this problem. The token reduction method works for all quantum computers whose architecture is represented by connected graphs. A major difference between our method and the existing ones is that our method synthesizes a circuit to an output qubit mapping that might be different from the input qubit mapping. The final mapping for the synthesis is determined dynamically during the synthesis process. Results showed that our algorithm consistently outperforms the best publicly accessible algorithm for all of the tested quantum architectures.
Quantum algorithm design usually assumes access to a perfect quantum computer with ideal properties like full connectivity, noise-freedom, and arbitrarily long coherence time. In noisy intermediate-scale quantum (NISQ) devices, however, the number of qubits is highly limited and quantum operation error and qubit coherence are not negligible. Besides, the connectivity of physical qubits in a quantum processing unit (QPU) is also strictly constrained. Thereby, additional operations like SWAP gates have to be inserted to satisfy this constraint while preserving the functionality of the original circuit. This process is known as quantum circuit transformation. Adding additional gates will increase both the size and depth of a quantum circuit and, therefore, cause further decay of the performance of a quantum circuit. Thus, it is crucial to minimize the number of added gates. In this article, we propose an efficient method to solve this problem. We first choose by using simulated annealing an initial mapping which fits well with the input circuit and then, with the help of a heuristic cost function, stepwise apply the best-selected SWAP gates until all quantum gates in the circuit can be executed. Our algorithm runs in time polynomial in all parameters, including the size and the qubit number of the input circuit, and the qubit number in the QPU. Its space complexity is quadratic to the number of edges in the QPU. The experimental results on extensive realistic circuits confirm that the proposed method is efficient and the number of added gates of our algorithm is, on average, only 57% of that of state-of-the-art algorithms on IBM Q20 (Tokyo), the most recent IBM quantum device.
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.