Binary integer programming for optimizing ebit cost in distributed quantum circuits with fixed module allocation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914333370351616 |
|---|---|
| author | Cha, Hyunho Lee, Jungwoo |
| author_facet | Cha, Hyunho Lee, Jungwoo |
| contents | Modular and networked quantum architectures can scale beyond the qubit count of a single device, but executing a circuit across modules requires implementing non-local two-qubit gates using shared entanglement (ebits) and classical communication, making ebit cost a central resource in distributed execution. The resulting distributed quantum circuit (DQC) problem is combinatorial, motivating prior heuristic approaches such as hypergraph partitioning. In this work, we decouple module allocation from distribution. For a fixed module allocation (i.e., assignment of each qubit to a specific Quantum Processing Unit), we formulate the remaining distribution layer as an exact binary integer programming (BIP). This yields solver-optimal distributions for the fixed-allocation subproblem and can be used as a post-processing step on top of any existing allocation method. We derive compact BIP formulations for four or more modules and a tighter specialization for three modules. Across a diverse benchmark suite, BIP post-processing reduces ebit cost by up to 20\% for random circuits and by more than an order of magnitude for some arithmetic circuits. While the method incurs offline classical overhead, it is amortized when circuits are executed repeatedly. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_11816 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Binary integer programming for optimizing ebit cost in distributed quantum circuits with fixed module allocation Cha, Hyunho Lee, Jungwoo Quantum Physics Distributed, Parallel, and Cluster Computing Modular and networked quantum architectures can scale beyond the qubit count of a single device, but executing a circuit across modules requires implementing non-local two-qubit gates using shared entanglement (ebits) and classical communication, making ebit cost a central resource in distributed execution. The resulting distributed quantum circuit (DQC) problem is combinatorial, motivating prior heuristic approaches such as hypergraph partitioning. In this work, we decouple module allocation from distribution. For a fixed module allocation (i.e., assignment of each qubit to a specific Quantum Processing Unit), we formulate the remaining distribution layer as an exact binary integer programming (BIP). This yields solver-optimal distributions for the fixed-allocation subproblem and can be used as a post-processing step on top of any existing allocation method. We derive compact BIP formulations for four or more modules and a tighter specialization for three modules. Across a diverse benchmark suite, BIP post-processing reduces ebit cost by up to 20\% for random circuits and by more than an order of magnitude for some arithmetic circuits. While the method incurs offline classical overhead, it is amortized when circuits are executed repeatedly. |
| title | Binary integer programming for optimizing ebit cost in distributed quantum circuits with fixed module allocation |
| topic | Quantum Physics Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2501.11816 |