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

ACM/IEEE Design Automation Conference (DAC)

Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures

Alireza Shafaei, Mehdi Saeedi, Massoud Pedram

Published May 28, 2013• 123 citations
Publisher

Abstract

Optimization of the interaction distance between qubits to map a quantum circuit into one-dimensional quantum architectures is addressed. The problem is formulated as the Minimum Linear Arrangement (MinLA) problem. To achieve this, an interaction graph is constructed for a given circuit, and multiple instances of the MinLA problem for selected subcircuits of the initial circuit are formulated and solved. In addition, a lookahead technique is applied to improve the cost of the proposed solution which examines different subcircuit candidates. Experiments on quantum circuits for quantum Fourier transform and reversible benchmarks show the effectiveness of the approach.

DOI
10.1145/2463209.2488785

Related papers

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

Depth-Optimal Quantum Circuit Placement for Arbitrary Topologies

Debjyoti Bhattacharjee, Anupam Chattopadhyay

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.

arXiv:1703.08540•Mar 24, 2017•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

Synthesis of Linear Nearest Neighbor Quantum Circuits

Md. Mazder Rahman, Gerhard W. Dueck

This paper presents models for transforming standard reversible circuits into Linear Nearest Neighbor (LNN) architecture without inserting SWAP gates. Templates to optimize the transformed LNN circuits are proposed. All minimal LNN circuits for all 3-qubit functions have been generated to serve as benchmarks to evaluate heuristic optimization algorithms. The minimal results generated are compared with optimized LNN circuits obtained from the post synthesis algorithm --- template matching with LNN templates. Experiments show that the suggested synthesis flow significantly improves the quantum cost of circuits.

arXiv:1508.05430•Aug 21, 2015•19 citations

An Algorithm of Optimization for Linear Nearest Neighbor Quantum Circuits by Parallel Processing

Zongyuan Zhang, Zhijin Guan, Hong Zhang

In order to realize the linear nearest neighbor(LNN) of quantum circuits and reduce the quantum cost of the linear reversible quantum circuits, a method of synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication is proposed. This method shows the matrix representation of linear quantum circuits by proposing the matrix representation of the CNOT gate and the SWAP gate. The rule of judging whether a two-qubit quantum circuit is in LNN state is proposed. The LNN realization by adding SWAP gates is proposed and the equivalence of two ways of adding SWAP gates is proved. The elimination rules of SWAP gates between two overlapped adjacent quantum gates in different cases are proposed, which reduce the quantum cost of quantum circuits after realizing the LNN architecture. We propose a particular algorithm to realize the LNN, which can effectively reduce the quantum cost and improve calculation efficiency by inserting the SWAP gates on parallel computing devices. Experiments show that the quantum cost can be improved by 34.31% on average and the speed-up ratio of the GPU-based algorithm can reach 4 times compared with the CPU-based algorithm.

International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC)•Jul 1, 2018•2 citations

A Method of Mapping and Nearest-Neighbor for IBM QX Architecture

Chao Zhang, Zhijin Guan, Yang Qian +1 more

In order to solve the problem of mapping a quantum circuit to IBM QX architecture and satisfy connectivity constraints. This paper presents a mapping method, which is divided into two parts: Qubit initial mapping and Nearest-neighbor optimization. To solve the problem of initial mapping of qubits, according to the execution order and interaction of quantum gates in quantum circuit, a qubit mapping order method based on the weight of qubits is proposed. Then, according to the qubit interaction degree in the coupling graph, the initial qubit mapping is completed. In order to solve the nearest-neighbor problem in the mapping process, the quantum cost of non-neighbor two-qubit gate is determined by introducing the lookahead quantum cost method. Our algorithm is evaluated on IBM Q 20. Experimental results show that the proposed algorithm can effectively complete the mapping task even in large-scale benchmark tests. The proposed method is verified by experiments and compared with the existing methods, the optimized results were obtained in 74% of the test circuits.

International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT)•Aug 1, 2022•1 citation
Optimization of the interaction distance between qubits to map a quantum circuit into one-dimensional quantum architectures is addressed. The problem is formulated as the Minimum Linear Arrangement (MinLA) problem. To achieve this, an interaction graph is constructed for a given circuit, and multiple instances of the MinLA problem for selected subcircuits of the initial circuit are formulated and solved. In addition, a lookahead technique is applied to improve the cost of the proposed solution which examines different subcircuit candidates. Experiments on quantum circuits for quantum Fourier transform and reversible benchmarks show the effectiveness of the 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.
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.
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.
This paper presents models for transforming standard reversible circuits into Linear Nearest Neighbor (LNN) architecture without inserting SWAP gates. Templates to optimize the transformed LNN circuits are proposed. All minimal LNN circuits for all 3-qubit functions have been generated to serve as benchmarks to evaluate heuristic optimization algorithms. The minimal results generated are compared with optimized LNN circuits obtained from the post synthesis algorithm --- template matching with LNN templates. Experiments show that the suggested synthesis flow significantly improves the quantum cost of circuits.
In order to realize the linear nearest neighbor(LNN) of quantum circuits and reduce the quantum cost of the linear reversible quantum circuits, a method of synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication is proposed. This method shows the matrix representation of linear quantum circuits by proposing the matrix representation of the CNOT gate and the SWAP gate. The rule of judging whether a two-qubit quantum circuit is in LNN state is proposed. The LNN realization by adding SWAP gates is proposed and the equivalence of two ways of adding SWAP gates is proved. The elimination rules of SWAP gates between two overlapped adjacent quantum gates in different cases are proposed, which reduce the quantum cost of quantum circuits after realizing the LNN architecture. We propose a particular algorithm to realize the LNN, which can effectively reduce the quantum cost and improve calculation efficiency by inserting the SWAP gates on parallel computing devices. Experiments show that the quantum cost can be improved by 34.31% on average and the speed-up ratio of the GPU-based algorithm can reach 4 times compared with the CPU-based algorithm.
In order to solve the problem of mapping a quantum circuit to IBM QX architecture and satisfy connectivity constraints. This paper presents a mapping method, which is divided into two parts: Qubit initial mapping and Nearest-neighbor optimization. To solve the problem of initial mapping of qubits, according to the execution order and interaction of quantum gates in quantum circuit, a qubit mapping order method based on the weight of qubits is proposed. Then, according to the qubit interaction degree in the coupling graph, the initial qubit mapping is completed. In order to solve the nearest-neighbor problem in the mapping process, the quantum cost of non-neighbor two-qubit gate is determined by introducing the lookahead quantum cost method. Our algorithm is evaluated on IBM Q 20. Experimental results show that the proposed algorithm can effectively complete the mapping task even in large-scale benchmark tests. The proposed method is verified by experiments and compared with the existing methods, the optimized results were obtained in 74% of the test circuits.