Phase-space negativity as a computational resource for quantum kernel methods

Ulysse Chabaud; Roohollah Ghobadi; Salman Beigi; Saleh Rahimi-Keshari

doi:10.22331/q-2024-11-07-1519

Phase-space negativity as a computational resource for quantum kernel methods

Ulysse Chabaud¹, Roohollah Ghobadi², Salman Beigi³, and Saleh Rahimi-Keshari⁴

¹DIENS, École Normale Supérieure, PSL University, CNRS, INRIA, 45 rue d'Ulm, Paris 75005, France
²Institute for Quantum Science and Technology, University of Calgary, Calgary, AB, T2N 1N4, Canada
³School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran
⁴School of Physics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5531, Tehran, Iran

Published:	2024-11-07, volume 8, page 1519
Eprint:	arXiv:2405.12378v2
Doi:	https://doi.org/10.22331/q-2024-11-07-1519
Citation:	Quantum 8, 1519 (2024).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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.

Featured image: Pictorial description of a classical algorithm for estimated quantum kernel functions.

Popular summary

In recent years, quantum computing has shown promise for machine learning, especially through methods like quantum kernel methods. These methods are designed to harness the unique capabilities of quantum computers to potentially solve problems that would be too complex for classical computers.

In quantum kernel methods, part of the calculation—estimating a quantum kernel function—is handled by a quantum computer. This kernel function aims to capture complex relationships in data that might be challenging or impossible for classical systems to model efficiently. The rest of the computational process, however, is managed by a classical computer. As a consequence, quantum kernel methods cannot be advantageous if the quantum kernel function can be estimated efficiently by a classical computer.

Our work explores when that is the case, by deriving new classical algorithms for estimating quantum kernel functions. We focus on bosonic systems, which are at the basis of many promising quantum computing architectures, and we provide sufficient conditions for our classical algorithms to efficiently estimate quantum kernel functions in these systems. When those sufficient conditions are satisfied, this negates any potential quantum advantage through quantum kernel methods.

Quantum states of bosonic systems can be equivalently described by functions in phase space, and our sufficient conditions are based on three phase-space properties of quantum systems: negative volume, non-classical depth, and excess range. These are three different signatures of "phase-space negativity", which is a well-known indicator of quantumness. Our findings show not only that phase-space negativity is an essential resource for realizing quantum advantages in machine learning, but also that a subtle interplay of its different aspects is in fact necessary.

► BibTeX data

@article{Chabaud2024phasespace,
  doi = {10.22331/q-2024-11-07-1519},
  url = {https://doi.org/10.22331/q-2024-11-07-1519},
  title = {Phase-space negativity as a computational resource for quantum kernel methods},
  author = {Chabaud, Ulysse and Ghobadi, Roohollah and Beigi, Salman and Rahimi-Keshari, Saleh},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1519},
  month = nov,
  year = {2024}
}

► References

[1] J. Preskill, ``Quantum Computing in the NISQ era and beyond,'' Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[2] 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–510 (2019).
https://doi.org/10.1117/12.2603523

[3] I. M. Georgescu, S. Ashhab, and F. Nori, ``Quantum simulation,'' Rev. Mod. Phys. 86, 153–185 (2014).
https://doi.org/10.1103/RevModPhys.86.153

[4] 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).
https://doi.org/10.1038/s41534-019-0209-0

[5] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, ``Quantum machine learning,'' Nature 549, 195–202 (2017).
https://doi.org/10.1038/nature23474

[6] E. Farhi and H. Neven, ``Classification with quantum neural networks on near term processors,'' arXiv:1802.06002.
arXiv:arXiv:1802.06002

[7] B. M. Terhal and D. P. DiVincenzo, ``Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games,'' Quantum Inf. Comput. 4, 134–145 (2004).
https://doi.org/10.26421/QIC4.2-5

[8] 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).
https://doi.org/10.1103/PhysRevLett.117.080501

[9] S. Aaronson and A. Arkhipov, ``The Computational Complexity of Linear Optics,'' Theory of Computing 9, 143–252 (2013).
https://doi.org/10.4086/toc.2013.v009a004

