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

Routing of Quantum States in 2D Lattices

Changchun Zhong

Published Jan 1, 2017• 0 citations
OpenAlex

Abstract

Running quantum algorithms in a quantum machine may solve some complex problems that are intractable for even the most powerful classical computers. Quantum algorithms can be described by quantum circuits consisting of a set of qubits and a sequence of gates operating on those qubits when the quantum circuit model of computation is adopted. This circuit description on an algorithm usually assumes that any kind of interaction between qubits is possible. However, in real experiments, qubits are placed on a specific physical qubit layout, which constraints the possible interactions between qubits due to its limited connectivity. One possible layout for arranging qubits is a 2D array with 4 neighbours per qubit, which corresponds with the topology of surface code, one of the most promising quantum correction codes. In such 2D nearest-neighbour (NN) arrangement of qubits not all pairs of qubits that have to interact during computation can be directly connected (be neighbours). This means that non-adjacent qubits or qubit states need to be moved or routed (by e.g. SWAP operations) and be placed close to each other when required. In this thesis, we applied different routing algorithms used in Network on Chip (NoC) for defining the routing paths when quantum states are moved. After investigating 7 different NoC routing algorithms, we redesign and adapt them to the quantum scenario. We use the quantum plane simulation platform for comparing the routing overhead and the success rate of such routing algorithms when running 4 different quantum algorithms. We conclude that the routing algorithm which has the best overall routing performance is the one called Hot Potato. It is deadlock and livelock free in perfect qubit lattices, and shows the best fault-tolerance when faulty qubits are considered.

Related papers

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

Mapping quantum circuits on 3D nearest-neighbor architectures

Azim Farghadan, Naser Mohammadzadeh

Abstract In some quantum technologies, an interaction is only allowed between physically adjacent qubits, hence the nearest-neighbor requirement is needed. In such technologies, quantum gates are limited to operate on adjacent qubits. To make a quantum circuit compliant with the nearest-neighbor requirement, SWAP gates are inserted into the circuit to move the interacting qubits of a gate to be adjacent to each other. The mapping of qubits on the physical environment has an important role on reducing the number of SWAP gates and thus the circuit latency. Focusing on this issue, in this paper, a method is proposed that maps a quantum circuit onto a 3D physical hardware such as a 3D optical lattice. A new methodology for this mapping problem is proposed based on a complex network spectral clustering algorithm and graph theory, which are suitable for very large scale networks. It includes three steps: finding the order of qubit mapping, placing physical qubits, and routing. Simulation results show that the proposed mapping approach not only decreases the average number of SWAP gates by about 37% but also improves the average runtime by about 87% for the 2D architecture compared to PAQCS. Moreover, it reduces the average number of SWAP gates for the 3D architecture by 17.1% compared to the best studies in the literatures.

Quantum Science and Technology•Apr 9, 2019•11 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

Fault-tolerant quantum circuits on connectivity-constrained hardware with swap gates

Shao-Hen Chiew, E. I. Rodríguez Chiacchio, Vishal Sharma +2 more

In near-term quantum computing devices, connectivity between qubits remain limited by architectural constraints. A computational circuit with given connectivity requirements necessary for multiqubit gates has to be embedded within physical hardware with fixed connectivity. Long-distance gates have to be done by first routing the relevant qubits together. The simplest routing strategy involves the use of gates to swap the information carried by two unconnected qubits to connected ones. Ideal gates just permute the qubits; real gates, however, have the added possibilities of causing simultaneous errors on the qubits involved and spreading errors across the circuit. A general swap scheme thus changes the error-propagation properties of a circuit, including those necessary for fault-tolerant functioning of a circuit. Here, we present a simple strategy to design the swap scheme needed to embed an arbitrary circuit onto a physical hardware with constrained connectivity, in a manner that preserves the fault-tolerant properties of the abstract circuit. Our approach is generally applicable, and works on any circuit, including ones that carry out logical operations and error correction. The embedded circuit will, of course, be noisier, compared to a native implementation of the abstract circuit, but we show in the examples of embedding surface codes on heavy-hexagonal and hexagonal lattices that the deterioration is not severe. This then offers a straightforward solution to implementing circuits with fault-tolerance properties on current hardware.

arXiv:2406.17044•Physical Review Research•Jun 4, 2026•2 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

Quantum circuit physical design flow for 2D nearest‐neighbor architectures

Azim Farghadan, Naser Mohammadzadeh

Summary The physical design process takes a netlist generated by the logic synthesis process and places and routes the netlist on a physical platform. In some physical platforms, physical qubits must be placed on a 2D grid. Each node of the grid represents a qubit. In these platforms, performing quantum gates on non‐adjacent qubits is very error prone or hard to control. Therefore, quantum gates are limited to be performed on adjacent qubits. A communication channel of swap gates needs to be constructed if the qubits in the logical circuit are not adjacent. The algorithms used for mapping of qubits on the grid have important roles in reducing the number of swap gates and thus decreasing of the circuit latency. Focusing on this issue, in this paper, a flow for physical design of quantum circuits on a 2D grid is proposed. It contains three algorithms for finding the order of qubit placement, physical qubit placement, and routing. Simulation results show that the proposed flow not only decreases the average number of swap gates by about 16% compared with the best in the literature but also improves the average runtime by about 94% compared with it. Copyright © 2017 John Wiley & Sons, Ltd.

