pith. sign in

arxiv: 2309.07027 · v2 · submitted 2023-09-13 · 🪐 quant-ph

High performance Boson Sampling simulation via data-flow engines

Gregory Morse , Tomasz Rybotycki , \'Agoston Kaposi , Zolt\'an Kolarovszki , Uro\v{s} Stoj\v{c}i\'c , Tam\'as Kozsik , Oskar Mencer , Micha{\l} Oszmaniec
show 2 more authors
Zolt\'an Zimbor\'as P\'eter Rakyta
This is my paper

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

classification 🪐 quant-ph
keywords boson samplingpermanent computationBB/FG formulaGray code orderingFPGA data-flow enginequantum simulation
0
0 comments X

The pith

Generalizing the BB/FG permanent formula with n-ary Gray codes cuts computation time for boson sampling matrices that have repeated rows.

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

The paper generalizes the Balasubramanian-Bax-Franklin-Glynn permanent formula so that it accounts for row multiplicities by ordering the addends according to an n-ary Gray code. This ordering lowers the number of operations needed when some rows repeat, a situation that arises in lossy boson sampling. The authors then map the resulting algorithm onto FPGA data-flow engines and use it to draw samples from 60-mode interferometers with up to 40 photons. The measured rate is roughly 80 seconds per sample on four chips, and the observed scaling matches the Clifford-Clifford bound. The same design works for both ideal and lossy experiments.

Core claim

We generalize the BB/FG permanent formula to account for row multiplicities during permanent evaluation by incorporating n-ary Gray code ordering of the addends; we then implement the algorithm on FPGA-based data-flow engines to draw samples from a 60-mode interferometer at up to 40 photons with an average rate of approximately 80 seconds per sample on four chips.

What carries the argument

Generalized BB/FG permanent formula that uses n-ary Gray code ordering of addends to exploit row multiplicities.

If this is right

  • Boson sampling instances with loss become directly simulable on the same hardware without separate handling of repeated rows.
  • A single scalar parameter extracted from run time versus photon number fully characterizes the performance of any BS simulator built on this method.
  • The FPGA design can be reused for both ideal and lossy experiments without code changes.
  • The approach supplies a concrete hardware benchmark against which future theoretical speed-ups can be compared.

Where Pith is reading between the lines

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

  • The same Gray-code trick could be applied to other permanent-evaluation tasks that encounter repeated rows, such as certain graph-counting problems.
  • If the FPGA implementation scales linearly with the number of chips, a modest cluster could reach the photon numbers where classical simulation is believed to become intractable.
  • A portable performance metric derived from the Clifford-Clifford bound lets different hardware platforms be compared without re-running full experiments.

Load-bearing premise

Ordering the addends of the permanent sum by an n-ary Gray code actually reduces the number of arithmetic operations whenever some rows of the matrix are identical.

What would settle it

Measure the exact number of additions and multiplications performed by the generalized formula on a matrix with known row multiplicities and compare it to the count for the unmodified BB/FG formula on the same matrix.

Figures

Figures reproduced from arXiv: 2309.07027 by \'Agoston Kaposi, Gregory Morse, Micha{\l} Oszmaniec, Oskar Mencer, P\'eter Rakyta, Tam\'as Kozsik, Tomasz Rybotycki, Uro\v{s} Stoj\v{c}i\'c, Zolt\'an Kolarovszki, Zolt\'an Zimbor\'as.

