Reformulation of the No-Free-Lunch Theorem for Entangled Datasets
Open accessThe DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Abstract
The no-free-lunch (NFL) theorem is a celebrated result in learning theory that limits one's ability to learn a function with a training dataset. With the recent rise of quantum machine learning, it is natural to ask whether there is a quantum analog of the NFL theorem, which would restrict a quantum computer's ability to learn a unitary process with quantum training data. However, in the quantum setting, the training data can possess entanglement, a strong correlation with no classical analog. In this Letter, we show that entangled datasets lead to an apparent violation of the (classical) NFL theorem. This motivates a reformulation that accounts for the degree of entanglement in the training set. As our main result, we prove a quantum NFL theorem whereby the fundamental limit on the learnability of a unitary is reduced by entanglement. We employ Rigetti's quantum computer to test both the classical and quantum NFL theorems. Our Letter establishes that entanglement is a commodity in quantum machine learning.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Learning representations by back-propagating errors
Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986) · Nature · doi:10.1038/323533a0 · Cited by 31,892
Quantum Computation and Quantum Information: 10th Anniversary Edition
Nielsen, M. A., & Chuang, I. L. (2012) · doi:10.1017/cbo9780511976667 · Cited by 8,436
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552 · cited 2×
“tional quantum algorithms [39–51].”
Understanding Machine Learning: From Theory to Algorithms
Shalev-Shwartz, S., & Ben-David, S. (2014) · doi:10.1017/cbo9781107298019 · Cited by 3,115
Barren plateaus in quantum neural network training landscapes
McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H. (2018) · Nature Communications · doi:10.1038/s41467-018-07090-4 · Cited by 2,329
The theory of variational hybrid quantum-classical algorithms
McClean, J. R., Romero, J., Babbush, R., & Aspuru-Guzik, A. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/2/023023 · Cited by 2,227
Quantum convolutional neural networks
Cong, I., Choi, S., & Lukin, M. D. (2019) · Nature Physics · doi:10.1038/s41567-019-0648-8 · Cited by 1,517 · cited 1×
“[29] Iris Cong, Soonwon Choi, and Mikhail D Lukin, “Quantum convolutional neural networks,” Nature Physics 15, 1273–1278 (2019).”
BackgroundCost function dependent barren plateaus in shallow parametrized quantum circuits
Cerezo, M., Sone, A., Volkoff, T., Cincio, L., & Coles, P. J. (2021) · Nature Communications · doi:10.1038/s41467-021-21728-w · Cited by 1,047
Self-citationSim, S., Johnson, P. D., & Aspuru‐Guzik, A. (2019) · Advanced Quantum Technologies · doi:10.1002/qute.201900070 · Cited by 972 · cited 2×
“[38] 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).”
BackgroundGeneral teleportation channel, singlet fraction, and quasidistillation
Horodecki, M., Horodecki, P., & Horodecki, R. (1999) · Physical Review A · doi:10.1103/physreva.60.1888 · Cited by 965 · cited 3×
“First note that the risk function in (4) can be expressed in terms of the Hilbert-Schmidt inner product of the target unitary U and the hypothesis unitary VSQ [58, 59] as”
BackgroundIdentifying and attacking the saddle point problem in high-dimensional non-convex optimization
Dauphin, Y., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., & Bengio, Y. (2014) · arXiv · doi:10.48550/arxiv.1406.2572 · Cited by 827 · cited 2×
“[9] Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio, “Identifying and attacking the saddle point problem in high-dimensional non-convex optimization,” in Advances in neural information processing systems (2014) pp.”
BackgroundTraining deep quantum neural networks
Beer, K., Bondarenko, D., Farrelly, T., Osborne, T. J., Salzmann, R., Scheiermann, D., & Wolf, R. (2020) · Nature Communications · doi:10.1038/s41467-020-14454-2 · Cited by 726 · cited 1×
“[30] Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias J Osborne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf, “Training deep quantum neural networks,” Nature Communications 11, 1–6 (2020).”
BackgroundA simple formula for the average gate fidelity of a quantum dynamical operation
Nielsen, M. A. (2002) · Physics Letters A · doi:10.1016/s0375-9601(02)01272-0 · Cited by 725
The quest for a Quantum Neural Network
Schuld, M., Sinayskiy, I., & Petruccione, F. (2014) · Quantum Information Processing · doi:10.1007/s11128-014-0809-8 · Cited by 671 · cited 1×
“[22] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione, “The quest for a quantum neural network,” Quantum Information Processing 13, 2567–2586 (2014).”
BackgroundClassification with Quantum Neural Networks on Near Term Processors
Farhi, E., & Neven, H. (2018) · arXiv · doi:10.48550/arxiv.1802.06002 · Cited by 598
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518
Quantum-Enhanced Machine Learning
Dunjko, V., Taylor, J. M., & Briegel, H. J. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.130501 · Cited by 460 · cited 2×
“[21] Vedran Dunjko, Jacob M Taylor, and Hans J Briegel, “Quantum-enhanced machine learning,” Physical review letters 117, 130501 (2016).”
BackgroundTheory of variational quantum simulation
Yuan, X., Endo, S., Zhao, Q., Li, Y., & Benjamin, S. C. (2019) · Quantum · doi:10.22331/q-2019-10-07-191 · Cited by 458 · cited 1×
“[46] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li, and Simon C Benjamin, “Theory of variational quantum simulation,” Quantum 3, 191 (2019).”
BackgroundContinuous-variable quantum neural networks
Killoran, N., Bromley, T. R., Arrazola, J. M., Schuld, M., Quesada, N., & Lloyd, S. (2019) · Physical Review Research · doi:10.1103/physrevresearch.1.033063 · Cited by 418
An initialization strategy for addressing barren plateaus in parametrized quantum circuits
Grant, E., Wossnig, L., Ostaszewski, M., & Benedetti, M. (2019) · Quantum · doi:10.22331/q-2019-12-09-214 · Cited by 406 · cited 1×
“[34] Edward Grant, Leonard Wossnig, Mateusz Ostaszewski, and Marcello Benedetti, “An initialization strategy for addressing barren plateaus in parametrized quantum circuits,” Quantum 3, 214 (2019).”
BackgroundQuantum-assisted quantum compiling
Khatri, S., LaRose, R., Poremba, A., Cincio, L., Sornborger, A. T., & Coles, P. J. (2019) · Quantum · doi:10.22331/q-2019-05-13-140 · Cited by 382 · cited 1×
“, tensor products of Bell states [50]) on HX ⊗HR and generate the corresponding output states |φj〉 by passing the X system through the unitary U .”
BackgroundSelf-citationLayerwise learning for quantum neural networks
Skolik, A., McClean, J. R., Mohseni, M., van der Smagt, P., & Leib, M. (2021) · Quantum Machine Intelligence · doi:10.1007/s42484-020-00036-4 · Cited by 324 · cited 1×
“[37] Andrea Skolik, Jarrod R McClean, Masoud Mohseni, Patrick van der Smagt, and Martin Leib, “Layerwise learning for quantum neural networks,” arXiv preprint arXiv:2006.”
BackgroundVariational quantum algorithms for discovering Hamiltonian spectra
Jones, T., Endo, S., McArdle, S., Yuan, X., & Benjamin, S. C. (2019) · Physical Review A · doi:10.1103/physreva.99.062304 · Cited by 256 · cited 2×
“[43] Tyson Jones, Suguru Endo, Sam McArdle, Xiao Yuan, and Simon C Benjamin, “Variational quantum algorithms for discovering hamiltonian spectra,” Physical Review A 99, 062304 (2019).”
BackgroundVariational fast forwarding for quantum simulation beyond the coherence time
Cîrstoiu, C., Holmes, Z., Iosue, J., Cincio, L., Coles, P. J., & Sornborger, A. (2020) · npj Quantum Information · doi:10.1038/s41534-020-00302-0 · Cited by 232 · cited 1×
“[47] Cristina Cirstoiu, Zoe Holmes, Joseph Iosue, Lukasz Cincio, Patrick J Coles, and Andrew Sornborger, “Variational fast forwarding for quantum simulation beyond the coherence time,” arXiv preprint arXiv:1910.”
BackgroundSelf-citationVariational quantum state diagonalization
LaRose, R., Tikku, A., O’Neel-Judy, É., Cincio, L., & Coles, P. J. (2019) · npj Quantum Information · doi:10.1038/s41534-019-0167-6 · Cited by 199 · cited 1×
“[51] Ryan LaRose, Arkin Tikku, Étude OâĂŹNeel-Judy, Lukasz Cincio, and Patrick J Coles, “Variational quantum state diagonalization,” npj Quantum Information 5, 1–10 (2019).”
BackgroundSelf-citationLarge gradients via correlation in random parameterized quantum circuits
Volkoff, T., & Coles, P. J. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/abd891 · Cited by 143 · cited 1×
“[36] Tyler Volkoff and Patrick J Coles, “Large gradients via correlation in random parameterized quantum circuits,” arXiv preprint arXiv:2005.”
BackgroundSelf-citationA universal training algorithm for quantum deep learning
Verdon, G., Pye, J., & Broughton, M. (2018) · arXiv · doi:10.48550/arxiv.1806.09729 · Cited by 68 · cited 1×
“[25] Guillaume Verdon, Jason Pye, and Michael Broughton, “A universal training algorithm for quantum deep learning,” arXiv preprint arXiv:1806.”
BackgroundVariational consistent histories as a hybrid algorithm for quantum foundations
Arrasmith, A., Cincio, L., Sornborger, A. T., Zurek, W. H., & Coles, P. J. (2019) · Nature Communications · doi:10.1038/s41467-019-11417-0 · Cited by 66
Self-citation
Cited by
Challenges and opportunities in quantum machine learning
Cerezo, M., Verdon, G., Huang, H.-Y., Cincio, L., & Coles, P. J. (2022) · Nature Computational Science · doi:10.1038/s43588-022-00311-3 · Cited by 689
Self-citationConnecting Ansatz Expressibility to Gradient Magnitudes and Barren Plateaus
Holmes, Z., Sharma, K., Cerezo, M., & Coles, P. J. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010313 · Cited by 570
“Thus our re-sults also apply to quantum machine learning approaches that utilize training data [50–53].”
BackgroundSelf-citationGeneralization in quantum machine learning from few training data
Caro, M. C., Huang, H.-Y., Cerezo, M., Sharma, K., Sornborger, A., Cincio, L., & Coles, P. J. (2022) · Nature Communications · doi:10.1038/s41467-022-32550-3 · Cited by 476
Self-citationAbsence of Barren Plateaus in Quantum Convolutional Neural Networks
Pesah, A., Cerezo, M., Wang, S., Volkoff, T., Sornborger, A. T., & Coles, P. J. (2021) · Physical Review X · doi:10.1103/physrevx.11.041011 · Cited by 343
Self-citationAbsence of Barren Plateaus in Quantum Convolutional Neural Networks
Pesah, A., Cerezo, M., Wang, S., Volkoff, T., Sornborger, A. T., & Coles, P. J. (2020) · arXiv · doi:10.48550/arxiv.2011.02966 · Cited by 343
Self-citation
Metadata
- Authors
- Sharma, K., Cerezo, M., Holmes, Z., Cincio, L., Sornborger, A., & Coles, P. J.
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2022-02-18
- Volume
- 128
- Issue
- 7
- Pages
- 070501-070501
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W3040826712
- Cited by
- 62
- References
- 29
- FWCI
- 3.47
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.