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

Scientific Reports

Quantum annealing for nearest neighbour compliance problem

Sven Müller, Frank Phillipson

Published Oct 7, 2024• 2 citations
Publisher

Abstract

Quantum Computing has emerged as a promising alternative, utilising quantum mechanics for faster computations. This paper explores the nearest neighbour compliance (NNC) Problem in Gate-based Quantum Computers, where quantum gates are constrained to operate on physically adjacent qubits. The NNC problem aims to optimise the insertion of SWAP-gates to ensure compliance with these constraints while minimising their count. This work introduces Quantum Annealing to tackle the NNC problem, proposing two Quadratic Unconstrained Optimisation Problem formulations. The formulations are tested on a contemporary Quantum Annealer, and their performance is compared with previous methods. It shows that the prospect of using Quantum Annealing is promising, however, the current state of the hardware makes that finding the embedding is the limiting factor.

DOI
10.1038/s41598-024-73882-y

Related papers

Exploiting symmetries in optimal quantum circuit design

Frank de Meijer, Dion Gijswijt, Renata Sotirov

A physical limitation in quantum circuit design is the fact that gates in a quantum system can only act on qubits that are physically adjacent in the architecture. To overcome this problem, SWAP gates need to be inserted to make the circuit physically realizable. The nearest neighbour compliance problem (NNCP) asks for an optimal embedding of qubits in a given architecture such that the total number of SWAP gates to be inserted is minimized. In this paper we study the NNCP on general quantum architectures. Building upon an existing linear programming formulation, we show how the model can be reduced by exploiting the symmetries of the graph underlying the formulation. The resulting model is equivalent to a generalized network flow problem and follows from an in-depth analysis of the automorphism group of specific Cayley graphs. As a byproduct of our approach, we show that the NNCP is polynomial time solvable for several classes of symmetric quantum architectures. Numerical tests on various architectures indicate that the reduction in the number of variables and constraints is on average at least 90%. In particular, NNCP instances on the star architecture can be solved for quantum circuits up to 100 qubits and more than 1000 quantum gates within a very short computation time. These results are far beyond the computational capacity when solving the instances without the exploitation of symmetries.

arXiv:2401.08262•Discrete Optimization•Dec 16, 2025•2 citations

Optimal SWAP gate insertion for nearest neighbor quantum circuits

Robert Wille, Aaron Lye, Rolf Drechsler

Motivated by its promising applications e.g. for database search or factorization, significant progress has been made in the development of automated design methods for quantum circuits. But in order to keep up with recent physical developments in this domain, new technological constraints have to be considered. Limited interaction distance between gate qubits is one of the most common of these constraints. This led to the development of several strategies aiming at making a given quantum circuit nearest neighbor-compliant by inserting SWAP gates into the existing structure. Usually these strategies are of heuristic nature. In this work, we present an exact approach that enables nearest neighbor-compliance by inserting a minimal number of SWAP gates. Experiments demonstrate the applicability of the approach which enabled a comparison of results obtained by heuristic methods to the actual optimum.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2014•101 citations

Improving the Designs of Nearest Neighbour Quantum Circuits for 1D and 2D Architectures

Chandan Bandyopadhyay, Anirban Bhattacharjee, Robert Wille +2 more

In recent years, the semiconductor industry is increasingly considering alternative computation schemes and in this conjuncture quantum computing has come up as a promising alternative due its ability to perform parallel computations (by exploiting superposition) and capacity to solve some of the intractable problems exponentially faster. But one of the criteria in the realization of quantum circuits is that corresponding descriptions demand a so-called nearest neighbour (NN) constraint to be satisfied. One of the possible solutions towards satisfying such constraints is through the insertion of SWAP gates that makes the qubit interactions within a gate adjacent. But since the incorporation of SWAP gates increases the cost of the circuits, strategies should be employed which satisfy the NN constraint while placing SWAP gates so that the cost are reduced. In this work, we propose improved design strategies to realize low-cost NN-compliant quantum circuits. Two approaches are introduced, where the first approach relies on a graph traversal process and uses heuristics in critical decision-making conditions to design a 1D NN-compliant representation. The second approach considers qubit-to-qubit interactions and realizes the circuits in a 2D platform based on some weighted metric. Both the designs are evaluated over a wide spectrum of benchmarks and results have been compared with related works. In those comparisons, we have seen that our approaches perform fairly better than the reported ones.

IETE Journal of Research•Sep 27, 2020•6 citations

Look-ahead schemes for nearest neighbor optimization of 1D and 2D quantum circuits

Robert Wille, Oliver Keszöcze, Marcel Walter +3 more

