Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2309.07027 · New Journal of Physics

High performance Boson sampling simulation via data-flow engines

Gregory Morse, Tomasz Rybotycki, Ágoston Kaposi, Zoltán Kolarovszki, Uroš Stojčić, Tamás Kozsik, Oskar Mencer, Michał Oszmaniec, Zoltán Zimborás, Péter Rakyta

Published Mar 1, 2024• 6 citations
arXivHTMLPDF

Abstract

Abstract Boson sampling (BS) is viewed to be an accessible quantum computing paradigm to demonstrate computational advantage compared to classical computers. In this context, the evolution of permanent calculation algorithms attracts a significant attention as the simulation of BS experiments involves the evaluation of vast number of permanents. For this reason, we generalize the Balasubramanian–Bax–Franklin–Glynn permanent formula, aiming to efficiently integrate it into the BS strategy of Clifford and Clifford (2020 Faster classical boson sampling). A reduction in simulation complexity originating from multiplicities in photon occupation was achieved through the incorporation of a n-ary Gray code ordering of the addends during the permanent evaluation. Implementing the devised algorithm on FPGA-based data-flow engines, we leverage the resulting tool to accelerate boson sampling simulations for up to 40 photons. Drawing samples from a 60-mode interferometer, the achieved rate averages around 80 s per sample, employing 4 FPGA chips. The developed design facilitates the simulation of both ideal and lossy boson sampling experiments.

DOI
10.1088/1367-2630/ad313b

Related papers

Faster classical boson sampling

Peter Clifford, Raphaël Clifford

Abstract Since its introduction boson sampling has been the subject of intense study in the world of quantum computing. In the context of Fock-state boson sampling, the task is to sample independently from the set of all n × n submatrices built from possibly repeated rows of a larger m × n complex matrix according to a probability distribution related to the permanents of the submatrices. Experimental systems exploiting quantum photonic effects can in principle perform the task at great speed. For classical computing, Aaronson and Arkhipov (2011) showed that exact boson sampling problem cannot be solved in polynomial time unless the polynomial hierarchy collapses to the third level. Indeed for a number of years the fastest known exact classical algorithm ran in O ( m + n − 1 n n 2 n ) time per sample, emphasising the potential speed advantage of quantum computation. The advantage was reduced by Clifford and Clifford (2018), who gave a significantly faster classical solution taking O ( n 2 n + poly ( m , n ) ) time and linear space, matching the complexity of computing the permanent of a single matrix when m is polynomial in n. We continue by presenting an algorithm for Fock boson sampling whose average-case time complexity is much faster when m is proportional to n. In particular, when m = n our algorithm runs in approximately O(n · 1.69 n ) time on average. This result further increases the problem size needed to establish quantum computational advantage via the Fock scheme of boson sampling.

arXiv:2005.04214•Physica Scripta•May 2, 2024•45 citations

Classical Boson Sampling Simulation via Parallel Glynn-Gray Complex Permanent

Andrés Sebastián Pirolo

