1Terra Quantum AG, Kornhausstrasse 25, 9000 St. Gallen, Switzerland
2QTF Centre of Excellence, Department of Applied Physics, Aalto University, P.O. Box 15100, FI-00076 AALTO, Finland
3InstituteQ – the Finnish Quantum Institute, Aalto University, Finland
4Physics Department, City College of the City University of New York, 160 Convent Ave, New York, NY 10031, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Quantum algorithms are getting extremely popular due to their potential to significantly outperform classical algorithms. Yet, applying quantum algorithms to optimization problems meets challenges related to the efficiency of quantum algorithms training, the shape of their cost landscape, the accuracy of their output, and their ability to scale to large-size problems. Here, we present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding. We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms. We employ numerical simulations to test it on $texttt{MaxCut}$ problems with complete weighted graphs with thousands of nodes and run the algorithm on a superconducting quantum processor. We find that for unconstrained $texttt{MaxCut}$ problems with more than 1000 nodes, the hybrid approach combining our algorithm with a classical solver called CPLEX can find a better solution than CPLEX alone. This demonstrates that hybrid optimization is one of the leading use cases for modern quantum devices.
Featured image: A plot of the energy (or cost) of the solutions as a function of the number of iterations. The constrained solutions are shown in red and the unconstrained solutions are in green. The dashed lines show the cost of the optimal solutions.
Popular summary
It is often useful to imagine each combination of settings as corresponding to a position on a map. The quantity being optimized — the energy efficiency in the previous example — would be represented by the height above sea level of the different map positions. In prior work, an efficient way of encoding optimization problems into quantum processors was combined with a gradient-based method (i.e., a method that uses the steepness or shallowness of the terrain to decide the next settings to try).
We build on this prior work by incorporating simple linear constraints into the problem. This is useful because it is usually the case that not every combination of settings is physically possible. Hence, the available options need to be constrained. Importantly, as shown by the analysis in the paper, our way of providing the constraints does not make the optimization problem more difficult or complicated.
► BibTeX data
► References
[1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. “Quantum approximate optimization of non-planar graph problems on a planar superconducting processor”. Nature Physics 17, 332–336 (2021).
https://doi.org/10.1038/s41567-020-01105-y
[2] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al. “Strong Quantum Computational Advantage Using a Superconducting Quantum Processor”. Phys. Rev. Lett. 127, 180501 (2021).
https://doi.org/10.1103/PhysRevLett.127.180501
[3] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, et al. “Quantum computational advantage via 60-qubit 24-cycle random circuit sampling”. Science Bulletin 67, 240–245 (2022).
https://doi.org/10.1016/j.scib.2021.10.017
[4] Suguru Endo, Zhenyu Cai, Simon C. Benjamin, and Xiao Yuan. “Hybrid Quantum-Classical Algorithms and Quantum Error Mitigation”. Journal of the Physical Society of Japan 90, 032001 (2021).
https://doi.org/10.7566/JPSJ.90.032001
[5] Michael Perelshtein, Asel Sagingalieva, Karan Pinto, Vishal Shete, Alexey Pakhomchik, Artem Melnikov, Florian Neukart, Georg Gesek, Alexey Melnikov, and Valerii Vinokur. “Practical application-specific advantage through hybrid quantum computing” (2022). arXiv:2205.04858.
arXiv:2205.04858
[6] Sergey Bravyi, Graeme Smith, and John A. Smolin. “Trading Classical and Quantum Computational Resources”. Phys. Rev. X 6, 021043 (2016).
https://doi.org/10.1103/PhysRevX.6.021043
[7] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. “The theory of variational hybrid quantum-classical algorithms”. New Journal of Physics 18, 023023 (2016).
https://doi.org/10.1088/1367-2630/18/2/023023
[8] Jun Li, Xiaodong Yang, Xinhua Peng, and Chang-Pu Sun. “Hybrid Quantum-Classical Approach to Quantum Optimal Control”. Phys. Rev. Lett. 118, 150503 (2017).
https://doi.org/10.1103/PhysRevLett.118.150503
[9] Daiwei Zhu, Norbert M Linke, Marcello Benedetti, Kevin A Landsman, Nhung H Nguyen, C Huerta Alderete, Alejandro Perdomo-Ortiz, Nathan Korda, A Garfoot, Charles Brecque, et al. “Training of quantum circuits on a hybrid quantum computer”. Science Advances 5, eaaw9918 (2019).
https://doi.org/10.1126/sciadv.aaw9918
[10] Akshay Ajagekar, Travis Humble, and Fengqi You. “Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems”. Computers & Chemical Engineering 132, 106630 (2020).
https://doi.org/10.1016/j.compchemeng.2019.106630
[11] Ruslan Shaydulin, Hayato Ushijima-Mwesigwa, Christian F. A. Negre, Ilya Safro, Susan M. Mniszewski, and Yuri Alexeev. “A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers”. Computer 52, 18–26 (2019).
https://doi.org/10.1109/MC.2019.2908942
[12] Libor Caha, Alexander Kliesch, and Robert Koenig. “Twisted hybrid algorithms for combinatorial optimization”. Quantum Science and Technology 7, 045013 (2022).
https://doi.org/10.1088/2058-9565/ac7f4f
[13] Boukthir Haddar, Mahdi Khemakhem, Saïd Hanafi, and Christophe Wilbaut. “A hybrid quantum particle swarm optimization for the Multidimensional Knapsack Problem”. Engineering Applications of Artificial Intelligence 55, 1–13 (2016).
https://doi.org/10.1016/j.engappai.2016.05.006
[14] Reza Mahroo and Amin Kargarian. “Hybrid Quantum-Classical Unit Commitment”. In 2022 IEEE Texas Power and Energy Conference (TPEC). Pages 1–5. (2022).
https://doi.org/10.1109/TPEC54980.2022.9750763
[15] Tony T Tran, Minh Do, Eleanor G Rieffel, Jeremy Frank, Zhihui Wang, Bryan O’Gorman, Davide Venturelli, and J Christopher Beck. “A Hybrid Quantum-Classical Approach to Solving Scheduling Problems”. In Ninth annual symposium on combinatorial search. Volume 7, pages 98–106. (2016).
https://doi.org/10.1609/socs.v7i1.18390
[16] Xiao-Hong Liu, Mi-Yuan Shan, Ren-Long Zhang, and Li-Hong Zhang. “Green Vehicle Routing Optimization Based on Carbon Emission and Multiobjective Hybrid Quantum Immune Algorithm”. Mathematical Problems in Engineering 2018, 8961505 (2018).
https://doi.org/10.1155/2018/8961505
[17] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. “Variational quantum algorithms”. Nature Reviews Physics 3, 625–644 (2021).
https://doi.org/10.1038/s42254-021-00348-9
[18] Samuel Mugel, Mario Abad, Miguel Bermejo, Javier Sánchez, Enrique Lizaso, and Román Orús. “Hybrid quantum investment optimization with minimal holding period”. Scientific Reports 11, 19587 (2021).
https://doi.org/10.1038/s41598-021-98297-x
[19] Xiaozhen Ge, Re-Bing Wu, and Herschel Rabitz. “The optimization landscape of hybrid quantum–classical algorithms: From quantum control to NISQ applications”. Annual Reviews in Control 54, 314–323 (2022).
https://doi.org/10.1016/j.arcontrol.2022.06.001
[20] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A Quantum Approximate Optimization Algorithm” (2014). arXiv:1411.4028.
arXiv:1411.4028
[21] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt, and Kristel Michielsen. “Benchmarking the quantum approximate optimization algorithm”. Quantum Information Processing 19, 197 (2020).
https://doi.org/10.1007/s11128-020-02692-8
[22] Danylo Lykov, Jonathan Wurtz, Cody Poole, Mark Saffman, Tom Noel, and Yuri Alexeev. “Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm” (2022). arXiv:2206.03579.
arXiv:2206.03579
[23] Davide Venturelli and Alexei Kondratyev. “Reverse quantum annealing approach to portfolio optimization problems”. Quantum Machine Intelligence 1, 17–30 (2019).
https://doi.org/10.1007/s42484-019-00001-w
[24] WangChun Peng, BaoNan Wang, Feng Hu, YunJiang Wang, XianJin Fang, XingYuan Chen, and Chao Wang. “Factoring larger integers with fewer qubits via quantum annealing with optimized parameters”. Science China Physics, Mechanics & Astronomy 62, 60311 (2019).
https://doi.org/10.1007/s11433-018-9307-1
[25] Fred Glover, Gary Kochenberger, and Yu Du. “A Tutorial on Formulating and Using QUBO Models” (2018). arXiv:1811.11538.
arXiv:1811.11538
[26] Marcello Benedetti, Mattia Fiorentini, and Michael Lubasch. “Hardware-efficient variational quantum algorithms for time evolution”. Phys. Rev. Res. 3, 033083 (2021).
https://doi.org/10.1103/PhysRevResearch.3.033083
[27] Sheir Yarkoni, Elena Raponi, Thomas Bäck, and Sebastian Schmitt. “Quantum annealing for industry applications: introduction and review”. Reports on Progress in Physics 85, 104001 (2022).
https://doi.org/10.1088/1361-6633/ac8c54
[28] Benjamin Tan, Marc-Antoine Lemonde, Supanut Thanasilp, Jirawat Tangpanitanon, and Dimitris G. Angelakis. “Qubit-efficient encoding schemes for binary optimisation problems”. Quantum 5, 454 (2021).
https://doi.org/10.22331/q-2021-05-04-454
[29] Jin-Guo Liu and Lei Wang. “Differentiable learning of quantum circuit Born machines”. Phys. Rev. A 98, 062324 (2018).
https://doi.org/10.1103/PhysRevA.98.062324
[30] Atsushi Matsuo, Yudai Suzuki, and Shigeru Yamashita. “Problem-specific Parameterized Quantum Circuits of the VQE Algorithm for Optimization Problems” (2020). arXiv:2006.05643.
arXiv:2006.05643
[31] Austin Gilliam, Stefan Woerner, and Constantin Gonciulea. “Grover Adaptive Search for Constrained Polynomial Binary Optimization”. Quantum 5, 428 (2021).
https://doi.org/10.22331/q-2021-04-08-428
[32] Pradeep Niroula, Ruslan Shaydulin, Romina Yalovetzky, Pierre Minssen, Dylan Herman, Shaohan Hu, and Marco Pistoia. “Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer”. Scientific Reports 12, 17171 (2022).
https://doi.org/10.1038/s41598-022-20853-w
[33] M. R. Perelshtein and A. I. Pakhomchik. “Polynomial-time hybrid quantum algorithm for discrete optimization”. Patent (2021).
[34] A. I. Pakhomchik and M. R. Perelshtein. “Hybrid quantum computation architecture for solving a system of linear binary relations”. Patent (2022).
[35] Richard M. Karp. “Reducibility among Combinatorial Problems”. Pages 85–103. Springer US. Boston, MA (1972).
https://doi.org/10.1007/978-1-4684-2001-2_9
[36] “QMware: The first global quantum cloud”.
[37] “IBM Q experience”.
[38] Giuseppe E Santoro and Erio Tosatti. “Optimization using quantum mechanics: quantum annealing through adiabatic evolution”. Journal of Physics A: Mathematical and General 39, R393 (2006).
https://doi.org/10.1088/0305-4470/39/36/R01
[39] Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt. “An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design”. Operations Research 36, 493–513 (1988).
https://doi.org/10.1287/opre.36.3.493
[40] Giuseppe E. Santoro, Roman Martoňák, Erio Tosatti, and Roberto Car. “Theory of Quantum Annealing of an Ising Spin Glass”. Science 295, 2427–2430 (2002).
https://doi.org/10.1126/science.1068774
[41] Yurii Nesterov and Vladimir Spokoiny. “Random Gradient-Free Minimization of Convex Functions”. Foundations of Computational Mathematics 17, 527–566 (2017).
https://doi.org/10.1007/s10208-015-9296-2
[42] Michael JD Powell. “A view of algorithms for optimization without derivatives”. Mathematics Today-Bulletin of the Institute of Mathematics and its Applications 43, 170–174 (2007). url: optimization-online.org/wp-content/uploads/2007/06/1680.pdf.
https://optimization-online.org/wp-content/uploads/2007/06/1680.pdf
[43] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. “Evaluating analytic gradients on quantum hardware”. Phys. Rev. A 99, 032331 (2019).
https://doi.org/10.1103/PhysRevA.99.032331
[44] Diederik P. Kingma and Jimmy Ba. “Adam: A Method for Stochastic Optimization” (2014). arXiv:1412.6980.
arXiv:1412.6980
[45] Mohammad Kordzanganeh, Markus Buchberger, Maxim Povolotskii, Wilhelm Fischer, Andrii Kurkin, Wilfrid Somogyi, Asel Sagingalieva, Markus Pflitsch, and Alexey Melnikov. “Benchmarking simulated and physical quantum processing units using quantum and hybrid algorithms” Adv Quantum Technol. 2023, 6, 2300043 (2023). arXiv:2211.15631.
https://doi.org/10.1002/qute.202300043
arXiv:2211.15631
[46] IBM ILOG CPLEX. “User’s Manual for CPLEX”. International Business Machines Corporation 46, 157 (2009). url: www.ibm.com/docs/en/icos/12.8.0.0?topic=cplex-users-manual.
https://www.ibm.com/docs/en/icos/12.8.0.0?topic=cplex-users-manual
[47] M. Somov, M. Abelian, M. Podobrii, V. Voloshinov, M. Veshchezerova, B. Nuriev, D. Lemtiuzhnikova, M. Zarrin, and M. R. Perelshtein. “Hybrid quantum branch-and-bound pipeline for discrete optimisation”. unpublished (2023).
[48] Junyu Liu, Frederik Wilde, Antonio Anna Mele, Liang Jiang, and Jens Eisert. “Noise can be helpful for variational quantum algorithms” (2022). arXiv:2210.06723.
arXiv:2210.06723
[49] Steven R. White. “Density matrix formulation for quantum renormalization groups”. Phys. Rev. Lett. 69, 2863–2866 (1992).
https://doi.org/10.1103/PhysRevLett.69.2863
[50] Johnnie Gray and Stefanos Kourtis. “Hyper-optimized tensor network contraction”. Quantum 5, 410 (2021).
https://doi.org/10.22331/q-2021-03-15-410
[51] Igor L. Markov and Yaoyun Shi. “Simulating Quantum Computation by Contracting Tensor Networks”. SIAM Journal on Computing 38, 963–981 (2008).
https://doi.org/10.1137/050644756
[52] Yong Liu, Xin Liu, Fang Li, Haohuan Fu, Yuling Yang, Jiawei Song, Pengpeng Zhao, Zhen Wang, Dajia Peng, Huarong Chen, et al. “Closing the “quantum supremacy” gap: Achieving real-time simulation of a random quantum circuit using a new Sunway supercomputer”. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. SC ’21New York, NY, USA (2021). Association for Computing Machinery. url: dl.acm.org/doi/abs/10.1145/3458817.3487399.
https://doi.org/10.1145/3458817.3487399
[53] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. “Quantum supremacy using a programmable superconducting processor”. Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5
[54] C. Schön, K. Hammerer, M. M. Wolf, J. I. Cirac, and E. Solano. “Sequential generation of matrix-product states in cavity QED”. Phys. Rev. A 75, 032311 (2007).
https://doi.org/10.1103/PhysRevA.75.032311
[55] Kouhei Nakaji and Naoki Yamamoto. “Expressibility of the alternating layered ansatz for quantum computation”. Quantum 5, 434 (2021).
https://doi.org/10.22331/q-2021-04-19-434
[56] I. V. Oseledets. “Tensor-Train Decomposition”. SIAM Journal on Scientific Computing 33, 2295–2317 (2011).
https://doi.org/10.1137/090752286
[57] Román Orús. “A practical introduction to tensor networks: Matrix product states and projected entangled pair states”. Annals of Physics 349, 117–158 (2014).
https://doi.org/10.1016/j.aop.2014.06.013
[58] Danylo Lykov, Roman Schutski, Alexey Galda, Valeri Vinokur, and Yuri Alexeev. “Tensor Network Quantum Simulator With Step-Dependent Parallelization”. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 582–593. (2022).
https://doi.org/10.1109/QCE53715.2022.00081
[59] Ilia A Luchnikov, Mikhail E Krechetov, and Sergey N Filippov. “Riemannian geometry and automatic differentiation for optimization problems of quantum physics and quantum technologies”. New Journal of Physics 23, 073006 (2021).
https://doi.org/10.1088/1367-2630/ac0b02
[60] Martin Larocca, Piotr Czarnik, Kunal Sharma, Gopikrishnan Muraleedharan, Patrick J. Coles, and M. Cerezo. “Diagnosing barren plateaus with tools from quantum optimal control”. Quantum 6, 824 (2022).
https://doi.org/10.22331/q-2022-09-29-824
[61] Ar A Melnikov, A A Termanova, S V Dolgov, F Neukart, and M R Perelshtein. “Quantum state preparation using tensor networks”. Quantum Science and Technology 8, 035027 (2023).
https://doi.org/10.1088/2058-9565/acd9e7
[62] Karol Życzkowski and Hans-Jürgen Sommers. “Average fidelity between random quantum states”. Phys. Rev. A 71, 032313 (2005).
https://doi.org/10.1103/PhysRevA.71.032313
[63] Zoë Holmes, Kunal Sharma, M. Cerezo, and Patrick J. Coles. “Connecting Ansatz Expressibility to Gradient Magnitudes and Barren Plateaus”. PRX Quantum 3, 010313 (2022).
https://doi.org/10.1103/PRXQuantum.3.010313
[64] AI Pakhomchik, S Yudin, MR Perelshtein, A Alekseyenko, and S Yarkoni. “Solving workflow scheduling problems with QUBO modeling” (2022). arXiv:2205.04844.
arXiv:2205.04844
[65] Marko J. Rančić. “Noisy intermediate-scale quantum computing algorithm for solving an $n$-vertex MaxCut problem with log($n$) qubits”. Phys. Rev. Res. 5, L012021 (2023).
https://doi.org/10.1103/PhysRevResearch.5.L012021
[66] Yagnik Chatterjee, Eric Bourreau, and Marko J. Rančić. “Solving various NP-hard problems using exponentially fewer qubits on a Quantum Computer” (2023). arXiv:2301.06978.
arXiv:2301.06978
[67] Jacek Gondzio. “Warm start of the primal-dual method applied in the cutting-plane scheme”. Mathematical Programming 83, 125–143 (1998).
https://doi.org/10.1007/bf02680554
[68] Daniel J. Egger, Jakub Mareček, and Stefan Woerner. “Warm-starting quantum optimization”. Quantum 5, 479 (2021).
https://doi.org/10.22331/q-2021-06-17-479
[69] Felix Truger, Martin Beisel, Johanna Barzen, Frank Leymann, and Vladimir Yussupov. “Selection and Optimization of Hyperparameters in Warm-Started Quantum Optimization for the MaxCut Problem”. Electronics 11, 1033 (2022).
https://doi.org/10.3390/electronics11071033
[70] Sukin Sim, Peter D. Johnson, and Alán Aspuru-Guzik. “Expressibility and Entangling Capability of Parameterized Quantum Circuits for Hybrid Quantum-Classical Algorithms”. Advanced Quantum Technologies 2, 1900070 (2019).
https://doi.org/10.1002/qute.201900070
Cited by
[1] Ar A. Melnikov, A. A. Termanova, S. V. Dolgov, F. Neukart, and M. R. Perelshtein, “Quantum state preparation using tensor networks”, Quantum Science and Technology 8 3, 035027 (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2023-11-23 02:16:28). 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 2023-11-23 02:16:26).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-11-21-1186/
