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

Vestnik Tomskogo gosudarstvennogo universiteta Upravlenie vychislitel naya tekhnika i informatika

Quantum circuit optimization via local qubit reordering by quantum annealing

Maria Maltseva

Published Jan 1, 2024• 0 citations
Publisher

Abstract

Mapping quantum circuits to the nearest-neighbor topology architecture requires additional gates. In this paper, we propose a hybrid approach to optimize quantum circuits for the two-dimensional nearest-neighbor architecture based on graph partitioning and solving SAT problem using quantum annealing. The technique's applicability and solution quality are studied via real experiments.

DOI
10.17223/19988605/69/11

Related papers

Quantum Circuit Optimization Via Graph Partitioning by Quantum Annealing

Maria Maltseva, Enrico Blanzieri, Alexander Rumyantsev

Abstract In quantum computing hardware, physical limitations are defining the connectivity of qubits, with Linear Nearest Neighbor being a convenient ordering for quantum mapping. To make quantum circuit Linear Nearest Neighbor-compatible, significant overhead (given by the so-called Nearest Neighbor Cost) may be caused by a set of additional gates necessary to make qubit lines of each gate of the circuit adjacent. In this work, the problem of quantum circuit optimization for Linear Nearest Neighbor architecture according to Nearest Neighbor Cost is treated by global qubit lines reordering. Such a reordering may be obtained as a result of graph partitioning heuristics. In this paper, we perform recursive graph partitioning on a quantum annealing hardware, thus making use of quantum optimizer to optimize a quantum circuit, to the best of our knowledge, for the first time. Extensive numerical experiments are performed for several circuits from various quantum circuit libraries, which demonstrate perspectives of the proposed approach.

Lobachevskii Journal of Mathematics•Oct 1, 2024•1 citation

Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures

Massoud Pedram, Alireza Shafaei

This paper is concerned with the physical design of quantum logic circuits. More precisely, it addresses the problem of minimizing the number of required qubit reorderings (achieved by inserting explicit SWAP gates) when mapping a quantum circuit into a linear nearest neighbor quantum archi-tecture. First, an interaction graph that captures the interaction distances among various qubits in the quantum circuit is constructed. The interaction graph is utilized to partition the quantum circuit into a set of subcircuits such that the number of required qubit reoderings within each subcircuit is provably no more than a given threshold. Next, a Minimum Linear Arrangement problem for each subcircuit is formulated and solved to achieve the minimum number of internal qubit reorderings and determine the subcircuit input and output qubit orderings. Finally, a bubble sort algorithm is repeatedly employed to minimize the number of qubit reorderings that are required between the consecutive subcircuits. Experiments done on various quantum Fourier transform circuits as well as various reversible logic circuits demonstrate the effectiveness of the proposed approach.

IEEE Circuits and Systems Magazine•Jan 1, 2016•42 citations

Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning

Amlan Chakrabarti, Susmita Sur‐Kolay, Ayan Chaudhury

Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.

arXiv:1112.0564•Dec 2, 2011•48 citations

Fast Qubit Placement in 2D Architecture Using Nearest Neighbor Realization

Ritu Ranjan Shrivastwa, Kamalika Datta, Indranil Sengupta

Design and synthesis of quantum circuits have gained huge momentum during the last few years. With various physical constraint sone of the major issues is in making quantum circuits nearest neighbor complaint. The existing one and two dimensional architectures for the placement of qubits does not scale well for larger circuits. The situation thus demands for a faster approach to solve the problem. To make a quantum circuit nearest neighbor compliant, SWAP gates are inserted in the quantum gate circuit to bring the interacting qubits of a gate adjacent. We have proposed a faster method with a simple yet effective algorithm to minimize the number of SWAP gates for adjacent interactions. The time required for processing does not exceed one second even for larger benchmark circuits. The proposed method is found to reduce the number of SWAP gates on an average by 9.5% compared to the best results in previous works on 2D architectures, and by 45.7% compared to the best results on 1D architecture.

IEEE International Symposium on Nanoelectronic and Information Systems (iNIS)•Dec 1, 2015•42 citations

A method of mapping and nearest neighbor optimization for 2-D quantum circuits

Yuxin Zhang, Zhijin Guan, Longyong Ji +2 more

In some practical quantum physical architectures, the qubits need to be distributed on 2-dimensional (2-D) grid structure to implement quantum computation. In order to map an 1-dimensional (1-D) quantum circuit into a 2-D grid structure and satisfy the nearest neighbor constraint of qubit interaction in the grid structure, a mapping method from 1-D quantum circuit to 2-D grid structure is proposed in this paper. This method firstly determines the order of placing qubits, and then presents the layout strategy of qubits in 2-D grid. We also proposed an algorithm for establishing interaction paths between non-adjacent qubits in 2-D grid structure, which can satisfy the physical constraints of the interaction of quantum bits in the grid in the process of mapping an 1-D quantum circuit to a 2-D grid structure. For some benchmark circuits, after using the method of this paper to place qubits, it is possible to make every 2-qubit gate in the circuit have a nearest neighbor, so that there is no need to use SWAP gate to establish channel routing. Compared with the latest available methods, the average optimization rate is 82.38%.

Quantum Information and Computation•Mar 1, 2020•1 citation

Exact Reordering of Circuit Lines for Nearest Neighbor Quantum Architectures

Robert Wille, Aaron Lye, Rolf Drechsler

