Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1904.01972 · Quantum Science and Technology

Quantum circuit optimizations for NISQ architectures

Beatrice Nash, Vlad Gheorghiu, Michele Mosca

Published Feb 25, 2020• 153 citations
arXivHTMLPDF

Abstract

Abstract Currently available quantum computing hardware platforms have limited 2-qubit connectivity among their addressable qubits. In order to run a generic quantum algorithm on such a platform, one has to transform the initial logical quantum circuit describing the algorithm into an equivalent one that obeys the connectivity restrictions. In this work we construct a circuit synthesis scheme that takes as input the qubit connectivity graph and a quantum circuit over the gate set generated by { CNOT , R Z } and outputs a circuit that respects the connectivity of the device. As a concrete application, we apply our techniques to Google’s Bristlecone 72-qubit quantum chip connectivity, IBM’s Tokyo 20-qubit quantum chip connectivity, and Rigetti’s Acorn 19-qubit quantum chip connectivity. In addition, we also compare the performance of our scheme as a function of sparseness of randomly generated quantum circuits, and discuss how to apply our techniques as a subroutine for the more general mapping problem over universal set of gates (Clifford + T).

DOI
10.1088/2058-9565/ab79b1

Related papers

Connectivity-Aware Qubit Mapping and CNOT Cost Minimization for Quantum Hashing Circuits

I. Zinnatullin, Kamil Ravilevich Khadiev, I. A. Nikitin

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.

Russian Microelectronics•Dec 1, 2025•2 citations

Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering Path

Kamil Khadiev, Aliya Khadieva, Vadim Sagitov +2 more

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 $MOD_p=\{a^\ell: \ell \bmod p=0\}$ language, and the $EQ_p=\{a^\ell b^r: \ell \equiv r \pmod p\}$ 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.

quant-pharXiv:2608.09134•Aug 11, 2026•0 citations

Quantum circuit synthesis on noisy intermediate-scale quantum devices

Shuai Yang, Guojing Tian, Jialin Zhang +1 more

In the near future of the noisy intermediate-scale quantum (NISQ) era, almost all quantum computing devices will be restricted to a specific fixed qubits connectivity architecture. Thus, the synthesis of quantum circuits with limited connectivity is urgent. We design quantum circuit synthesis algorithms for basic and essential synthesis problems, such as quantum state preparation, general unitary synthesis, and quantum isometries. For any architecture, the controlled not (cnot) count is at most 5/3 times the state-of-the-art result on complete-graph architecture. For some specific architectures, such as square-grid ones, the ratio is reduced to 1.126. The numerical simulation result is confirmatory of theoretical conclusions. Our algorithms significantly reduce by more than $50%$ additional cnot count compared to mapping algorithms. These algorithms help to implement the larger-scale algorithm in the physics device. Our results illustrate that well-designed synthesis algorithms can mitigate the problem of limited qubit connectivity in the NISQ era and may suggest the design of large-scale quantum devices.

Physical Review A•Jan 2, 2024•7 citations

Efficient CNOT Synthesis for NISQ Devices

Yao Tang

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.

arXiv:2011.06760•Nov 12, 2020•5 citations

Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search

Sanjiang Li, Xiangzhen Zhou, Yuan Feng

Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ) devices is a challenging problem which has attracted rapidly increasing interests from both quantum and classical computing communities. This article proposes an efficient method by (i) selecting an initial mapping that takes into consideration the similarity between the architecture graph of the given NISQ device and a graph induced by the input logical circuit and (ii) searching, in a filtered and depth-limited way, a most usefulswapcombination that makes executable as many as possible two-qubit gates in the logical circuit. The proposed circuit transformation algorithm can significantly decrease the number of auxiliary two-qubit gates required to be added to the logical circuit, especially when it has a large number of two-qubit gates. For an extensive benchmark set of 131 circuits and IBM's current premium Q system, viz., IBM Q Tokyo, our algorithm needs, in average, 0.3801 extra two-qubit gates per input two-qubit gate, while the corresponding figures for three state-of-the-art algorithms are 0.4705, 0.8154, and 1.0066, respectively.

arXiv:2004.07138•IEEE Transactions on Computers•Sep 10, 2020•57 citations

Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs

Kamil Ravilevich Khadiev, Aliya Khadieva, Vadim Sagitov +1 more