[10] S. Bravyi, D. Gosset, and R. König, ``Quantum advantage with shallow circuits,'' Science 362, 308–311 (2018).
https://doi.org/10.1126/science.aar3106

[11] K. E. Cahill and R. J. Glauber, ``Density Operators and Quasiprobability Distributions,'' Phys. Rev. 177, 1882–1902 (1969).
https://doi.org/10.1103/PhysRev.177.1882

[12] R. W. Spekkens, ``Negativity and Contextuality are Equivalent Notions of Nonclassicality,'' Phys. Rev. Lett. 101, 020401 (2008).
https://doi.org/10.1103/PhysRevLett.101.020401

[13] A. Mari and J. Eisert, ``Positive Wigner Functions Render Classical Simulation of Quantum Computation Efficient,'' Phys. Rev. Lett. 109, 230503 (2012).
https://doi.org/10.1103/PhysRevLett.109.230503

[14] 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).
https://doi.org/10.1088/1367-2630/15/1/013037

[15] 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).
https://doi.org/10.1103/PhysRevX.6.021039

[16] D. Stahlke, ``Quantum interference as a resource for quantum speedup,'' Phys. Rev. A 90, 022302 (2014).
https://doi.org/10.1103/PhysRevA.90.022302

[17] H. Pashayan, J. J. Wallman, and S. D. Bartlett, ``Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities,'' Phys. Rev. Lett. 115, 070501 (2015).
https://doi.org/10.1103/PhysRevLett.115.070501

[18] R. Mengoni and A. Di Pierro, ``Kernel methods in quantum machine learning,'' Quantum Machine Intelligence 1, 65–71 (2019).
https://doi.org/10.1007/s42484-019-00007-4

[19] R. Ghobadi, ``Nonclassical kernels in continuous-variable systems,'' Physical Review A 104, 052403 (2021).
https://doi.org/10.1103/PhysRevA.104.052403

[20] M. Bohmann and E. Agudelo, ``Phase-space inequalities beyond negativities,'' Physical Review Letters 124, 133601 (2020).
https://doi.org/10.1103/PhysRevLett.124.133601

[21] A. Kenfack and K. Życzkowski, ``Negativity of the Wigner function as an indicator of non-classicality,'' Journal of Optics B: Quantum and Semiclassical Optics 6, 396 (2004).
https://doi.org/10.1088/1464-4266/6/10/003

[22] 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).
https://doi.org/10.1103/PhysRevA.98.052350

[23] C. T. Lee, ``Measure of the nonclassicality of nonclassical states,'' Physical Review A 44, R2775 (1991).
https://doi.org/10.1103/PhysRevA.44.R2775

[24] K. K. Sabapathy, ``Process output nonclassicality and nonclassicality depth of quantum-optical channels,'' Phys. Rev. A 93, 042103 (2016).
https://doi.org/10.1103/PhysRevA.93.042103

[25] M. Schuld and F. Petruccione, Quantum Models as Kernel Methods, pp. 217–245. Springer International Publishing, Cham, 2021.
https://doi.org/10.1007/978-3-030-83098-4_6

[26] B. Schölkopf, R. Herbrich, and A. J. Smola, ``A Generalized Representer Theorem,'' in Computational Learning Theory, D. Helmbold and B. Williamson, eds., pp. 416–426. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001.
https://doi.org/10.1007/3-540-44581-1_27

[27] T. Hofmann, B. Schölkopf, and A. J. Smola, ``Kernel methods in machine learning,'' The Annals of Statistics 36, 1171–1220 (2008).
https://doi.org/10.1214/009053607000000677

[28] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, ``Supervised learning with quantum-enhanced feature spaces,'' Nature 567, 209–212 (2019).
https://doi.org/10.1038/s41586-019-0980-2

[29] M. Schuld and N. Killoran, ``Quantum Machine Learning in Feature Hilbert Spaces,'' Phys. Rev. Lett. 122, 040504 (2019).
https://doi.org/10.1103/PhysRevLett.122.040504

