Solving the Max-Flow Problem on a Quantum Annealing Computer
This article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QU...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Transactions on Quantum Engineering |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9224181/ |
| _version_ | 1818839000162500608 |
|---|---|
| author | Thomas Krauss Joey McCollum Chapman Pendery Sierra Litwin Alan J. Michaels |
| author_facet | Thomas Krauss Joey McCollum Chapman Pendery Sierra Litwin Alan J. Michaels |
| author_sort | Thomas Krauss |
| collection | DOAJ |
| description | This article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem amenable to quantum annealing. The first implementation augments a graph with integral edge capacities into a multigraph with unit-capacity edges and encodes the fundamental objective and constraints of the maximum flow problem using a number of qubits equal to the total capacity of the graph $\sum _i{c_i}$. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to $\mathcal {O}(|E| \log C_{\max })$, where $|E|$ and $C_{\max }$ denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using $|V|$ qubits, where $|V|$ is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article. |
| first_indexed | 2024-12-19T03:47:20Z |
| format | Article |
| id | doaj.art-3816304de68c4d388bdaf672241e7cbc |
| institution | Directory Open Access Journal |
| issn | 2689-1808 |
| language | English |
| last_indexed | 2024-12-19T03:47:20Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Transactions on Quantum Engineering |
| spelling | doaj.art-3816304de68c4d388bdaf672241e7cbc2022-12-21T20:37:05ZengIEEEIEEE Transactions on Quantum Engineering2689-18082020-01-01111010.1109/TQE.2020.30310859224181Solving the Max-Flow Problem on a Quantum Annealing ComputerThomas Krauss0https://orcid.org/0000-0001-8040-8046Joey McCollum1https://orcid.org/0000-0002-5647-0365Chapman Pendery2Sierra Litwin3Alan J. Michaels4Ted and Karyn Hume Center for National Security and Technology, Virginia Polytechnic Institute and State University, Blacksburg, VA, USATed and Karyn Hume Center for National Security and Technology, Virginia Polytechnic Institute and State University, Blacksburg, VA, USATed and Karyn Hume Center for National Security and Technology, Virginia Polytechnic Institute and State University, Blacksburg, VA, USATed and Karyn Hume Center for National Security and Technology, Virginia Polytechnic Institute and State University, Blacksburg, VA, USATed and Karyn Hume Center for National Security and Technology, Virginia Polytechnic Institute and State University, Blacksburg, VA, USAThis article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem amenable to quantum annealing. The first implementation augments a graph with integral edge capacities into a multigraph with unit-capacity edges and encodes the fundamental objective and constraints of the maximum flow problem using a number of qubits equal to the total capacity of the graph $\sum _i{c_i}$. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to $\mathcal {O}(|E| \log C_{\max })$, where $|E|$ and $C_{\max }$ denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using $|V|$ qubits, where $|V|$ is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article.https://ieeexplore.ieee.org/document/9224181/Maximum flow problemminimum cut problemquantum annealingquantum computingsimulated annealing |
| spellingShingle | Thomas Krauss Joey McCollum Chapman Pendery Sierra Litwin Alan J. Michaels Solving the Max-Flow Problem on a Quantum Annealing Computer IEEE Transactions on Quantum Engineering Maximum flow problem minimum cut problem quantum annealing quantum computing simulated annealing |
| title | Solving the Max-Flow Problem on a Quantum Annealing Computer |
| title_full | Solving the Max-Flow Problem on a Quantum Annealing Computer |
| title_fullStr | Solving the Max-Flow Problem on a Quantum Annealing Computer |
| title_full_unstemmed | Solving the Max-Flow Problem on a Quantum Annealing Computer |
| title_short | Solving the Max-Flow Problem on a Quantum Annealing Computer |
| title_sort | solving the max flow problem on a quantum annealing computer |
| topic | Maximum flow problem minimum cut problem quantum annealing quantum computing simulated annealing |
| url | https://ieeexplore.ieee.org/document/9224181/ |
| work_keys_str_mv | AT thomaskrauss solvingthemaxflowproblemonaquantumannealingcomputer AT joeymccollum solvingthemaxflowproblemonaquantumannealingcomputer AT chapmanpendery solvingthemaxflowproblemonaquantumannealingcomputer AT sierralitwin solvingthemaxflowproblemonaquantumannealingcomputer AT alanjmichaels solvingthemaxflowproblemonaquantumannealingcomputer |