Grover Adaptive Search for Constrained Polynomial Binary Optimization

Austin Gilliam1, Stefan Woerner2, and Constantin Gonciulea1

1JPMorgan Chase
2IBM Quantum, IBM Research – Zurich

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

Abstract

In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.

In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.

► BibTeX data

► References

[1] 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, pages 212–219, New York, NY, USA, 1996. ACM. ISBN 0-89791-785-5. 10.1145/​237814.237866.
https:/​/​doi.org/​10.1145/​237814.237866

[2] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26 (5): 1484–1509, Oct 1997. ISSN 1095-7111. 10.1137/​s0097539795293172.
https:/​/​doi.org/​10.1137/​s0097539795293172

[3] B. P. Lanyon, J. D. Whitfield, G. G. Gillett, M. E. Goggin, M. P. Almeida, I. Kassal, J. D. Biamonte, M. Mohseni, B. J. Powell, M. Barbieri, and et al. Towards quantum chemistry on a quantum computer. Nature Chemistry, 2 (2): 106–111, Jan 2010. ISSN 1755-4349. 10.1038/​nchem.483.
https:/​/​doi.org/​10.1038/​nchem.483

[4] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103 (15), Oct 2009. ISSN 1079-7114. 10.1103/​physrevlett.103.150502.
https:/​/​doi.org/​10.1103/​physrevlett.103.150502

[5] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J. Coles. Variational quantum linear solver, 2020. URL https:/​/​arxiv.org/​abs/​1909.05820.
arXiv:1909.05820

[6] Patrick Rebentrost, Brajesh Gupt, and Thomas R. Bromley. Quantum computational finance: Monte carlo pricing of financial derivatives. Phys. Rev. A, 98: 022321, Aug 2018. 10.1103/​PhysRevA.98.022321.
https:/​/​doi.org/​10.1103/​PhysRevA.98.022321

[7] Stefan Woerner and Daniel J. Egger. Quantum risk analysis. npj Quantum Information, 5: 15, 2019. 10.1038/​s41534-019-0130-6.
https:/​/​doi.org/​10.1038/​s41534-019-0130-6

[8] D. J. Egger, R. Garcia Gutierrez, J. Cahue Mestre, and S. Woerner. Credit risk analysis using quantum computers. IEEE Transactions on Computers, pages 1–1, 2020. 10.1109/​TC.2020.3038063.
https:/​/​doi.org/​10.1109/​TC.2020.3038063

[9] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen, and Stefan Woerner. Option pricing using quantum computers. Quantum, 4: 291, Jul 2020. ISSN 2521-327X. 10.22331/​q-2020-07-06-291.
https:/​/​doi.org/​10.22331/​q-2020-07-06-291

[10] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm, 2014. URL https:/​/​arxiv.org/​abs/​1411.4028.
arXiv:1411.4028

[11] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man Hong Yung, Xiao Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5: 4213, 2014. ISSN 20411723. 10.1038/​ncomms5213.
https:/​/​doi.org/​10.1038/​ncomms5213

[12] Giacomo Nannicini. Performance of hybrid quantum-classical variational heuristics for combinatorial optimization. Physical Review E, 99: 013304, Jan 2019. 10.1103/​PhysRevE.99.013304.
https:/​/​doi.org/​10.1103/​PhysRevE.99.013304

[13] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner. Improving variational quantum optimization using cvar. Quantum, 4: 256, Apr 2020. ISSN 2521-327X. 10.22331/​q-2020-04-20-256.
https:/​/​doi.org/​10.22331/​q-2020-04-20-256

[14] L. Braine, D. J. Egger, J. Glick, and S. Woerner. Quantum algorithms for mixed binary optimization applied to transaction settlement. IEEE Transactions on Quantum Engineering, 2: 1–8, 2021. 10.1109/​TQE.2021.3063635.
https:/​/​doi.org/​10.1109/​TQE.2021.3063635

[15] Andrew M Childs, Edward Farhi, and John Preskill. Robustness of adiabatic quantum computation. Physical Review A, 65 (1): 012322, 2001. 10.1103/​PhysRevA.65.012322.
https:/​/​doi.org/​10.1103/​PhysRevA.65.012322

[16] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. Quantum annealing with manufactured spins. Nature, 473 (7346): 194–198, 2011. 10.1038/​nature10012.
https:/​/​doi.org/​10.1038/​nature10012

