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

arXiv:2504.09268

A mixed-integer program for circuit execution time minimization with precedence constraints

Mostafa Atallah, James Ostrowski, Rebekah Herrman

Published Apr 12, 2025• 0 citations
arXivHTMLPDF

Abstract

We present a mixed-integer programming (MIP) model for scheduling quantum circuits to minimize execution time. Our approach maximizes parallelism by allowing non-overlapping gates (those acting on distinct qubits) to execute simultaneously. Our methods apply to general circuits with precedence constraints. First, we derive closed-formulas for the execution time of circuits generated by ma-QAOA on star graphs for a layered, greedy, and MIP schedules. We then compare the MIP schedule against layered and greedy scheduling approaches on the circuits generated by ma-QAOA for solving the MaxCut problem on all non-isomorphic connected graphs with 3-7 vertices. These experiments demonstrate that the MIP scheduler consistently results in shorter circuit execution times than greedy and layered approaches, with up to 24\% savings.

DOI
10.48550/arxiv.2504.09268

Related papers

Dependency-Aware Circuit Scheduling for Multi-Core Quantum Systems to Minimize Makespan

Rajeswari Suance P S, Ruchika Gupta, Maurizio Palesi +1 more

Multi-core quantum computing architectures have emerged as a promising solution to the qubit scalability limitations of monolithic NISQ devices. Quantum algorithms are expressed as quantum circuits composed of single- and two-qubit gates. However, circuit scheduling in multi-core quantum systems remains largely unexplored. Reducing overall execution time (makespan), increasing core utilization, and hiding communication latency behind computation depends on effective scheduling. In this paper, we first introduce a layered scheduling approach as a baseline where quantum gates within the same layer are executed in parallel, while layers themselves are executed sequentially. We then propose a greedy scheduling strategy which schedules each gate as soon as all its dependencies and required resources are available. This allows fine-grained parallelism across cores. Our evaluation shows that on real benchmarks, greedy scheduling achieves an average 40% reduction in makespan and improvement in core utilization. The results suggest that the use of intelligent circuit scheduling to exploit parallelism can greatly enhance the speed of circuit execution in multi-core quantum architectures.

quant-pharXiv:2607.00469•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Jul 2, 2026•0 citations

Quantum Circuit Mapping Using Binary Integer Nonlinear Programming

Aaron Orenstein, Vipin Chaudhary

As Quantum Computers continue to increase in size, throughput has not increased proportionally [1]. Errors in qubit measurement and gate operations continue to increase with circuit width and depth. In order to maximize machine throughput, researchers have begun exploring ways of parallelizing circuit execution [2]–[9]. Due to the noisyness of quantum computers, this requires new algorithms for efficient resource allocation, qubit mapping, and scheduling. We improve on existing greedy algorithms by formulating the mapping search as a Binary Integer Non-Linear Programming (BINLP) problem. We model practical constraints and propose new heuristics for determining the goodness of a mapping. We evaluate our mappings on several sets of benchmark circuits and investigate the usefulness of parallel execution for circuit cutting, QAOAs, and deep circuits. We observe similar fidelity compared to Qiskit's transpiler for circuit cutting and throughput benchmarks. We observe greater fidelity over Qiskit's transpiler for dense QAOA ansatzes. Finally, we find that parallel circuit cutting provides greater fidelity than full-circuit execution.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 27, 2024•0 citations

Distributed Scheduling of Quantum Circuits with Noise and Time Optimization

Debasmita Bhoumik, Ritajit Majumdar, Amit Saha +1 more

Quantum computers are currently noisy, particularly without error correction and fault tolerance. Methods like error suppression and mitigation are widely used to improve performance. Circuit cutting, which partitions a circuit into smaller subcircuits, can also reduce noise. In this paper, we propose an Integer Linear Program (ILP) based scheduler for optimizing subcircuit schedules on available hardware. The goal is to maximize overall fidelity and ensure each hardware does not exceed its predefined execution time. For 10-qubit circuits, our method achieves an average fidelity improvement of ~12.3% and ~21% with and without measurement error mitigation, respectively, even with minimal execution time. Additionally, we introduce a polynomial-time graph-theoretic scheduling method that matches the ILP scheduler's results when the number of subcircuits does not exceed the number of hardware units, each with minimal execution time. This noise and time-optimized scheduler represents a crucial step towards optimal quantum computing performance, especially with limited hardware access.

arXiv:2309.06005•Sep 12, 2023•19 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•6 citations

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•21 citations

Instance-Wise Mixed Integer Programming Solver Configuration for Quantum Circuit Decomposition via Large Language Model Distillation

Yuheon Song, Sungbin Lim

Quantum Circuit Decomposition (QCD) aims to realize target unitary operations under stringent physical and logical constraints using limited native gate sets. However, standard data-driven approaches struggle to enforce these constraints explicitly, failing to guarantee physically valid and logically equivalent circuits. Mixed Integer Programming (MIP) formulations address this limitation by encoding such constraints, enabling globally optimal, constraint-satisfying solutions. MIP solvers expose large configuration spaces that affect search performance, and effective configurations vary substantially across instances. This motivates instance-specific approaches rather than a single global tuning strategy. We propose a two-stage instance-wise configuration optimization framework for QCD MIPs. Stage 1 trains a Graph Neural Network (GNN)–based reinforcement learning policy on bipartite graphs that capture MIP structure, using a novel instance-wise relative reward to stabilize learning under heterogeneous and timeout-dominated solver feedback. Stage 2 distills this graph-informed policy into a graph-free Large Language Model (LLM) student operating directly on QCD-level inputs. Both proposed policies outperform the solver’s built-in default configuration and remain competitive with automatic configurators. On the 4-qubit benchmark, LLM-Student solves an average of 53.4 instances versus 2.2 under the default, and its average geometric mean solving time on commonly solved instances is 25.2% and 28.5% lower than those of SMAC3 and irace, respectively. It remains competitive with the GNN-Teacher while avoiding approximately nine hours of graph construction per 4-qubit instance at inference time. These results suggest that combining graph-based policy learning with graph-free distillation provides a practical and promising direction for learning-based optimization of QCD MIPs and beyond.

