Noise-induced barren plateaus in variational quantum algorithms.
Journal
Nature communications
ISSN: 2041-1723
Titre abrégé: Nat Commun
Pays: England
ID NLM: 101528555
Informations de publication
Date de publication:
29 Nov 2021
29 Nov 2021
Historique:
received:
04
02
2021
accepted:
01
11
2021
entrez:
30
11
2021
pubmed:
1
12
2021
medline:
1
12
2021
Statut:
epublish
Résumé
Variational Quantum Algorithms (VQAs) may be a path to quantum advantage on Noisy Intermediate-Scale Quantum (NISQ) computers. A natural question is whether noise on NISQ devices places fundamental limitations on VQA performance. We rigorously prove a serious limitation for noisy VQAs, in that the noise causes the training landscape to have a barren plateau (i.e., vanishing gradient). Specifically, for the local Pauli noise considered, we prove that the gradient vanishes exponentially in the number of qubits n if the depth of the ansatz grows linearly with n. These noise-induced barren plateaus (NIBPs) are conceptually different from noise-free barren plateaus, which are linked to random parameter initialization. Our result is formulated for a generic ansatz that includes as special cases the Quantum Alternating Operator Ansatz and the Unitary Coupled Cluster Ansatz, among others. For the former, our numerical heuristics demonstrate the NIBP phenomenon for a realistic hardware noise model.
Identifiants
pubmed: 34845216
doi: 10.1038/s41467-021-27045-6
pii: 10.1038/s41467-021-27045-6
pmc: PMC8630047
doi:
Types de publication
Journal Article
Langues
eng
Sous-ensembles de citation
IM
Pagination
6961Informations de copyright
© 2021. The Author(s).
Références
Preskill, J. Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018).
doi: 10.22331/q-2018-08-06-79
Cerezo, M. et al. Variational quantum algorithms. Nat. Rev. Phys.3, 625–644 (2021).
doi: 10.1038/s42254-021-00348-9
Endo, S., Cai, Z., Benjamin, S. C., & Yuan, X. Hybrid quantum-classical algorithms and quantum error mitigation. Journal of the Physical Society of Japan 90, 032001 (2021).
doi: 10.7566/JPSJ.90.032001
Bharti, K. et al. Noisy intermediate-scale quantum (nisq) algorithms. Preprint at https://arxiv.org/abs/arXiv:2101.08448 (2021).
Peruzzo, A. et al. A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014).
pubmed: 25055053
doi: 10.1038/ncomms5213
McClean, J. R., Romero, J., Babbush, R. & Aspuru-Guzik, A. The theory of variational hybrid quantum-classical algorithms. N. J. Phys. 18, 023023 (2016).
doi: 10.1088/1367-2630/18/2/023023
Bauer, B., Wecker, D., Millis, A. J., Hastings, M. B. & Troyer, M. Hybrid quantum-classical approach to correlated materials. Phys. Rev. X 6, 031045 (2016).
Jones, T., Endo, S., McArdle, S., Yuan, X. & Benjamin, S. C. Variational quantum algorithms for discovering hamiltonian spectra. Phys. Rev. A 99, 062304 (2019).
doi: 10.1103/PhysRevA.99.062304
Li, Y. & Benjamin, S. C. Efficient variational quantum simulator incorporating active error minimization. Phys. Rev. X 7, 021050 (2017).
Cirstoiu, C. et al. Variational fast forwarding for quantum simulation beyond the coherence time. npj Quantum Inf. 6, 1–10 (2020).
doi: 10.1038/s41534-020-00302-0
Heya, K., Nakanishi, K. M., Mitarai, K. & Fujii, K. Subspace variational quantum simulator. Phys. Rev. Research 1, 033062 (2019).
doi: 10.1103/PhysRevResearch.1.033062
Yuan, X., Endo, S., Zhao, Q., Li, Y. & Benjamin, S. C. Theory of variational quantum simulation. Quantum 3, 191 (2019).
doi: 10.22331/q-2019-10-07-191
Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. Preprint at http://arxiv.org/abs/1411.4028 (2021).
Wang, Z., Hadfield, S., Jiang, Z. & Rieffel, E. G. Quantum approximate optimization algorithm for MaxCut: a fermionic view. Phys. Rev. A 97, 022304 (2018a).
doi: 10.1103/PhysRevA.97.022304
Crooks, G. E. Performance of the quantum approximate optimization algorithm on the maximum cut problem. Preprint at http://arxiv.org/abs/1811.08419 (2021).
Hadfield, S. et al. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms 12, 34 (2019).
doi: 10.3390/a12020034
Bravo-Prieto, C. et al. Variational quantum linear solver: a hybrid algorithm for linear systems. Preprint at https://arxiv.org/abs/1909.05820 (2019).
Xu, X. et al. Variational algorithms for linear algebra. Preprint at http://arxiv.org/abs/1909.03898 (2021).
Koczor, B., Endo, S., Jones, T., Matsuzaki, Y. & Benjamin, S. C. Variational-state quantum metrology. N. J. Phys. https://iopscience.iop.org/article/10.1088/1367-2630/ab965e (2020).
Meyer, J. J., Borregaard, J. & Eisert, J. A variational toolbox for quantum multi-parameter estimation. https://arxiv.org/abs/2006.06303 (2020).
Anschuetz, E., Olson, J., Aspuru-Guzik, A. & Cao, Y. Variational quantum factoring. In Quantum Technology and Optimization Problems. pp. 74–85 (Springer International Publishing, Cham, 2019) https://link.springer.com/chapter/10.1007/978-3-030-14082-3_7 .
Khatri, S. et al. Quantum-assisted quantum compiling. Quantum 3, 140 (2019).
doi: 10.22331/q-2019-05-13-140
Sharma, K., Khatri, S., Cerezo, M. & Coles, P. Noise resilience of variational quantum compiling. N. J. Phys. https://iopscience.iop.org/article/10.1088/1367-2630/ab784c (2020).
Jones, T. & Benjamin, S. C. Quantum compilation and circuit optimisation via energy dissipation. http://arxiv.org/abs/1811.03147 .
Arrasmith, A., Cincio, L., Sornborger, A. T., Zurek, W. H. & Coles, P. J. Variational consistent histories as a hybrid algorithm for quantum foundations. Nat. Commun. 10, 3438 (2019).
pubmed: 31366888
pmcid: 6668436
doi: 10.1038/s41467-019-11417-0
Cerezo, M., Poremba, A., Cincio, L. & Coles, P. J. Variational quantum fidelity estimation. Quantum 4, 248 (2020).
doi: 10.22331/q-2020-03-26-248
Cerezo, M., Sharma, K., Arrasmith, A. & Coles, P. J. Variational quantum state eigensolver. Preprint at https://arxiv.org/abs/2004.01372 (2020).
LaRose, R., Tikku, A., O’Neel-Judy, É., Cincio, L. & Coles, P. J. Variational quantum state diagonalization. npj Quantum Inf. 5, 1–10 (2019).
doi: 10.1038/s41534-019-0167-6
Verdon, G., Marks, J., Nanda, S., Leichenauer, S. & Hidary, J. Quantum Hamiltonian-based models and the variational quantum thermalizer algorithm. Preprint at https://arxiv.org/abs/1910.02071 (2019).
Johnson, P. D., Romero, J., Olson, J., Cao, Y. & Aspuru-Guzik, A. QVECTOR: an algorithm for device-tailored quantum error correction. Preprint at https://arxiv.org/abs/1711.02249 (2017).
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).
pubmed: 30446662
pmcid: 6240101
doi: 10.1038/s41467-018-07090-4
Holmes, Z., Sharma, K., Cerezo, M. & Coles, P. J. Connecting ansatz expressiblity to gradient magnitudes and barren plateaus. Preprint at https://arxiv.org/abs/arXiv:2101.02138 (2021).
Sharma, K., Cerezo, M., Cincio, L. & Coles, P. J. Trainability of dissipative perceptron-based quantum neural networks. Preprint at https://arxiv.org/abs/arXiv:2005.12458 (2020).
Cerezo, M., Sone, A., Volkoff, T., Cincio, L. & Coles, P. J. Cost-function-dependent barren plateaus in shallow quantum neural networks. Nature Communications 12, 1791 (2021).
pubmed: 33741913
pmcid: 7979934
doi: 10.1038/s41467-021-21728-w
Marrero, C. O., Kieferová, M. & Wiebe, N. Entanglement induced barren plateaus. PRX Quantum 2, 040316 (2021).
doi: 10.1103/PRXQuantum.2.040316
Patti, T. L., Najafi, K., Gao, X. & Yelin, S. F. Entanglement devised barren plateau mitigation. Phys. Rev. Research 3, 033090 (2021).
doi: 10.1103/PhysRevResearch.3.033090
Volkoff, T. & Coles, P. J. Large gradients via correlation in random parameterized quantum circuits. Quantum Sci. Technol. http://iopscience.iop.org/article/10.1088/2058-9565/abd891 (2021).
Cerezo, M. & Coles, P. J. Higher order derivatives of quantum neural networks with barren plateaus. Quantum Sci. Technol. 6, 035006 (2021).
doi: 10.1088/2058-9565/abf51a
Arrasmith, A., Cerezo, M., Czarnik, P., Cincio, L. & Coles, P. J. Effect of barren plateaus on gradient-free optimization. Quantum 5, 558 (2021).
doi: 10.22331/q-2021-10-05-558
Uvarov, A. & Biamonte, J. On barren plateaus and cost function locality in variational quantum algorithms. Preprint at https://arxiv.org/abs/arXiv:2011.10530 (2020).
Verdon, G. et al. Learning to learn with quantum neural networks via classical neural networks. Preprint at https://arxiv.org/abs/arXiv:1907.05415 (2019).
Grant, E., Wossnig, L., Ostaszewski, M. & Benedetti, M. An initialization strategy for addressing barren plateaus in parametrized quantum circuits. Quantum 3, 214 (2019).
doi: 10.22331/q-2019-12-09-214
Skolik, A., McClean, J. R., Mohseni, M., Smagt, P. & Leib, M. Layerwise learning for quantum neural networks. Quantum Mach. Intell. 3, 5 (2021).
doi: 10.1007/s42484-020-00036-4
Xue, C., Chen, Z.-Y., Wu, Y.-C. & Guo, G.-P. Effects of quantum noise on quantum approximate optimization algorithm. Chinese Phys. Lett. 38, 030302 (2021).
Marshall, J., Wudarski, F., Hadfield, S. & Hogg, T. Characterizing local noise in QAOA circuits. IOP SciNotes 1, 025208 (2020).
doi: 10.1088/2633-1357/abb0d7
Gentini, L., Cuccoli, A., Pirandola, S., Verrucchi, P. & Banchi, L. Noise-resilient variational hybrid quantum-classical optimization. Phys. Rev. A 102, 052414 (2020).
doi: 10.1103/PhysRevA.102.052414
Farhi, E. & Harrow, A. W. Quantum supremacy through the quantum approximate optimization algorithm. Preprint at https://arxiv.org/abs/arXiv:1602.07674 (2016).
Kübler, J. M., Arrasmith, A., Cincio, L. & Coles, P. J. An adaptive optimizer for measurement-frugal variational algorithms. Quantum 4, 263 (2020).
doi: 10.22331/q-2020-05-11-263
Arrasmith, A., Cincio, L., Somma, R. D. & Coles, P. J. Operator sampling for shot-frugal optimization in variational algorithms. Preprint at https://arxiv.org/abs/arXiv:2004.06252 (2020).
Cao, Y. et al. Quantum chemistry in the age of quantum computing. Chem. Rev. 119, 10856–10915 (2019).
pubmed: 31469277
doi: 10.1021/acs.chemrev.8b00803
Bartlett, R. J. & Musiał, M. Coupled-cluster theory in quantum chemistry. Rev. Mod. Phys. 79, 291 (2007).
doi: 10.1103/RevModPhys.79.291
Lee, J., Huggins, W. J., Head-Gordon, M. & Whaley, K. B. Generalized unitary coupled cluster wave functions for quantum computation. J. Chem. Theory Comput. 15, 311–324 (2018).
pubmed: 30485748
doi: 10.1021/acs.jctc.8b01004
Kandala, A. et al. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature 549, 242 (2017).
pubmed: 28905916
doi: 10.1038/nature23879
Arute, F. et al. Hartree-fock on a superconducting qubit quantum computer. Science 369, 1084–1089 (2020a).
doi: 10.1126/science.abb9811
Harrigan, M. P. et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nat. Phys. 17, 332–336 (2021).
doi: 10.1038/s41567-020-01105-y
Wecker, D., Hastings, M. B. & Troyer, M. Progress towards practical quantum variational algorithms. Phys. Rev. A 92, 042303 (2015).
doi: 10.1103/PhysRevA.92.042303
Wiersema, R. et al. Exploring entanglement and optimization within the hamiltonian variational ansatz. PRX Quantum 1, 020319 (2020).
doi: 10.1103/PRXQuantum.1.020319
Schuld, M., Sinayskiy, I. & Petruccione, F. The quest for a quantum neural network. Quantum Inf. Process. 13, 2567–2586 (2014).
doi: 10.1007/s11128-014-0809-8
Schuld, M., Sinayskiy, I. & Petruccione, F. An introduction to quantum machine learning. Contemp. Phys. 56, 172–185 (2015).
doi: 10.1080/00107514.2014.964942
Biamonte, J. et al. Quantum machine learning. Nature 549, 195–202 (2017).
pubmed: 28905917
doi: 10.1038/nature23474
Beer, K. et al. Training deep quantum neural networks. Nat. Commun. 11, 1–6 (2020).
doi: 10.1038/s41467-020-14454-2
Abbas, A. et al. The power of quantum neural networks. Nat. Comput. Sci.1, 403–409 (2020).
doi: 10.1038/s43588-021-00084-1
Gorman, B. O., Huggins, W. J., Rieffel, E. G. & Whaley, K. B. Generalized swap networks for near-term quantum computing. Preprint at https://arxiv.org/abs/arXiv:1905.05118 (2019).
Bravyi, S., Kliesch, A., Koenig, R. & Tang, E. Obstacles to Variational Quantum Optimization from Symmetry Protection. Phys. Rev. Lett. 125, 260505 (2020).
Wang, Z., Hadfield, S., Jiang, Z. & Rieffel, E. G. Quantum approximate optimization algorithm for maxcut: a fermionic view. Phys. Rev. A 97, 022304 (2018b).
doi: 10.1103/PhysRevA.97.022304
Hastings, M. B. Classical and quantum bounded depth approximation algorithms. Preprint at https://arxiv.org/abs/arXiv:1905.07047 (2019).
Jiang, Z., Rieffel, E. G. & Wang, Z. Near-optimal quantum circuit for grover’s unstructured search using a transverse field. Phys. Rev. A 95, 062317 (2017).
doi: 10.1103/PhysRevA.95.062317
Akshay, V., Philathong, H., Morales, M. E. S. & Biamonte, J. D. Reachability deficits in quantum approximate optimization. Phys. Rev. Lett. 124, 090504 (2020).
pubmed: 32202873
doi: 10.1103/PhysRevLett.124.090504
McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S. C. & Yuan, X. Quantum computational chemistry. Rev. Mod. Phys. 92, 015003 (2020).
doi: 10.1103/RevModPhys.92.015003
Romero, J. et al. Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. Quantum Sci. Technol. 4, 014008 (2018).
doi: 10.1088/2058-9565/aad3e4
Ortiz, G., Gubernatis, J. E., Knill, E. & Laflamme, R. Quantum algorithms for fermionic simulations. Phys. Rev. A 64, 022319 (2001).
doi: 10.1103/PhysRevA.64.022319
Bravyi, S. B. & Kitaev, A. Y. Fermionic quantum computation. Ann. Phys. 298, 210–226 (2002).
doi: 10.1006/aphy.2002.6254
Nooijen, M. Can the eigenstates of a many-body hamiltonian be represented exactly using a general two-body cluster expansion? Phys. Rev. Lett. 84, 2108 (2000).
pubmed: 11017220
doi: 10.1103/PhysRevLett.84.2108
Ho, W. W. & Hsieh, T. H. Efficient variational simulation of non-trivial quantum states. SciPost Phys. 6, 029 (2019).
doi: 10.21468/SciPostPhys.6.3.029
Cade, C., Mineh, L., Montanaro, A. & Stanisic, S. Strategies for solving the fermi-hubbard model on near-term quantum computers. Phys. Rev. B 102, 235122 (2020).
doi: 10.1103/PhysRevB.102.235122
Erdos, P. & Renyi, A. On random graphs i. Publ. math. Debr. 6, 18 (1959).
Goemans, M. X. & Williamson, D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995).
doi: 10.1145/227683.227684
Arora, S., Lund, C., Motwani, R., Sudan, M. & Szegedy, M. Proof verification and the hardness of approximation problems. J. ACM 45, 501–555 (1998).
doi: 10.1145/278298.278306
Håstad, J. Some optimal inapproximability results. J. ACM 48, 798–859 (2001).
doi: 10.1145/502090.502098
Jurcevic, P. et al. Demonstration of quantum volume 64 on a superconducting quantum computing system. Quantum Sci. Technol. 6, 025020 (2021).
doi: 10.1088/2058-9565/abe519
Nelder, J. A. & Mead, R. A simplex method for function minimization. Computer J. 7, 308–313 (1965).
doi: 10.1093/comjnl/7.4.308
Koczor, B. & Benjamin, S. C. Quantum analytic descent. Preprint at https://arxiv.org/abs/arXiv:2008.13774 (2020).
Czarnik, P., Arrasmith, A., Coles, P. J. & Cincio, L. Error mitigation with clifford quantum-circuit data. Preprint at https://arxiv.org/abs/arXiv:2005.10189 (2020).
Montanaro, A. & Stanisic, S. Error mitigation by training with fermionic linear optics. Preprint at https://arxiv.org/abs/arXiv:2102.02120 (2021).
Vovrosh, J. et al. Efficient mitigation of depolarizing errors in quantum simulations. Preprint at https://arxiv.org/abs/arXiv:2101.01690 (2021).
Rosenberg, E., Ginsparg, P. & McMahon, P. L. Experimental error mitigation using linear rescaling for variational quantum eigensolving with up to 20 qubits. Preprint at https://arxiv.org/abs/arXiv:2106.01264 (2021).
He, A., Nachman, B., de Jong, W. A. & Bauer, C. W. Zero-noise extrapolation for quantum-gate error mitigation with identity insertions. Phys. Rev. A 102, 012426 (2020).
doi: 10.1103/PhysRevA.102.012426
Shaw, A. Classical-quantum noise mitigation for NISQ hardware. Preprint at https://arxiv.org/abs/arXiv:2105.08701 (2021).
Arute, F. et al. Observation of separated dynamics of charge and spin in the Fermi-Hubbard model. Preprint at https://arxiv.org/abs/arXiv:2010.07965 (2020).
Bilkis, M., Cerezo, M., Verdon, G., Coles, P. J. & Cincio, L. A semi-agnostic ansatz with variable structure for quantum machine learning. Preprint at https://arxiv.org/abs/arXiv:2103.06712 (2021).
Grimsley, H. R., Economou, S. E., Barnes, E. & Mayhall, N. J. An adaptive variational algorithm for exact molecular simulations on a quantum computer. Nat. Commun. 10, 1–9 (2019).
doi: 10.1038/s41467-019-10988-2
Tang, H. L. et al. qubit-adapt-vqe: An adaptive algorithm for constructing hardware-efficient ansätze on a quantum processor. PRX Quantum 2, 020310 (2021).
doi: 10.1103/PRXQuantum.2.020310
Zhang, Z.-J., Kyaw, T. H., Kottmann, J., Degroote, M. & Aspuru-Guzik, A. Mutual information-assisted adaptive variational quantum eigensolver. Quantum Sci. Technol. 6, 035001 (2021).
doi: 10.1088/2058-9565/abdca4
Rattew, A. G., Hu, S., Pistoia, M., Chen, R. & Wood, S. A domain-agnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver. Preprint at https://arxiv.org/abs/arXiv:1910.09694 (2019).
Chivilikhin, D. et al. MoG-VQE: Multiobjective genetic variational quantum eigensolver. Preprint at https://arxiv.org/abs/arXiv:2007.04424 (2020).
Cincio, L., Rudinger, K., Sarovar, M. & Coles, P. J. Machine learning of noise-resilient quantum circuits. PRX Quantum 2, 010324 (2021).
doi: 10.1103/PRXQuantum.2.010324
Cincio, L., Subaşí, Y., Sornborger, A. T. & Coles, P. J. Learning the quantum algorithm for state overlap. N. J. Phys. 20, 113022 (2018).
doi: 10.1088/1367-2630/aae94a
Du, Y., Huang, T., You, S., Hsieh, M.-H. & Tao, D. Quantum circuit architecture search: error mitigation and trainability enhancement for variational quantum solvers. Preprint at https://arxiv.org/abs/arXiv:2010.10217 (2020).
Hirche, C., Rouzé, C. & França, D. S. On contraction coefficients, partial orders and approximation of capacities for quantum channels. Preprint at https://arxiv.org/abs/arXiv:2011.05949 (2020).
Baumgartner, B. An inequality for the trace of matrix products, using absolute values. Preprint at https://arxiv.org/abs/arXiv:1106.6189 (2011).
Wenzel, D. & Audenaert, K. M. R. Impressions of convexity: an illustration for commutator bounds. Linear algebra its Appl. 433, 1726–1759 (2010).
doi: 10.1016/j.laa.2010.06.039
Ohya, M. & Petz, D. Quantum entropy and its use (Springer Science & Business Media, 2004) https://www.springer.com/gp/book/9783540208068 .
Blume-Kohout, R. et al. Demonstration of qubit operations below a rigorous fault tolerance threshold with gate set tomography. Nat. Commun. 8, 1–13 (2017).
doi: 10.1038/ncomms14485
Nielsen, E. et al. Probing quantum processor performance with pyGSTi. Quantum Sci. Technol. 5, 044002 (2020).
doi: 10.1088/2058-9565/ab8aa4
Müller-Hermes, A., França, D. S. & Wolf, M. M. Relative entropy convergence for depolarizing channels. J. Math. Phys. 57, 022202 (2016).
doi: 10.1063/1.4939560