Figure 1
Figure 1. Figure 1: The structure of the computing kernels realized on t [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Performance comparison of the permanent calculator D [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Performance comparison of the permanent calculator D [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The numerical accuracy of different implementations t [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Left: A schematic of a standard BS experiment. The blue elements denote beam splitters inside the interferometer. A net of interconnected beam splitters is the usual physical realization of the interferometer. Right: A schematic representation of the loss model we use in this work. On the left side of the diagrammatic equation, we see a lossy channel on a single mode, with particle transmission probability… view at source ↗
Figure 6
Figure 6. Figure 6: Performance of the developed BS simulation design ex [PITH_FULL_IMAGE:figures/full_fig_p015_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The staggered strategy to calculate the multiplici [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Batched performance comparison of the permanent calc [PITH_FULL_IMAGE:figures/full_fig_p023_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Batched performance comparison of the permanent calc [PITH_FULL_IMAGE:figures/full_fig_p024_9.png] view at source ↗
read the original abstract

In this work, we generalize the Balasubramanian-Bax-Franklin-Glynn (BB/FG) permanent formula to account for row multiplicities during the permanent evaluation and reduce the complexity of permanent evaluation in scenarios where such multiplicities occur. This is achieved by incorporating n-ary Gray code ordering of the addends during the evaluation. We implemented the designed algorithm on FPGA-based data-flow engines and utilized the developed accessory to speed up boson sampling simulations up to $40$ photons, by drawing samples from a $60$ mode interferometer at an averaged rate of $\sim80$ seconds per sample utilizing $4$ FPGA chips. We also show that the performance of our BS simulator is in line with the theoretical estimation of Clifford \& Clifford \cite{clifford2020faster} providing a way to define a single parameter to characterize the performance of the BS simulator in a portable way. The developed design can be used to simulate both ideal and lossy boson sampling experiments.

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 / 1 minor

Summary. The paper generalizes the Balasubramanian-Bax-Franklin-Glynn (BB/FG) permanent formula to account for row multiplicities during permanent evaluation by incorporating n-ary Gray code ordering of the addends. This algorithm is implemented on FPGA-based data-flow engines to accelerate boson sampling simulations, achieving draws from a 60-mode interferometer with up to 40 photons at an average rate of ~80 seconds per sample on 4 FPGA chips. Performance is reported to align with the Clifford & Clifford theoretical bound, enabling a portable single-parameter characterization, and the design supports both ideal and lossy experiments.

Significance. If the generalization is shown to be correct and the implementation verified with explicit checks, the work would advance practical classical simulation of boson sampling at scales relevant to quantum device benchmarking. The hardware mapping to data-flow engines and the use of an independent theoretical bound (rather than self-fitted parameters) for performance characterization are positive features that could aid reproducibility across platforms.

major comments (2)
  1. [Generalization of BB/FG formula and permanent evaluation] The generalization of the BB/FG formula via n-ary Gray code ordering for row multiplicities is stated in the abstract and algorithm description, but supplies neither an explicit derivation of the adjusted addend contributions nor a worked example on a matrix with repeated rows confirming that the sum matches the permanent definition while correctly skipping redundant terms. This directly affects the validity of the claimed complexity reduction and the headline sampling rate.
  2. [Implementation results and performance claims] The results section asserts successful FPGA implementation and agreement with theory for the 40-photon/60-mode case at ~80 s/sample, yet provides no verification details, error analysis, comparison data against exact permanents, or cross-checks that the hardware mapping preserves the generalized formula's output. Without these, the soundness of the reported performance cannot be confirmed.
minor comments (1)
  1. The abstract and text would benefit from a brief statement of the exact matrix dimensions and multiplicity patterns used in the largest reported runs to allow independent reproduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed review. The comments highlight areas where additional clarity would strengthen the manuscript. We address each major comment below and will revise accordingly.

read point-by-point responses

  1. Referee: [Generalization of BB/FG formula and permanent evaluation] The generalization of the BB/FG formula via n-ary Gray code ordering for row multiplicities is stated in the abstract and algorithm description, but supplies neither an explicit derivation of the adjusted addend contributions nor a worked example on a matrix with repeated rows confirming that the sum matches the permanent definition while correctly skipping redundant terms. This directly affects the validity of the claimed complexity reduction and the headline sampling rate.

    Authors: We agree that an explicit derivation and worked example would improve verifiability. The manuscript presents the generalized algorithm and its use of n-ary Gray codes, but we will add a dedicated subsection deriving the adjusted addend contributions for row multiplicities and include a small worked example (e.g., a 3x3 matrix with repeated rows) demonstrating that the result equals the permanent while correctly handling multiplicities and skipping redundancies. This revision will directly address concerns about the complexity reduction. revision: yes

  2. Referee: [Implementation results and performance claims] The results section asserts successful FPGA implementation and agreement with theory for the 40-photon/60-mode case at ~80 s/sample, yet provides no verification details, error analysis, comparison data against exact permanents, or cross-checks that the hardware mapping preserves the generalized formula's output. Without these, the soundness of the reported performance cannot be confirmed.

    Authors: The performance characterization relies on the independent Clifford & Clifford bound rather than self-fitted parameters, which is a strength for portability. We acknowledge that the current draft lacks explicit verification details for the large-scale case. Direct comparison to exact permanents is infeasible at 40 photons due to computational cost. In revision we will add: (i) verification results on smaller instances where exact permanents can be computed, (ii) details of hardware mapping validation via RTL simulation and consistency checks, and (iii) error analysis for the FPGA implementation. These additions will support the reported rates without changing the headline figures. revision: partial

Circularity Check

0 steps flagged

No circularity: empirical performance measured against external theoretical bound

full rationale

The paper's central result is an FPGA implementation achieving measured sampling rates for boson sampling up to 40 photons, reported as aligning with the independent Clifford & Clifford theoretical bound rather than any fitted parameter derived from the authors' own runs. The generalization of the BB/FG formula via n-ary Gray code is presented as a new algorithmic contribution without any self-referential definition or reduction of the reported performance metric to the inputs by construction. No load-bearing step reduces a prediction or uniqueness claim to a self-citation chain or fitted input; the work is self-contained against the external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the validity of the existing BB/FG permanent formula, the correctness of the n-ary Gray code reordering for multiplicity reduction, and the assumption that FPGA data-flow engines can realize the algorithm at the claimed throughput; no free parameters or invented entities are introduced.

axioms (2)
  • standard math The Balasubramanian-Bax-Franklin-Glynn (BB/FG) formula correctly computes the permanent of a matrix.
    The paper explicitly generalizes this established formula.
  • domain assumption n-ary Gray code ordering reduces the number of operations when row multiplicities are present.
    This is the key step asserted in the generalization.

pith-pipeline@v0.9.0 · 5756 in / 1451 out tokens · 27994 ms · 2026-05-24T06:52:17.622164+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

73 extracted references · 73 canonical work pages

  1. [1]

    Faster classical bos on sampling, 2020

    Peter Clifford and Raphaël Clifford. Faster classical bos on sampling, 2020. 16

    work page 2020

  2. [2]

    Quantum computing and the entanglement f rontier, 2012

    John Preskill. Quantum computing and the entanglement f rontier, 2012

    work page 2012

  3. [3]

    Qua ntum sampling problems, bosonsampling and quantum supremacy

    Austin P Lund, Michael J Bremner, and Timothy C Ralph. Qua ntum sampling problems, bosonsampling and quantum supremacy. npj Quantum Information , 3(1):1–8, 2017

    work page 2017

  4. [4]

    Quantum computation al supremacy

    Aram W Harrow and Ashley Montanaro. Quantum computation al supremacy. Nature, 549(7671):203–209, 2017

    work page 2017

  5. [5]

    The computational com plexity of linear optics, 2010

    Scott Aaronson and Alex Arkhipov. The computational com plexity of linear optics, 2010

    work page 2010

  6. [6]

    The computational com plexity of linear optics

    Scott Aaronson and Alex Arkhipov. The computational com plexity of linear optics. In Re- search in Optical Sciences , page QTh1A.2. Optical Society of America, 2014

    work page 2014

  7. [7]

    A verage-case complexity ver- sus approximate simulation of commuting quantum computati ons

    Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. A verage-case complexity ver- sus approximate simulation of commuting quantum computati ons. Physical review letters , 117(8):080501, 2016

    work page 2016

  8. [8]

    Characterizing quantum supremacy in near-term devices

    Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven . Characterizing quantum supremacy in near-term devices. Nature Physics, 14(6):595–600, 2018

    work page 2018

  9. [9]

    On the complexity and verification of quantum random circuit sampling

    Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh V azirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159–163, 2019

    work page 2019

  10. [10]

    Haferkamp, D

    J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J . Eisert, and J. Bermejo-Vega. Closing gaps of a quantum advantage with short-time hamilto nian dynamics. Phys. Rev. Lett., 125:250501, Dec 2020

    work page 2020

  11. [11]

    Fermion sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states

    Michał Oszmaniec, Ninnat Dangniam, Mauro ES Morales, a nd Zoltán Zimborás. Fermion sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states. arXiv preprint arXiv:2012.15825 , 2020

    work page arXiv 2012

  12. [12]

    Signatures of a sampling quantum adva ntage in driven quantum many- body systems

    Jirawat Tangpanitanon, Supanut Thanasilp, Marc-Anto ine Lemonde, Ninnat Dangniam, and Dimitris G Angelakis. Signatures of a sampling quantum adva ntage in driven quantum many- body systems. Quantum Science and Technology , 8(2):025019, mar 2023

    work page 2023

  13. [13]

    Hamilton, Regina Kruse, Linda Sansoni, Sonja B arkhofen, Christine Silberhorn, and Igor Jex

    Craig S. Hamilton, Regina Kruse, Linda Sansoni, Sonja B arkhofen, Christine Silberhorn, and Igor Jex. Gaussian boson sampling. Phys. Rev. Lett. , 119:170501, Oct 2017

    work page 2017

  14. [14]

    Hamilton, Linda Sansoni, Sonja B arkhofen, Christine Silberhorn, and Igor Jex

    Regina Kruse, Craig S. Hamilton, Linda Sansoni, Sonja B arkhofen, Christine Silberhorn, and Igor Jex. Detailed study of gaussian boson sampling. Phys. Rev. A , 100:032326, Sep 2019

    work page 2019

  15. [15]

    Gaussian boson sampling using threshold detectors

    Nicolás Quesada, Juan Miguel Arrazola, and Nathan Kill oran. Gaussian boson sampling using threshold detectors. Phys. Rev. A , 98:062322, Dec 2018

    work page 2018

  16. [16]

    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, Sep 2014

    work page 2014

  17. [17]

    Brod, Ernesto F

    Marco Bentivegna, Nicolò Spagnolo, Chiara Vitelli, Fu lvio Flamini, Niko Viggianiello, Lu- dovico Latmiral, Paolo Mataloni, Daniel J. Brod, Ernesto F. Galvão, Andrea Crespi, Roberta Ramponi, Roberto Osellame, and Fabio Sciarrino. Experimen tal scattershot boson sampling. Science Advances, 1(3), 2015

    work page 2015

  18. [18]

    Bartley, Linda Sansoni, Regina Kruse, Craig S

    Sonja Barkhofen, Tim J. Bartley, Linda Sansoni, Regina Kruse, Craig S. Hamilton, Igor Jex, and Christine Silberhorn. Driven boson sampling. Phys. Rev. Lett. , 118:020502, Jan 2017

    work page 2017

  19. [19]

    Motes, Alexei Gilchrist, Jonathan P

    Keith R. Motes, Alexei Gilchrist, Jonathan P. Dowling, and Peter P. Rohde. Scalable boson sampling with time-bin encoding using a loop-based archite cture. Phys. Rev. Lett., 113:120501, Sep 2014

    work page 2014

  20. [20]

    High-dimensional unitary transformations and boson sampling on temporal modes using dispersive optics

    Mihir Pant and Dirk Englund. High-dimensional unitary transformations and boson sampling on temporal modes using dispersive optics. Phys. Rev. A , 93:043803, Apr 2016

    work page 2016

  21. [21]

    C. Shen, Z. Zhang, and L.-M. Duan. Scalable implementat ion of boson sampling with trapped ions. Phys. Rev. Lett. , 112:050504, Feb 2014

    work page 2014

  22. [22]

    Hong–ou–mandel interference of two phonons in trapped ions

    Kenji Toyoda, Ryoto Hiji, Atsushi Noguchi, and Shinji U rabe. Hong–ou–mandel interference of two phonons in trapped ions. Nature, 527(7576):74–77, Nov 2015. 17

    work page 2015

  23. [23]

    Boson sampling with ultracold a toms, 2022

    Carsten Robens, Iñigo Arrazola, Wolfgang Alt, Dieter M eschede, Lucas Lamata, Enrique Solano, and Andrea Alberti. Boson sampling with ultracold a toms, 2022

    work page 2022

  24. [24]

    Proposal for microwave boson sampling

    Borja Peropadre, Gian Giacomo Guerreschi, Joonsuk Huh , and Alán Aspuru-Guzik. Proposal for microwave boson sampling. Phys. Rev. Lett. , 117:140505, Sep 2016

    work page 2016

  25. [25]

    Broome, Alessandro Fedrizzi, Saleh Rahimi- Keshari, Justin Dove, Scott Aaron- son, Timothy C

    Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi- Keshari, Justin Dove, Scott Aaron- son, Timothy C. Ralph, and Andrew G. White. Photonic boson sa mpling in a tunable circuit. Science, 339(6121):794–798, 2013

    work page 2013

  26. [26]

    Spring, Benjamin J

    Justin B. Spring, Benjamin J. Metcalf, Peter C. Humphre ys, W. Steven Kolthammer, Xian- Min Jin, Marco Barbieri, Animesh Datta, Nicholas Thomas-Pe ter, Nathan K. Langford, Dmytro Kundys, James C. Gates, Brian J. Smith, Peter G. R. Smi th, and Ian A. Walms- ley. Boson sampling on a photonic chip. Science, 339(6121):798–801, 2013

    work page 2013

  27. [27]

    Brod, Ernesto F

    Andrea Crespi, Roberto Osellame, Roberta Ramponi, Dan iel J. Brod, Ernesto F. Galvão, Nicolò Spagnolo, Chiara Vitelli, Enrico Maiorino, Paolo Ma taloni, and Fabio Sciarrino. Inte- grated multimode interferometers with arbitrary designs f or photonic boson sampling. Nature Photonics, 7(7):545–549, Jul 2013

    work page 2013

  28. [28]

    Experimental boson sampling

    Max Tillmann, Borivoje Dakić, René Heilmann, Stefan No lte, Alexander Szameit, and Philip Walther. Experimental boson sampling. Nature Photonics, 7(7):540–544, Jul 2013

    work page 2013

  29. [29]

    Brod, Andrea Crespi, Fulvio Flamini, Sandro Giacomini, Giorgio Milani, Roberta Rampon i, Paolo Mataloni, Roberto Osel- lame, Ernesto F

    Nicolò Spagnolo, Chiara Vitelli, Marco Bentivegna, Da niel J. Brod, Andrea Crespi, Fulvio Flamini, Sandro Giacomini, Giorgio Milani, Roberta Rampon i, Paolo Mataloni, Roberto Osel- lame, Ernesto F. Galvão, and Fabio Sciarrino. Experimental validation of photonic boson sampling. Nature Photonics, 8(8):615–620, Aug 2014

    work page 2014

  30. [30]

    Spring, Paolo L

    Justin B. Spring, Paolo L. Mennea, Benjamin J. Metcalf, Peter C. Humphreys, James C. Gates, Helen L. Rogers, Christoph Söller, Brian J. Smith, W. Steven Kolthammer, Peter G. R. Smith, and Ian A. Walmsley. Chip-based array of near-id entical, pure, heralded single- photon sources. Optica, 4(1):90–96, Jan 2017

    work page 2017

  31. [31]

    Faruque, Gary F

    Imad I. Faruque, Gary F. Sinclair, Damien Bonneau, John G. Rarity, and Mark G. Thomp- son. On-chip quantum interference with heralded photons fr om two independent micro-ring resonator sources in silicon photonics. Opt. Express, 26(16):20379–20395, Aug 2018

    work page 2018

  32. [32]

    Signorini and L

    S. Signorini and L. Pavesi. On-chip heralded single pho ton sources. AVS Quantum Science , 2(4):041701, 2020

    work page 2020

  33. [33]

    Hui Wang, Jian Qin, Xing Ding, Ming-Cheng Chen, Si Chen, Xiang You, Yu-Ming He, Xiao Jiang, L. You, Z. Wang, C. Schneider, Jelmer J. Renema, Sven H öfling, Chao-Yang Lu, and Jian-Wei Pan. Boson sampling with 20 input photons and a 60-m ode interferometer in a 1014-dimensional hilbert space. Phys. Rev. Lett. , 123:250503, Dec 2019

    work page 2019

  34. [34]

    Quantum computational advantage using photons

    Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, We i-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zh en Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. Quantum computational advantage using photons. Science, 370(6523):146...

    work page 2020

  35. [35]

    Phase-programmable gaussian boson sampling using stimulated squeezed light

    Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Ch eng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, et al. Phase-programmable gaussian boson sampling using stimulated squeezed light. arXiv preprint arXiv:2106.15534 , 2021

    work page arXiv 2021

  36. [36]

    Platt, Vadim N

    Benjamin Villalonga, Murphy Yuezhen Niu, Li Li, Hartmu t Neven, John C. Platt, Vadim N. Smelyanskiy, and Sergio Boixo. Efficient approximation of ex perimental gaussian boson sam- pling, 2022

    work page 2022

  37. [37]

    Madsen, Fabian Laudenbach, Mohsen Falamarzi

    Lars S. Madsen, Fabian Laudenbach, Mohsen Falamarzi. A skarani, Fabien Rortais, Trevor Vin- cent, Jacob F. F. Bulmer, Filippo M. Miatto, Leonhard Neuhau s, Lukas G. Helt, Matthew J. Collins, Adriana E. Lita, Thomas Gerrits, Sae Woo Nam, Varun D. Vaidya, Matteo Menotti, Ish Dhand, Zachary Vernon, Nicolás Quesada, and Jonathan La voie. Quantum computational...

    work page 2022

  38. [38]

    Spoofing cr oss-entropy measure in boson sampling

    Changhun Oh, Liang Jiang, and Bill Fefferman. Spoofing cr oss-entropy measure in boson sampling. Phys. Rev. Lett. , 131:010401, Jul 2023

    work page 2023

  39. [39]

    Birchall, Ashley Montanaro, and Anthony Laing

    Alex Neville, Chris Sparrow, Raphaël Clifford, Eric Joh nston, Patrick M. Birchall, Ashley Montanaro, and Anthony Laing. Classical boson sampling alg orithms with superior perfor- mance to near-term experiments. Nature Physics, 13(12):1153–1157, oct 2017

    work page 2017

  40. [40]

    Benoit Seron, Leonardo Novo, Alex Arkhipov, and Nicola s J. Cerf. Efficient validation of boson sampling from binned photon-number distributions, 2 022

    work page

  41. [41]

    Efficient verifi- cation of Boson Sampling

    Ulysse Chabaud, Frédéric Grosshans, Elham Kashefi, and Damian Markham. Efficient verifi- cation of Boson Sampling. Quantum, 5:578, November 2021

    work page 2021

  42. [42]

    Pattern recog nition techniques for boson sampling validation

    Iris Agresti, Niko Viggianiello, Fulvio Flamini, Nico lò Spagnolo, Andrea Crespi, Roberto Osellame, Nathan Wiebe, and Fabio Sciarrino. Pattern recog nition techniques for boson sampling validation. Physical Review X , 9(1), jan 2019

    work page 2019

  43. [43]

    Visual assessment of multi-photon interference

    Fulvio Flamini, Nicolò Spagnolo, and Fabio Sciarrino. Visual assessment of multi-photon interference. Quantum Science and Technology , 4(2):024008, mar 2019

    work page 2019

  44. [44]

    The classical compl exity of boson sampling

    Peter Clifford and Raphaël Clifford. The classical compl exity of boson sampling. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Al gorithms, SODA ’18, page 146–155, USA, 2018. Society for Industrial and Applied Math ematics

    work page 2018

  45. [45]

    L.G. Valiant. The complexity of computing the permanen t. Theoretical Computer Science , 8(2):189–201, 1979

    work page 1979

  46. [46]

    H.J. Ryser. Combinatorial Mathematics. The Carus Mathematical Monographs. Mathematical Association of America, 1963

    work page 1963

  47. [47]

    David G. Glynn. Permanent formulae from the veronesean . Designs, Codes and Cryptography , 68(1):39–47, Jul 2013

    work page 2013

  48. [48]

    A benchmark test of boson sampling on Tianhe-2 superco mputer

    Junjie Wu, Yong Liu, Baida Zhang, Xianmin Jin, Yang Wang , Huiquan Wang, and Xuejun Yang. A benchmark test of boson sampling on Tianhe-2 superco mputer. National Science Review, 5(5):715–720, 07 2018

    work page 2018

  49. [49]

    A d ynamic programming approach for generating n-ary reflected gray code list, 2013

    Mehmet Kurt, Can Atilgan, and Murat Ersen Berberler. A d ynamic programming approach for generating n-ary reflected gray code list, 2013

    work page 2013

  50. [50]

    https:// github.com/Budapest-Quantum-Computing-Group/piquass o, 2021

    A python library for designing and simulating photonic quantum computers. https:// github.com/Budapest-Quantum-Computing-Group/piquass o, 2021

    work page 2021

  51. [51]

    Johnston, J

    Wesley M. Johnston, J. R. Paul Hanna, and Richard J. Mill ar. Advances in dataflow pro- gramming languages. ACM Comput. Surv. , 36(1):1–34, mar 2004

    work page 2004

  52. [52]

    Nijenhuis and Herbert S

    Albert. Nijenhuis and Herbert S. Wilf. Combinatorial algorithms / Albert Nijenhuis and Herbert S. Wilf . Academic Press New York, 1975

    work page 1975

  53. [53]

    Mpfr: A multiple-precision binary floating-point library w ith correct rounding

    Laurent Fousse, Guillaume Hanrot, Vincent Lefèvre, Pa trick Pélissier, and Paul Zimmermann. Mpfr: A multiple-precision binary floating-point library w ith correct rounding. ACM Trans. Math. Softw. , 33(2):13–es, jun 2007

    work page 2007

  54. [54]

    https://github.com/Budapest-Quantum-Computing-Group / piquassoboost, 2021

    Piquasso boost libraries. https://github.com/Budapest-Quantum-Computing-Group / piquassoboost, 2021

    work page 2021

  55. [55]

    Generalized concurren ce in boson sampling

    Seungbeom Chin and Joonsuk Huh. Generalized concurren ce in boson sampling. Scientific Reports, 8(1):6101, Apr 2018

    work page 2018

  56. [56]

    Lundow and K

    P.H. Lundow and K. Markström. Efficient computation of pe rmanents, with applications to boson sampling and random matrices. Journal of Computational Physics , 455:110990, 2022

    work page 2022

  57. [57]

    The walr us: a library for the calculation of hafnians, hermite polynomials and gaussian boson sampling

    Brajesh Gupt, Josh Izaac, and Nicolás Quesada. The walr us: a library for the calculation of hafnians, hermite polynomials and gaussian boson sampling . Journal of Open Source Software, 4(44):1705, 2019

    work page 2019

  58. [58]

    Jacob F. F. Bulmer, Bryn A. Bell, Rachel S. Chadwick, Ale x E. Jones, Diana Moise, Alessan- dro Rigazzi, Jan Thorbecke, Utz-Uwe Haus, Thomas Van Vaeren bergh, Raj B. Patel, Ian A. Walmsley, and Anthony Laing. The boundary for quantum advan tage in gaussian boson sampling. Science Advances, 8(4):eabl9236, 2022. 19

    work page 2022

  59. [59]

    D. J. Guan. Generalized gray codes with applications. 1 998

    work page

  60. [60]

    https://www.xilinx.com/ content/dam/xilinx/support/documents/data_sheets/ds962-u200-u250.pdf, 2021

    Alveo u200 and u250 data center accelerator cards data s heet. https://www.xilinx.com/ content/dam/xilinx/support/documents/data_sheets/ds962-u200-u250.pdf, 2021

    work page 2021

  61. [61]

    Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algo rithms. Addison-Wesley, Boston, third edition, 1997

    work page 1997

  62. [62]

    Nicholas J. Higham. Stability of a method for multiplyi ng complex matrices with three real matrix multiplications. SIAM Journal on Matrix Analysis and Applications , 13(3):681–687, 1992

    work page 1992

  63. [63]

    Karatsuba with rectangular multipliers for fpgas

    Martin Kumm, Oscar Gustafsson, Florent de Dinechin, Jo hannes Kappauf, and Peter Zipf. Karatsuba with rectangular multipliers for fpgas. In 2018 IEEE 25th Symposium on Computer Arithmetic (ARITH) , pages 13–20, 2018

    work page 2018

  64. [64]

    Large multiplier s with fewer dsp blocks

    Florent de Dinechin and Bogdan Pasca. Large multiplier s with fewer dsp blocks. In 2009 International Conference on Field Programmable Logic and App lications, pages 250–255, 2009

    work page 2009

  65. [65]

    Montgomery

    P.L. Montgomery. Five, six, and seven-term karatsuba- like formulae. IEEE Transactions on Computers, 54(3):362–369, 2005

    work page 2005

  66. [66]

    Polynomial speedup in torontonian calculation by a scalabl e recursive algorithm, 2022

    Ágoston Kaposi, Zoltán Kolarovszki, Tamás Kozsik, Zol tán Zimborás, and Péter Rakyta. Polynomial speedup in torontonian calculation by a scalabl e recursive algorithm, 2022

    work page 2022

  67. [67]

    Noise and the frontier of quantum supremacy

    Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao L iu. Noise and the frontier of quantum supremacy. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1308–1317, 2022

    work page 2021

  68. [68]

    Boson sampling with a linear number of mode

    Adam Bouland, Daniel Brod, Shaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, and Michał Oszmaniec. Boson sampling with a linear number of mode. in preparation, 2023

    work page 2023

  69. [69]

    Simulating boson sampling in lossy architectures

    Raúl García-Patrón, Jelmer J Renema, and Valery Shches novich. Simulating boson sampling in lossy architectures. Quantum, 3:169, 2019

    work page 2019

  70. [70]

    Classical simul ation of linear optics subject to nonuniform losses

    Daniel Jost Brod and Michał Oszmaniec. Classical simul ation of linear optics subject to nonuniform losses. Quantum, 4:267, May 2020. 20 A Technical details of the DFE implementation to efficiently e valuate the permanent A.1 Generalization to matrices of variable size A fundamental concept of a DFE is that the static data-flow cir cuit implemented on the ch...

    work page 2020

  71. [71]

    Due to the chosen structure of zeros and ones in matrix B, the column sums calculated for the corresponding columns w ould be equal to unity for all of the vectors δ

    can be generalized for rectangular-shaped input matrices , just the upper limit of the product reduction of column sums is needed to be adjust ed. Due to the chosen structure of zeros and ones in matrix B, the column sums calculated for the corresponding columns w ould be equal to unity for all of the vectors δ. These column sums would not contribute to t...

    work page

  72. [72]

    distance in time

    on the FPGA chip as well. However, due to the peculiar proper ties of the FPGA 21 multiplicity factor, colum sum and parity associated with g(k) FPGA implementation to calculate the next multiplicity factor and colums sum data-streams of multiplicity factors, columns sums and parities Gray-code increasing direction Figure 7: The staggered strategy to calc...

    work page

  73. [73]

    Now we briefly describe our mathematical co nsiderations when determining the normalization factors

    and ( 8) with row and column multiplicities the DFE result then needs to be re-scaled by t he product of the scaling factors α j, by taking the multiplicity of the individual factors corres ponding to the column multiplicities in the input matrix. Now we briefly describe our mathematical co nsiderations when determining the normalization factors. In order ...

    work page