Euromicro Conference on Digital System Design (DSD)

Geometric Refactoring of Quantum and Reversible Circuits: Quantum Layout

Martin Lukáč, Saadat Nursultan, Georgiy Krylov, Oliver Keszöcze

Published Aug 1, 2020• 2 citations

Abstract

With the advent of gated quantum computers and regular structures of the qubit layout, methods for placement, routing, noise estimation and logic to hardware mapping become imminently required. In this paper, we propose a method for quantum circuit layout that is intended to solve such problems when mapping a quantum circuit to a quantum computer. The proposed method starts by building a Circuit Interaction Graph (CIG) that represents the ideal hardware layout minimizing the distance and path length between the individual qubits. The CIG is also used to introduce a qubit noise model. Once constructed, the CIG is iteratively reduced to a given architecture (qubit coupling model) specifying the neighborhood, qubits, priority and qubits noise. The introduced constraints allow to additionally reduce the graph according to preferred weights of desired properties. The proposed method is verified and tested on a set of standard benchmarks.

DOI: 10.1109/dsd51259.2020.00074

Related papers

Geometric Refactoring of Quantum and Reversible Circuits Using Graph Algorithms

Martin Lukáč, Saadat Nursultan, Georgiy Krylov +3 more

With the advent of gated quantum computers and the regular structures for qubit layout, methods for placement, routing, noise estimation, and logic to hardware mapping become imminently required. In this paper, we propose a method for quantum circuit layout that is intended to solve such problems when mapping a quantum circuit to a gated quantum computer. The proposed methodology starts by building a Circuit Interaction Graph (CIG) that represents the ideal hardware layout minimizing the distance and path length between the individual qubits. The CIG is also used to introduce a qubit noise model. Once constructed, the CIG is iteratively reduced to a given architecture (qubit coupling model) specifying the neighborhood, qubits, priority, and qubits noise. The introduced constraints allow us to additionally reduce the graph according to preferred weights of desired properties. We propose two different methods of reducing the CIG: iterative reduction or the iterative isomorphism search algorithm. The proposed method is verified and tested on a set of standard benchmarks with results showing improvement on certain functions while in average improving the cost of the implementation over the current state of the art methods.

IEICE Transactions on Information and SystemsJul 31, 20241 citation

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 MagazineJan 1, 201642 citations

Optimal Layout Synthesis for Quantum Circuits as Classical Planning

Irfansha Shaik, Jaco van de Pol

In Layout Synthesis, the logical qubits of a quantum circuit are mapped to the physical qubits of a given quantum hardware platform, taking into account the connectivity of physical qubits. This involves inserting SWAP gates before an operation is applied on distant qubits. Optimal Layout Synthesis is crucial for practical Quantum Computing on current error-prone hardware: Minimizing the number of SWAP gates directly mitigates the error rates when running quantum circuits. In recent years, several approaches have been proposed for minimizing the required SWAP insertions. The proposed exact approaches can only scale to a small number of qubits. In this paper, we provide two encodings for Optimal Layout Synthesis as a classical planning problem. We use optimal classical planners to synthesize the optimal layout for a standard set of benchmarks. Our results show the scalability of our approach compared to previous leading approaches. We can optimally map circuits with 9 qubits onto a 14 qubit platform, which could not be handled before by exact methods.

Oct 28, 202314 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 ComputationMar 1, 20201 citation

Optimizing Layout Synthesis for Quantum Computing Performance

Chi‐Chou Kao, Hung-Yi Lin

In recent years, the emergence of the Noisy Intermediate-Scale Quantum (NISQ) era has led to the development of a wide variety of quantum devices, marking a dynamic phase in the field of quantum computing. Despite these advancements, practical applications of quantum computers still face significant challenges, one of the most prominent being the limited connectivity between physical quantum bits (qubits). This limitation requires quantum circuits to be recompiled through layout synthesis before they can be executed on quantum devices. Layout synthesis determines the specific placement of quantum gates within the circuit on the physical hardware. When gates do not align with the connectivity constraints of the device, additional quantum gates must be inserted to remap the qubits, which can negatively affect the circuit’s efficiency and performance. To address this issue, the primary goal of this paper is to enhance the mapping process within layout synthesis, aiming to optimize both the layout and the circuit depth. Experimental results demonstrate that the proposed method effectively reduces the quantum circuit depth, outperforming other existing approaches in terms of efficiency.

Journal of Circuits Systems and ComputersMar 6, 20250 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.06804Jul 14, 20201 citation