{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:42:03Z","timestamp":1757313723914,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,2,17]],"date-time":"2021-02-17T00:00:00Z","timestamp":1613520000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,17]],"date-time":"2021-02-17T00:00:00Z","timestamp":1613520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000844","name":"European Space Agency","doi-asserted-by":"publisher","award":["ESA RFQ\/3-16506\/20\/NL\/MH\/hm"],"award-info":[{"award-number":["ESA RFQ\/3-16506\/20\/NL\/MH\/hm"]}],"id":[{"id":"10.13039\/501100000844","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Gaussian processes are well-established Bayesian machine learning algorithms with significant merits, despite a strong limitation: lack of scalability. Clever solutions address this issue by inducing sparsity through low-rank approximations, often based on the Nystrom method. Here, we propose a different method to achieve better scalability and higher accuracy using quantum computing, outperforming classical Bayesian neural networks for large datasets significantly. Unlike other approaches to quantum machine learning, the computationally expensive linear algebra operations are not just replaced with their quantum counterparts. Instead, we start from a recent study that proposed a quantum circuit for implementing quantum Gaussian processes and then we use quantum phase estimation to induce a low-rank approximation analogous to that in classical sparse Gaussian processes. We provide evidence through numerical tests, mathematical error bound estimation, and complexity analysis that the method can address the \u201ccurse of dimensionality,\u201d where each additional input parameter no longer leads to an exponential growth of the computational cost. This is also demonstrated by applying the algorithm in a practical setting and using it in the data-driven design of a recently proposed metamaterial. The algorithm, however, requires significant quantum computing hardware improvements before quantum advantage can be achieved.<\/jats:p>","DOI":"10.1007\/s42484-020-00032-8","type":"journal-article","created":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T05:01:34Z","timestamp":1613710894000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Sparse quantum Gaussian processes to counter the curse of dimensionality"],"prefix":"10.1007","volume":"3","author":[{"given":"Gawe\u0142 I.","family":"Ku\u015b","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sybrand","family":"van der Zwaag","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6216-0355","authenticated-orcid":false,"given":"Miguel A.","family":"Bessa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,17]]},"reference":[{"key":"32_CR1","unstructured":"Acerbi L, Ji W (2017) Practical Bayesian optimization for model fitting with Bayesian adaptive direct search. In: Advances in neural information processing systems, pp 1836\u20131846"},{"issue":"4","key":"32_CR2","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/j.isatra.2007.04.001","volume":"46","author":"K A\u017eman","year":"2007","unstructured":"A\u017eman K, Kocijan J (2007) Application of Gaussian processes for black-box modelling of biosystems. ISA Transactions 46(4):443\u2013457","journal-title":"ISA Transactions"},{"issue":"1","key":"32_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0304-3975(01)00057-3","volume":"284","author":"PL Bartlett","year":"2002","unstructured":"Bartlett PL, Ben-David S (2002) Hardness results for neural network approximation problems. Theor Comput Sci 284(1):53\u201366","journal-title":"Theor Comput Sci"},{"issue":"6","key":"32_CR4","doi-asserted-by":"publisher","first-page":"063505","DOI":"10.1103\/PhysRevD.101.063505","volume":"101","author":"E Belgacem","year":"2020","unstructured":"Belgacem E, Foffa S, Maggiore M, Yang T (2020) Gaussian processes reconstruction of modified gravitational wave propagation. Physical Review D 101(6):063505","journal-title":"Physical Review D"},{"issue":"2","key":"32_CR5","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s00220-006-0150-x","volume":"270","author":"DW Berry","year":"2007","unstructured":"Berry DW, Ahokas G, Cleve R, Sanders BC (2007) Efficient quantum algorithms for simulating sparse Hamiltonians. Commun Math Phys 270(2):359\u2013371","journal-title":"Commun Math Phys"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.ijsolstr.2018.01.035","volume":"139","author":"M Bessa","year":"2018","unstructured":"Bessa M, Pellegrino S (2018) Design of ultra-thin shell structures in the stochastic post-buckling range using Bayesian machine learning and optimization. Int J Solids Struct 139:174\u2013188","journal-title":"Int J Solids Struct"},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/j.cma.2017.03.037","volume":"320","author":"M Bessa","year":"2017","unstructured":"Bessa M, Bostanabad R, Liu Z, Hu A, Apley DW, Brinson C, Chen W, Liu WK (2017) A framework for data-driven analysis of materials under uncertainty: countering the curse of dimensionality. Comput Methods Appl Mech Eng 320:633\u2013667","journal-title":"Comput Methods Appl Mech Eng"},{"issue":"48","key":"32_CR8","doi-asserted-by":"publisher","first-page":"1904845","DOI":"10.1002\/adma.201904845","volume":"31","author":"MA Bessa","year":"2019","unstructured":"Bessa MA, Glowacki P, Houlder M (2019) Bayesian machine learning in metamaterial design: fragile becomes supercompressible. Advanced Materials 31(48):1904845","journal-title":"Advanced Materials"},{"issue":"7671","key":"32_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1038\/nature23474","volume":"549","author":"J Biamonte","year":"2017","unstructured":"Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N, Lloyd S (2017) Quantum machine learning. Nature 549(7671):195","journal-title":"Nature"},{"issue":"1","key":"32_CR10","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0893-6080(05)80010-3","volume":"5","author":"AL Blum","year":"1992","unstructured":"Blum AL, Rivest RL (1992) Training a 3-node neural network is np-complete. Neural Netw 5 (1):117\u2013127","journal-title":"Neural Netw"},{"issue":"233","key":"32_CR11","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1090\/S0025-5718-00-01251-5","volume":"70","author":"M Buhmann","year":"2001","unstructured":"Buhmann M (2001) A new class of radial basis functions with compact support. Math Comput 70(233):307\u2013318","journal-title":"Math Comput"},{"issue":"Feb","key":"32_CR12","first-page":"333","volume":"14","author":"K Chalupka","year":"2013","unstructured":"Chalupka K, Williams CK, Murray I (2013) A framework for evaluating approximation methods for Gaussian process regression. J Mach Learn Res 14(Feb):333\u2013350","journal-title":"J Mach Learn Res"},{"issue":"2","key":"32_CR13","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/s00220-009-0930-1","volume":"294","author":"AM Childs","year":"2010","unstructured":"Childs AM (2010) On the relationship between continuous-and discrete-time quantum walk. Commun Math Phys 294(2):581\u2013 603","journal-title":"Commun Math Phys"},{"issue":"1","key":"32_CR14","doi-asserted-by":"publisher","first-page":"49","DOI":"10.3847\/1538-4357\/aa6aab","volume":"840","author":"I Czekala","year":"2017","unstructured":"Czekala I, Mandel KS, Andrews SM, Dittmann JA, Ghosh SK, Montet BT, Newton ER (2017) Disentangling time-series spectra with Gaussian processes: applications to radial velocity analysis. The Astrophysical Journal 840(1):49","journal-title":"The Astrophysical Journal"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"Daniely A, Linial N, Shalev-Shwartz S (2014) From average case complexity to improper learning complexity. In: Proceedings of the forty-sixth annual ACM symposium on theory of computing, pp 441\u2013448","DOI":"10.1145\/2591796.2591820"},{"issue":"2","key":"32_CR16","doi-asserted-by":"publisher","first-page":"022315","DOI":"10.1103\/PhysRevA.97.022315","volume":"97","author":"S Das","year":"2018","unstructured":"Das S, Siopsis G, Weedbrook C (2018) Continuous-variable quantum Gaussian process regression and quantum singular value decomposition of nonsparse low-rank matrices. Physical Review A 97(2):022315","journal-title":"Physical Review A"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"Frazier PI, Wang J (2016) Bayesian optimization for materials design. In: Information science for materials discovery and design. Springer, pp 45\u201375","DOI":"10.1007\/978-3-319-23871-5_3"},{"issue":"1","key":"32_CR18","doi-asserted-by":"publisher","first-page":"012115","DOI":"10.1103\/PhysRevE.100.012115","volume":"100","author":"M Geiger","year":"2019","unstructured":"Geiger M, Spigler S, d\u2019Ascoli S, Sagun L, Baity-Jesi M, Biroli G, Wyart M (2019) Jamming transition as a paradigm to understand the loss landscape of deep neural networks. Physical Review E 100(1):012115","journal-title":"Physical Review E"},{"issue":"2","key":"32_CR19","doi-asserted-by":"publisher","first-page":"023401","DOI":"10.1088\/1742-5468\/ab633c","volume":"2020","author":"M Geiger","year":"2020","unstructured":"Geiger M, Jacot A, Spigler S, Gabriel F, Sagun L, d\u2019Ascoli S, Biroli G, Hongler C, Wyart M (2020) Scaling description of generalization with number of parameters in deep learning. Journal of Statistical Mechanics: Theory and Experiment 2020(2):023401","journal-title":"Journal of Statistical Mechanics: Theory and Experiment"},{"issue":"16","key":"32_CR20","doi-asserted-by":"publisher","first-page":"160501","DOI":"10.1103\/PhysRevLett.100.160501","volume":"100","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti V, Lloyd S, Maccone L (2008) Quantum random access memory. Phys Rev Lett 100(16):160501","journal-title":"Phys Rev Lett"},{"key":"32_CR21","doi-asserted-by":"publisher","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for linear systems of equations. Phys Rev Lett 103:150502","journal-title":"Phys Rev Lett"},{"key":"32_CR22","doi-asserted-by":"crossref","unstructured":"Hatano N, Suzuki M (2005) Finding exponential product formulas of higher orders. In: Quantum annealing and other optimization methods. Springer, pp 37\u201368","DOI":"10.1007\/11526216_2"},{"key":"32_CR23","unstructured":"Hensman J, Fusi N, Lawrence ND (2013) Gaussian processes for big data. arXiv:1309.6835"},{"key":"32_CR24","first-page":"351","volume":"38","author":"J Hensman","year":"2015","unstructured":"Hensman J, Matthews A, Ghahramani Z (2015) Scalable variational Gaussian process classification. J Mach Learn Res 38:351\u2013 360","journal-title":"J Mach Learn Res"},{"key":"32_CR25","unstructured":"Kumar S, Mohri M, Talwalkar A (2009) Sampling techniques for the nystrom method. In: Artificial intelligence and statistics, pp 304\u2013311"},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"Lee J, Xiao L, Schoenholz S, Bahri Y, Novak R, Sohl-Dickstein J, Pennington J (2019) Wide neural networks of any depth evolve as linear models under gradient descent. In: Advances in neural information processing systems, pp 8570\u20138581","DOI":"10.1088\/1742-5468\/abc62b"},{"issue":"1","key":"32_CR27","doi-asserted-by":"publisher","first-page":"012001","DOI":"10.1103\/PhysRevD.101.012001","volume":"101","author":"L Li","year":"2020","unstructured":"Li L, Nayak N, Bian J, Baldi P (2020) Efficient neutrino oscillation parameter inference using Gaussian processes. Physical Review D 101(1):012001","journal-title":"Physical Review D"},{"key":"32_CR28","unstructured":"Liu H, Ong YS, Shen X, Cai J (2018) When Gaussian process meets big data: a review of scalable GPs. arXiv:1807.01065"},{"key":"32_CR29","unstructured":"Livni R, Shalev-Shwartz S, Shamir O (2014) On the computational efficiency of training neural networks. In: Advances in neural information processing systems, pp 855\u2013863"},{"issue":"9","key":"32_CR30","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1038\/nphys3029","volume":"10","author":"S Lloyd","year":"2014","unstructured":"Lloyd S, Mohseni M, Rebentrost P (2014) Quantum principal component analysis. Nat Phys 10(9):631\u2013633","journal-title":"Nat Phys"},{"issue":"3","key":"32_CR31","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.cossms.2016.10.002","volume":"21","author":"T Lookman","year":"2017","unstructured":"Lookman T, Balachandran PV, Xue D, Hogden J, Theiler J (2017) Statistical inference and adaptive design for materials discovery. Curr Opinion Solid State Mater Sci 21(3):121\u2013128","journal-title":"Curr Opinion Solid State Mater Sci"},{"key":"32_CR32","unstructured":"Melkumyan A, Ramos FT (2009) A sparse covariance function for exact Gaussian process inference in large datasets. In: Twenty-first international joint conference on artificial intelligence"},{"key":"32_CR33","unstructured":"Murphy KP (2012) Machine learning: a probabilistic perspective. MIT Press"},{"key":"32_CR34","unstructured":"Nielsen MA, Chuang IL (2000) Quantum computation and quantum information"},{"key":"32_CR35","unstructured":"Pearce T, Zaki M, Brintrup A, Anastassacos N, Neely A (2018) Uncertainty in neural networks: Bayesian ensembling. arXiv:1810.05546"},{"key":"32_CR36","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V, Vanderplas J, Passos A, Cournapeau D, Brucher M, Perrot M, Duchesnay E (2011) Scikit-learn: machine learning in python. J Mach Learn Res 12:2825\u20132830","journal-title":"J Mach Learn Res"},{"issue":"Dec","key":"32_CR37","first-page":"1939","volume":"6","author":"J Qui\u00f1onero-Candela","year":"2005","unstructured":"Qui\u00f1onero-Candela J, Rasmussen CE (2005) A unifying view of sparse approximate Gaussian process regression. J Mach Learn Res 6(Dec):1939\u20131959","journal-title":"J Mach Learn Res"},{"issue":"02","key":"32_CR38","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1142\/S0129065704001899","volume":"14","author":"M Seeger","year":"2004","unstructured":"Seeger M (2004) Gaussian processes for machine learning. Int J Neural Syst 14(02):69\u2013106","journal-title":"Int J Neural Syst"},{"issue":"1","key":"32_CR39","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/JPROC.2015.2494218","volume":"104","author":"B Shahriari","year":"2015","unstructured":"Shahriari B, Swersky K, Wang Z, Adams RP, De Freitas N (2015) Taking the human out of the loop: a review of Bayesian optimization. Proc IEEE 104(1):148\u2013175","journal-title":"Proc IEEE"},{"key":"32_CR40","unstructured":"Snelson E, Ghahramani Z (2006) Sparse Gaussian processes using pseudo-inputs. In: Advances in neural information processing systems, pp 1257\u20131264"},{"issue":"10","key":"32_CR41","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.2355\/isijinternational.39.1020","volume":"39","author":"F Tancret","year":"1999","unstructured":"Tancret F, HKDH B, DJC M (1999) Comparison of artificial neural networks with gaussian processes to model the yield strength of nickel-base superalloys. ISIJ International 39(10):1020\u20131026","journal-title":"ISIJ International"},{"key":"32_CR42","unstructured":"Titsias M (2009) Variational learning of inducing variables in sparse Gaussian processes. In: Artificial intelligence and statistics, pp 567\u2013574"},{"issue":"2","key":"32_CR43","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/MCSE.2011.37","volume":"13","author":"S van der Walt","year":"2011","unstructured":"van der Walt S, Colbert SC, Varoquaux G (2011) The numpy array: a structure for efficient numerical computation. Computing in Science & Engineering 13(2):22\u201330","journal-title":"Computing in Science & Engineering"},{"key":"32_CR44","unstructured":"Wang S, Zhang Z (2014) Efficient algorithms and error analysis for the modified Nystrom method. In: Artificial intelligence and statistics, pp 996\u20131004"},{"issue":"4","key":"32_CR45","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/s11075-015-9970-0","volume":"70","author":"AJ Wathen","year":"2015","unstructured":"Wathen AJ, Zhu S (2015) On spectral distribution of kernel matrices related to radial basis functions. Numerical Algorithms 70(4):709\u2013726","journal-title":"Numerical Algorithms"},{"key":"32_CR46","volume-title":"Gaussian processes for machine learning, vol 2","author":"CK Williams","year":"2006","unstructured":"Williams CK, Rasmussen CE (2006) Gaussian processes for machine learning, vol 2. MIT Press, Cambridge"},{"key":"32_CR47","unstructured":"Williams CK, Seeger M (2001) Using the Nystr\u00f6m method to speed up kernel machines. In: Advances in neural information processing systems, pp 682\u2013688"},{"key":"32_CR48","unstructured":"Wilson A, Nickisch H (2015) Kernel interpolation for scalable structured gaussian processes (kiss-gp). In: International conference on machine learning, pp 1775\u20131784"},{"key":"32_CR49","unstructured":"Wilson AG, Izmailov P (2020) Bayesian deep learning and a probabilistic perspective of generalization. arXiv:2002.08791"},{"issue":"5","key":"32_CR50","doi-asserted-by":"publisher","first-page":"050502","DOI":"10.1103\/PhysRevLett.120.050502","volume":"120","author":"L Wossnig","year":"2018","unstructured":"Wossnig L, Zhao Z, Prakash A (2018) Quantum linear system algorithm for dense matrices. Phys Rev Lett 120(5):050502","journal-title":"Phys Rev Lett"},{"key":"32_CR51","unstructured":"Zhao Z, Fitzsimons JK, Rebentrost P, Dunjko V, Fitzsimons JF (2018) Smooth input preparation for quantum and quantum-inspired machine learning. arXiv:1804.00281"},{"issue":"5","key":"32_CR52","doi-asserted-by":"publisher","first-page":"052331","DOI":"10.1103\/PhysRevA.99.052331","volume":"99","author":"Z Zhao","year":"2019","unstructured":"Zhao Z, Fitzsimons JK, Fitzsimons JF (2019a) Quantum-assisted gaussian process regression. Physical Review A 99(5):052331","journal-title":"Physical Review A"},{"issue":"1-2","key":"32_CR53","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s42484-019-00004-7","volume":"1","author":"Z Zhao","year":"2019","unstructured":"Zhao Z, Pozas-Kerstjens A, Rebentrost P, Wittek P (2019b) Bayesian deep learning on a quantum computer. Quantum Machine Intelligence 1(1-2):41\u201351","journal-title":"Quantum Machine Intelligence"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00032-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-020-00032-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00032-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T08:24:32Z","timestamp":1625214272000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-020-00032-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,17]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["32"],"URL":"https:\/\/doi.org\/10.1007\/s42484-020-00032-8","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"type":"print","value":"2524-4906"},{"type":"electronic","value":"2524-4914"}],"subject":[],"published":{"date-parts":[[2021,2,17]]},"assertion":[{"value":"22 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"6"}}