Ensuring nearest neighbor compliance of quantum circuits by inserting SWAP gates has heavily been considered in the past. Here, quantum gates are considered which work on non-adjacent qubits. SWAP gates are applied in order to “move” these qubits onto adjacent positions. However, a decision how exactly the SWAPs are “moved” has mainly been made without considering the effect a “movement” of qubits may have on the remaining circuit. In this work, we propose a methodology for nearest neighbor optimization which addresses this problem by means of a look-ahead scheme. To this end, two representative implementations are presented and discussed in detail. Experimental evaluations show that, in the best case, reductions in the number of SWAP gates of 56% (compared to the state-of-the-art methods) can be achieved following the proposed methodology.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2016•125 citations

The synthesis of nearest neighbour compliant quantum circuits

Leo Rogers

Quantum computers are reaching the size necessary to begin to perform useful tasks, however they are still limited by noise. One source of this noise is the error rate of the physical gates the processor uses. This means that when compiling high level quantum programs into executable code, it is vitally important to minimise the number of gates in the executable. It is common for physical qubits to be restricted in which other qubits they can interact with. To meet this constraint, swap gates must be inserted to route logical qubits around the processor. Minimising the number of swap gates inserted is known to be an intractable problem for all but small circuits, which means heuristics must be employed. When using heuristics, there is a trade-off between the run-time and the performance. The run-time/performance trade-off was investigated for a variety of functions which determine how important each gate should be based on its position in the circuit, and it was found that while the quadratic decreasing weight function from the literature had the lowest swap cost, the previously unstudied linear decreasing weight function was faster. Averaged over a number of large random circuits, the relative run-time improvement of the linear function compared to the quadratic outweighs the increase in swap cost. To reduce the time taken to find an initial placement, a method of random sampling was proposed. The distribution of the swap costs for random circuits was modelled as a normal distribution to approximate how many random placements need to be inspected in order to find one within a certain distance of the optimum. It was experimentally observed that when taking a random sample of 100 placements, the best placement in the sample was below the predicted 10th percentile of all placements 96.85% of the time, averaged over physical qubit arrays with between 10 and 16 qubits in varying arrangements. A method for an offline estimation of the number of gates that should be considered when choosing the placement and swap gates was proposed. This speeds up the compilation process by ensuring the swap insertion pass only needs to be performed once per circuit, with negligible difference in swap cost. When generating a circuit whose only purpose is to move the logical qubits from one layout to another, the A* algorithm is guaranteed to find the smallest circuit. The time complexity of A* depends on the quality of the heuristic, and this thesis proposes a new heuristic which significantly outperforms the previous heuristic, and in some circumstances is shown to behave optimally. The swap insertion pass of a circuit can be parallelised by splitting it up into subcircuits, however doing so will affect the swap cost. This thesis calculates the relationship between the number of subcircuits and the swap cost, which brings the estimation of the optimal number of subcircuits offline. This speeds up the compilation of a circuit compared to methods which try multiple different numbers of subcircuits in order to choose the best.