[17] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum, 1996. URL https:/​/​arxiv.org/​abs/​quant-ph/​9607014.
arXiv:quant-ph/9607014

[18] D. Bulger, W. P. Baritompa, and G. R. Wood. Implementing pure adaptive search with grover's quantum algorithm. Journal of Optimization Theory and Applications, 116 (3): 517–529, Mar 2003. ISSN 1573-2878. 10.1023/​A:1023061218864.
https:/​/​doi.org/​10.1023/​A:1023061218864

[19] W. P. Baritompa, D. W. Bulger, and G. R. Wood. Grover's quantum algorithm applied to global optimization. SIAM J. on Optimization, 15 (4): 1170–1184, April 2005. ISSN 1052-6234. 10.1137/​040605072.
https:/​/​doi.org/​10.1137/​040605072

[20] Austin Gilliam, Charlene Venci, Sreraman Muralidharan, Vitaliy Dorum, Eric May, Rajesh Narasimhan, and Constantin Gonciulea. Foundational patterns for efficient quantum computing, 2019. URL https:/​/​arxiv.org/​abs/​1907.11513.
arXiv:1907.11513

[21] Thomas G. Draper. Addition on a quantum computer, 2000. URL https:/​/​arxiv.org/​abs/​quant-ph/​0008033.
arXiv:quant-ph/0008033

[22] Román Orús, Samuel Mugel, and Enrique Lizaso. Quantum computing for finance: Overview and prospects. Reviews in Physics, 4: 100028, Nov 2019. ISSN 2405-4283. 10.1016/​j.revip.2019.100028.
https:/​/​doi.org/​10.1016/​j.revip.2019.100028

[23] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner, and Elena Yndurain. Quantum computing for finance: State-of-the-art and future prospects. IEEE Transactions on Quantum Engineering, 1: 1–24, 2020a. ISSN 2689-1808. 10.1109/​tqe.2020.3030314.
https:/​/​doi.org/​10.1109/​tqe.2020.3030314

[24] Patrick Rebentrost and Seth Lloyd. Quantum computational finance: quantum algorithm for portfolio optimization, 2018. URL https:/​/​arxiv.org/​abs/​1811.03975.
arXiv:1811.03975

[25] Davide Venturelli and Alexei Kondratyev. Reverse Quantum Annealing Approach to Portfolio Optimization Problems. Quantum Machine Intelligence, 1, 2019. 10.1007/​s42484-019-00001-w.
https:/​/​doi.org/​10.1007/​s42484-019-00001-w

[26] Daniel J. Egger, Jakub Marecek, and Stefan Woerner. Warm-starting quantum optimization, 2020b. URL https:/​/​arxiv.org/​abs/​2009.10095.
arXiv:2009.10095

[27] Héctor Abraham et. al. Qiskit: An open-source framework for quantum computing. 2019. 10.5281/​zenodo.2562110.
https:/​/​doi.org/​10.5281/​zenodo.2562110

[28] Michele Mosca. Quantum searching, counting and amplitude amplification by eigenvector analysis. In Proceedings of Randomized Algorithms, Workshop of Mathematical Foundations of Computer Science, pages 90–100, 1998. URL https:/​/​eccc.weizmann.ac.il/​/​resources/​pdf/​moscafi.pdf.
https:/​/​eccc.weizmann.ac.il/​/​resources/​pdf/​moscafi.pdf

[29] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum Amplitude Amplification and Estimation. Contemporary Mathematics, 305, 2002. 10.1090/​conm/​305.
https:/​/​doi.org/​10.1090/​conm/​305

[30] Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, and Naoki Yamamoto. Amplitude estimation without phase estimation. Quantum Information Processing, 19 (2), Jan 2020. ISSN 1573-1332. 10.1007/​s11128-019-2565-2.
https:/​/​doi.org/​10.1007/​s11128-019-2565-2

[31] Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. Symposium on Simplicity in Algorithms, page 24–32, Jan 2020. 10.1137/​1.9781611976014.5.
https:/​/​doi.org/​10.1137/​1.9781611976014.5

[32] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46 (4-5): 493–505, Jun 1998. ISSN 1521-3978. 10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P.
https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[33] Benjamín Barán and Marcos Villagra. Multiobjective Optimization Grover Adaptive Search, pages 191–211. Springer International Publishing, Cham, 2019. ISBN 978-3-319-99648-6. 10.1007/​978-3-319-99648-6_11.
https:/​/​doi.org/​10.1007/​978-3-319-99648-6_11

