Quantum approximate optimization via learning-based adaptive optimization
Schuetz, M. J., Brubaker, J. K. & Katzgraber, H. G. Combinatorial optimization with physics-inspired graph neural networks. Nat. Mach. Intell. 4, 367–377 (2022).
Angelini, M. C. & Ricci-Tersenghi, F. Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nat. Mach. Intell. 5, 29–31 (2022).
Boettcher, S. Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems. Nat. Mach. Intell. 5, 24–25 (2023).
Kadowaki, T. & Nishimori, H. Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355–5363 (1998).
Farhi, E. et al. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–475 (2001).
Johnson, M. W. et al. Quantum annealing with manufactured spins. Nature 473, 194–198 (2011).
Hauke, P., Katzgraber, H. G., Lechner, W., Nishimori, H. & Oliver, W. D. Perspectives of quantum annealing: methods and implementations. Rep. Prog. Phys. 83, 054,401 (2020).
Hibat-Allah, M., Inack, E. M., Wiersema, R., Melko, R. G. & Carrasquilla, J. Variational neural annealing. Nat. Mach. Intell. 3, 952–961 (2021).
Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. Preprint at https://arXiv.org/abs/1411.4028 (2014).
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, 021,067 (2020).
Harrigan, M. P. et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nat. Phys. 17, 332–336 (2021).
Larkin, J., Jonsson, M., Justice, D. & Guerreschi, G. G. Evaluation of QAOA based on the approximation ratio of individual samples. Quantum Sci. Technol. 7, 045,014 (2022).
Pelofske, E., Bärtschi, A. & Eidenbenz, S. In International Conference on High Performance Computing 240–258 (Springer, 2023).
Bittel, L. & Kliesch, M. Training variational quantum algorithms is NP-hard. Phys. Rev. Lett. 127, 120502 (2021).
Anschuetz, E. R. Critical points in quantum generative models. In proceedings International Conference on Learning Representations, https://openreview.net/forum?id=2f1z55GVQN (2022).
McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R. & Neven, H. Barren plateaus in quantum neural network training landscapes. Nat. Commun. 9, 4812 (2018).
Ortiz Marrero, C., Kieferová, M. & Wiebe, N. Entanglement-induced barren plateaus. PRX Quantum 2, 040316 (2021).
Wang, S. et al. Noise-induced barren plateaus in variational quantum algorithms. Nat. Commun. 12, 6961 (2021).
Arrasmith, A., Cerezo, M., Czarnik, P., Cincio, L. & Coles, P. J. Effect of barren plateaus on gradient-free optimization. Quantum 5, 558 (2021).
Verdon, G. et al. Learning to learn with quantum neural networks via classical neural networks. Preprint at https://arXiv.org/abs/1907.05415 (2019).
Alam, M., Ash-Saki, A. & Ghosh, S. in 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE) 686–689 (IEEE, 2020).
Khairy, S., Shaydulin, R., Cincio, L., Alexeev, Y. & Balaprakash, P. Learning to optimize variational quantum circuits to solve combinatorial problems. In Proceedings of the AAAI Conference on Artificial Intelligence, 34, 2367–2375 (2020).
Jain, N., Coyle, B., Kashefi, E. & Kumar, N. Graph neural network initialisation of quantum approximate optimisation. Quantum 6, 861 (2022).
Shaydulin, R., Marwaha, K., Wurtz, J. & Lotshaw, P. C. In 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS), Vol. 50, 64–71 (IEEE, 2021).
Moussa, C., Wang, H., Bäck, T. & Dunjko, V. Unsupervised strategies for identifying optimal parameters in quantum approximate optimization algorithm. EPJ Quantum Technol. 9, 11 (2022).
Amosy, O., Danzig, T., Porat, E., Chechik, G. & Makmal, A. Iterative-free quantum approximate optimization algorithm using neural networks. Preprint at https://arXiv.org/abs/2208.09888 (2022).
Yao, J., Li, H., Bukov, M., Lin, L. & Ying, L. In Mathematical and Scientific Machine Learning 49–64 (PMLR, 2022).
Xie, N., Lee, X., Cai, D., Saito, Y. & Asai, N. In Journal of Physics: Conference Series, Vol. 2595, 012001 (IOP Publishing, 2023).
Tate, R., Farhadi, M., Herold, C., Mohler, G. & Gupta, S. Bridging classical and quantum with SDP initialized warm-starts for QAOA. ACM Trans. Intell. Syst. Technol. 4, 1–39 (2023).
Campos, E., Rabinovich, D., Akshay, V. & Biamonte, J. Training saturation in layerwise quantum approximate optimization. Phys. Rev. A 104, L030401 (2021).
Shaydulin, R., Lotshaw, P. C., Larson, J., Ostrowski, J. & Humble, T. S. Parameter transfer for quantum approximate optimization of weighted maxcut. ACM Trans. Quantum Comput. 4, 1–15 (2023).
Sack, S. H., Medina, R. A., Kueng, R. & Serbyn, M. Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement. Phys. Rev. A 107, 062404 (2023).
Mele, A. A., Mbeng, G. B., Santoro, G. E., Collura, M. & Torta, P. Avoiding barren plateaus via transferability of smooth solutions in a hamiltonian variational ansatz. Phys. Rev. A 106, L060401 (2022).
Norouzi, M., Ranjbar, M. & Mori, G. Stacks of convolutional restricted boltzmann machines for shift-invariant feature learning. In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, CVPR Workshops 2009, 2735–2742 (2009).
Larocca, M., Ju, N., García-Martín, D., Coles, P. J. & Cerezo, M. Theory of overparametrization in quantum neural networks. Nat. Comput. Sci. 3, 542–551 (2023).
Kim, J., Kim, J. & Rosa, D. Universal effectiveness of high-depth circuits in variational eigenproblems. Phys. Rev. Res. 3, 023203 (2021).
Frazier, P. I. A tutorial on Bayesian optimization. Preprint at https://arXiv.org/abs/1807.02811 (2018).
Eriksson, D., Pearce, M., Gardner, J., Turner, R. D. & Poloczek, M. In Advances in Neural Information Processing Systems, Vol. 32 (eds Wallach, H.) (Curran Associates, Inc., 2019).
Letham, B., Karrer, B., Ottoni, G. & Bakshy, E. Constrained Bayesian optimization with noisy experiments. Bayesian Anal. 14, 495–519 (2019).
Letham, B., Calandra, R., Rai, A. & Bakshy, E. In Advances in Neural Information Processing Systems, Vol. 33 (eds Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. & Lin, H.) 1546–1558 (Curran Associates, Inc., 2020).
Yuan, Y. X. Recent advances in trust region algorithms. Math. Program. 151, 249–281 (2015).
Powell, M. J. D. A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation 51–67 (Springer, 1994).
Kingma, D. P. & Ba, J. Adam: A method for stochastic optimization. In Proceedings International Conference on Learning Representations (ICLR) (eds Bengio, Y. & LeCun, Y.) (2015).
Spall, J. Implementation of the simultaneous perturbation algorithm for stochastic optimization. IEEE Trans. Aerosp. Electron. Syst. 34, 817–823 (1998).
Tibaldi, S., Vodola, D., Tignone, E. & Ercolessi, E. Bayesian optimization for QAOA. IEEE Trans. Quantum Eng. 4, 1–11 (2023).
Self, C. N. et al. Variational quantum algorithm with information sharing. Npj Quantum Inf. 7, 116 (2021).
Tamiya, S. & Yamasaki, H. Stochastic gradient line Bayesian optimization for efficient noise-robust optimization of parameterized quantum circuits. Npj Quantum Inf. 8, 90 (2022).
Shaffer, R., Kocia, L. & Sarovar, M. Surrogate-based optimization for variational quantum algorithms. Phys. Rev. A 107, 032415 (2023).
Gelbart, M. A., Snoek, J. & Adams, R. P. Bayesian optimization with unknown constraints. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence 250–259 (Arlington, Virginia, USA Quebec City, Quebec, Canada, AUAI Press, 2014).
Bravyi, S., Sheldon, S., Kandala, A., Mckay, D. C. & Gambetta, J. M. Mitigating measurement errors in multiqubit experiments. Phys. Rev. A 103, 042605 (2021).
Nation, P. D., Kang, H., Sundaresan, N. & Gambetta, J. M. Scalable mitigation of measurement errors on quantum computers. PRX Quantum 2, 040326 (2021).
Temme, K., Bravyi, S. & Gambetta, J. M. Error mitigation for short-depth quantum circuits. Phys. Rev. Lett. 119, 180509 (2017).
Li, Y. & Benjamin, S. C. Efficient variational quantum simulator incorporating active error minimization. Phys. Rev. X. 7, 021050 (2017).
Eriksson, D. & Jankowiak, M. In Uncertainty in Artificial Intelligence 493–503 (PMLR, 2021).
Nayebi, A., Munteanu, A. & Poloczek, M. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 97 (eds Chaudhuri, K. & Salakhutdinov, R.) 4752–4761 (PMLR, 2019).
Martinez-Cantin, R., Tee, K. & McCourt, M. In International Conference on Artificial Intelligence and Statistics 1722–1731 (PMLR, 2018).
Fröhlich, L., Klenske, E., Vinogradska, J., Daniel, C. & Zeilinger, M. In International Conference on Artificial Intelligence and Statistics 2262–2272 (PMLR, 2020).
Daulton, S. et al. In International Conference on Machine Learning 4831–4866 (PMLR, 2022).
Dave, A. et al. Autonomous optimization of non-aqueous li-ion battery electrolytes via robotic experimentation and machine learning coupling. Nat. Commun. 13, 5454 (2022).
Zhang, Y., Apley, D. W. & Chen, W. Bayesian optimization for materials design with mixed quantitative and qualitative variables. Sci. Rep. 10, 1–13 (2020).
Cheng, L., Yang, Z., Liao, B., Hsieh, C. & Zhang, S. Odbo: Bayesian optimization with search space prescreening for directed protein evolution. Preprint at https://arXiv.org/abs/2205.09548 (2022).
Zhang, S. X., Hsieh, C. Y., Zhang, S. & Yao, H. Differentiable quantum architecture search. Quantum Sci. Technol. 7, 045023 (2022).
Weidinger, A., Mbeng, G. B. & Lechner, W. Error mitigation for quantum approximate optimization. Phys. Rev. A 108, 032408 (American Physical Society, 2023) https://doi.org/10.1103/PhysRevA.108.032408.
Mockus, J. Bayesian Approach to Global Optimization: Theory and Applications, Vol. 37 (Springer Science & Business Media, 2012).
Rasmussen, C. E. & Williams, C. K. I. Gaussian Processes for Machine Learning (MIT Press, 2006).
Gardner, J. R., Pleiss, G., Bindel, D., Weinberger, K. Q. & Wilson, A. G. In Advances in Neural Information Processing Systems (eds Bengio, S. et al.) (Curran Associates, Inc., 2018).
Srinivas, N., Krause, A., Kakade, S. & Seeger, M. Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning 1015–1022 (Omnipress, Madison, WI, USA, Haifa, Israel, 2010).
Zhang, S. X. et al. TensorCircuit: a quantum software framework for the NISQ era. Quantum 7, 912 (2023).
