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

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. T...

Full description

Saved in:
Bibliographic Details
Published in:ACM journal on emerging technologies in computing systems 2015-09, Vol.12 (3), p.1-20
Main Authors: Bahreini, Tayebeh, Mohammadzadeh, Naser
Format: Article
Language:English
Subjects:
Circuits
Combinatorial analysis
Mathematical models
Mixed integer
Nonlinear programming
Optimization
Placement
Scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1550-4832
1550-4840
DOI:10.1145/2766452