Description Boson sampling, originally proposed by Scott Aaronson and Alex Arkhipov as a candidate pathway toward quantum computational advantage, requires the evaluation of matrix permanents of complex-valued submatrices drawn from Haar-random unitary transformations. Computing the permanent of a general complex matrix is a well-known #P-hard problem and represents the principal computational barrier for classical simulation of linear-optical quantum circuits. This work introduces an evolutionary approach to permanent evaluation, derived from Glynn’s ±1 enumeration formula, traversed through binary reflected Gray code, extended to complex-valued arithmetic, and organized as a shared-nothing parallel computation model. Preliminary experiments suggest that the resulting implementation exhibits unexpected performance characteristics, enabling evaluation of boson-sampling–relevant matrix sizes on low-resource commodity hardware without the use of specialized accelerators. These observations raise a natural question: How far can classical simulation of boson sampling be pushed using carefully engineered algorithms? The accompanying manuscript provides the full algorithmic formulation, validation methodology, benchmark procedures, and numerical results required to reproduce and evaluate the approach. Statement of Prior Art and License Terms (Aligned with PolyForm Noncommercial License 1.0.0) 1. Permitted Noncommercial Use Use of the concepts, algorithms, and computational methods described in this work for noncommercial purposes, including academic research, independent study, education, benchmarking, validation, reproducibility studies, and experimental evaluation, is permitted under the terms of the PolyForm Noncommercial License 1.0.0, provided that proper attribution is given. 2. Statement of Prior Art This publication constitutes a formal public disclosure establishing prior art for the algorithmic methods and computational strategies described herein, including but not limited to: parallel traversal of Glynn permanent enumeration Gray-code–driven combinatorial traversal techniques complex-valued permanent computation strategies for boson-sampling matrices multi-core implementations targeting low-resource commodity hardware environments This disclosure is intended solely to prevent third-party patent claims on the disclosed concepts and does not grant any commercial rights. 3. Scope of the License All implementations of the methods described in this work—whether in software or hardware—are governed by the PolyForm Noncommercial License 1.0.0. This includes implementations in: any programming language interpreted or compiled environments parallel or distributed computing systems programmable hardware platforms such as CPU, GPU, or FPGA fixed hardware implementations including ASIC or silicon-level architectures 4. Noncommercial Restriction Any use of this work outside the definition of noncommercial use, as defined by the PolyForm Noncommercial License 1.0.0, is not permitted under this license. 5. Commercial and Operational Use Any commercial, industrial, governmental, institutional, regulatory, or production deployment of the methods described in this work constitutes use outside the scope of the PolyForm Noncommercial License 1.0.0 and therefore requires separate authorization from the author(s). 6. Derivative Works and Functional Equivalence Reimplementation, translation, refactoring, optimization, architectural modification, or claims of functional equivalence do not remove a work from the scope of the PolyForm Noncommercial License 1.0.0. Any such implementation remains subject to the same license terms. 6.a Code Size Irrelevance (No Minimum Threshold) For the avoidance of doubt, applicability of the PolyForm Noncommercial License 1.0.0 is independent of code size, number of lines, percentage of implementation, degree of literal similarity, or partial extraction. There is no minimum threshold of code volume required for a work to fall within the scope of this license. Any use, reproduction, reimplementation, refactoring, selective reuse, architectural translation, or functional incorporation of the disclosed concepts—regardless of size or extent—is subject to the terms of the PolyForm Noncommercial License 1.0.0. 7. Knowledge Contamination and Attribution Exposure to this work constitutes prior knowledge of the disclosed techniques. Subsequent implementations making material use of the described concepts remain subject to attribution and license requirements as defined by the PolyForm Noncommercial License 1.0.0. 8. Intellectual Property Ownership Nothing in this document shall be construed as transferring ownership of intellectual property. All intellectual property rights remain with the author(s), subject only to the permissions explicitly granted under the PolyForm Noncommercial License 1.0.0. 9. No Additional Rights Granted This document does not grant any rights beyond those expressly provided by the PolyForm Noncommercial License 1.0.0. In the event of any conflict, the terms of the PolyForm Noncommercial License 1.0.0 shall prevail. 10. Enforcement and Remedies Any use of the methods described in this work in violation of the PolyForm Noncommercial License 1.0.0 may be addressed through remedies available under applicable international law. Nothing in this disclosure prevents the author(s), or third parties acting on their behalf, from performing technical analysis or reverse engineering of deployed systems for the purpose of determining whether the disclosed methods have been implemented following the publication date of this work. 11. Versioning This record may contain multiple versions. Updates to presentation, terminology, benchmarks, or documentation do not alter: the core methodological contributions the scope of protection the license terms The most recent license and scope documents in the repository are authoritative. 12. Knowledge Contamination Any individual or entity that has reviewed, studied, tested, or otherwise been exposed to the materials contained in this record shall be considered knowledge-contaminated with respect to the disclosed concepts. Subsequent development of substantially similar implementations may therefore be evaluated in light of this prior exposure and the timestamped archival record of this publication. AuthorAndrés Sebastián Pirolo ORCID 0009-0004-3899-1222 andrespirolo@gmail.com Legal and External Affairs📧 brisademar96@gmail.com

•Mar 13, 2026•0 citations

Computing Permanents for Boson Sampling on Tianhe-2 Supercomputer.

Junjie Wu, Liu Y, Baida Zhang +4 more

