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

• URL: http://arxiv.org/abs/2504.09268v1
• Date: Sat, 12 Apr 2025 16:06:09 GMT
• Title: A mixed-integer program for circuit execution time minimization with precedence constraints
• Authors: Mostafa Atallah, James Ostrowski, Rebekah Herrman,
• Abstract summary: We present a mixed-integer programming model for scheduling quantum circuits to minimize execution time.<n>Our approach maximizes parallelism by allowing non-overlapping gates (those acting on distinct qubits) to execute simultaneously.<n>Experiments demonstrate that the MIP scheduler consistently results in shorter circuit execution times than greedy and layered approaches, with up to 24% savings.
• Score: 2.048226951354646
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Lazy Qubit Reordering for Accelerating Parallel State-Vector-based Quantum Circuit Simulation [0.0]
  Two quantum operation scheduling methods are proposed for quantum circuit simulation. The proposed methods reduce all-to-all communication caused by qubit reordering. We develop these methods tailored for two primary procedures in variational quantum eigensolver (VQE) simulation.
  arXiv  Detail & Related papers  (2024-10-05T18:20:37Z)
• Ecmas: Efficient Circuit Mapping and Scheduling for Surface Code [20.03248840966205]
  We study the surface code mapping and scheduling problem. To reduce the execution time of a quantum circuit, we first introduce two novel metrics. Ecmas can dramatically reduce the execution time in both double defect and lattice surgery models.
  arXiv  Detail & Related papers  (2023-12-23T13:27:59Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  We present Unified Spectral Bundling with Sketching (USBS), a provably correct, fast and scalable algorithm for solving massive SDPs. USBS provides a 500x speed-up over the state-of-the-art scalable SDP solver on an instance with over 2 billion decision variables.
  arXiv  Detail & Related papers  (2023-12-19T02:27:22Z)
• Distributed Scheduling of Quantum Circuits with Noise and Time Optimization [0.6869438083004812]
  We propose a scheduler that finds the optimum schedule for the subcircuits obtained by circuit cutting on the available set of hardware. The fidelity obtained by this method on various benchmark circuits is significantly better than that of the uncut circuit executed on the least noisy device.
  arXiv  Detail & Related papers  (2023-09-12T07:02:21Z)
• Pulse-level Scheduling of Quantum Circuits for Neutral-Atom Devices [0.0]
  We show how a pulse-level implementation of the multi-qubit gates in neutral-atom device architectures allows for the simultaneous execution of single- and multi-qubit gates. We present an algorithm to schedule the execution of a quantum circuit as a pulse sequence on a neutral-atom device with a single channel for single- and multi-qubit gate execution.
  arXiv  Detail & Related papers  (2022-06-10T14:37:09Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  We propose a conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. The proposed method, equipped with an average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques.
  arXiv  Detail & Related papers  (2022-02-26T19:10:48Z)
• GCNScheduler: Scheduling Distributed Computing Applications using Graph Convolutional Networks [12.284934135116515]
  We propose a graph convolutional network-based scheduler (GCNScheduler) By carefully integrating an inter-task data dependency structure with network settings into an input graph, the GCNScheduler can efficiently schedule tasks for a given objective. We show that it better makespan than the classic HEFT algorithm, and almost the same throughput as throughput-oriented HEFT.
  arXiv  Detail & Related papers  (2021-10-22T01:54:10Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay. We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
  arXiv  Detail & Related papers  (2021-05-01T10:18:34Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
  arXiv  Detail & Related papers  (2021-03-03T22:42:15Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks. One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
  arXiv  Detail & Related papers  (2020-10-11T14:39:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.