[30] H. Buhrman, R. Cleve, J. Watrous, and R. De Wolf, ``Quantum fingerprinting,'' Physical review letters 87, 167902 (2001).
https://doi.org/10.1103/PhysRevLett.87.167902

[31] M. Hillery, R. O'Connell, M. Scully, and E. Wigner, ``Distribution functions in physics: Fundamentals,'' Physics Reports 106, 121–167 (1984).
https://doi.org/10.1016/0370-1573(84)90160-1

[32] 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).
https://doi.org/10.1103/PhysRevA.96.022117

[33] W. Hoeffding, ``Probability Inequalities for Sums of Bounded Random Variables,'' Journal of the American Statistical Association 58, 13–30 (1963).
https://doi.org/10.1007/978-1-4612-0865-5_26

[34] L. Gurvits, ``On the Complexity of Mixed Discriminants and Related Problems,'' in Mathematical Foundations of Computer Science 2005, J. Jȩdrzejowicz and A. Szepietowski, eds., pp. 447–458. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005.
https://doi.org/10.1007/11549345_39

[35] Y. Lim and C. Oh, ``Approximating outcome probabilities of linear optical circuits,'' npj Quantum Information 9, 124 (2023).
https://doi.org/10.1038/s41534-023-00791-9

[36] 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).
https://doi.org/10.1103/PhysRevA.101.043809

[37] A. Ferraro, S. Olivares, and M. G. A. Paris, ``Gaussian States in Quantum Information,'' arxiv:quant-ph/0503237.
arXiv:arxiv:quant-ph/0503237

[38] M. Schuld, K. Brádler, R. Israel, D. Su, and B. Gupt, ``Measuring the similarity of graphs with a Gaussian boson sampler,'' Phys. Rev. A 101, 032314 (2020).
https://doi.org/10.1103/PhysRevA.101.032314

[39] 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).
https://doi.org/10.1103/PhysRevLett.113.100502

[40] 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).
https://doi.org/10.1103/PhysRevLett.114.060501

[41] C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Gaussian Boson Sampling,'' Phys. Rev. Lett. 119, 170501 (2017).
https://doi.org/10.1103/PhysRevLett.119.170501

[42] 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.
arXiv:arXiv:2006.16985

[43] C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Gaussian boson sampling,'' Physical review letters 119, 170501 (2017).
https://doi.org/10.1103/PhysRevLett.119.170501

[44] U. Chabaud and S. Mehraban, ``Holomorphic representation of quantum computations,'' Quantum 6, 831 (2022).
https://doi.org/10.22331/q-2022-10-06-831

[45] U. Chabaud and M. Walschaers, ``Resources for bosonic quantum computational advantage,'' Physical Review Letters 130, 090602 (2023).
https://doi.org/10.1103/PhysRevLett.130.090602

[46] A. Hertz and S. De Bièvre, ``Quadrature coherence scale driven fast decoherence of bosonic quantum field states,'' Physical Review Letters 124, 090402 (2020).
https://doi.org/10.1103/PhysRevLett.124.090402

[47] U. Chabaud, D. Markham, and F. Grosshans, ``Stellar representation of non-Gaussian quantum states,'' Physical Review Letters 124, 063605 (2020).
https://doi.org/10.1103/PhysRevLett.124.063605

[48] L. J. Henderson, R. Goel, and S. Shrapnel, ``Quantum kernel machine learning with continuous variables,'' arXiv:2401.05647.
arXiv:arXiv:2401.05647

[49] 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).
https://doi.org/10.1103/PhysRevX.8.021073

[50] 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).
https://doi.org/10.1103/PhysRevLett.124.170502

[51] O. Černotík, I. Pietikäinen, S. Puri, S. Girvin, and R. Filip, ``Swap-test interferometry with biased qubit noise,'' Physical Review Research 6, 033074 (2024).
https://doi.org/10.1103/PhysRevResearch.6.033074

[52] 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).
https://doi.org/10.1103/PhysRevA.88.063853

[53] 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.
arXiv:arXiv:2407.13809

[54] 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).
https://doi.org/10.1088/1751-8113/41/35/352001