Research in the domain of quantum computation is mainly driven by their promising applications e.g., for factorization or database search. At the same time, physical developments for this emerging technology constantly lead to new constraints to be addressed by logic designers. The limited interaction distance between qubits, the elementary information storage in quantum circuits, is one of the most common restrictions, leading to the fact that, for many quantum architectures, computations can only be performed on adjacent (i.e., nearest neighbor) qubits. Motivated by that, optimization of quantum circuits with respect to this restriction has become an intensely considered research topic. In this paper, we briefly review existing approaches that have been proposed in the past for this purpose. We particularly consider that almost all existing solutions are of heuristic nature, i.e., do not guarantee an optimal solution. In order to address this, exact alternatives are introduced which make use of the deductive power of constraint solvers. By this, we are able to perform a qualitative evaluation of the performance of existing (heuristic) solutions for linear nearest neighbor quantum circuit optimization.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Nov 26, 2014•98 citations
Mapping quantum circuits to the nearest-neighbor topology architecture requires additional gates. In this paper, we propose a hybrid approach to optimize quantum circuits for the two-dimensional nearest-neighbor architecture based on graph partitioning and solving SAT problem using quantum annealing. The technique's applicability and solution quality are studied via real experiments.
Abstract In quantum computing hardware, physical limitations are defining the connectivity of qubits, with Linear Nearest Neighbor being a convenient ordering for quantum mapping. To make quantum circuit Linear Nearest Neighbor-compatible, significant overhead (given by the so-called Nearest Neighbor Cost) may be caused by a set of additional gates necessary to make qubit lines of each gate of the circuit adjacent. In this work, the problem of quantum circuit optimization for Linear Nearest Neighbor architecture according to Nearest Neighbor Cost is treated by global qubit lines reordering. Such a reordering may be obtained as a result of graph partitioning heuristics. In this paper, we perform recursive graph partitioning on a quantum annealing hardware, thus making use of quantum optimizer to optimize a quantum circuit, to the best of our knowledge, for the first time. Extensive numerical experiments are performed for several circuits from various quantum circuit libraries, which demonstrate perspectives of the proposed approach.
This paper is concerned with the physical design of quantum logic circuits. More precisely, it addresses the problem of minimizing the number of required qubit reorderings (achieved by inserting explicit SWAP gates) when mapping a quantum circuit into a linear nearest neighbor quantum archi-tecture. First, an interaction graph that captures the interaction distances among various qubits in the quantum circuit is constructed. The interaction graph is utilized to partition the quantum circuit into a set of subcircuits such that the number of required qubit reoderings within each subcircuit is provably no more than a given threshold. Next, a Minimum Linear Arrangement problem for each subcircuit is formulated and solved to achieve the minimum number of internal qubit reorderings and determine the subcircuit input and output qubit orderings. Finally, a bubble sort algorithm is repeatedly employed to minimize the number of qubit reorderings that are required between the consecutive subcircuits. Experiments done on various quantum Fourier transform circuits as well as various reversible logic circuits demonstrate the effectiveness of the proposed approach.
Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.
Design and synthesis of quantum circuits have gained huge momentum during the last few years. With various physical constraint sone of the major issues is in making quantum circuits nearest neighbor complaint. The existing one and two dimensional architectures for the placement of qubits does not scale well for larger circuits. The situation thus demands for a faster approach to solve the problem. To make a quantum circuit nearest neighbor compliant, SWAP gates are inserted in the quantum gate circuit to bring the interacting qubits of a gate adjacent. We have proposed a faster method with a simple yet effective algorithm to minimize the number of SWAP gates for adjacent interactions. The time required for processing does not exceed one second even for larger benchmark circuits. The proposed method is found to reduce the number of SWAP gates on an average by 9.5% compared to the best results in previous works on 2D architectures, and by 45.7% compared to the best results on 1D architecture.
In some practical quantum physical architectures, the qubits need to be distributed on 2-dimensional (2-D) grid structure to implement quantum computation. In order to map an 1-dimensional (1-D) quantum circuit into a 2-D grid structure and satisfy the nearest neighbor constraint of qubit interaction in the grid structure, a mapping method from 1-D quantum circuit to 2-D grid structure is proposed in this paper. This method firstly determines the order of placing qubits, and then presents the layout strategy of qubits in 2-D grid. We also proposed an algorithm for establishing interaction paths between non-adjacent qubits in 2-D grid structure, which can satisfy the physical constraints of the interaction of quantum bits in the grid in the process of mapping an 1-D quantum circuit to a 2-D grid structure. For some benchmark circuits, after using the method of this paper to place qubits, it is possible to make every 2-qubit gate in the circuit have a nearest neighbor, so that there is no need to use SWAP gate to establish channel routing. Compared with the latest available methods, the average optimization rate is 82.38%.
Research in the domain of quantum computation is mainly driven by their promising applications e.g., for factorization or database search. At the same time, physical developments for this emerging technology constantly lead to new constraints to be addressed by logic designers. The limited interaction distance between qubits, the elementary information storage in quantum circuits, is one of the most common restrictions, leading to the fact that, for many quantum architectures, computations can only be performed on adjacent (i.e., nearest neighbor) qubits. Motivated by that, optimization of quantum circuits with respect to this restriction has become an intensely considered research topic. In this paper, we briefly review existing approaches that have been proposed in the past for this purpose. We particularly consider that almost all existing solutions are of heuristic nature, i.e., do not guarantee an optimal solution. In order to address this, exact alternatives are introduced which make use of the deductive power of constraint solvers. By this, we are able to perform a qualitative evaluation of the performance of existing (heuristic) solutions for linear nearest neighbor quantum circuit optimization.