Boson sampling, a specific quantum computation problem, is widely regarded to be one of the most achievable fields in which quantum machine will outperform the most powerful classical computer in the near term, although up to now no upper-bound of how fast the classical computers can compute matrix permanents, core problem of Boson sampling, has been reported. Here we test the computing of the matrix permanent on Tianhe-2, a supercomputer retaining its position as the world's No. 1 system for six times since June 2013. We arrived at the time (about 77.41~112.44 minutes) to compute the permanent of a $50\times 50$ matrix in an acceptable precision. In addition, we have found that Ryser's algorithm will produce an unacceptable error with the increase of problem scale, compared to Balasubramanian-Bax/Franklin-Glynn's algorithm in the same complexity. The precision issue suggests carefully check in future research of Boson sampling, and comprehensive comparison between quantum computer and classical computer.

•Jun 19, 2016•6 citations

A benchmark test of boson sampling on Tianhe-2 supercomputer

Junjie Wu, Yong Liu, Baida Zhang +4 more

Boson sampling, thought to be intractable classically, can be solved by a quantum machine composed of merely generation, linear evolution and detection of single photons. Such an analog quantum computer for this specific problem provides a shortcut to boost the absolute computing power of quantum computers to beat classical ones. However, the capacity bound of classical computers for simulating boson sampling has not yet been identified. Here we simulate boson sampling on the Tianhe-2 supercomputer, which occupied the first place in the world ranking six times from 2013 to 2016. We computed the permanent of the largest matrix using up to 312 000 CPU cores of Tianhe-2, and inferred from the current most efficient permanent-computing algorithms that an upper bound on the performance of Tianhe-2 is one 50-photon sample per ∼100 min. In addition, we found a precision issue with one of two permanent-computing algorithms.

arXiv:1606.05836•National Science Review•Jul 24, 2018•73 citations

A fast and frugal Gaussian Boson Sampling emulator

Tom Dodd, Javier Martínez-Cifuentes, Oliver Thomson Brown +2 more

If classical algorithms have been successful in reproducing the estimation of expectation values of observables of some quantum circuits using off-the-shelf computing resources, matching the performance of the most advanced quantum devices on sampling problems usually requires extreme cost in terms of memory and computing operations, making them accessible to only a handful of supercomputers around the world. In this work, we demonstrate for the first time a classical simulation outperforming Gaussian boson sampling experiments of one hundred modes on established benchmark tests using a single CPU or GPU. Being embarrassingly parallelizable, a small number of CPUs or GPUs allows us to match previous sampling rates that required more than one hundred GPUs. We believe algorithmic and implementation improvements will generalize our tools to photo-counting, single-photon inputs, and pseudo-photon-number-resolving scenarios beyond one thousand modes. Finally, most of the innovations in our tools remain valid for generic probability distributions over binary variables, rendering it potentially applicable to the simulation of qubit-based sampling problems and creating classical surrogates for classical-quantum algorithms.

quant-pharXiv:2511.14923•Science Advances•Nov 20, 2025•9 citations

Efficient computation of permanents, with applications to Boson sampling and random matrices

P. H. Lundow, Klas Markström

In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task. Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth. The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version. As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.

