pith. sign in

arxiv: 2301.01232 · v3 · submitted 2023-01-03 · 🪐 quant-ph

Sample efficient graph classification using binary Gaussian boson sampling

Amanuel Anteneh , Olivier Pfister This is my paper

Pith reviewed 2026-05-24 10:05 UTC · model grok-4.3

classification 🪐 quant-ph
keywords Gaussian boson samplinggraph classificationbinary detectorsTorontonianquantum machine learningfeature extraction
0
0 comments X

The pith

Gaussian boson sampling classifies graphs using only binary detectors instead of photon-number-resolving ones.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a quantum feature extraction method for classifying graphs that relies on Gaussian boson sampling but substitutes binary detectors for the usual photon-number-resolving detectors. This substitution simplifies the hardware requirements and permits room-temperature operation. The approach maintains sample efficiency for the machine learning task while connecting the sampling probabilities to the Torontonian matrix function from graph theory. A reader would care because it brings this quantum method closer to practical implementation on near-term devices.

Core claim

The central discovery is that binary Gaussian boson sampling, characterized by the Torontonian, can extract features for graph classification with performance comparable to setups using more advanced detectors, thereby reducing implementation complexity.

What carries the argument

Binary Gaussian boson sampling setup linked to the Torontonian for computing detection probabilities.

If this is right

  • Classification tasks on graphs can use simpler quantum hardware.
  • Room-temperature detectors become viable for this quantum ML application.
  • The Torontonian provides a theoretical bridge between graph structures and sampling outcomes.
  • Sample efficiency is preserved without needing number-resolving capabilities.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This method might apply to other sampling-based quantum algorithms where full photon counting is unnecessary.
  • Further work could test whether binary detectors maintain performance on larger or more complex graphs.
  • Classical approximations to the Torontonian might yield hybrid algorithms.

Load-bearing premise

Binary detection events capture enough information about the graph to enable effective classification without loss compared to full photon counting.

What would settle it

Demonstrating that a graph classification model trained on binary GBS data achieves substantially lower accuracy than one using photon-number-resolving data on the same set of graphs.

Figures

Figures reproduced from arXiv: 2301.01232 by Amanuel Anteneh, Olivier Pfister.