In the paper, we consider quantum circuits for the Quantum Fourier Transform (QFT) algorithm. The QFT algorithm is a very popular technique used in many quantum algorithms. We present a generic method for constructing quantum circuits for this algorithm implementing on quantum devices with restrictions. Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates. These restrictions are presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture of the qubit connection, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit for implementing on such architecture. We compare quantum circuits built by our algorithm with existing quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, ``sun'' (a cycle with tails, presented by the 16-qubit IBMQ device) and ``two joint suns'' (two joint cycles with tails, presented by the 27-qubit IBMQ device). Our generic method gives similar results with existing optimized circuits for ``sun'' and ``two joint suns'' architectures, and a circuit with slightly more CNOT gates for the LNN architecture. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.

arXiv:2510.09824•Oct 10, 2025•0 citations
Abstract Currently available quantum computing hardware platforms have limited 2-qubit connectivity among their addressable qubits. In order to run a generic quantum algorithm on such a platform, one has to transform the initial logical quantum circuit describing the algorithm into an equivalent one that obeys the connectivity restrictions. In this work we construct a circuit synthesis scheme that takes as input the qubit connectivity graph and a quantum circuit over the gate set generated by { CNOT , R Z } and outputs a circuit that respects the connectivity of the device. As a concrete application, we apply our techniques to Google’s Bristlecone 72-qubit quantum chip connectivity, IBM’s Tokyo 20-qubit quantum chip connectivity, and Rigetti’s Acorn 19-qubit quantum chip connectivity. In addition, we also compare the performance of our scheme as a function of sparseness of randomly generated quantum circuits, and discuss how to apply our techniques as a subroutine for the more general mapping problem over universal set of gates (Clifford + T).
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.
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ℓ:ℓ mod p=0}MOD_p=\{a^\ell: \ell \bmod p=0\}MODp​={aℓ:ℓmodp=0} language, and the EQp={aℓbr:ℓ≡r(modp)}EQ_p=\{a^\ell b^r: \ell \equiv r \pmod p\}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.
In the near future of the noisy intermediate-scale quantum (NISQ) era, almost all quantum computing devices will be restricted to a specific fixed qubits connectivity architecture. Thus, the synthesis of quantum circuits with limited connectivity is urgent. We design quantum circuit synthesis algorithms for basic and essential synthesis problems, such as quantum state preparation, general unitary synthesis, and quantum isometries. For any architecture, the controlled not (cnot) count is at most 5/3 times the state-of-the-art result on complete-graph architecture. For some specific architectures, such as square-grid ones, the ratio is reduced to 1.126. The numerical simulation result is confirmatory of theoretical conclusions. Our algorithms significantly reduce by more than 5050%50 additional cnot count compared to mapping algorithms. These algorithms help to implement the larger-scale algorithm in the physics device. Our results illustrate that well-designed synthesis algorithms can mitigate the problem of limited qubit connectivity in the NISQ era and may suggest the design of large-scale quantum devices.
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.
Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ) devices is a challenging problem which has attracted rapidly increasing interests from both quantum and classical computing communities. This article proposes an efficient method by (i) selecting an initial mapping that takes into consideration the similarity between the architecture graph of the given NISQ device and a graph induced by the input logical circuit and (ii) searching, in a filtered and depth-limited way, a most usefulswapcombination that makes executable as many as possible two-qubit gates in the logical circuit. The proposed circuit transformation algorithm can significantly decrease the number of auxiliary two-qubit gates required to be added to the logical circuit, especially when it has a large number of two-qubit gates. For an extensive benchmark set of 131 circuits and IBM's current premium Q system, viz., IBM Q Tokyo, our algorithm needs, in average, 0.3801 extra two-qubit gates per input two-qubit gate, while the corresponding figures for three state-of-the-art algorithms are 0.4705, 0.8154, and 1.0066, respectively.
In the paper, we consider quantum circuits for the Quantum Fourier Transform (QFT) algorithm. The QFT algorithm is a very popular technique used in many quantum algorithms. We present a generic method for constructing quantum circuits for this algorithm implementing on quantum devices with restrictions. Many quantum devices (for example, based on superconductors) have restrictions on applying two-qubit gates. These restrictions are presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture of the qubit connection, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit for implementing on such architecture. We compare quantum circuits built by our algorithm with existing quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, ``sun'' (a cycle with tails, presented by the 16-qubit IBMQ device) and ``two joint suns'' (two joint cycles with tails, presented by the 27-qubit IBMQ device). Our generic method gives similar results with existing optimized circuits for ``sun'' and ``two joint suns'' architectures, and a circuit with slightly more CNOT gates for the LNN architecture. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.