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

Quantum Engineering

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

Published Dec 10, 2020• 3 citations
Publisher

Abstract

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.

DOI
10.1002/que2.57

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 Systems•Sep 21, 2015•19 citations

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

Naser Mohammadzadeh, Tayebeh Bahreini, Hossein Badri

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.

Modelling and Simulation in Engineering•Jan 1, 2014•5 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 Technology•May 13, 2026•0 citations

Automated generation of layout and control for quantum circuits

Mark Whitney, Nemanja Isailovic, Yatish Patel +1 more

We present a computer-aided design flow for quantum circuits, complete with automatic layout and control logic extraction. To motivate automated layout for quantum circuits, we investigate grid-based layouts and show a performance variance of four times as we vary grid structure and initial qubit placement. We then propose two polynomial-time design heuristics: a greedy algorithm suitable for small, congestion-free quantum circuits and a dataflow-based analysis approach to placement and routing with implicit initial placement of qubits. Finally, we show that our dataflow-based heuristic generates better layouts than the state-of-the-art automated grid-based layout and scheduling mechanism in terms of latency and potential pipelinability, but at the cost of some area.

arXiv:0704.0268•ACM International Conference on Computing Frontiers (CF)•May 7, 2007•69 citations

Resource-aware scheduling of multiple quantum circuits on a hardware device

Debasmita Bhoumik, Ritajit Majumdar, Susmita Sur‐Kolay

Recent quantum technologies and quantum error-correcting codes emphasize the requirement for arranging interacting qubits in a nearest-neighbor (NN) configuration while mapping a quantum circuit onto a given hardware device, in order to avoid undesirable noise. It is equally important to minimize the wastage of qubits in a quantum hardware device with m qubits while running circuits of n qubits in total, with n < m. In order to prevent cross-talk between two circuits, a buffer distance between their layouts is needed. Furthermore, not all the qubits and all the two-qubit interactions are at the same noise-level. Scheduling multiple circuits on the same hardware may create a possibility that some circuits are executed on a noisier layout than the others. In this paper, we consider an optimization problem which schedules as many circuits as possible for execution in parallel on the hardware, while maintaining a pre-defined layout quality for each. An integer linear programming formulation to ensure maximum fidelity while preserving the nearest neighbor arrangement among interacting qubits is presented. Our assertion is supported by comprehensive investigations involving various well-known quantum circuit benchmarks. As this scheduling problem is shown to be NP Hard, we also propose a greedy heuristic method which provides 2x and 3x better utilization for 27-qubit and 127-qubit hardware devices respectively in terms of qubits and time.

arXiv:2407.08930•Jul 12, 2024•1 citation

Qubit placement to minimize communication overhead in 2D quantum architectures

Alireza Shafaei, Mehdi Saeedi, Massoud Pedram

Regular, local-neighbor topologies of quantum architectures restrict interactions to adjacent qubits, which in turn increases the latency of quantum circuits mapped to these architectures. To alleviate this effect, optimization methods that consider qubit-to-qubit interactions in 2D grid architectures are presented in this paper. The proposed approaches benefit from Mixed Integer Programming (MIP) formulation for the qubit placement problem. Simulation results on various benchmarks show 27% on average reduction in communication overhead between qubits compared to best results of previous work.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2014•121 citations
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.
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.
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.
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.
We present a computer-aided design flow for quantum circuits, complete with automatic layout and control logic extraction. To motivate automated layout for quantum circuits, we investigate grid-based layouts and show a performance variance of four times as we vary grid structure and initial qubit placement. We then propose two polynomial-time design heuristics: a greedy algorithm suitable for small, congestion-free quantum circuits and a dataflow-based analysis approach to placement and routing with implicit initial placement of qubits. Finally, we show that our dataflow-based heuristic generates better layouts than the state-of-the-art automated grid-based layout and scheduling mechanism in terms of latency and potential pipelinability, but at the cost of some area.
Recent quantum technologies and quantum error-correcting codes emphasize the requirement for arranging interacting qubits in a nearest-neighbor (NN) configuration while mapping a quantum circuit onto a given hardware device, in order to avoid undesirable noise. It is equally important to minimize the wastage of qubits in a quantum hardware device with m qubits while running circuits of n qubits in total, with n < m. In order to prevent cross-talk between two circuits, a buffer distance between their layouts is needed. Furthermore, not all the qubits and all the two-qubit interactions are at the same noise-level. Scheduling multiple circuits on the same hardware may create a possibility that some circuits are executed on a noisier layout than the others. In this paper, we consider an optimization problem which schedules as many circuits as possible for execution in parallel on the hardware, while maintaining a pre-defined layout quality for each. An integer linear programming formulation to ensure maximum fidelity while preserving the nearest neighbor arrangement among interacting qubits is presented. Our assertion is supported by comprehensive investigations involving various well-known quantum circuit benchmarks. As this scheduling problem is shown to be NP Hard, we also propose a greedy heuristic method which provides 2x and 3x better utilization for 27-qubit and 127-qubit hardware devices respectively in terms of qubits and time.
Regular, local-neighbor topologies of quantum architectures restrict interactions to adjacent qubits, which in turn increases the latency of quantum circuits mapped to these architectures. To alleviate this effect, optimization methods that consider qubit-to-qubit interactions in 2D grid architectures are presented in this paper. The proposed approaches benefit from Mixed Integer Programming (MIP) formulation for the qubit placement problem. Simulation results on various benchmarks show 27% on average reduction in communication overhead between qubits compared to best results of previous work.