A mixed-integer program for circuit execution time minimization with precedence constraints
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917984094650368 |
|---|---|
| author | Atallah, Mostafa Ostrowski, James Herrman, Rebekah |
| author_facet | Atallah, Mostafa Ostrowski, James Herrman, Rebekah |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_09268 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A mixed-integer program for circuit execution time minimization with precedence constraints Atallah, Mostafa Ostrowski, James Herrman, Rebekah Quantum Physics 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. |
| title | A mixed-integer program for circuit execution time minimization with precedence constraints |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2504.09268 |