Modelling and Simulation in Engineering

Optimal ILP-Based Approach for Gate Location Assignment and Scheduling in Quantum Circuits

Naser Mohammadzadeh, Tayebeh Bahreini, Hossein Badri

Published Jan 1, 2014• 5 citations

Abstract

Physical design and synthesis are two key processes of quantum circuit design methodology. The physical design process itself decomposes into scheduling, mapping, routing, and placement. In this paper, a mathematical model is proposed for mapping, routing, and scheduling in ion-trap technology in order to minimize latency of the circuit. The proposed model which is a mixed integer linear programming (MILP) model gives the optimal locations for gates and the best sequence of operations in terms of latency. Experimental results show that our scheme outperforms the other schemes for the attempted benchmarks.

DOI: 10.1155/2014/571374

Related papers

An MINLP Model for Scheduling and Placement of Quantum Circuits with a Heuristic Solution Approach

Tayebeh Bahreini, Naser Mohammadzadeh

Recent works on quantum physical design have pushed the scheduling and placement of quantum circuit into their prominent positions. In this article, a mixed integer nonlinear programming model is proposed for the placement and scheduling of quantum circuits in such a way that latency is minimized. The proposed model determines locations of gates and the sequence of operations. The proposed model is proved reducible to a quadratic assignment problem which is a well-known NP-complete combinatorial optimization problem. Since it is impossible to find the optimal solution of this NP-complete problem for large quantum circuits within a reasonable amount of time, a metaheuristic solution method is developed for the proposed model. Some experiments are conducted to evaluate the performance of the developed solution approach. Experimental results show that the proposed approach improves average latency by about 24.09% for the attempted benchmarks.

ACM Journal on Emerging Technologies in Computing SystemsSep 21, 201519 citations

A Quantum Physical Design Flow Using ILP and Graph Drawing

Yazdani, Maryam, Morteza Saheb Zamani, Mehdi Sedighi

Implementing large-scale quantum circuits is one of the challenges of quantum computing. One of the central challenges of accurately modeling the architecture of these circuits is to schedule a quantum application and generate the layout while taking into account the cost of communications and classical resources as well as the maximum exploitable parallelism. In this paper, we present and evaluate a design flow for arbitrary quantum circuits in ion trap technology. Our design flow consists of two parts. First, a scheduler takes a description of a circuit and finds the best order for the execution of its quantum gates using integer linear programming (ILP) regarding the classical resources (qubits) and instruction dependencies. Then a layout generator receives the schedule produced by the scheduler and generates a layout for this circuit using a graph-drawing algorithm. Our experimental results show that the proposed flow decreases the average latency of quantum circuits by about 11% for a set of attempted benchmarks and by about 9% for another set of benchmarks compared with the best in literature.

arXiv:1306.2037Jun 9, 20130 citations

A congestion‐aware mixed integer linear programming model for placement and scheduling of quantum circuits with a two‐level heuristic solution approach

Tayebeh Bahreini, Naser Mohammadzadeh

In recent years, many studies have been focused on designing quantum circuits for the promising future of quantum computers. In these studies, latency has been considered as one of the main performance measures in quantum circuit design. This paper proposes a congestion-aware mixed integer linear programming model for placement and scheduling of quantum circuits. The proposed model determines initial locations for qubits and locations for gates, and schedules the movement of qubits along the channels in such a way that the total latency is minimized. Since finding the optimal solution of the model for large circuits within a reasonable amount of time is not practical, a heuristic solution method has been developed for the proposed model. Moreover, some experiments are conducted to evaluate the performance of the proposed model and the solution approach. Experimental results show that the proposed approach improves the average latency by about 14.5% for the attempted benchmarks compared with the best in the literature.

Quantum EngineeringDec 10, 20203 citations

Improving Latency of Quantum Circuits by Gate Exchanging

Naser Mohammadzadeh, Morteza Saheb Zamani, Mehdi Sedighi

Quantum circuit design flow consists of two main tasks: synthesis and physical design. In the current flows, two procedures are performed subsequently; synthesis converts the design description into a technology-dependent netlist and then physical design takes the fixed netlist, produces layout, and schedules the netlist on the layout. This style of design suffers from limiting the optimization process in the physical design stage, whereas using a flexible netlist and changing it locally during physical design using layout information often can provide more chance to optimize quantum circuit metrics. Focusing on this issue, in this paper, we propose an optimization flow using gate exchanging heuristic to improve the latency of quantum circuits. We have chosen ion trap technology as the underlying technology to study our flow. Our experimental results show that the proposed flow decreases the latency of quantum circuit by about 23% for the attempted benchmarks.

Euromicro Conference on Digital System Design (DSD)Aug 1, 200912 citations

Minimizing the latency of quantum circuits during mapping to the ion-trap circuit fabric

Mohammad Javad Dousti, Massoud Pedram

Abstract — Quantum computers are exponentially faster than their classical counterparts in terms of solving some specific, but important problems. The biggest challenge in realizing a quantum computing system is the environmental noise. One way to decrease the effect of noise (and hence, reduce the overhead of building fault tolerant quantum circuits) is to reduce the latency of the quantum circuit that runs on a quantum circuit. In this paper, a novel algorithm is presented for scheduling, placement, and routing of a quantum algorithm, which is to be realized on a target quantum circuit fabric technology. This algorithm, and the accompanying software tool, advances state-of-the-art in quantum CAD methodologies and methods while considering key characteristics and constraints of the ion-trap quantum circuit fabric. Experimental results show that the presented tool improves results of the previous tool by about 41%. Keywords- quantum computing; scheduling; routing; placement; ion-trap technology; CAD tool I.

Design, Automation, and Test in EuropeJan 1, 201227 citations

A scalable architecture for quantum information processors: qubit partitioning, placement, and scheduling for minimized circuit latency

Zahra Alimohammadi, Naser Mohammadzadeh, Saeid Seyedi +1 more

Proposing an architecture that effectively compensates for physical hardware inefficiencies through redundant resources is a key challenge in quantum computer design. Although the representation of quantum systems is currently limited to tens of qubits, scaling existing small scale laboratory systems into large scale quantum computers capable of solving meaningful practical problems remains a primary research objective. Focusing on this issue, this paper proposes a scalable architecture for quantum information processors. Physical design, one of the two main processes in quantum computer design, transforms a circuit netlist into a technology specific layout. Quantum mapping comprising partitioning, placement, scheduling, and routing is an essential part of this process, and these stages are inherently interdependent. In this research, considering the dependencies between these stages, we present an Integer Linear Programming (ILP) model for qubit partitioning and placement, determining the optimal module and physical location for each qubit. Furthermore, we propose a heuristic approach for the placement and scheduling of quantum operators on a scalable, modular, universal ion trap quantum computer (MUSIQC), aiming to minimize circuit execution delay. Qubit routing is performed using a greedy strategy. For evaluation, the proposed method was applied to both Ripple-Carry Adder and Carry-Lookahead Adder circuits. Experimental results demonstrate that the proposed approach reduces the average circuit delay by approximately 58.98% for Ripple-Carry Adder circuits and 33% for Carry-Lookahead Adder circuits compared to the best existing method. These results underscore the effectiveness of our integrated framework, where ILP-based partitioning optimizes for dominant operational costs, while our subsequent resource-aware scheduler actively manages parallelism and contention to achieve the minimal overall circuit execution delay.

EPJ Quantum TechnologyMay 13, 20260 citations