{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T10:57:52Z","timestamp":1770893872932,"version":"3.50.1"},"reference-count":64,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T00:00:00Z","timestamp":1730937600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100018703","name":"European Innovation Council","doi-asserted-by":"crossref","award":["101114899"],"award-info":[{"award-number":["101114899"]}],"id":[{"id":"10.13039\/100018703","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Quantum kernel methods are a proposal for achieving quantum computational advantage in machine learning. They are based on a hybrid classical-quantum computation where a function called the quantum kernel is estimated by a quantum device while the rest of computation is performed classically. Quantum advantages may be achieved through this method only if the quantum kernel function cannot be estimated efficiently on a classical computer. In this paper, we provide sufficient conditions for the efficient classical estimation of quantum kernel functions for bosonic systems. These conditions are based on phase-space properties of data-encoding quantum states associated with the quantum kernels: negative volume, non-classical depth, and excess range, which are shown to be three signatures of phase-space negativity. We consider quantum optical examples involving linear-optical networks with and without adaptive non-Gaussian measurements, and investigate the effects of loss on the efficiency of the classical simulation. Our results underpin the role of the negativity in phase-space quasi-probability distributions as an essential resource in quantum machine learning based on kernel methods.<\/jats:p>","DOI":"10.22331\/q-2024-11-07-1519","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T16:43:32Z","timestamp":1730997812000},"page":"1519","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":6,"title":["Phase-space negativity as a computational resource for quantum kernel methods"],"prefix":"10.22331","volume":"8","author":[{"given":"Ulysse","family":"Chabaud","sequence":"first","affiliation":[{"name":"DIENS, \u00c9cole Normale Sup\u00e9rieure, PSL University, CNRS, INRIA, 45 rue d'Ulm, Paris 75005, France"}]},{"given":"Roohollah","family":"Ghobadi","sequence":"additional","affiliation":[{"name":"Institute for Quantum Science and Technology, University of Calgary, Calgary, AB, T2N 1N4, Canada"}]},{"given":"Salman","family":"Beigi","sequence":"additional","affiliation":[{"name":"School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran"}]},{"given":"Saleh","family":"Rahimi-Keshari","sequence":"additional","affiliation":[{"name":"School of Physics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5531, Tehran, Iran"}]}],"member":"9598","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"J. Preskill, ``Quantum Computing in the NISQ era and beyond,'' Quantum 2, 79 (2018).","DOI":"10.22331\/q-2018-08-06-79"},{"key":"1","doi-asserted-by":"publisher","unstructured":"F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., ``Quantum supremacy using a programmable superconducting processor,'' Nature 574, 505\u2013510 (2019).","DOI":"10.1117\/12.2603523"},{"key":"2","doi-asserted-by":"publisher","unstructured":"I. M. Georgescu, S. Ashhab, and F. Nori, ``Quantum simulation,'' Rev. Mod. Phys. 86, 153\u2013185 (2014).","DOI":"10.1103\/RevModPhys.86.153"},{"key":"3","doi-asserted-by":"publisher","unstructured":"A. J. McCaskey, Z. P. Parks, J. Jakowski, S. V. Moore, T. D. Morris, T. S. Humble, and R. C. Pooser, ``Quantum chemistry as a benchmark for near-term quantum computers,'' npj Quantum Information 5, 99 (2019).","DOI":"10.1038\/s41534-019-0209-0"},{"key":"4","doi-asserted-by":"publisher","unstructured":"J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, ``Quantum machine learning,'' Nature 549, 195\u2013202 (2017).","DOI":"10.1038\/nature23474"},{"key":"5","unstructured":"E. Farhi and H. Neven, ``Classification with quantum neural networks on near term processors,'' arXiv:1802.06002."},{"key":"6","doi-asserted-by":"publisher","unstructured":"B. M. Terhal and D. P. DiVincenzo, ``Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games,'' Quantum Inf. Comput. 4, 134\u2013145 (2004).","DOI":"10.26421\/QIC4.2-5"},{"key":"7","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, A. Montanaro, and D. J. Shepherd, ``Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations,'' Phys. Rev. Lett. 117, 080501 (2016).","DOI":"10.1103\/PhysRevLett.117.080501"},{"key":"8","doi-asserted-by":"publisher","unstructured":"S. Aaronson and A. Arkhipov, ``The Computational Complexity of Linear Optics,'' Theory of Computing 9, 143\u2013252 (2013).","DOI":"10.4086\/toc.2013.v009a004"},{"key":"9","doi-asserted-by":"publisher","unstructured":"S. Bravyi, D. Gosset, and R. K\u00f6nig, ``Quantum advantage with shallow circuits,'' Science 362, 308\u2013311 (2018).","DOI":"10.1126\/science.aar3106"},{"key":"10","doi-asserted-by":"publisher","unstructured":"K. E. Cahill and R. J. Glauber, ``Density Operators and Quasiprobability Distributions,'' Phys. Rev. 177, 1882\u20131902 (1969).","DOI":"10.1103\/PhysRev.177.1882"},{"key":"11","doi-asserted-by":"publisher","unstructured":"R. W. Spekkens, ``Negativity and Contextuality are Equivalent Notions of Nonclassicality,'' Phys. Rev. Lett. 101, 020401 (2008).","DOI":"10.1103\/PhysRevLett.101.020401"},{"key":"12","doi-asserted-by":"publisher","unstructured":"A. Mari and J. Eisert, ``Positive Wigner Functions Render Classical Simulation of Quantum Computation Efficient,'' Phys. Rev. Lett. 109, 230503 (2012).","DOI":"10.1103\/PhysRevLett.109.230503"},{"key":"13","doi-asserted-by":"publisher","unstructured":"V. Veitch, N. Wiebe, C. Ferrie, and J. Emerson, ``Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation,'' New Journal of Physics 15, 013037 (2013).","DOI":"10.1088\/1367-2630\/15\/1\/013037"},{"key":"14","doi-asserted-by":"publisher","unstructured":"S. Rahimi-Keshari, T. C. Ralph, and C. M. Caves, ``Sufficient Conditions for Efficient Classical Simulation of Quantum Optics,'' Phys. Rev. X 6, 021039 (2016).","DOI":"10.1103\/PhysRevX.6.021039"},{"key":"15","doi-asserted-by":"publisher","unstructured":"D. Stahlke, ``Quantum interference as a resource for quantum speedup,'' Phys. Rev. A 90, 022302 (2014).","DOI":"10.1103\/PhysRevA.90.022302"},{"key":"16","doi-asserted-by":"publisher","unstructured":"H. Pashayan, J. J. Wallman, and S. D. Bartlett, ``Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities,'' Phys. Rev. Lett. 115, 070501 (2015).","DOI":"10.1103\/PhysRevLett.115.070501"},{"key":"17","doi-asserted-by":"publisher","unstructured":"R. Mengoni and A. Di Pierro, ``Kernel methods in quantum machine learning,'' Quantum Machine Intelligence 1, 65\u201371 (2019).","DOI":"10.1007\/s42484-019-00007-4"},{"key":"18","doi-asserted-by":"publisher","unstructured":"R. Ghobadi, ``Nonclassical kernels in continuous-variable systems,'' Physical Review A 104, 052403 (2021).","DOI":"10.1103\/PhysRevA.104.052403"},{"key":"19","doi-asserted-by":"publisher","unstructured":"M. Bohmann and E. Agudelo, ``Phase-space inequalities beyond negativities,'' Physical Review Letters 124, 133601 (2020).","DOI":"10.1103\/PhysRevLett.124.133601"},{"key":"20","doi-asserted-by":"publisher","unstructured":"A. Kenfack and K. \u017byczkowski, ``Negativity of the Wigner function as an indicator of non-classicality,'' Journal of Optics B: Quantum and Semiclassical Optics 6, 396 (2004).","DOI":"10.1088\/1464-4266\/6\/10\/003"},{"key":"21","doi-asserted-by":"publisher","unstructured":"F. Albarelli, M. G. Genoni, M. G. A. Paris, and A. Ferraro, ``Resource theory of quantum non-Gaussianity and Wigner negativity,'' Phys. Rev. A 98, 052350 (2018).","DOI":"10.1103\/PhysRevA.98.052350"},{"key":"22","doi-asserted-by":"publisher","unstructured":"C. T. Lee, ``Measure of the nonclassicality of nonclassical states,'' Physical Review A 44, R2775 (1991).","DOI":"10.1103\/PhysRevA.44.R2775"},{"key":"23","doi-asserted-by":"publisher","unstructured":"K. K. Sabapathy, ``Process output nonclassicality and nonclassicality depth of quantum-optical channels,'' Phys. Rev. A 93, 042103 (2016).","DOI":"10.1103\/PhysRevA.93.042103"},{"key":"24","doi-asserted-by":"publisher","unstructured":"M. Schuld and F. Petruccione, Quantum Models as Kernel Methods, pp. 217\u2013245. Springer International Publishing, Cham, 2021.","DOI":"10.1007\/978-3-030-83098-4_6"},{"key":"25","doi-asserted-by":"publisher","unstructured":"B. Sch\u00f6lkopf, R. Herbrich, and A. J. Smola, ``A Generalized Representer Theorem,'' in Computational Learning Theory, D. Helmbold and B. Williamson, eds., pp. 416\u2013426. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001.","DOI":"10.1007\/3-540-44581-1_27"},{"key":"26","doi-asserted-by":"publisher","unstructured":"T. Hofmann, B. Sch\u00f6lkopf, and A. J. Smola, ``Kernel methods in machine learning,'' The Annals of Statistics 36, 1171\u20131220 (2008).","DOI":"10.1214\/009053607000000677"},{"key":"27","doi-asserted-by":"publisher","unstructured":"V. Havl\u00ed\u010dek, A. D. C\u00f3rcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, ``Supervised learning with quantum-enhanced feature spaces,'' Nature 567, 209\u2013212 (2019).","DOI":"10.1038\/s41586-019-0980-2"},{"key":"28","doi-asserted-by":"publisher","unstructured":"M. Schuld and N. Killoran, ``Quantum Machine Learning in Feature Hilbert Spaces,'' Phys. Rev. Lett. 122, 040504 (2019).","DOI":"10.1103\/PhysRevLett.122.040504"},{"key":"29","doi-asserted-by":"publisher","unstructured":"H. Buhrman, R. Cleve, J. Watrous, and R. De Wolf, ``Quantum fingerprinting,'' Physical review letters 87, 167902 (2001).","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"30","doi-asserted-by":"publisher","unstructured":"M. Hillery, R. O'Connell, M. Scully, and E. Wigner, ``Distribution functions in physics: Fundamentals,'' Physics Reports 106, 121\u2013167 (1984).","DOI":"10.1016\/0370-1573(84)90160-1"},{"key":"31","doi-asserted-by":"publisher","unstructured":"R. P. Rundle, P. W. Mills, T. Tilma, J. H. Samson, and M. J. Everitt, ``Simple procedure for phase-space measurement and entanglement validation,'' Phys. Rev. A 96, 022117 (2017).","DOI":"10.1103\/PhysRevA.96.022117"},{"key":"32","doi-asserted-by":"publisher","unstructured":"W. Hoeffding, ``Probability Inequalities for Sums of Bounded Random Variables,'' Journal of the American Statistical Association 58, 13\u201330 (1963).","DOI":"10.1007\/978-1-4612-0865-5_26"},{"key":"33","doi-asserted-by":"publisher","unstructured":"L. Gurvits, ``On the Complexity of Mixed Discriminants and Related Problems,'' in Mathematical Foundations of Computer Science 2005, J. J\u0229drzejowicz and A. Szepietowski, eds., pp. 447\u2013458. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005.","DOI":"10.1007\/11549345_39"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Y. Lim and C. Oh, ``Approximating outcome probabilities of linear optical circuits,'' npj Quantum Information 9, 124 (2023).","DOI":"10.1038\/s41534-023-00791-9"},{"key":"35","doi-asserted-by":"publisher","unstructured":"S. Rahimi-Keshari, S. Baghbanzadeh, and C. M. Caves, ``In situ characterization of linear-optical networks in randomized boson sampling,'' Physical Review A 101, 043809 (2020).","DOI":"10.1103\/PhysRevA.101.043809"},{"key":"36","unstructured":"A. Ferraro, S. Olivares, and M. G. A. Paris, ``Gaussian States in Quantum Information,'' arxiv:quant-ph\/0503237."},{"key":"37","doi-asserted-by":"publisher","unstructured":"M. Schuld, K. Br\u00e1dler, R. Israel, D. Su, and B. Gupt, ``Measuring the similarity of graphs with a Gaussian boson sampler,'' Phys. Rev. A 101, 032314 (2020).","DOI":"10.1103\/PhysRevA.101.032314"},{"key":"38","doi-asserted-by":"publisher","unstructured":"A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O'Brien, and T. C. Ralph, ``Boson Sampling from a Gaussian State,'' Phys. Rev. Lett. 113, 100502 (2014).","DOI":"10.1103\/PhysRevLett.113.100502"},{"key":"39","doi-asserted-by":"publisher","unstructured":"S. Rahimi-Keshari, A. P. Lund, and T. C. Ralph, ``What Can Quantum Optics Say about Computational Complexity Theory?,'' Phys. Rev. Lett. 114, 060501 (2015).","DOI":"10.1103\/PhysRevLett.114.060501"},{"key":"40","doi-asserted-by":"publisher","unstructured":"C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Gaussian Boson Sampling,'' Phys. Rev. Lett. 119, 170501 (2017).","DOI":"10.1103\/PhysRevLett.119.170501"},{"key":"41","unstructured":"A. Lvovsky, P. Grangier, A. Ourjoumtsev, V. Parigi, M. Sasaki, and R. Tualle-Brouri, ``Production and applications of non-Gaussian quantum states of light,'' arXiv:2006.16985."},{"key":"42","doi-asserted-by":"publisher","unstructured":"C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Gaussian boson sampling,'' Physical review letters 119, 170501 (2017).","DOI":"10.1103\/PhysRevLett.119.170501"},{"key":"43","doi-asserted-by":"publisher","unstructured":"U. Chabaud and S. Mehraban, ``Holomorphic representation of quantum computations,'' Quantum 6, 831 (2022).","DOI":"10.22331\/q-2022-10-06-831"},{"key":"44","doi-asserted-by":"publisher","unstructured":"U. Chabaud and M. Walschaers, ``Resources for bosonic quantum computational advantage,'' Physical Review Letters 130, 090602 (2023).","DOI":"10.1103\/PhysRevLett.130.090602"},{"key":"45","doi-asserted-by":"publisher","unstructured":"A. Hertz and S. De Bi\u00e8vre, ``Quadrature coherence scale driven fast decoherence of bosonic quantum field states,'' Physical Review Letters 124, 090402 (2020).","DOI":"10.1103\/PhysRevLett.124.090402"},{"key":"46","doi-asserted-by":"publisher","unstructured":"U. Chabaud, D. Markham, and F. Grosshans, ``Stellar representation of non-Gaussian quantum states,'' Physical Review Letters 124, 063605 (2020).","DOI":"10.1103\/PhysRevLett.124.063605"},{"key":"47","unstructured":"L. J. Henderson, R. Goel, and S. Shrapnel, ``Quantum kernel machine learning with continuous variables,'' arXiv:2401.05647."},{"key":"48","doi-asserted-by":"publisher","unstructured":"Y. Y. Gao, B. J. Lester, Y. Zhang, C. Wang, S. Rosenblum, L. Frunzio, L. Jiang, S. Girvin, and R. J. Schoelkopf, ``Programmable interference between two microwave quantum memories,'' Physical Review X 8, 021073 (2018).","DOI":"10.1103\/PhysRevX.8.021073"},{"key":"49","doi-asserted-by":"publisher","unstructured":"H. Gan, G. Maslennikov, K.-W. Tseng, C. Nguyen, and D. Matsukevich, ``Hybrid quantum computing with conditional beam splitter gate in trapped ion system,'' Physical review letters 124, 170502 (2020).","DOI":"10.1103\/PhysRevLett.124.170502"},{"key":"50","doi-asserted-by":"publisher","unstructured":"O. \u010cernot\u00edk, I. Pietik\u00e4inen, S. Puri, S. Girvin, and R. Filip, ``Swap-test interferometry with biased qubit noise,'' Physical Review Research 6, 033074 (2024).","DOI":"10.1103\/PhysRevResearch.6.033074"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Z. Wang, A. Marandi, K. Wen, R. L. Byer, and Y. Yamamoto, ``Coherent Ising machine based on degenerate optical parametric oscillators,'' Phys. Rev. A 88, 063853 (2013).","DOI":"10.1103\/PhysRevA.88.063853"},{"key":"52","unstructured":"S. Dehdashti, P. Tiwari, K. H. E. Safty, P. Bruza, and J. Notzel, ``Enhancing Quantum Machine Learning: The Power of Non-Linear Optical Reproducing Kernels,'' arXiv:2407.13809."},{"key":"53","doi-asserted-by":"publisher","unstructured":"C. Ferrie and J. Emerson, ``Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations,'' Journal of Physics A: Mathematical and Theoretical 41, 352001 (2008).","DOI":"10.1088\/1751-8113\/41\/35\/352001"},{"key":"54","doi-asserted-by":"publisher","unstructured":"C. Ferrie and J. Emerson, ``Framed Hilbert space: hanging the quasi-probability pictures of quantum theory,'' New Journal of Physics 11, 063040 (2009).","DOI":"10.1088\/1367-2630\/11\/6\/063040"},{"key":"55","doi-asserted-by":"publisher","unstructured":"C. Weedbrook, S. Pirandola, R. Garc\u00eda-Patr\u00f3n, N. J. Cerf, T. C. Ralph, J. H. Shapiro, and S. Lloyd, ``Gaussian quantum information,'' Reviews of Modern Physics 84, 621 (2012).","DOI":"10.1103\/RevModPhys.84.621"},{"key":"56","doi-asserted-by":"publisher","unstructured":"S. Boyd, S. P. Boyd, and L. Vandenberghe, ``Convex optimization,''. Cambridge university press, 2004.","DOI":"10.1017\/cbo9780511804441"},{"key":"57","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, ``Introduction to algorithms,''. MIT press, 2009."},{"key":"58","doi-asserted-by":"publisher","unstructured":"H. J. Briegel, D. E. Browne, W. D\u00fcr, R. Raussendorf, and M. Van den Nest, ``Measurement-based quantum computation,'' Nature Physics 5, 19\u201326 (2009).","DOI":"10.1038\/nphys1157"},{"key":"59","doi-asserted-by":"publisher","unstructured":"E. Knill, R. Laflamme, and G. J. Milburn, ``A scheme for efficient quantum computation with linear optics,'' nature 409, 46\u201352 (2001).","DOI":"10.1038\/35051009"},{"key":"60","doi-asserted-by":"publisher","unstructured":"S. Bartolucci, P. Birchall, H. Bombin, H. Cable, C. Dawson, M. Gimeno-Segovia, E. Johnston, K. Kieling, N. Nickerson, M. Pant, et al., ``Fusion-based quantum computation,'' Nature Communications 14, 912 (2023).","DOI":"10.1038\/s41467-023-36493-1"},{"key":"61","doi-asserted-by":"publisher","unstructured":"U. Chabaud, D. Markham, and A. Sohbi, ``Quantum machine learning with adaptive linear optics,'' Quantum 5, 496 (2021).","DOI":"10.22331\/q-2021-07-05-496"},{"key":"62","doi-asserted-by":"publisher","unstructured":"D. J. Brod, E. F. Galv\u00e3o, A. Crespi, R. Osellame, N. Spagnolo, and F. Sciarrino, ``Photonic implementation of boson sampling: a review,'' Advanced Photonics 1, 034001\u2013034001 (2019).","DOI":"10.1117\/1.AP.1.3.034001"},{"key":"63","doi-asserted-by":"publisher","unstructured":"H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, et al., ``Quantum computational advantage using photons,'' Science 370, 1460\u20131463 (2020).","DOI":"10.1017\/cbo9780511622748.004"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-11-07-1519\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T16:43:35Z","timestamp":1730997815000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-11-07-1519\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,7]]},"references-count":64,"URL":"https:\/\/doi.org\/10.22331\/q-2024-11-07-1519","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,7]]},"article-number":"1519"}}