International Journal of Circuit Theory and Applications•Mar 17, 2017•28 citations
Running quantum algorithms in a quantum machine may solve some complex problems that are intractable for even the most powerful classical computers. Quantum algorithms can be described by quantum circuits consisting of a set of qubits and a sequence of gates operating on those qubits when the quantum circuit model of computation is adopted. This circuit description on an algorithm usually assumes that any kind of interaction between qubits is possible. However, in real experiments, qubits are placed on a specific physical qubit layout, which constraints the possible interactions between qubits due to its limited connectivity. One possible layout for arranging qubits is a 2D array with 4 neighbours per qubit, which corresponds with the topology of surface code, one of the most promising quantum correction codes. In such 2D nearest-neighbour (NN) arrangement of qubits not all pairs of qubits that have to interact during computation can be directly connected (be neighbours). This means that non-adjacent qubits or qubit states need to be moved or routed (by e.g. SWAP operations) and be placed close to each other when required. In this thesis, we applied different routing algorithms used in Network on Chip (NoC) for defining the routing paths when quantum states are moved. After investigating 7 different NoC routing algorithms, we redesign and adapt them to the quantum scenario. We use the quantum plane simulation platform for comparing the routing overhead and the success rate of such routing algorithms when running 4 different quantum algorithms. We conclude that the routing algorithm which has the best overall routing performance is the one called Hot Potato. It is deadlock and livelock free in perfect qubit lattices, and shows the best fault-tolerance when faulty qubits are considered.
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.
Abstract In some quantum technologies, an interaction is only allowed between physically adjacent qubits, hence the nearest-neighbor requirement is needed. In such technologies, quantum gates are limited to operate on adjacent qubits. To make a quantum circuit compliant with the nearest-neighbor requirement, SWAP gates are inserted into the circuit to move the interacting qubits of a gate to be adjacent to each other. The mapping of qubits on the physical environment has an important role on reducing the number of SWAP gates and thus the circuit latency. Focusing on this issue, in this paper, a method is proposed that maps a quantum circuit onto a 3D physical hardware such as a 3D optical lattice. A new methodology for this mapping problem is proposed based on a complex network spectral clustering algorithm and graph theory, which are suitable for very large scale networks. It includes three steps: finding the order of qubit mapping, placing physical qubits, and routing. Simulation results show that the proposed mapping approach not only decreases the average number of SWAP gates by about 37% but also improves the average runtime by about 87% for the 2D architecture compared to PAQCS. Moreover, it reduces the average number of SWAP gates for the 3D architecture by 17.1% compared to the best studies in the literatures.
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%.
In near-term quantum computing devices, connectivity between qubits remain limited by architectural constraints. A computational circuit with given connectivity requirements necessary for multiqubit gates has to be embedded within physical hardware with fixed connectivity. Long-distance gates have to be done by first routing the relevant qubits together. The simplest routing strategy involves the use of gates to swap the information carried by two unconnected qubits to connected ones. Ideal gates just permute the qubits; real gates, however, have the added possibilities of causing simultaneous errors on the qubits involved and spreading errors across the circuit. A general swap scheme thus changes the error-propagation properties of a circuit, including those necessary for fault-tolerant functioning of a circuit. Here, we present a simple strategy to design the swap scheme needed to embed an arbitrary circuit onto a physical hardware with constrained connectivity, in a manner that preserves the fault-tolerant properties of the abstract circuit. Our approach is generally applicable, and works on any circuit, including ones that carry out logical operations and error correction. The embedded circuit will, of course, be noisier, compared to a native implementation of the abstract circuit, but we show in the examples of embedding surface codes on heavy-hexagonal and hexagonal lattices that the deterioration is not severe. This then offers a straightforward solution to implementing circuits with fault-tolerance properties on current hardware.
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.
Summary The physical design process takes a netlist generated by the logic synthesis process and places and routes the netlist on a physical platform. In some physical platforms, physical qubits must be placed on a 2D grid. Each node of the grid represents a qubit. In these platforms, performing quantum gates on non‐adjacent qubits is very error prone or hard to control. Therefore, quantum gates are limited to be performed on adjacent qubits. A communication channel of swap gates needs to be constructed if the qubits in the logical circuit are not adjacent. The algorithms used for mapping of qubits on the grid have important roles in reducing the number of swap gates and thus decreasing of the circuit latency. Focusing on this issue, in this paper, a flow for physical design of quantum circuits on a 2D grid is proposed. It contains three algorithms for finding the order of qubit placement, physical qubit placement, and routing. Simulation results show that the proposed flow not only decreases the average number of swap gates by about 16% compared with the best in the literature but also improves the average runtime by about 94% compared with it. Copyright © 2017 John Wiley & Sons, Ltd.