[55] C. Ferrie and J. Emerson, ``Framed Hilbert space: hanging the quasi-probability pictures of quantum theory,'' New Journal of Physics 11, 063040 (2009).
https://doi.org/10.1088/1367-2630/11/6/063040

[56] C. Weedbrook, S. Pirandola, R. García-Patrón, N. J. Cerf, T. C. Ralph, J. H. Shapiro, and S. Lloyd, ``Gaussian quantum information,'' Reviews of Modern Physics 84, 621 (2012).
https://doi.org/10.1103/RevModPhys.84.621

[57] S. Boyd, S. P. Boyd, and L. Vandenberghe, ``Convex optimization,''. Cambridge university press, 2004.
https://doi.org/10.1017/cbo9780511804441

[58] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, ``Introduction to algorithms,''. MIT press, 2009.

[59] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest, ``Measurement-based quantum computation,'' Nature Physics 5, 19–26 (2009).
https://doi.org/10.1038/nphys1157

[60] E. Knill, R. Laflamme, and G. J. Milburn, ``A scheme for efficient quantum computation with linear optics,'' nature 409, 46–52 (2001).
https://doi.org/10.1038/35051009

[61] 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).
https://doi.org/10.1038/s41467-023-36493-1

[62] U. Chabaud, D. Markham, and A. Sohbi, ``Quantum machine learning with adaptive linear optics,'' Quantum 5, 496 (2021).
https://doi.org/10.22331/q-2021-07-05-496

[63] D. J. Brod, E. F. Galvão, A. Crespi, R. Osellame, N. Spagnolo, and F. Sciarrino, ``Photonic implementation of boson sampling: a review,'' Advanced Photonics 1, 034001–034001 (2019).
https://doi.org/10.1117/1.AP.1.3.034001

[64] 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–1463 (2020).
https://doi.org/10.1017/cbo9780511622748.004

Cited by

[1] Changhun Oh and Youngrong Lim, "Classical Algorithms for Measurement-Adaptive Gaussian Circuits", PRX Quantum 7 1, 010329 (2026).

[2] V. S. Kovtoniuk, M. Bohmann, and A. A. Semenov, "Nonclassical photocounting statistics with a single on-off detector", Physical Review A 113 6, 063726 (2026).

[3] Irene Kahvazadeh and A.C. Fong, 2025 International Conference on Intelligent & Innovative Practices in Engineering & Management (IIPEM) 1 (2025) ISBN:979-8-3315-9604-0.

[4] Laura J. Henderson, Rishi Goel, and Sally Shrapnel, "Quantum Kernel Machine Learning With Continuous Variables", Quantum 8, 1570 (2024).

[5] V. S. Kovtoniuk, A. B. Klimov, and A. A. Semenov, "Latent optical nonclassicality of conditionally prepared states", Physical Review A 111 5, 053701 (2025).

[6] A. Campos-Uscanga, E. Benítez Rodríguez, E. Piceno Martínez, and M. A. Bastarrachea-Magnani, "Magic states in the asymmetric quantum Rabi model", Physical Review A 113 1, 012412 (2026).

[7] Arash Azizi, "Tunable non-Gaussianity and exact higher-order coherences for quantum advantage", Physical Review A 112 6, 062607 (2025).

[8] Omar Fawzi, Aadil Oufkir, and Robert Salzmann, "Optimal Fidelity Estimation from Binary Measurements for Discrete and Continuous Variable Systems", PRX Quantum 7 1, 010309 (2026).

[9] Anaelle Hertz, Noah Lupu-Gladstein, Khabat Heshami, and Aaron Z. Goldberg, "Equalities and inequalities from entanglement, loss, and beam splitters", Quantum Studies: Mathematics and Foundations 13 3, 34 (2026).

[10] Massimo Frigerio, Antoine Debray, Nicolas Treps, and Mattia Walschaers, "Resourcefulness of non-classical continuous-variable quantum gates", Quantum 10, 2155 (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 16:21:40) and SAO/NASA ADS (last updated successfully 2026-08-09 16:21:41). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.