•Oct 1, 2026•0 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•43 citations
Quantum Computing has emerged as a promising alternative, utilising quantum mechanics for faster computations. This paper explores the nearest neighbour compliance (NNC) Problem in Gate-based Quantum Computers, where quantum gates are constrained to operate on physically adjacent qubits. The NNC problem aims to optimise the insertion of SWAP-gates to ensure compliance with these constraints while minimising their count. This work introduces Quantum Annealing to tackle the NNC problem, proposing two Quadratic Unconstrained Optimisation Problem formulations. The formulations are tested on a contemporary Quantum Annealer, and their performance is compared with previous methods. It shows that the prospect of using Quantum Annealing is promising, however, the current state of the hardware makes that finding the embedding is the limiting factor.
A physical limitation in quantum circuit design is the fact that gates in a quantum system can only act on qubits that are physically adjacent in the architecture. To overcome this problem, SWAP gates need to be inserted to make the circuit physically realizable. The nearest neighbour compliance problem (NNCP) asks for an optimal embedding of qubits in a given architecture such that the total number of SWAP gates to be inserted is minimized. In this paper we study the NNCP on general quantum architectures. Building upon an existing linear programming formulation, we show how the model can be reduced by exploiting the symmetries of the graph underlying the formulation. The resulting model is equivalent to a generalized network flow problem and follows from an in-depth analysis of the automorphism group of specific Cayley graphs. As a byproduct of our approach, we show that the NNCP is polynomial time solvable for several classes of symmetric quantum architectures. Numerical tests on various architectures indicate that the reduction in the number of variables and constraints is on average at least 90%. In particular, NNCP instances on the star architecture can be solved for quantum circuits up to 100 qubits and more than 1000 quantum gates within a very short computation time. These results are far beyond the computational capacity when solving the instances without the exploitation of symmetries.
Motivated by its promising applications e.g. for database search or factorization, significant progress has been made in the development of automated design methods for quantum circuits. But in order to keep up with recent physical developments in this domain, new technological constraints have to be considered. Limited interaction distance between gate qubits is one of the most common of these constraints. This led to the development of several strategies aiming at making a given quantum circuit nearest neighbor-compliant by inserting SWAP gates into the existing structure. Usually these strategies are of heuristic nature. In this work, we present an exact approach that enables nearest neighbor-compliance by inserting a minimal number of SWAP gates. Experiments demonstrate the applicability of the approach which enabled a comparison of results obtained by heuristic methods to the actual optimum.
In recent years, the semiconductor industry is increasingly considering alternative computation schemes and in this conjuncture quantum computing has come up as a promising alternative due its ability to perform parallel computations (by exploiting superposition) and capacity to solve some of the intractable problems exponentially faster. But one of the criteria in the realization of quantum circuits is that corresponding descriptions demand a so-called nearest neighbour (NN) constraint to be satisfied. One of the possible solutions towards satisfying such constraints is through the insertion of SWAP gates that makes the qubit interactions within a gate adjacent. But since the incorporation of SWAP gates increases the cost of the circuits, strategies should be employed which satisfy the NN constraint while placing SWAP gates so that the cost are reduced. In this work, we propose improved design strategies to realize low-cost NN-compliant quantum circuits. Two approaches are introduced, where the first approach relies on a graph traversal process and uses heuristics in critical decision-making conditions to design a 1D NN-compliant representation. The second approach considers qubit-to-qubit interactions and realizes the circuits in a 2D platform based on some weighted metric. Both the designs are evaluated over a wide spectrum of benchmarks and results have been compared with related works. In those comparisons, we have seen that our approaches perform fairly better than the reported ones.
Ensuring nearest neighbor compliance of quantum circuits by inserting SWAP gates has heavily been considered in the past. Here, quantum gates are considered which work on non-adjacent qubits. SWAP gates are applied in order to “move” these qubits onto adjacent positions. However, a decision how exactly the SWAPs are “moved” has mainly been made without considering the effect a “movement” of qubits may have on the remaining circuit. In this work, we propose a methodology for nearest neighbor optimization which addresses this problem by means of a look-ahead scheme. To this end, two representative implementations are presented and discussed in detail. Experimental evaluations show that, in the best case, reductions in the number of SWAP gates of 56% (compared to the state-of-the-art methods) can be achieved following the proposed methodology.
Quantum computers are reaching the size necessary to begin to perform useful tasks, however they are still limited by noise. One source of this noise is the error rate of the physical gates the processor uses. This means that when compiling high level quantum programs into executable code, it is vitally important to minimise the number of gates in the executable. It is common for physical qubits to be restricted in which other qubits they can interact with. To meet this constraint, swap gates must be inserted to route logical qubits around the processor. Minimising the number of swap gates inserted is known to be an intractable problem for all but small circuits, which means heuristics must be employed. When using heuristics, there is a trade-off between the run-time and the performance. The run-time/performance trade-off was investigated for a variety of functions which determine how important each gate should be based on its position in the circuit, and it was found that while the quadratic decreasing weight function from the literature had the lowest swap cost, the previously unstudied linear decreasing weight function was faster. Averaged over a number of large random circuits, the relative run-time improvement of the linear function compared to the quadratic outweighs the increase in swap cost. To reduce the time taken to find an initial placement, a method of random sampling was proposed. The distribution of the swap costs for random circuits was modelled as a normal distribution to approximate how many random placements need to be inspected in order to find one within a certain distance of the optimum. It was experimentally observed that when taking a random sample of 100 placements, the best placement in the sample was below the predicted 10th percentile of all placements 96.85% of the time, averaged over physical qubit arrays with between 10 and 16 qubits in varying arrangements. A method for an offline estimation of the number of gates that should be considered when choosing the placement and swap gates was proposed. This speeds up the compilation process by ensuring the swap insertion pass only needs to be performed once per circuit, with negligible difference in swap cost. When generating a circuit whose only purpose is to move the logical qubits from one layout to another, the A* algorithm is guaranteed to find the smallest circuit. The time complexity of A* depends on the quality of the heuristic, and this thesis proposes a new heuristic which significantly outperforms the previous heuristic, and in some circumstances is shown to behave optimally. The swap insertion pass of a circuit can be parallelised by splitting it up into subcircuits, however doing so will affect the swap cost. This thesis calculates the relationship between the number of subcircuits and the swap cost, which brings the estimation of the optimal number of subcircuits offline. This speeds up the compilation of a circuit compared to methods which try multiple different numbers of subcircuits in order to choose the best.
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.