Figure 1
Figure 1. Figure 1: FIG. 1: In the original input space [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: Example of a 3-mode Gaussian boson sampler. [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: 4-vertex graph and its corresponding adjacency [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4: Results of the principal component analysis (PCA) on the [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5: Distribution of graph sizes according to class for each dataset. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6: The complete graph of 4 vertices and its [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7: Different photon detection events [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
read the original abstract

We present a variation of a quantum algorithm for the machine learning task of classification with graph-structured data. The algorithm implements a feature extraction strategy that is based on Gaussian boson sampling (GBS) a near term model of quantum computing. However, unlike the currently proposed algorithms for this problem, our GBS setup only requires binary (light/no light) detectors, as opposed to photon number resolving detectors. These detectors are technologically simpler and can operate at room temperature, making our algorithm less complex and less costly to implement on the physical hardware. We also investigate the connection between graph theory and the matrix function called the Torontonian which characterizes the probabilities of binary GBS detection events.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper proposes a variant of Gaussian boson sampling (GBS) for classifying graph-structured data that relies exclusively on binary (click/no-click) detectors rather than photon-number-resolving detectors. It asserts that this reduces hardware complexity and cost while still enabling sample-efficient feature extraction, and it examines the mathematical link between the Torontonian of the GBS covariance matrix and graph-theoretic quantities.

Significance. If the binary-detector GBS features retain sufficient discriminative power for graphs, the approach would lower the technological barrier for near-term photonic quantum machine learning by permitting room-temperature operation. The investigation of the Torontonian-graph connection could also supply a new analytic tool for GBS-based algorithms, but the manuscript supplies no performance benchmarks or derivations to quantify the retained accuracy.

major comments (2)
  1. [Abstract] Abstract: the central claim that binary detectors preserve the feature quality needed for effective graph classification is stated without any supporting equations, sampling complexity bounds, or comparison to photon-number-resolving GBS; the Torontonian is introduced only as an object of investigation rather than as the basis of a proven equivalence or approximation.
  2. [Abstract] The manuscript does not derive or bound the information loss incurred by replacing the full photon-number distribution with its binary marginals; if higher-order correlations encode the relevant graph invariants, the sample-efficiency and accuracy assertions cannot be substantiated from the given description.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for their comments on the abstract and the need for clearer support of our claims. We respond point by point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that binary detectors preserve the feature quality needed for effective graph classification is stated without any supporting equations, sampling complexity bounds, or comparison to photon-number-resolving GBS; the Torontonian is introduced only as an object of investigation rather than as the basis of a proven equivalence or approximation.

    Authors: The abstract summarizes the contribution at a high level. The manuscript body presents the binary GBS model and uses the Torontonian as the exact function governing click probabilities (i.e., the binary marginals), which directly supplies the feature map for classification. We investigate its graph-theoretic properties but do not assert a proven equivalence to the full photon-number distribution or provide sampling-complexity bounds in the current text. We will revise the abstract to clarify that the Torontonian furnishes the precise binary probabilities rather than an approximation. revision: yes

  2. Referee: [Abstract] The manuscript does not derive or bound the information loss incurred by replacing the full photon-number distribution with its binary marginals; if higher-order correlations encode the relevant graph invariants, the sample-efficiency and accuracy assertions cannot be substantiated from the given description.

    Authors: Our approach employs binary detectors and the associated Torontonian probabilities for feature extraction, motivated by reduced hardware requirements. The manuscript does not derive quantitative bounds on information loss relative to photon-number-resolving GBS, nor does it compare sample efficiency or accuracy. This is a substantive gap; if higher-order photon correlations carry essential graph invariants, the claimed advantages would require further justification. revision: partial

standing simulated objections not resolved
  • Deriving or providing sampling complexity bounds and quantitative information-loss analysis comparing binary GBS to photon-number-resolving GBS, as the current work centers on the proposal and Torontonian-graph investigation without these derivations.

Circularity Check

0 steps flagged

No circularity; derivation is self-contained

full rationale

The paper proposes a hardware variation of GBS-based graph classification that replaces photon-number-resolving detectors with binary detectors and investigates (rather than derives) the Torontonian-graph theory connection. No equations, fitted parameters, or self-citations are presented that reduce any claimed prediction or feature quality to the input data or prior results by construction. The Torontonian link is explicitly framed as an investigation, and the hardware-simplification claim rests on the technological properties of binary detectors, not on any self-referential mapping or uniqueness theorem imported from the authors' prior work. The manuscript is therefore self-contained against external benchmarks with no load-bearing circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no information on free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5631 in / 941 out tokens · 28646 ms · 2026-05-24T10:05:21.715143+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

50 extracted references · 50 canonical work pages · 3 internal anchors

  1. [1]

    The problem with using GBS beyond sampling The sample complexity of a machine learning algo- rithm refers to the number of samples or amount of data required to learn some target function. In the case of GBS applications it refers to the number of samples we need to generate from the GBS device to learn or approx- imate a probability distribution over som...

    work page

  2. [2]

    Coarse graining of sample distributions However a method was suggested in [19] to coarse-grain the probability distribution by combining outcomes into groups called orbits. Coarse-graining in this sense means to construct a new probability distribution over the set of these groups, the cardinality of which is less than the original set of all possible det...

    work page

  3. [3]

    meta-orbit

    Sample complexity of previously proposed GBS graph kernels The first GBS based graph kernel proposed in [3] maps a graph G to feature vectors in a feature space ϕ : G → f = ( f1, f2, ..., fD) ∈ RD. Where fi = p(Oi n) is the probability of detecting a detection event from the orbit Oi n. This kernel was shown to perform well against three of the four class...

    work page

  4. [4]

    The number of binary strings of length M with exactly i ones is M i

    Sample Complexity Since the ni’s for binary detection events can be either 0 or 1 we can think of the detection outcomes as binary strings of length M with at most M ones. The number of binary strings of length M with exactly i ones is M i . So the number of possible binary detection events, the number of binary strings of length M with at most M ones, is...

    work page

  5. [5]

    How- ever storing the adjacency matrix of the graphs requires O(M2) space complexity

    Space Complexity The size of the ν feature vectors is constant with re- spect to the graph size so the space required is O(1) and for the µ feature vectors the size grows linearly with N which is ≤ M so the space required is O(M). How- ever storing the adjacency matrix of the graphs requires O(M2) space complexity

    work page

  6. [6]

    Time Complexity The time complexity is determined by the most com- putationally time intensive step of the algorithm which is encoding the adjacency matrix into the GBS device. This is the case because the encoding process requires taking the Takagi decomposition of the matrix A which for a M × M matrix has time complexity O(M3) as it is a special case of...

    work page

  7. [7]

    Here we present the important concepts

    GBS with PNR detectors There has been substantial work done already on the connection between graph theory and Gaussian boson sampling with PNR detectors [18–20]. Here we present the important concepts. Any undirected graph G with no self-loops and |V | = M vertices can be encoded into a M-mode GBS setup consisting of a set of M squeezers followed by an i...

    work page

  8. [8]

    Encoding a graph into a GBS device To map a graph to a feature vector we must first pro- gram the GBS device, by setting the squeezing parame- ters and beamsplitter angles of the device, according to the adjacency matrix A of the graph. Any adjacency ma- trix A ∈ RM ×M of an undirected graph of M vertices can be mapped to a symmetric, positive definite 2M...

    work page

  9. [9]

    Nikolentzos, G

    G. Nikolentzos, G. Siglidis, and M. Vazirgiannis, Graph kernels: A survey, Journal of Artificial Intelligence Re- search 72, 943 (2021)

    work page 2021

  10. [10]

    N. M. Kriege, F. D. Johansson, and C. Morris, A survey on graph kernels, Applied Network Science 5, 1 (2020)

    work page 2020

  11. [11]

    Schuld, K

    M. Schuld, K. Br´ adler, R. Israel, D. Su, and B. Gupt, Measuring the similarity of graphs with a gaussian boson sampler, Physical Review A 101, 032314 (2020)

    work page 2020

  12. [12]

    Aaronson and A

    S. Aaronson and A. Arkhipov, The computational com- plexity of linear optics, Electronic Colloquium on Com- putational Complexity Report No. 170 , 1 (2010)

    work page 2010

  13. [13]

    L. G. Valiant, The complexity of computing the perma- nent, Theoretical computer science 8, 189 (1979)

    work page 1979

  14. [14]

    C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, Gaussian boson sampling, Phys. Rev. Lett. 119, 170501 (2017)

    work page 2017

  15. [15]

    Bachor and T

    H.-A. Bachor and T. C. Ralph, A Guide to Experiments in Quantum Optics, 3rd ed. (Wiley-VCH, 2019)

    work page 2019

  16. [16]

    Zhong, H

    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, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Quantum computational advantage using photons, Science 370, 1460 (2020), https://science.sciencemag.org/content/370/6523/146...

    work page 2020

  17. [17]

    L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins, A. E. Lita, T. Gerrits, S. W. Nam, V. D. Vaidya, M. Menotti, I. Dhand, Z. Vernon, N. Quesada, and J. Lavoie, Quantum computational ad- vantage with a programmable photonic processor, Nature 606, 75 (2022)

    work page 2022

  18. [18]

    Arute, K

    F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S...

    work page 2019

  19. [19]

    Weissman, E

    T. Weissman, E. Ordentlich, G. Seroussi, S. Verdu, and M. J. Weinberger, Inequalities for the l1 deviation of the empirical distribution, HP Technical Reports HPL- 2003-97, R1 (2003)

    work page 2003

  20. [20]

    parameters of a simulated Hamiltonian

    Note that this is not related to the number of possi- ble output quantum states, which scales with the num- ber of parameters governing the quantum evolution, e.g. parameters of a simulated Hamiltonian. Obviously, no quantum advantage can be obtained for M-qubit Hamil- tonians that have O(2M) parameters but all classically intractable M-qubit Hamiltonians...

    work page

  21. [21]

    A. E. Lita, A. J. Miller, and S. W. Nam, Counting near- infrared single-photons with 95% efficiency, Opt. Expr. 16, 3032 (2008)

    work page 2008

  22. [22]

    Cahall, K

    C. Cahall, K. L. Nicolich, N. T. Islam, G. P. Lafyatis, A. J. Miller, D. J. Gauthier, and J. Kim, Multi-photon detection using a conventional superconducting nanowire single-photon detector, Optica 4, 1534 (2017)

    work page 2017

  23. [23]

    Eaton, A

    M. Eaton, A. Hossameldin, R. J. Birrittella, P. M. Alsing, C. C. Gerry, H. Dong, C. Cuevas, and O. Pfister, Resolu- tion of 100 photons and quantum generation of unbiased random numbers, Nature Photonics 10.1038/s41566-022- 01105-9 (2022)

    work page doi:10.1038/s41566-022- 2022

  24. [24]

    Cheng, Y

    R. Cheng, Y. Zhou, S. Wang, M. Shen, T. Taher, and H. X. Tang, A 100-pixel photon-number-resolving detector unveiling photon statistics, Nature Photonics 10.1038/s41566-022-01119-3 (2022)

    work page doi:10.1038/s41566-022-01119-3 2022

  25. [25]

    Weedbrook, S

    C. Weedbrook, S. Pirandola, R. Garc´ ıa-Patr´ on, N. J. Cerf, T. C. Ralph, J. H. Shapiro, and S. Lloyd, Gaus- sian quantum information, Reviews of Modern Physics 84, 621 (2012)

    work page 2012

  26. [26]

    Br´ adler, P.-L

    K. Br´ adler, P.-L. Dallaire-Demers, P. Rebentrost, D. Su, and C. Weedbrook, Gaussian boson sampling for perfect matchings of arbitrary graphs, Physical Review A 98, 032310 (2018)

    work page 2018

  27. [27]

    Br´ adler, S

    K. Br´ adler, S. Friedland, J. Izaac, N. Killoran, and D. Su, Graph isomorphism and gaussian boson sampling, Spe- cial Matrices 9, 166 (2021)

    work page 2021

  28. [28]

    J. M. Arrazola and T. R. Bromley, Using gaussian boson sampling to find dense subgraphs, Physical review letters 121, 030503 (2018)

    work page 2018

  29. [29]

    C. L. Canonne, A short note on learning discrete distri- butions, arXiv preprint arXiv:2002.11457 (2020)

    work page arXiv 2002

  30. [30]

    A. Y. Oru¸ c, On number of partitions of an integer into a fixed number of positive integers, Journal of Number Theory 159, 355 (2016)

    work page 2016

  31. [31]

    Bradler, R

    K. Bradler, R. Israel, M. Schuld, and D. Su, A duality at the heart of gaussian boson sampling, arXiv preprint arXiv:1910.04022 (2019)

    work page arXiv 1910

  32. [32]

    Quesada, J

    N. Quesada, J. M. Arrazola, and N. Killoran, Gaussian boson sampling using threshold detectors, Physical Re- view A 98, 062322 (2018)

    work page 2018

  33. [33]

    The Torontonian was also shown to be a generating func- tion for the Hafnian given by Haf(A) = 1 M! dM dzM Tor(zXA) z=0 (C1) where A is a 2 M × 2M matrix

    work page

  34. [34]

    Routines for the diagonalization of complex matrices

    T. Hahn, Routines for the diagonalization of complex ma- trices, arXiv preprint physics/0607103 (2006)

    work page internal anchor Pith review Pith/arXiv arXiv 2006

  35. [35]

    L. Gu, X. Wang, and G. Zhang, Quantum higher or- der singular value decomposition (IEEE, 2019) pp. 1166– 1171

    work page 2019

  36. [36]

    Quantum Recommendation Systems

    I. Kerenidis and A. Prakash, Quantum recommendation systems, arXiv preprint arXiv:1603.08675 (2016)

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  37. [37]

    B. Gupt, J. Izaac, and N. Quesada, The walrus: a library for the calculation of hafnians, hermite polynomials and gaussian boson sampling, Journal of Open Source Soft- ware 4, 1705 (2019)

    work page 2019

  38. [38]

    Siglidis, G

    G. Siglidis, G. Nikolentzos, S. Limnios, C. Giatsidis, K. Skianis, and M. Vazirgiannis, Grakel: A graph ker- nel library in python., J. Mach. Learn. Res. 21, 1 (2020)

    work page 2020

  39. [39]

    Subgraph Matching Kernels for Attributed Graphs

    N. Kriege and P. Mutzel, Subgraph matching kernels for attributed graphs, arXiv preprint arXiv:1206.6483 (2012)

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  40. [40]

    Shervashidze, S

    N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt, Efficient graphlet kernels for large graph comparison, in Artificial intelligence and statistics (PMLR, 2009) pp. 488–495

    work page 2009

  41. [41]

    S. V. N. Vishwanathan, N. N. Schraudolph, R. Kondor, and K. M. Borgwardt, Graph kernels, Journal of Machine Learning Research 11, 1201 (2010)

    work page 2010

  42. [42]

    K. M. Borgwardt and H.-P. Kriegel, Shortest-path kernels on graphs, in Fifth IEEE international conference on data mining (ICDM’05) (IEEE, 2005) pp. 8–pp

    work page 2005

  43. [43]

    Barab´ asi and M

    A.-L. Barab´ asi and M. P´ osfai,Network Science (Cam- bridge University Press, Cambridge, 2016)

    work page 2016

  44. [44]

    Although this has been proven rigorously for the exact sampling case [4, 42] the proof pertaining to the approx- imate sampling case rests on the assumption of two con- jectures known as the Permanent-of-Gaussians Conjec- ture and the Permanent Anti-Concentration Conjecture which are as of now still unproven

    work page

  45. [45]

    Quesada, Franck-condon factors by counting perfect matchings of graphs with loops, The Journal of chemical physics 150, 164113 (2019)

    N. Quesada, Franck-condon factors by counting perfect matchings of graphs with loops, The Journal of chemical physics 150, 164113 (2019)

    work page 2019

  46. [46]

    J. F. Bulmer, S. Paesani, R. S. Chadwick, and N. Que- sada, Threshold detection statistics of bosonic states, arXiv preprint arXiv:2202.04600 (2022)

    work page arXiv 2022

  47. [47]

    W. R. Clements, P. C. Humphreys, B. J. Metcalf, W. S. Kolthammer, and I. A. Walmsley, Optimal design for uni- versal multiport interferometers, Optica 3, 1460 (2016)

    work page 2016

  48. [48]

    Lloyd, Universal quantum simulators, Science 273, 1073 (1996)

    S. Lloyd, Universal quantum simulators, Science 273, 1073 (1996). 14

    work page 1996

  49. [49]

    R. P. Feynman, Simulating physics with computers, Int. J. Theor. Phys. 21, 467 (1982)

    work page 1982

  50. [50]

    Kruse, C

    R. Kruse, C. S. Hamilton, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, Detailed study of gaussian bo- son sampling, Physical Review A 100, 032326 (2019)

    work page 2019