QED driven QAOA for network-flow optimization

Yuxuan Zhang1, Ruizhe Zhang2, and Andrew C. Potter1

1Center for Complex Quantum Systems, University of Texas at Austin, Austin, TX 78712, USA
2Department of Computer Science, University of Texas at Austin, Austin, TX 78712, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We present a general framework for modifying quantum approximate optimization algorithms (QAOA) to solve constrained network flow problems. By exploiting an analogy between flow-constraints and Gauss' law for electromagnetism, we design lattice quantum electrodynamics (QED)- inspired mixing Hamiltonians that preserve flow constraints throughout the QAOA process. This results in an exponential reduction in the size of the configuration space that needs to be explored, which we show through numerical simulations, yields higher quality approximate solutions compared to the original QAOA routine. We outline a specific implementation for edge-disjoint path (EDP) problems related to traffic congestion minimization, numerically analyze the effect of initial state choice, and explore trade-offs between circuit complexity and qubit resources via a particle-vortex duality mapping. Comparing the effect of initial states reveals that starting with an ergodic (unbiased) superposition of solutions yields better performance than beginning with the mixer ground-state, suggesting a departure from the ``short-cut to adiabaticity" mechanism often used to motivate QAOA.

► BibTeX data

► References

[1] Quantum supremacy using a programmable superconducting processor. Nature, 574: 505–510, 2019. https:/​/​doi.org/​10.1038/​s41586-019-1666-5.

[2] Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR, abs/​1505.03424, 2015. URL http:/​/​arxiv.org/​abs/​1505.03424.

[3] Richard Bellman. On a routing problem. Quarterly of applied mathematics, 16 (1): 87–90, 1958.

[4] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Oct 2015. https:/​/​doi.org/​10.1109/​focs.2015.54. URL http:/​/​dx.doi.org/​10.1109/​FOCS.2015.54.

[5] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection, Dec 2020. URL https:/​/​doi.org/​10.1103/​PhysRevLett.125.260505.

[6] Julia Chuzhoy and Shi Li. A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 233–242, 2012. 10.1109/​FOCS.2012.54.

[7] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. ISBN 9783540779735. URL http:/​/​www.worldcat.org/​oclc/​227584184.

[8] Edsger W Dijkstra et al. A note on two problems in connexion with graphs. Numerische mathematik, 1 (1): 269–271, 1959.

[9] Shimon Even, Alon Itai, and Adi Shamir. "on the complexity of time table and multi-commodity flow problems". In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pages 184–193. IEEE, 1975. https:/​/​doi.org/​10.1137/​0205048.

[10] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv e-prints, art. arXiv:1411.4028, November 2014. URL https:/​/​ui.adsabs.harvard.edu/​abs/​2014arXiv1411.4028F.

[11] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem, 2014. URL https:/​/​arxiv.org/​abs/​1412.6062.

[12] Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples, 2020a. URL https:/​/​arxiv.org/​abs/​2005.08747.

[13] Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case, 2020b. URL https:/​/​arxiv.org/​abs/​2004.09002.

[14] Matthew P. A. Fisher. Chapter 13 duality in low dimensional quantum field theories. 2018. https:/​/​doi.org/​10.1007/​978-1-4020-3463-3_13.

[15] Roger Fletcher. Practical methods of optimization. John Wiley & Sons, 2013.

[16] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC '96, page 212–219, New York, NY, USA, 1996. Association for Computing Machinery. ISBN 0897917855. 10.1145/​237814.237866.

[17] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12 (2): 34, 2019. 10.3390/​a12020034.

[18] Thomas C Hales. The jordan curve theorem, formally and informally. The American Mathematical Monthly, 114 (10): 882–894, 2007. https:/​/​doi.org/​10.1080/​00029890.2007.11920481.

[19] Matthew B Hastings. Classical and quantum bounded depth approximation algorithms. arXiv preprint arXiv:1905.07047, 2019. https:/​/​doi.org/​10.26421/​QIC19.13-14-3.

[20] KR Khadiev and LI Safina. Quantum algorithm for shortest path search in directed acyclic graph. Moscow University Computational Mathematics and Cybernetics, 43 (1): 47–51, 2019. https:/​/​doi.org/​10.3103/​S0278641919010023.

[21] D. Marcos, P. Widmer, E. Rico, M. Hafezi, P. Rabl, U.-J. Wiese, and P. Zoller. Two-dimensional lattice gauge theories with superconducting quantum circuits. Annals of Physics, 351: 634–654, Dec 2014. ISSN 0003-4916. 10.1016/​j.aop.2014.09.011.

[22] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994. 10.1109/​SFCS.1994.365700.

[23] Zhihui Wang, Nicholas C Rubin, Jason M Dominy, and Eleanor G Rieffel. $xy$ mixers: Analytical and numerical results for the quantum alternating operator ansatz. Physical Review A, 101 (1): 012320, 2020. 10.1103/​PhysRevA.101.012320.

Cited by

[1] Felix Gemeinhardt, Antonio Garmendia, Manuel Wimmer, Benjamin Weder, and Frank Leymann, "Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study", ACM Computing Surveys 56 3, 1 (2024).

[2] Miguel Pineda Martín and Sébastien Martin, 2023 9th International Conference on Control, Decision and Information Technologies (CoDIT) 385 (2023) ISBN:979-8-3503-1140-2.

[3] Shao-Hen Chiew, Kilian Poirier, Rajesh Mishra, Ulrike Bornheimer, Ewan Munro, Si Han Foon, Christopher Wanru Chen, Wei Sheng Lim, and Chee Wei Nga, "Multiobjective Optimization and Network Routing With Near-Term Quantum Computers", IEEE Transactions on Quantum Engineering 5, 1 (2024).

[4] Yingyue Zhu, Zewen Zhang, Bhuvanesh Sundar, Alaina M Green, C Huerta Alderete, Nhung H Nguyen, Kaden R A Hazzard, and Norbert M Linke, "Multi-round QAOA and advanced mixers on a trapped-ion quantum computer", Quantum Science and Technology 8 1, 015007 (2023).

[5] Benjamin C B Symons, David Galvin, Emre Sahin, Vassil Alexandrov, and Stefano Mensa, "A practitioner’s guide to quantum algorithms for optimisation problems", Journal of Physics A: Mathematical and Theoretical 56 45, 453001 (2023).

[6] Bobak Toussi Kiani, Giacomo De Palma, Milad Marvian, Zi-Wen Liu, and Seth Lloyd, "Learning quantum data with the quantum Earth Mover's distance", arXiv:2101.03037, (2021).

[7] Bobak Toussi Kiani, Giacomo De Palma, Milad Marvian, Zi-Wen Liu, and Seth Lloyd, "Learning quantum data with the quantum earth mover's distance", Quantum Science and Technology 7 4, 045002 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-21 22:51:05) and SAO/NASA ADS (last updated successfully 2024-06-21 22:51:06). The list may be incomplete as not all publishers provide suitable and complete citation data.