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

Russian Microelectronics

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

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

Published Dec 1, 2025• 2 citations
Publisher

Abstract

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.

DOI
10.1134/s1063739725602073

Related papers

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

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

Reducing the CNOT Count for Clifford+T Circuits on NISQ Architectures

Vlad Gheorghiu, Jiaxin Huang, Sarah Meng Li +2 more

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$\{\text {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.

arXiv:2011.12191•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 10, 2022•49 citations

Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search

Xiangzhen Zhou, Sanjiang Li, Yuan Feng

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.

arXiv:1908.08853•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Feb 2, 2020•84 citations

A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era

Siyuan Niu, Adrien Suau, Gabriel Staffelbach +1 more

Due to several physical limitations in the realization of quantum hardware, today's quantum computers are qualified as noisy intermediate-scale quantum (NISQ) hardware. NISQ hardware is characterized by a small number of qubits (50 to a few hundred) and noisy operations. Moreover, current realizations of superconducting quantum chips do not have the ideal all-to-all connectivity between qubits but rather at most a nearest-neighbor connectivity. All these hardware restrictions add supplementary low-level requirements. They need to be addressed before submitting the quantum circuit to an actual chip. Satisfying these requirements is a tedious task for the programmer. Instead, the task of adapting the quantum circuit to a given hardware is left to the compiler. In this article, we propose a hardware-aware (HA) mapping transition algorithm that takes the calibration data into account with the aim to improve the overall fidelity of the circuit. Evaluation results on IBM quantum hardware show that our HA approach can outperform the state of the art, both in terms of the number of additional gates and circuit fidelity.

arXiv:2010.03397•IEEE Transactions on Quantum Engineering•Jan 1, 2020•120 citations

Quantum circuit optimizations for NISQ architectures

Beatrice Nash, Vlad Gheorghiu, Michele Mosca

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).

arXiv:1904.01972•Quantum Science and Technology•Feb 25, 2020•153 citations
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.
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.
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.
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}\{\text {CNOT},{T}\}{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.
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.
Due to several physical limitations in the realization of quantum hardware, today's quantum computers are qualified as noisy intermediate-scale quantum (NISQ) hardware. NISQ hardware is characterized by a small number of qubits (50 to a few hundred) and noisy operations. Moreover, current realizations of superconducting quantum chips do not have the ideal all-to-all connectivity between qubits but rather at most a nearest-neighbor connectivity. All these hardware restrictions add supplementary low-level requirements. They need to be addressed before submitting the quantum circuit to an actual chip. Satisfying these requirements is a tedious task for the programmer. Instead, the task of adapting the quantum circuit to a given hardware is left to the compiler. In this article, we propose a hardware-aware (HA) mapping transition algorithm that takes the calibration data into account with the aim to improve the overall fidelity of the circuit. Evaluation results on IBM quantum hardware show that our HA approach can outperform the state of the art, both in terms of the number of additional gates and circuit fidelity.
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).