arXiv:1904.06229•Journal of Computational Physics•Jan 19, 2022•25 citations
Abstract Boson sampling (BS) is viewed to be an accessible quantum computing paradigm to demonstrate computational advantage compared to classical computers. In this context, the evolution of permanent calculation algorithms attracts a significant attention as the simulation of BS experiments involves the evaluation of vast number of permanents. For this reason, we generalize the Balasubramanian–Bax–Franklin–Glynn permanent formula, aiming to efficiently integrate it into the BS strategy of Clifford and Clifford (2020 Faster classical boson sampling). A reduction in simulation complexity originating from multiplicities in photon occupation was achieved through the incorporation of a n-ary Gray code ordering of the addends during the permanent evaluation. Implementing the devised algorithm on FPGA-based data-flow engines, we leverage the resulting tool to accelerate boson sampling simulations for up to 40 photons. Drawing samples from a 60-mode interferometer, the achieved rate averages around 80 s per sample, employing 4 FPGA chips. The developed design facilitates the simulation of both ideal and lossy boson sampling experiments.
Abstract Since its introduction boson sampling has been the subject of intense study in the world of quantum computing. In the context of Fock-state boson sampling, the task is to sample independently from the set of all n × n submatrices built from possibly repeated rows of a larger m × n complex matrix according to a probability distribution related to the permanents of the submatrices. Experimental systems exploiting quantum photonic effects can in principle perform the task at great speed. For classical computing, Aaronson and Arkhipov (2011) showed that exact boson sampling problem cannot be solved in polynomial time unless the polynomial hierarchy collapses to the third level. Indeed for a number of years the fastest known exact classical algorithm ran in O ( m + n − 1 n n 2 n ) time per sample, emphasising the potential speed advantage of quantum computation. The advantage was reduced by Clifford and Clifford (2018), who gave a significantly faster classical solution taking O ( n 2 n + poly ( m , n ) ) time and linear space, matching the complexity of computing the permanent of a single matrix when m is polynomial in n. We continue by presenting an algorithm for Fock boson sampling whose average-case time complexity is much faster when m is proportional to n. In particular, when m = n our algorithm runs in approximately O(n · 1.69 n ) time on average. This result further increases the problem size needed to establish quantum computational advantage via the Fock scheme of boson sampling.
Description Boson sampling, originally proposed by Scott Aaronson and Alex Arkhipov as a candidate pathway toward quantum computational advantage, requires the evaluation of matrix permanents of complex-valued submatrices drawn from Haar-random unitary transformations. Computing the permanent of a general complex matrix is a well-known #P-hard problem and represents the principal computational barrier for classical simulation of linear-optical quantum circuits. This work introduces an evolutionary approach to permanent evaluation, derived from Glynn’s ±1 enumeration formula, traversed through binary reflected Gray code, extended to complex-valued arithmetic, and organized as a shared-nothing parallel computation model. Preliminary experiments suggest that the resulting implementation exhibits unexpected performance characteristics, enabling evaluation of boson-sampling–relevant matrix sizes on low-resource commodity hardware without the use of specialized accelerators. These observations raise a natural question: How far can classical simulation of boson sampling be pushed using carefully engineered algorithms? The accompanying manuscript provides the full algorithmic formulation, validation methodology, benchmark procedures, and numerical results required to reproduce and evaluate the approach. Statement of Prior Art and License Terms (Aligned with PolyForm Noncommercial License 1.0.0) 1. Permitted Noncommercial Use Use of the concepts, algorithms, and computational methods described in this work for noncommercial purposes, including academic research, independent study, education, benchmarking, validation, reproducibility studies, and experimental evaluation, is permitted under the terms of the PolyForm Noncommercial License 1.0.0, provided that proper attribution is given. 2. Statement of Prior Art This publication constitutes a formal public disclosure establishing prior art for the algorithmic methods and computational strategies described herein, including but not limited to: parallel traversal of Glynn permanent enumeration Gray-code–driven combinatorial traversal techniques complex-valued permanent computation strategies for boson-sampling matrices multi-core implementations targeting low-resource commodity hardware environments This disclosure is intended solely to prevent third-party patent claims on the disclosed concepts and does not grant any commercial rights. 3. Scope of the License All implementations of the methods described in this work—whether in software or hardware—are governed by the PolyForm Noncommercial License 1.0.0. This includes implementations in: any programming language interpreted or compiled environments parallel or distributed computing systems programmable hardware platforms such as CPU, GPU, or FPGA fixed hardware implementations including ASIC or silicon-level architectures 4. Noncommercial Restriction Any use of this work outside the definition of noncommercial use, as defined by the PolyForm Noncommercial License 1.0.0, is not permitted under this license. 5. Commercial and Operational Use Any commercial, industrial, governmental, institutional, regulatory, or production deployment of the methods described in this work constitutes use outside the scope of the PolyForm Noncommercial License 1.0.0 and therefore requires separate authorization from the author(s). 6. Derivative Works and Functional Equivalence Reimplementation, translation, refactoring, optimization, architectural modification, or claims of functional equivalence do not remove a work from the scope of the PolyForm Noncommercial License 1.0.0. Any such implementation remains subject to the same license terms. 6.a Code Size Irrelevance (No Minimum Threshold) For the avoidance of doubt, applicability of the PolyForm Noncommercial License 1.0.0 is independent of code size, number of lines, percentage of implementation, degree of literal similarity, or partial extraction. There is no minimum threshold of code volume required for a work to fall within the scope of this license. Any use, reproduction, reimplementation, refactoring, selective reuse, architectural translation, or functional incorporation of the disclosed concepts—regardless of size or extent—is subject to the terms of the PolyForm Noncommercial License 1.0.0. 7. Knowledge Contamination and Attribution Exposure to this work constitutes prior knowledge of the disclosed techniques. Subsequent implementations making material use of the described concepts remain subject to attribution and license requirements as defined by the PolyForm Noncommercial License 1.0.0. 8. Intellectual Property Ownership Nothing in this document shall be construed as transferring ownership of intellectual property. All intellectual property rights remain with the author(s), subject only to the permissions explicitly granted under the PolyForm Noncommercial License 1.0.0. 9. No Additional Rights Granted This document does not grant any rights beyond those expressly provided by the PolyForm Noncommercial License 1.0.0. In the event of any conflict, the terms of the PolyForm Noncommercial License 1.0.0 shall prevail. 10. Enforcement and Remedies Any use of the methods described in this work in violation of the PolyForm Noncommercial License 1.0.0 may be addressed through remedies available under applicable international law. Nothing in this disclosure prevents the author(s), or third parties acting on their behalf, from performing technical analysis or reverse engineering of deployed systems for the purpose of determining whether the disclosed methods have been implemented following the publication date of this work. 11. Versioning This record may contain multiple versions. Updates to presentation, terminology, benchmarks, or documentation do not alter: the core methodological contributions the scope of protection the license terms The most recent license and scope documents in the repository are authoritative. 12. Knowledge Contamination Any individual or entity that has reviewed, studied, tested, or otherwise been exposed to the materials contained in this record shall be considered knowledge-contaminated with respect to the disclosed concepts. Subsequent development of substantially similar implementations may therefore be evaluated in light of this prior exposure and the timestamped archival record of this publication. AuthorAndrés Sebastián Pirolo ORCID 0009-0004-3899-1222 andrespirolo@gmail.com Legal and External Affairs📧 brisademar96@gmail.com
Boson sampling, a specific quantum computation problem, is widely regarded to be one of the most achievable fields in which quantum machine will outperform the most powerful classical computer in the near term, although up to now no upper-bound of how fast the classical computers can compute matrix permanents, core problem of Boson sampling, has been reported. Here we test the computing of the matrix permanent on Tianhe-2, a supercomputer retaining its position as the world's No. 1 system for six times since June 2013. We arrived at the time (about 77.41~112.44 minutes) to compute the permanent of a 50×5050\times 5050×50 matrix in an acceptable precision. In addition, we have found that Ryser's algorithm will produce an unacceptable error with the increase of problem scale, compared to Balasubramanian-Bax/Franklin-Glynn's algorithm in the same complexity. The precision issue suggests carefully check in future research of Boson sampling, and comprehensive comparison between quantum computer and classical computer.
Boson sampling, thought to be intractable classically, can be solved by a quantum machine composed of merely generation, linear evolution and detection of single photons. Such an analog quantum computer for this specific problem provides a shortcut to boost the absolute computing power of quantum computers to beat classical ones. However, the capacity bound of classical computers for simulating boson sampling has not yet been identified. Here we simulate boson sampling on the Tianhe-2 supercomputer, which occupied the first place in the world ranking six times from 2013 to 2016. We computed the permanent of the largest matrix using up to 312 000 CPU cores of Tianhe-2, and inferred from the current most efficient permanent-computing algorithms that an upper bound on the performance of Tianhe-2 is one 50-photon sample per ∼100 min. In addition, we found a precision issue with one of two permanent-computing algorithms.
If classical algorithms have been successful in reproducing the estimation of expectation values of observables of some quantum circuits using off-the-shelf computing resources, matching the performance of the most advanced quantum devices on sampling problems usually requires extreme cost in terms of memory and computing operations, making them accessible to only a handful of supercomputers around the world. In this work, we demonstrate for the first time a classical simulation outperforming Gaussian boson sampling experiments of one hundred modes on established benchmark tests using a single CPU or GPU. Being embarrassingly parallelizable, a small number of CPUs or GPUs allows us to match previous sampling rates that required more than one hundred GPUs. We believe algorithmic and implementation improvements will generalize our tools to photo-counting, single-photon inputs, and pseudo-photon-number-resolving scenarios beyond one thousand modes. Finally, most of the innovations in our tools remain valid for generic probability distributions over binary variables, rendering it potentially applicable to the simulation of qubit-based sampling problems and creating classical surrogates for classical-quantum algorithms.
In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task. Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth. The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version. As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.