IEEE Access•Jan 1, 2026•0 citations
We present a mixed-integer programming (MIP) model for scheduling quantum circuits to minimize execution time. Our approach maximizes parallelism by allowing non-overlapping gates (those acting on distinct qubits) to execute simultaneously. Our methods apply to general circuits with precedence constraints. First, we derive closed-formulas for the execution time of circuits generated by ma-QAOA on star graphs for a layered, greedy, and MIP schedules. We then compare the MIP schedule against layered and greedy scheduling approaches on the circuits generated by ma-QAOA for solving the MaxCut problem on all non-isomorphic connected graphs with 3-7 vertices. These experiments demonstrate that the MIP scheduler consistently results in shorter circuit execution times than greedy and layered approaches, with up to 24% savings.
Multi-core quantum computing architectures have emerged as a promising solution to the qubit scalability limitations of monolithic NISQ devices. Quantum algorithms are expressed as quantum circuits composed of single- and two-qubit gates. However, circuit scheduling in multi-core quantum systems remains largely unexplored. Reducing overall execution time (makespan), increasing core utilization, and hiding communication latency behind computation depends on effective scheduling. In this paper, we first introduce a layered scheduling approach as a baseline where quantum gates within the same layer are executed in parallel, while layers themselves are executed sequentially. We then propose a greedy scheduling strategy which schedules each gate as soon as all its dependencies and required resources are available. This allows fine-grained parallelism across cores. Our evaluation shows that on real benchmarks, greedy scheduling achieves an average 40% reduction in makespan and improvement in core utilization. The results suggest that the use of intelligent circuit scheduling to exploit parallelism can greatly enhance the speed of circuit execution in multi-core quantum architectures.
As Quantum Computers continue to increase in size, throughput has not increased proportionally [1]. Errors in qubit measurement and gate operations continue to increase with circuit width and depth. In order to maximize machine throughput, researchers have begun exploring ways of parallelizing circuit execution [2]–[9]. Due to the noisyness of quantum computers, this requires new algorithms for efficient resource allocation, qubit mapping, and scheduling. We improve on existing greedy algorithms by formulating the mapping search as a Binary Integer Non-Linear Programming (BINLP) problem. We model practical constraints and propose new heuristics for determining the goodness of a mapping. We evaluate our mappings on several sets of benchmark circuits and investigate the usefulness of parallel execution for circuit cutting, QAOAs, and deep circuits. We observe similar fidelity compared to Qiskit's transpiler for circuit cutting and throughput benchmarks. We observe greater fidelity over Qiskit's transpiler for dense QAOA ansatzes. Finally, we find that parallel circuit cutting provides greater fidelity than full-circuit execution.
Quantum computers are currently noisy, particularly without error correction and fault tolerance. Methods like error suppression and mitigation are widely used to improve performance. Circuit cutting, which partitions a circuit into smaller subcircuits, can also reduce noise. In this paper, we propose an Integer Linear Program (ILP) based scheduler for optimizing subcircuit schedules on available hardware. The goal is to maximize overall fidelity and ensure each hardware does not exceed its predefined execution time. For 10-qubit circuits, our method achieves an average fidelity improvement of ~12.3% and ~21% with and without measurement error mitigation, respectively, even with minimal execution time. Additionally, we introduce a polynomial-time graph-theoretic scheduling method that matches the ILP scheduler's results when the number of subcircuits does not exceed the number of hardware units, each with minimal execution time. This noise and time-optimized scheduler represents a crucial step towards optimal quantum computing performance, especially with limited hardware access.
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.
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.
Quantum Circuit Decomposition (QCD) aims to realize target unitary operations under stringent physical and logical constraints using limited native gate sets. However, standard data-driven approaches struggle to enforce these constraints explicitly, failing to guarantee physically valid and logically equivalent circuits. Mixed Integer Programming (MIP) formulations address this limitation by encoding such constraints, enabling globally optimal, constraint-satisfying solutions. MIP solvers expose large configuration spaces that affect search performance, and effective configurations vary substantially across instances. This motivates instance-specific approaches rather than a single global tuning strategy. We propose a two-stage instance-wise configuration optimization framework for QCD MIPs. Stage 1 trains a Graph Neural Network (GNN)–based reinforcement learning policy on bipartite graphs that capture MIP structure, using a novel instance-wise relative reward to stabilize learning under heterogeneous and timeout-dominated solver feedback. Stage 2 distills this graph-informed policy into a graph-free Large Language Model (LLM) student operating directly on QCD-level inputs. Both proposed policies outperform the solver’s built-in default configuration and remain competitive with automatic configurators. On the 4-qubit benchmark, LLM-Student solves an average of 53.4 instances versus 2.2 under the default, and its average geometric mean solving time on commonly solved instances is 25.2% and 28.5% lower than those of SMAC3 and irace, respectively. It remains competitive with the GNN-Teacher while avoiding approximately nine hours of graph construction per 4-qubit instance at inference time. These results suggest that combining graph-based policy learning with graph-free distillation provides a practical and promising direction for learning-based optimization of QCD MIPs and beyond.