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

The synthesis of nearest neighbour compliant quantum circuits

Leo Rogers

Published Oct 1, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.17034/32631069

Related papers

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 New Heuristic for $N$ -Dimensional Nearest Neighbor Realization of a Quantum Circuit

Abhoy Kole, Kamalika Datta, Indranil Sengupta

One of the main challenges in quantum computing is to ensure error-free operation of the basic quantum gates. There are various implementation technologies of quantum gates for which the distance between interacting qubits must be kept within a limit for reliable operation. This leads to the so-called requirement of neighborhood arrangements of the interacting qubits, often referred to as nearest neighbor (NN) constraint. This is typically achieved by inserting SWAP gates in the quantum circuits, where a SWAP gate between two qubits exchanges their states. Minimizing the number of SWAP gates to provide NN compliance is an important problem to solve. A number of approaches have been proposed in this regard, based on local and global ordering techniques. In this paper, a generalized approach for combined local and global ordering of qubits have been proposed that is based on an improved heuristic for cost estimation and is also scalable. The approach can be extended to N -dimensional arrangement of qubits, for any arbitrary values of N . Practical constraints, however, restrict the maximum value of N to 3. Extensive experiments on benchmark functions have been carried out to evaluate the performance in terms of SWAP gate requirements. 3-D organization of qubits shows average reductions of 6.7% and 37.4%, respectively, in the number of SWAP gates over 2-D and 1-D organizations. Also compared to the best 2-D and 1-D results reported in the literature, on the average 8.7% and 8.4% reductions, respectively, are observed.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Apr 18, 2017•68 citations

Efficient Design of Quantum Circuits Using Nearest Neighbor Constraint in 3D Architecture

Leniency Marbaniang, Kamalika Datta

Synthesis and optimization of quantum circuits have received significant attention from researchers in recent years. Developments in the physical realization of qubits in quantum computing have led to new physical constraints to be addressed. One of the most important constraints that is considered by many researchers is the nearest neighbor constraint which limits the interaction distance between qubits for quantum gate operations. Various works have been reported in the literature that deal with nearest neighbor compliance in multi-dimensional (mostly 1D and 2D) qubit arrangements. This is normally achieved by inserting SWAP gates in the gate netlist to bring the interacting qubits closer together. The main objective function to minimize here is the number of SWAP gates. The present paper proposes an efficient qubit placement strategy in a three-dimensional (3D) grid that considers not only qubit interactions but also the relative positions of the gates in the circuit. Experimental evaluation on a number of benchmark circuits show that the proposed method reduces the number of SWAP gates by 16.2% to 47.0% on the average as compared to recently published works.

Journal of Circuits Systems and Computers•Jun 24, 2018•5 citations

Window Size Estimation for Nearest Neighbour Compliant Quantum Circuit Mapping

Leo Rogers, John McAllister

In general, quantum circuits permit any two logical qubits to be combined via a quantum gate. When these are to be deployed on locally-connected grid-shaped quantum processors, swap operations are required to make adjacent interacting qubits. Swap insertion algorithms are complex and time-consuming. Windowing limits this complexity by considering only a subset of the circuit's gates when inserting swaps, but has not been applied to the latest generation of swap insertion algorithms, nor has any systematic method been proposed for determining the appropriate window length. This paper shows how off-line analysis of swap density across the circuit identifies thresholds for window length which limit increases in the number of swap gates. When adopted, speed-ups in the swap insertion process asymptotically approach 100% with the length of the circuit, whilst maintaining swap costs at comparable levels to non-windowed algorithms.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2019•0 citations

BQA: A High-performance Quantum Circuits Scheduling Strategy Based on Heuristic Search

Xin-miao Chen, Shi Wang, Yong-jin Ye +2 more

Currently, quantum computing is developing at a high speed because its high parallelism and high computing power bring new solutions to many fields. However, due to chip process technology, it is difficult to achieve full coupling of all qubits on a quantum chip, so when compiling a quantum circuit onto a physical chip, it is necessary to ensure that the two-qubit gate acts on a pair of coupled qubits by inserting swap gates. It will cause great additional cost when a large number of swap gates are inserted, leading to the execution time of quantum circuits longer. In this paper, we designed a way based on the business to insert swap gates BQA(Busy Qubits Avoid). We exploit the imbalance of the number of gates on qubits, trying to hide the overhead of swap gates. At the same time, we also expect swap gates to make as little negative impact on subsequent two-qubit gates as possible. We have designed a heuristic function that can take into account both of these points. Compared with qiskit, the execution time of the circuit optimized by our proposed method is only 0.5 times that of the qiskit compiled circuit. And when the number of two-qubit gates is large, it will achieve higher level than general conditions. This implies higher execution efficiency and lower decoherence error rate.

arXiv:2209.03542•Sep 8, 2022•0 citations

2D Qubit Placement of Quantum Circuits using LONGPATH

Ghosh, Mrityunjay, Nivedita Dey, Debdeep Mitra +1 more

In order to achieve speedup over conventional classical computing for finding solution of computationally hard problems, quantum computing was introduced. Quantum algorithms can be simulated in a pseudo quantum environment, but implementation involves realization of quantum circuits through physical synthesis of quantum gates. This requires decomposition of complex quantum gates into a cascade of simple one qubit and two qubit gates. The methodological framework for physical synthesis imposes a constraint regarding placement of operands (qubits) and operators. If physical qubits can be placed on a grid, where each node of the grid represents a qubit then quantum gates can only be operated on adjacent qubits, otherwise SWAP gates must be inserted to convert non-Linear Nearest Neighbor architecture to Linear Nearest Neighbor architecture. Insertion of SWAP gates should be made optimal to reduce cumulative cost of physical implementation. A schedule layout generation is required for placement and routing apriori to actual implementation. In this paper, two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. The first algorithm is intended to start with generation of an interaction graph followed by finding the longest path starting from the node with maximum degree. The second algorithm optimizes the number of SWAP gates between any pair of non-neighbouring qubits. Our proposed approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.

