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

arXiv:1703.08540

Depth-Optimal Quantum Circuit Placement for Arbitrary Topologies

Debjyoti Bhattacharjee, Anupam Chattopadhyay

Published Mar 24, 2017• 73 citations
arXivHTMLPDF

Abstract

A significant hurdle towards realization of practical and scalable quantum computing is to protect the quantum states from inherent noises during the computation. In physical implementation of quantum circuits, a long-distance interaction between two qubits is undesirable since, it can be interpreted as a noise. Therefore, multiple quantum technologies and quantum error correcting codes strongly require the interacting qubits to be arranged in a nearest neighbor (NN) fashion. The current literature on converting a given quantum circuit to an NN-arranged one mainly considered chained qubit topologies or Linear Nearest Neighbor (LNN) topology. However, practical quantum circuit realizations, such as Nuclear Magnetic Resonance (NMR), may not have an LNN topology. To address this gap, we consider an arbitrary qubit topology. We present an Integer Linear Programming (ILP) formulation for achieving minimal logical depth while guaranteeing the nearest neighbor arrangement between the interacting qubits. We substantiate our claim with studies on diverse network topologies and prominent quantum circuit benchmarks.

DOI
10.48550/arxiv.1703.08540

Related papers

An Efficient Method to Convert Arbitrary Quantum Circuits to Ones on a Linear Nearest Neighbor Architecture

Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita +1 more

A variety of quantum circuits have been designed.Most of them assume that arbitrary pairs of qubits can interact.However, several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only.Therefore, several specific circuits have been designed on an LNN architecture.However, a general and efficient conversion technique for an arbitrary circuit has not been established.Therefore, this paper gives an efficient method that converts an arbitrary quantum circuit to one on an LNN architecture.Our method achieves small overhead and time complexity compared with naive techniques.To develop the method, we introduce two key theorems that may be interesting on their own.In addition, our method also achieves smaller overhead for some known circuits designed on an LNN architecture.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2009•73 citations

An efficient conversion of quantum circuits to a linear nearest neighbor architecture

Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita +1 more

Several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only. Therefore, several specific circuits have been designed on an LNN architecture. However, a general and efficient conversion method for an arbitrary circuit has not been established. Therefore, this paper gives an efficient conversion technique to convert quantum circuits to an LNN architecture. When a quantum circuit is converted to an LNN architecture, the objective is to reduce the size of the additional circuit added by the conversion and the time complexity of the conversion. The proposed method requires less additional circuitry and time complexity compared with naive techniques. To develop the method, we introduce two key theorems that may be interesting on their own. In addition, the proposed method also achieves less overhead than some known circuits designed from scratch on an LNN architecture.

Quantum Information and Computation•Jan 1, 2011•79 citations

A multiobjective approach to linear nearest neighbor optimization for 2D quantum circuits

Daniel Ruffinelli, Benjamín Barán

The linear nearest neighbor (LNN) restriction, present in several current implementations of 1D and 2D quantum circuits, limits the interaction of qubits to those which are adjacent to each other. While there have been several proposals to optimize the process of achieving LNN compliance in 1D circuits, there are few proposals for 2D circuits. Here, we present a new perspective on this problem for 2D quantum circuits. We propose to see this as a multiobjective optimization problem with two objectives: minimizing the size of the 2D grid in the circuit, and minimizing the number of SWAP gates required to achieve LNN compliance. We present some preliminary results which show that these are two contradictory objectives. Since this is common in multiobjective problems, these results indicate that a multiobjective algorithm might be a suitable way to address this problem, since it would make considerations which currently available methods do not make.

Latin American Computer Conference (CLEI)•Oct 1, 2016•4 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•6 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

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
A significant hurdle towards realization of practical and scalable quantum computing is to protect the quantum states from inherent noises during the computation. In physical implementation of quantum circuits, a long-distance interaction between two qubits is undesirable since, it can be interpreted as a noise. Therefore, multiple quantum technologies and quantum error correcting codes strongly require the interacting qubits to be arranged in a nearest neighbor (NN) fashion. The current literature on converting a given quantum circuit to an NN-arranged one mainly considered chained qubit topologies or Linear Nearest Neighbor (LNN) topology. However, practical quantum circuit realizations, such as Nuclear Magnetic Resonance (NMR), may not have an LNN topology. To address this gap, we consider an arbitrary qubit topology. We present an Integer Linear Programming (ILP) formulation for achieving minimal logical depth while guaranteeing the nearest neighbor arrangement between the interacting qubits. We substantiate our claim with studies on diverse network topologies and prominent quantum circuit benchmarks.
A variety of quantum circuits have been designed.Most of them assume that arbitrary pairs of qubits can interact.However, several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only.Therefore, several specific circuits have been designed on an LNN architecture.However, a general and efficient conversion technique for an arbitrary circuit has not been established.Therefore, this paper gives an efficient method that converts an arbitrary quantum circuit to one on an LNN architecture.Our method achieves small overhead and time complexity compared with naive techniques.To develop the method, we introduce two key theorems that may be interesting on their own.In addition, our method also achieves smaller overhead for some known circuits designed on an LNN architecture.
Several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only. Therefore, several specific circuits have been designed on an LNN architecture. However, a general and efficient conversion method for an arbitrary circuit has not been established. Therefore, this paper gives an efficient conversion technique to convert quantum circuits to an LNN architecture. When a quantum circuit is converted to an LNN architecture, the objective is to reduce the size of the additional circuit added by the conversion and the time complexity of the conversion. The proposed method requires less additional circuitry and time complexity compared with naive techniques. To develop the method, we introduce two key theorems that may be interesting on their own. In addition, the proposed method also achieves less overhead than some known circuits designed from scratch on an LNN architecture.
The linear nearest neighbor (LNN) restriction, present in several current implementations of 1D and 2D quantum circuits, limits the interaction of qubits to those which are adjacent to each other. While there have been several proposals to optimize the process of achieving LNN compliance in 1D circuits, there are few proposals for 2D circuits. Here, we present a new perspective on this problem for 2D quantum circuits. We propose to see this as a multiobjective optimization problem with two objectives: minimizing the size of the 2D grid in the circuit, and minimizing the number of SWAP gates required to achieve LNN compliance. We present some preliminary results which show that these are two contradictory objectives. Since this is common in multiobjective problems, these results indicate that a multiobjective algorithm might be a suitable way to address this problem, since it would make considerations which currently available methods do not make.
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.
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.
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.