[34] Yunseong Nam, Yuan Su, and Dmitri Maslov. Approximate quantum fourier transform with o(n log(n)) t gates. npj Quantum Information, 6 (1), Mar 2020. ISSN 2056-6387. 10.1038/​s41534-020-0257-5.
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[35] Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit, 2004. URL https:/​/​arxiv.org/​abs/​quant-ph/​0410184.
arXiv:quant-ph/0410184

[36] Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, and Krysta M. Svore. A logarithmic-depth quantum carry-lookahead adder. Quantum Info. Comput., 6 (4): 351–369, July 2006. ISSN 1533-7146. 10.26421/​QIC6.4-5-4.
https:/​/​doi.org/​10.26421/​QIC6.4-5-4

[37] Craig Gidney. Halving the cost of quantum addition. Quantum, 2: 74, Jun 2018. ISSN 2521-327X. 10.22331/​q-2018-06-18-74.
https:/​/​doi.org/​10.22331/​q-2018-06-18-74

[38] Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation, and Jay M. Gambetta. Validating quantum computers using randomized model circuits. Physical Review A, 100 (3), Sep 2019. ISSN 2469-9934. 10.1103/​physreva.100.032328.
https:/​/​doi.org/​10.1103/​physreva.100.032328

[39] A. Dewes, F. R. Ong, V. Schmitt, R. Lauro, N. Boulant, P. Bertet, D. Vion, and D. Esteve. Characterization of a two-transmon processor with individual single-shot qubit readout. Phys. Rev. Lett., 108: 057002, Feb 2012. 10.1103/​PhysRevLett.108.057002.
https:/​/​doi.org/​10.1103/​PhysRevLett.108.057002

[40] Svante Janson. Moments of gamma type and the brownian supremum process area. Probab. Surveys, 7: 1–52, 2010. 10.1214/​10-PS160.
https:/​/​doi.org/​10.1214/​10-PS160

[41] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, New York, NY, USA, 10th edition, 2011. ISBN 1107002176, 9781107002173. 10.1017/​CBO9780511976667.
https:/​/​doi.org/​10.1017/​CBO9780511976667

Cited by

[1] Claudio Gambella and Andrea Simonetto, "Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers", arXiv:2001.02069.

[2] Julien Gacon, Christa Zoufal, Giuseppe Carleo, and Stefan Woerner, "Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information", arXiv:2103.09232.

[3] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner, and Elena Yndurain, "Quantum Computing for Finance: State of the Art and Future Prospects", arXiv:2006.14510.

[4] Yidong Liao, Min-Hsiu Hsieh, and Chris Ferrie, "Quantum Optimization for Training Quantum Neural Networks", arXiv:2103.17047.

[5] Austin Gilliam, Marco Pistoia, and Constantin Gonciulea, "Canonical Construction of Quantum Oracles", arXiv:2006.10656.

[6] Austin Gilliam, Marco Pistoia, and Constantin Gonciulea, "Optimizing Quantum Search Using a Generalized Version of Grover's Algorithm", arXiv:2005.06468.

[7] Austin Gilliam, Marco Pistoia, and Constantin Gonciulea, "Optimizing Quantum Search with a Binomial Version of Grover's Algorithm", arXiv:2007.10894.

[8] Su Yeon Chang, Steven Herbert, Sofia Vallecorsa, Elías F. Combarro, and Ross Duncan, "Dual-Parameterized Quantum Circuit GAN Model in High Energy Physics", arXiv:2103.15470.

[9] Sayantan Pramanik, M Girish Chandra, Shampa Sarkar, and Manoj Nambiar, "Approximate Phase Search and Eigen Estimation using Modified Grover's Algorithm", arXiv:2012.11497.

[10] Chien-Hung Cho, Chih-Yu Chen, Kuo-Chin Chen, Tsung-Wei Huang, Ming-Chien Hsu, Ning-Ping Cao, Bei Zeng, Seng-Ghee Tan, and Ching-Ray Chang, "Quantum computation: Algorithms and Applications", Chinese Journal of Physics 72, 248 (2021).

The above citations are from SAO/NASA ADS (last updated successfully 2021-08-01 12:27:05). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2021-08-01 12:27:03).