arXiv:2007.06804•Jul 14, 2020•1 citation
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.
A New Heuristic for NNN -Dimensional Nearest Neighbor Realization of a Quantum Circuit
One of the main challenges in quantum computing is to ensure error-free operation of the basic quantum gates. There are various implementation technologies of quantum gates for which the distance between interacting qubits must be kept within a limit for reliable operation. This leads to the so-called requirement of neighborhood arrangements of the interacting qubits, often referred to as nearest neighbor (NN) constraint. This is typically achieved by inserting SWAP gates in the quantum circuits, where a SWAP gate between two qubits exchanges their states. Minimizing the number of SWAP gates to provide NN compliance is an important problem to solve. A number of approaches have been proposed in this regard, based on local and global ordering techniques. In this paper, a generalized approach for combined local and global ordering of qubits have been proposed that is based on an improved heuristic for cost estimation and is also scalable. The approach can be extended to N -dimensional arrangement of qubits, for any arbitrary values of N . Practical constraints, however, restrict the maximum value of N to 3. Extensive experiments on benchmark functions have been carried out to evaluate the performance in terms of SWAP gate requirements. 3-D organization of qubits shows average reductions of 6.7% and 37.4%, respectively, in the number of SWAP gates over 2-D and 1-D organizations. Also compared to the best 2-D and 1-D results reported in the literature, on the average 8.7% and 8.4% reductions, respectively, are observed.
Synthesis and optimization of quantum circuits have received significant attention from researchers in recent years. Developments in the physical realization of qubits in quantum computing have led to new physical constraints to be addressed. One of the most important constraints that is considered by many researchers is the nearest neighbor constraint which limits the interaction distance between qubits for quantum gate operations. Various works have been reported in the literature that deal with nearest neighbor compliance in multi-dimensional (mostly 1D and 2D) qubit arrangements. This is normally achieved by inserting SWAP gates in the gate netlist to bring the interacting qubits closer together. The main objective function to minimize here is the number of SWAP gates. The present paper proposes an efficient qubit placement strategy in a three-dimensional (3D) grid that considers not only qubit interactions but also the relative positions of the gates in the circuit. Experimental evaluation on a number of benchmark circuits show that the proposed method reduces the number of SWAP gates by 16.2% to 47.0% on the average as compared to recently published works.
In general, quantum circuits permit any two logical qubits to be combined via a quantum gate. When these are to be deployed on locally-connected grid-shaped quantum processors, swap operations are required to make adjacent interacting qubits. Swap insertion algorithms are complex and time-consuming. Windowing limits this complexity by considering only a subset of the circuit's gates when inserting swaps, but has not been applied to the latest generation of swap insertion algorithms, nor has any systematic method been proposed for determining the appropriate window length. This paper shows how off-line analysis of swap density across the circuit identifies thresholds for window length which limit increases in the number of swap gates. When adopted, speed-ups in the swap insertion process asymptotically approach 100% with the length of the circuit, whilst maintaining swap costs at comparable levels to non-windowed algorithms.
Currently, quantum computing is developing at a high speed because its high parallelism and high computing power bring new solutions to many fields. However, due to chip process technology, it is difficult to achieve full coupling of all qubits on a quantum chip, so when compiling a quantum circuit onto a physical chip, it is necessary to ensure that the two-qubit gate acts on a pair of coupled qubits by inserting swap gates. It will cause great additional cost when a large number of swap gates are inserted, leading to the execution time of quantum circuits longer. In this paper, we designed a way based on the business to insert swap gates BQA(Busy Qubits Avoid). We exploit the imbalance of the number of gates on qubits, trying to hide the overhead of swap gates. At the same time, we also expect swap gates to make as little negative impact on subsequent two-qubit gates as possible. We have designed a heuristic function that can take into account both of these points. Compared with qiskit, the execution time of the circuit optimized by our proposed method is only 0.5 times that of the qiskit compiled circuit. And when the number of two-qubit gates is large, it will achieve higher level than general conditions. This implies higher execution efficiency and lower decoherence error rate.
In order to achieve speedup over conventional classical computing for finding solution of computationally hard problems, quantum computing was introduced. Quantum algorithms can be simulated in a pseudo quantum environment, but implementation involves realization of quantum circuits through physical synthesis of quantum gates. This requires decomposition of complex quantum gates into a cascade of simple one qubit and two qubit gates. The methodological framework for physical synthesis imposes a constraint regarding placement of operands (qubits) and operators. If physical qubits can be placed on a grid, where each node of the grid represents a qubit then quantum gates can only be operated on adjacent qubits, otherwise SWAP gates must be inserted to convert non-Linear Nearest Neighbor architecture to Linear Nearest Neighbor architecture. Insertion of SWAP gates should be made optimal to reduce cumulative cost of physical implementation. A schedule layout generation is required for placement and routing apriori to actual implementation. In this paper, two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. The first algorithm is intended to start with generation of an interaction graph followed by finding the longest path starting from the node with maximum degree. The second algorithm optimizes the number of SWAP gates between any pair of non-neighbouring qubits. Our proposed approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.