Training variational quantum algorithms is NP-hard

J. Stokes, J. Izaac, N. Killoran, and G. Carleo, Quantum natural gradient , Quantum 4

Original

1909

Earlier work this paper cites.

R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu, A limited memory algorithm for bound constrained optimization , SIAM J. Sci. Comput. 16

1995

Earlier work this paper cites.

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , J. ACM 42

1995

Earlier work this paper cites.

M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost-function-dependent barren plateaus in shallow quantum neural networks , arXiv:2001.00550 [quant-ph]

Original

2001

Earlier work this paper cites.

J. Håstad, Some optimal inapproximability results , J. ACM 48

2001

Earlier work this paper cites.

A. Y. Kitaev, A. Shen, and M. N. Vyalyi, Classical and quantum computation , Vol. 47 (American Mathematical Society, 2002)

2002

Earlier work this paper cites.

D. Wierichs, C. Gogolin, and M. Kastoryano, Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer , arXiv:2004.14666 [quant-ph]

Original

2004

Earlier work this paper cites.

J. Kempe, A. Kitaev, and O. Regev, The complexity of the local Hamiltonian problem , SIAM Journal of Computing 35

2006

Earlier work this paper cites.

J. Eisert, Computational difficulty of global variations in the density matrix renormalization group , Phys. Rev. Lett. 97

2006

Cited alongside, same era.

S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, Noise-induced barren plateaus in variational quantum algorithms , arXiv:2007.14384 [quant-ph]

Original

2007

Cited alongside, same era.

S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? SIAM J. Comput. 37

2007

Cited alongside, same era.

A. Mari, T. R. Bromley, and N. Killoran, Estimating the gradient and higher-order derivatives on quantum hardware , arXiv:2008.06517 [quant-ph]

Original

2008

Cited alongside, same era.

B. Koczor and S. C. Benjamin, Quantum analytic descent , arXiv:2008.13774 [quant-ph]

M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms , arXiv:2012.09265 [quant-ph]

Original

2012

Later among the works it cites.

A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor , Nat. Commun. 5

Original

2014

Later among the works it cites.

Z. Landau, U. Vazirani, and T. Vidick, A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians , Nat. Phys. 11

Original

2015

Later among the works it cites.

J. Preskill, Quantum computing in the NISQ era and beyond , Quantum 2

Original

2018

Later among the works it cites.