A practitioner’s guide to quantum algorithms for optimisation problems. (English) Zbl 1534.81038
Summary: Quantum computing is gaining popularity across a wide range of scientific disciplines due to its potential to solve long-standing computational problems that are considered intractable with classical computers. One promising area where quantum computing has potential is in the speed-up of \(NP\)-hard optimisation problems that are common in industrial areas such as logistics and finance. Newcomers to the field of quantum computing who are interested in using this technology to solve optimisation problems do not have an easily accessible source of information on the current capabilities of quantum computers and algorithms. This paper aims to provide a comprehensive overview of the theory of quantum optimisation techniques and their practical application, focusing on their near-term potential for noisy intermediate scale quantum devices. The paper starts by drawing parallels between classical and quantum optimisation problems, highlighting their conceptual similarities and differences. Two main paradigms for quantum hardware are then discussed: analogue and gate-based quantum computers. While analog devices such as quantum annealers are effective for some optimisation problems, they have limitations and cannot be used for universal quantum computation. In contrast, gate-based quantum computers offer the potential for universal quantum computation, but they face challenges with hardware limitations and accurate gate implementation. The paper provides a detailed mathematical discussion with references to key works in the field, as well as a more practical discussion with relevant examples. The most popular techniques for quantum optimisation on gate-based quantum computers, the quantum approximate optimisation algorithm and the quantum alternating operator ansatz framework, are discussed in detail. However, it is still unclear whether these techniques will yield quantum advantage, even with advancements in hardware and noise reduction. The paper concludes with a discussion of the challenges facing quantum optimisation techniques and the need for further research and development to identify new, effective methods for achieving quantum advantage.
{© 2023 The Author(s). Published by IOP Publishing Ltd}
{© 2023 The Author(s). Published by IOP Publishing Ltd}
MSC:
| 81P68 | Quantum computation |
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 81P65 | Quantum gates |
| 13P25 | Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) |
| 62J12 | Generalized linear models (logistic models) |
| 60H50 | Regularization by noise |
| 81-10 | Mathematical modeling or simulation for problems pertaining to quantum theory |
Keywords:
quantum optimisation; combinatorial optimisation; quantum approximate optimisation algorithm; quantum alternating operator ansatz; gate-based quantum computingSoftware:
VRPReferences:
| [1] | Shor, P. W., Algorithms for quantum computation: discrete logarithms and factoring, pp 124-34 (1994) |
| [2] | Mensa, S.; Sahin, E.; Tacchino, F.; Barkoutsos, P. K.; Tavernelli, I., Quantum machine learning framework for virtual screening in drug discovery: a prospective quantum advantage, Mach. Learn.: Sci. Technol., 4 (2023) · doi:10.1088/2632-2153/acb900 |
| [3] | Bauer, B.; Bravyi, S.; Motta, M.; Chan, G. K-L, Quantum algorithms for quantum chemistry and quantum materials science, Chem. Rev., 120 (2020) · doi:10.1021/acs.chemrev.9b00829 |
| [4] | Biamonte, J.; Wittek, P.; Pancotti, N.; Rebentrost, P.; Wiebe, N.; Lloyd, S., Quantum machine learning, Nature, 549, 195 (2017) · doi:10.1038/nature23474 |
| [5] | Vogiatzis, C.; Pardalos, P. M., Combinatorial optimization in transportation and logistics networks, Handbook of Combinatorial Optimization, pp 673-722 (2013), Springer |
| [6] | Bentley, C D BMarsh, SCarvalho, A R RKilby, PBiercuk, M JQuantum computing for transport optimization · doi:10.48550/arXiv.2206.07313 |
| [7] | Clark, J.; West, T.; Zammit, J.; Guo, X.; Mason, L.; Russell, D., Towards real time multi-robot routing using quantum computing technologies, pp 111-9 (2019) |
| [8] | Osaba, E.; Villar-Rodriguez, E.; Oregi, I., A systematic literature review of quantum computing for routing problems, IEEE Access, 10 (2022) · doi:10.1109/ACCESS.2022.3177790 |
| [9] | Yarkoni, S.; Neukart, F.; Tagle, E. M G.; Magiera, N.; Mehta, B.; Hire, K.; Narkhede, S.; Hofmann, M., Quantum shuttle: traffic navigation with quantum computing, pp 22-30 (2020) |
| [10] | Slate, N.; Matwiejew, E.; Marsh, S.; Wang, J. B., Quantum walk-based portfolio optimisation, Quantum, 5, 513 (2021) · doi:10.22331/q-2021-07-28-513 |
| [11] | Phillipson, F.; Bhatia, H. S., Portfolio optimisation using the d-wave quantum annealer, pp 45-59 (2021), Springer |
| [12] | Herman, D.; Googin, C.; Liu, X.; Galda, A.; Safro, I.; Sun, Y.; Pistoia, M.; Alexeev, Y., A survey of quantum computing for finance (2022) |
| [13] | Krelina, M., Quantum technology for military applications, EPJ Quantum Technol., 8, 24 (2021) · doi:10.1140/epjqt/s40507-021-00113-y |
| [14] | Boyd, S. P.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press · Zbl 1058.90049 |
| [15] | Applegate, D. L.; Bixby, R. E.; Chvátal, V.; Cook, W. J., The traveling salesman problem, The Traveling Salesman Problem (2011), Princeton University Press |
| [16] | Nielsen, M. A.; Chuang, I., Quantum Computation and Quantum Information (2002), American Association of Physics Teachers |
| [17] | Daley, A. J.; Bloch, I.; Kokail, C.; Flannigan, S.; Pearson, N.; Troyer, M.; Zoller, P., Practical quantum advantage in quantum simulation, Nature, 607, 667 (2022) · doi:10.1038/s41586-022-04940-6 |
| [18] | Korte, B. H.; Vygen, J.; Korte, B.; Vygen, J., Combinatorial Optimization, vol 1 (2011), Springer · Zbl 1207.90002 |
| [19] | Korte, B.; Vygen, J., Combinatorial Optimization (Algorithms and Combinatorics) (2018), Springer · Zbl 1390.90001 |
| [20] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1998), Courier Corporation |
| [21] | Blum, C.; Roli, A., Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Comput. Surv., 35, 268 (2003) · doi:10.1145/937503.937505 |
| [22] | Bookatz, A. D., QMA-complete problems, Quantum Inf. Comput., 14, 361 (2014) · doi:10.26421/QIC14.5-6-1 |
| [23] | Toth, P.; Vigo, D., The Vehicle Routing Problem (2002), SIAM · Zbl 0979.00026 |
| [24] | Strang, G.; Freund, L., Introduction to applied mathematics, J. Appl. Mech., 53, 480 (1986) · Zbl 0618.00015 · doi:10.1115/1.3171799 |
| [25] | King, A. D., Coherent quantum annealing in a programmable 2,000 qubit Ising chain, Nat. Phys., 18, 1324-8 (2022) · doi:10.1038/s41567-022-01741-6 |
| [26] | King, A. D., Quantum critical dynamics in a 5,000-qubit programmable spin glass, Nature, 617, 61 (2023) · doi:10.1038/s41586-023-05867-2 |
| [27] | Scholl, P., Quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms, Nature, 595, 233 (2021) · doi:10.1038/s41586-021-03585-1 |
| [28] | Saffman, M., Quantum computing with atomic qubits and Rydberg interactions: progress and challenges, J. Phys. B: At. Mol. Opt. Phys., 49 (2016) · doi:10.1088/0953-4075/49/20/202001 |
| [29] | Henriet, L.; Beguin, L.; Signoles, A.; Lahaye, T.; Browaeys, A.; Reymond, G-O; Jurczak, C., Quantum computing with neutral atoms, Quantum, 4, 327 (2020) · doi:10.22331/q-2020-09-21-327 |
| [30] | Ebadi, S., Quantum optimization of maximum independent set using Rydberg atom arrays, Science, 376, 1209-15 (2022) · doi:10.1126/science.abo6587 |
| [31] | Albash, T.; Lidar, D. A., Adiabatic quantum computation, Rev. Mod. Phys., 90 (2018) · doi:10.1103/RevModPhys.90.015002 |
| [32] | Hauke, P.; Katzgraber, H. G.; Lechner, W.; Nishimori, H.; Oliver, W. D., Perspectives of quantum annealing: methods and implementations, Rep. Prog. Phys., 83 (2020) · doi:10.1088/1361-6633/ab85b8 |
| [33] | Yarkoni, S.; Raponi, E.; Bäck, T.; Schmitt, S., Quantum annealing for industry applications: introduction and review, Rep. Prog. Phys., 85 (2022) · doi:10.1088/1361-6633/ac8c54 |
| [34] | Das, A.; Chakrabarti, B. K., Colloquium: quantum annealing and analog quantum computation, Rev. Mod. Phys., 80, 1061 (2008) · Zbl 1205.81058 · doi:10.1103/RevModPhys.80.1061 |
| [35] | Santoro, G. E.; Tosatti, E., Optimization using quantum mechanics: quantum annealing through adiabatic evolution, J. Phys. A: Math. Gen., 39, R393 (2006) · Zbl 1130.49037 · doi:10.1088/0305-4470/39/36/R01 |
| [36] | Jörg, T.; Krzakala, F.; Kurchan, J.; Maggs, A. C., Simple glass models and their quantum annealing, Phys. Rev. Lett., 101 (2008) · doi:10.1103/PhysRevLett.101.147204 |
| [37] | Aharonov, D.; van Dam, W.; Kempe, J.; Landau, Z.; Lloyd, S.; Regev, O., Adiabatic quantum computation is equivalent to standard quantum computation, SIAM Rev., 50, 755 (2008) · Zbl 1152.81008 · doi:10.1137/080734479 |
| [38] | Bravyi, S.; Terhal, B., Complexity of stoquastic frustration-free hamiltonians, SIAM J. Comput., 39, 1462 (2010) · Zbl 1206.68121 · doi:10.1137/08072689X |
| [39] | Lucas, A., Ising formulations of many NP problems, Front. Phys., 2, 5 (2014) · doi:10.3389/fphy.2014.00005 |
| [40] | King, A. D., Scaling advantage over path-integral Monte Carlo in quantum simulation of geometrically frustrated magnets, Nat. Commun., 12, 1113 (2021) · doi:10.1038/s41467-021-20901-5 |
| [41] | Mandrá, S.; Katzgraber, H. G.; Thomas, C., The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again), Quantum Sci. Technol., 2 (2017) · doi:10.1088/2058-9565/aa7877 |
| [42] | Sao, M.; Watanabe, H.; Musha, Y.; Utsunomiya, A., Application of digital annealer for faster combinatorial optimization, Fujitsu Sci. Tech. J., 55, 45-51 (2019) |
| [43] | Kitaev, A. Y., Quantum computations: algorithms and error correction, Russ. Math. Surv., 52, 1191 (1997) · Zbl 0917.68063 · doi:10.1070/RM1997v052n06ABEH002155 |
| [44] | Grover, L. K., A fast quantum mechanical algorithm for database search (1996) · Zbl 0922.68044 |
| [45] | McClean, J. R.; Romero, J.; Babbush, R.; Aspuru-Guzik, A., The theory of variational hybrid quantum-classical algorithms, New J. Phys., 18 (2016) · Zbl 1456.81149 · doi:10.1088/1367-2630/18/2/023023 |
| [46] | Cerezo, M., Variational quantum algorithms, Nat. Rev. Phys., 3, 625 (2021) · doi:10.1038/s42254-021-00348-9 |
| [47] | Tilly, J., The variational quantum eigensolver: a review of methods and best practices, Phys. Rep., 986, 1 (2022) · Zbl 1510.81052 · doi:10.1016/j.physrep.2022.08.003 |
| [48] | Lee, J.; Magann, A. B.; Rabitz, H. A.; Arenz, C., Progress toward favorable landscapes in quantum combinatorial optimization, Phys. Rev. A, 104 (2021) · doi:10.1103/PhysRevA.104.032401 |
| [49] | Kim, J.; Kim, J.; Rosa, D., Universal effectiveness of high-depth circuits in variational eigenproblems, Phys. Rev. Res., 3 (2021) · doi:10.1103/PhysRevResearch.3.023203 |
| [50] | Larocca, M.; Ju, N.; García-Martín, D.; Coles, P. J.; Cerezo, M., Theory of overparametrization in quantum neural networks (2021) |
| [51] | Farhi, E.; Goldstone, J.; Gutmann, S., A quantum approximate optimization algorithm (2014) |
| [52] | Farhi, E.; Harrow, A. W., Quantum supremacy through the quantum approximate optimization algorithm (2019) |
| [53] | Farhi, E.; Goldstone, J.; Gutmann, S., A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem (2015) |
| [54] | Barak, B.; Moitra, A.; O’Donnell, R.; Raghavendra, P.; Regev, O.; Steurer, D.; Trevisan, L.; Vijayaraghavan, A.; Witmer, D.; Wright, J., Beating the random assignment on constraint satisfaction problems of bounded degree (2015) · Zbl 1375.68102 |
| [55] | Guerreschi, G. G.; Matsuura, A. Y., QAOA for Max-Cut requires hundreds of qubits for quantum speed-up, Sci. Rep., 9, 6903 (2019) · doi:10.1038/s41598-019-43176-9 |
| [56] | Wurtz, J.; Love, P., MaxCut quantum approximate optimization algorithm performance guarantees for p > 1, Phys. Rev. A, 103 (2021) · doi:10.1103/PhysRevA.103.042612 |
| [57] | Marwaha, K.; Hadfield, S., Bounds on approximating max κXOR with quantum and classical local algorithms, Quantum, 6, 757 (2022) · doi:10.22331/q-2022-07-07-757 |
| [58] | Marwaha, K., Local classical MAX-CUT algorithm outperforms p = 2 QAOA on high-girth regular graphs, Quantum, 5, 437 (2021) · doi:10.22331/q-2021-04-20-437 |
| [59] | Crooks, G. E., Performance of the quantum approximate optimization algorithm on the maximum cut problem (2018) |
| [60] | Wang, Z.; Hadfield, S.; Jiang, Z.; Rieffel, E. G., Quantum approximate optimization algorithm for MaxCut: a fermionic view, Phys. Rev. A, 97 (2018) · doi:10.1103/PhysRevA.97.022304 |
| [61] | Brandão, F. G S. L.; Broughton, M.; Farhi, E.; Gutmann, S.; Neven, H., For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances (2018) |
| [62] | Sack, S. H.; Serbyn, M., Quantum annealing initialization of the quantum approximate optimization algorithm, Quantum, 5, 491 (2021) · doi:10.22331/q-2021-07-01-491 |
| [63] | Galda, A.; Liu, X.; Lykov, D.; Alexeev, Y.; Safro, I., Transferability of optimal QAOA parameters between random graphs (2021) |
| [64] | Akshay, V.; Rabinovich, D.; Campos, E.; Biamonte, J., Parameter concentrations in quantum approximate optimization, Phys. Rev. A, 104 (2021) · doi:10.1103/PhysRevA.104.L010401 |
| [65] | Boulebnane, S.; Montanaro, A., Predicting parameters for the quantum approximate optimization algorithm for MAX-CUT from the infinite-size limit (2021) |
| [66] | Zhou, L.; Wang, S-T; Choi, S.; Pichler, H.; Lukin, M. D., Quantum approximate optimization algorithm: performance, mechanism and implementation on near-term devices, Phys. Rev. X, 10 (2020) · doi:10.1103/PhysRevX.10.021067 |
| [67] | Streif, M.; Leib, M., Training the quantum approximate optimization algorithm without access to a quantum processing unit, Quantum Sci. Technol., 5 (2020) · doi:10.1088/2058-9565/ab8c2b |
| [68] | Zhu, L.; Tang, H. L.; Barron, G. S.; Calderon-Vargas, F. A.; Mayhall, N. J.; Barnes, E.; Economou, S. E., Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer, Phys. Rev. Res., 4 (2022) · doi:10.1103/PhysRevResearch.4.033029 |
| [69] | Majumdar, R.; Madan, D.; Bhoumik, D.; Vinayagamurthy, D.; Raghunathan, S.; Sur-Kolay, S., Optimizing ansatz design in QAOA for Max-cut (2021) |
| [70] | Ayanzadeh, R.; Alavisamani, N.; Das, P.; Qureshi, M., Frozenqubits: boosting fidelity of QAOA by skipping hotspot nodes (2022) |
| [71] | Guerreschi, G. G., Solving quadratic unconstrained binary optimization with divide-and-conquer and quantum algorithms (2021) |
| [72] | Zhou, Z.; Du, Y.; Tian, X.; Tao, D., QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines, Phys. Rev. Appl., 19 (2023) · doi:10.1103/PhysRevApplied.19.024027 |
| [73] | Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684 |
| [74] | Alam, S. G M.; Ash-Saki, A., Analysis of quantum approximate optimization algorithm under realistic noise in superconducting qubits (2019) |
| [75] | Alam, S. G M.; Ash-Saki, A., Design-space exploration of quantum approximate optimization algorithm under noise, p 1 (2020) |
| [76] | Lotshaw, P. C.; Nguyen, T.; Santana, A.; McCaskey, A.; Herrman, R.; Ostrowski, J.; Siopsis, G.; Humble, T. S., Scaling quantum approximate optimization on near-term hardware, Sci. Rep., 12 (2022) · doi:10.1038/s41598-022-14767-w |
| [77] | Stilck França, D.; Garcia-Patron, R., Limitations of optimization algorithms on noisy quantum devices, Nat. Phys., 17, 1221 (2021) · doi:10.1038/s41567-021-01356-3 |
| [78] | Weidenfeller, J.; Valor, L. C.; Gacon, J.; Tornow, C.; Bello, L.; Woerner, S.; Egger, D. J., Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware, Quantum, 6, 870 (2022) · doi:10.22331/q-2022-12-07-870 |
| [79] | Willsch, M.; Willsch, D.; Jin, F.; De Raedt, H.; Michielsen, K., Benchmarking the quantum approximate optimization algorithm, Quantum Inf. Process., 19, 1 (2020) · Zbl 1508.81554 · doi:10.1007/s11128-020-02692-8 |
| [80] | Lubinski, T.; Coffrin, C.; McGeoch, C.; Sathe, P.; Apanavicius, J.; Neira, D. E B., Optimization applications as quantum performance benchmarks (2023) |
| [81] | Harrigan, M. P., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nat. Phys., 17, 332 (2021) · doi:10.1038/s41567-020-01105-y |
| [82] | Streif, M.; Yarkoni, S.; Skolik, A.; Neukart, F.; Leib, M., Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm, Phys. Rev. A, 104 (2021) · doi:10.1103/PhysRevA.104.012403 |
| [83] | Farhi, E.; Gamarnik, D.; Gutmann, S., The quantum approximate optimization algorithm needs to see the whole graph: worst case examples (2020) |
| [84] | Farhi, E.; Gamarnik, D.; Gutmann, S., The quantum approximate optimization algorithm needs to see the whole graph: a typical case (2020) |
| [85] | Hadfield, S.; Wang, Z.; O’Gorman, B.; Rieffel, E. G.; Venturelli, D.; Biswas, R., From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Algorithms, 12, 34 (2019) · Zbl 1461.68085 · doi:10.3390/a12020034 |
| [86] | Hadfield, S.; Hogg, T.; Rieffel, E. G., Analytical framework for quantum alternating operator ansätze, Quantum Sci. Technol., 8 (2022) · doi:10.1088/2058-9565/aca3ce |
| [87] | Ruan, Y.; Marsh, S.; Xue, X.; Li, X.; Liu, Z.; Wang, J., Quantum approximate algorithm for NP optimization problems with constraints (2020) |
| [88] | Fuchs, F. G.; Kolden, H.; Aase, N. H.; Sartor, G., Efficient encoding of the weighted MAX k -CUT on a quantum computer using QAOA, SN Comput. Sci., 2, 89 (2021) · doi:10.1007/s42979-020-00437-z |
| [89] | Marsh, S.; Wang, J. B., Combinatorial optimization via highly efficient quantum walks, Phys. Rev. Res., 2 (2020) · doi:10.1103/PhysRevResearch.2.023302 |
| [90] | Fuchs, F. G.; Lye, K. O.; Nilsen, H. M.; Stasik, A. J.; Sartor, G., Constraint preserving mixers for QAOA, Algorithms, 15, 202 (2022) · doi:10.3390/a15060202 |
| [91] | Wang, Z.; Rubin, N. C.; Dominy, J. M.; Rieffel, E. G., XY mixers: analytical and numerical results for the quantum alternating operator ansatz, Phys. Rev. A, 101 (2020) · doi:10.1103/PhysRevA.101.012320 |
| [92] | Saleem, Z. H.; Tomesh, T.; Tariq, B.; Suchara, M., Approaches to constrained quantum approximate optimization, SN Comput. Sci., 4, 183 (2023) · doi:10.1007/s42979-022-01638-4 |
| [93] | Egger, D. J.; mareček, J.; Woerner, S., Warm-starting quantum optimization, Quantum, 5, 479 (2021) · doi:10.22331/q-2021-06-17-479 |
| [94] | Tate, R.; Farhadi, M.; Herold, C.; Mohler, G.; Gupta, S., Bridging classical and quantum with SDP initialized warm-starts for QAOA, ACM Trans. Quantum Comput., 4, 1 (2023) · doi:10.1145/3549554 |
| [95] | Okada, K. N.; Nishi, H.; Kosugi, T.; Matsushita, Y., Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions (2022) |
| [96] | Kremenetski, V.; Hogg, T.; Hadfield, S.; Cotton, S. J.; Tubman, N. M., Quantum alternating operator ansatz (QAOA) phase diagrams and applications for quantum chemistry (2021) |
| [97] | Babej, T.; Ing, C.; Fingerhuth, M., Coarse-grained lattice protein folding on a quantum annealer (2018) |
| [98] | Fingerhuth, M.; Babej, T.; Ing, C., A quantum alternating operator ansatz with hard and soft constraints for lattice protein folding (2018) |
| [99] | Shaydulin, R.; Hadfield, S.; Hogg, T.; Safra, I., Classical symmetries and the quantum approximate optimization algorithm, Quantum Inf. Process., 20, 359 (2021) · Zbl 1508.81530 · doi:10.1007/s11128-021-03298-4 |
| [100] | Zhang, Y.; Zhang, R.; Potter, A. C., QED driven QAOA for network-flow optimization, Quantum, 5, 510 (2021) · doi:10.22331/q-2021-07-27-510 |
| [101] | Niroula, P.; Shaydulin, R.; Yalovetsky, R.; Minssen, P.; Herman, D.; Hu, S.; Pistoia, M., Constrained quantum optimization for extractive summarization on a trappedion quantum computer, Sci. Rep., 12 (2022) · doi:10.1038/s41598-022-20853-w |
| [102] | Liu, X.; Angone, A.; Shaydulin, R.; Safro, I.; Alexeev, Y.; Cincio, L., Layer VQE: a variational approach for combinatorial optimization on noisy quantum computers, IEEE Trans. Quantum Eng., 3, 1 (2022) · doi:10.1109/TQE.2022.3223368 |
| [103] | Baker, J. S.; Radha, S. K., Wasserstein solution quality and the quantum approximate optimization algorithm: a portfolio optimization case study (2022) |
| [104] | Aktar, S.; Bärtschi, A.; Badawy, A-H A.; Eidenbenz, S., A divide-and-conquer approach to Dicke state preparation, IEEE Trans. Quantum Eng., 3, 1 (2022) · doi:10.1109/TQE.2022.3174547 |
| [105] | Lee, Y. T.; Sidford, A.; Wong, S. C.; Chiu-Wai, S., A faster cutting plane method and its implications for combinatorial and convex optimization, pp 1049-65 (2015) |
| [106] | Arora, S.; Hazan, E.; Kale, S., Fast algorithms for approximate semidefinite programming using the multiplicative weights update method, pp 339-48 (2005) |
| [107] | Arora, S.; Hazan, E.; Kale, S., The multiplicative weights update method: a meta-algorithm and applications, Theory Comput., 8, 121 (2012) · Zbl 1283.68414 · doi:10.4086/toc.2012.v008a006 |
| [108] | Chakrabarti, S.; Childs, A. M.; Li, T.; Wu, X., Quantum algorithms and lower bounds for convex optimization, Quantum, 4, 221 (2020) · doi:10.22331/q-2020-01-13-221 |
| [109] | van Apeldoorn, J.; Gilyén, A.; Gribling, S.; de Wolf, R., Quantum SDP-solvers: better upper and lower bounds, Quantum, 4, 230 (2020) · doi:10.22331/q-2020-02-14-230 |
| [110] | Kerenidis, I.; Prakash, A., A quantum interior point method for LPs and SDPs, ACM Trans. Quantum Comput., 1, 1 (2020) · doi:10.1145/3406306 |
| [111] | Bharti, K.; Haug, T.; Vedral, V.; Kwek, L-C, Noisy intermediate-scale quantum algorithm for semidefinite programming, Phys. Rev. A, 105 (2022) · doi:10.1103/PhysRevA.105.052445 |
| [112] | Huang, B.; Jiang, S.; Song, Z.; Tao, R.; Zhang, R., A faster quantum algorithm for semidefinite programming via robust IPM framework (2023) |
| [113] | Brandão, F. G.; Svore, K. M., Quantum speed-ups for solving semidefinite programs, pp 415-26 (2017) |
| [114] | Crosson, E.; Lidar, D., Prospects for quantum enhancement with diabatic quantum annealing, Nat. Rev. Phys., 3, 466 (2021) · doi:10.1038/s42254-021-00313-6 |
| [115] | Amaro, D.; Modica, C.; Rosenkranz, M.; Fiorentini, M.; Benedetti, M.; Lubasch, M., Filtering variational quantum algorithms for combinatorial optimization, Quantum Sci. Technol., 7 (2022) · doi:10.1088/2058-9565/ac3e54 |
| [116] | Montanaro, A., Quantum speedup of branch-and-bound algorithms, Phys. Rev. Res., 2 (2020) · doi:10.1103/PhysRevResearch.2.013056 |
| [117] | Rančić, M. J., Noisy intermediate-scale quantum computing algorithm for solving an n-vertex MaxCut problem with log(n) qubits, Phys. Rev. Res., 5 (2021) · doi:10.1103/PhysRevResearch.5.L012021 |
| [118] | Chatterjee, Y.; Bourreau, E.; Rančić, M. J., Solving various np-hard problems using exponentially fewer qubits on a quantum computer (2023) |
| [119] | Dupont, M., Quantum enhanced greedy solver for optimization problems (2023) |
| [120] | Temme, K.; Osborne, T. J.; Vollbrecht, K. G.; Poulin, D.; Verstraete, F., Quantum metropolis sampling, Nature, 471, 87 (2011) · doi:10.1038/nature09770 |
| [121] | Yung, M-H; Aspuru-Guzik, A., A quantum-quantum metropolis algorithm, Proc. Natl Acad. Sci., 109, 754 (2012) · doi:10.1073/pnas.1111758109 |
| [122] | Shtanko, O.; Movassagh, R., Preparing thermal states on noiseless and noisy programmable quantum processors (2021) |
| [123] | Chen, C-F; Kastoryano, M. J.; Brandão, F. G S. L.; Gilyén, A., Quantum thermal state preparation (2023) |
| [124] | Matwiejew, E.; Pye, J.; Wang, J. B., Quantum optimisation for continuous multivariable functions by a structured search, Quantum Sci. Technol., 8 (2023) · doi:10.1088/2058-9565/ace6cc |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
