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

Classical Boson Sampling Simulation via Parallel Glynn-Gray Complex Permanent

Andrés Sebastián Pirolo

Published Mar 13, 2026• 0 citations
Publisher

Abstract

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

DOI
10.5281/zenodo.18993830

Related papers

High performance Boson sampling simulation via data-flow engines

Gregory Morse, Tomasz Rybotycki, Ágoston Kaposi +7 more

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.

arXiv:2309.07027•New Journal of Physics•Mar 1, 2024•3 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•21 citations

The race for quantum supremacy: pushing the classical limit for photonic hardware

Nicolò Spagnolo, Fabio Sciarrino

The strong efforts towards the realization of scalable quantum computing are motivated by the promise of super-polynomial speed-up in several computational tasks. A first fundamental step in this route is to provide concrete evidence of ‘quantum supremacy'. Such a regime is obtained when a quantum device is capable of solving a specific problem faster than the best classical hardware. A serious attempt to provide a first demonstration of quantum speed-up with affordable resources is represented by boson sampling [1,2], a non-universal quantum-computational protocol exploiting indistinguishable single photons and linear optical devices. In this context, strong theoretical evidence has been reported that the interference pattern generated by a boson sampler is hard to simulate with classical resources, this pattern being related to the calculation of a hard-to-compute quantity known as a matrix permanent. Formal achievement of the regime of quantum supremacy will answer two very relevant questions: Are we able to benefit from the power of quantum mechanics or does there exist a fundamental reason why this achievement is forbidden? Once this regime has been achieved, are we able to certify the correct functioning of the quantum boson samplers or do we face an undecidability problem? Starting from these intriguing and promising theoretical results, an experimental race kicked off with the aim of reaching the quantum supremacy regime with boson sampling by employing a photonic platform [3]. A large amount of effort has been devoted to pushing the limits of current photonic systems [1], in order to significantly increase the size (number of photons and optical modes) that can be handled with a quantum device. In parallel to this quest for improved quantum performance, it is fundamental to benchmark the limits of a classical simulation of boson sampling. More specifically, in the race for quantum supremacy, what is the best possible classical simulation that can be performed? Such an analysis would be necessary to define the computational capacity possessed by such a classical agent to perform the task (see Fig. 1). In the race for quantum supremacy, a user who employs the best classical hardware and software, and a second agent who exploits a quantum device compete to solve the boson sampling task faster. In a recent article, Wu et al. [4] have provided a fundamental step to define and push the limits of a classical simulation of boson sampling. The authors have employed Tianhe-2, one of the world's most powerful super-computers, to perform such a task. More specifically, by using such high-performance computing hardware and by employing the fastest algorithm to date, Wu et al. have shown that calculating the permanent of a |$50 \times 50$| matrix can be performed in 100 min. Recent results [5] have shown that this computation corresponds to the classical hardness of drawing a 50-photon sample from a boson sampling distribution. The strong computational capacity of Tianhe-2 also allowed us to address the precision that the known fastest classical algorithms can reach in such a large-scale calculation. This latter aspect is indeed of fundamental importance, since any reliable classical computation must be accompanied by an appropriate error analysis. The study reported in Ref. [4] represents by far the largest calculation to date related to the classical simulation of boson sampling, whose relevance can be found in two different but related aspects. First, it raises the bar for any quantum implementation aimed at reaching quantum advantage, and provides a fundamental benchmark to which any photonic hardware must compare. This result suggests that a larger effort must be dedicated to pushing quantum technologies in this direction. Second, improved classical simulation also has important consequences in the context of boson sampling certification, i.e. the verification that a quantum device is correctly performing the required task. Indeed, first validation procedures in the quantum advantage regime must be assisted by powerful classical computational resources that, while requiring longer processing time than quantum hardware, will necessarily have to perform complex calculations.

National Science Review•Nov 6, 2018•11 citations

The Classical Complexity of Boson Sampling

Peter Clifford, Raphaël Clifford A

We study the classical complexity of the exact Boson Sampling problem where the objective is to produce provably correct random samples from a particular quantum mechanical distribution. The computational framework was proposed in STOC ’11 by Aaronson and Arkhipov in 2011 as an attainable demonstration of ‘quantum supremacy’, that is a practical quantum computing experiment able to produce output at a speed beyond the reach of classical (that is non-quantum) computer hardware. Since its introduction Boson Sampling has been the subject of intense international research in the world of quantum computing. On the face of it, the problem is challenging for classical computation. Aaronson and Arkhipov show that exact Boson Sampling is not efficiently solvable by a classical computer unless P#P = BPPNP and the polynomial hierarchy collapses to the third level. The fastest known exact classical algorithm for the standard Boson Sampling problem requires time to produce samples for a system with input size n and m output modes, making it infeasible for anything but the smallest values of n and m. We give an algorithm that is much faster, running in time and additional space. The algorithm is simple to implement and has low constant factor overheads. As a consequence our classical algorithm is able to solve the exact Boson Sampling problem for system sizes far beyond current photonic quantum computing experimentation, thereby significantly reducing the likelihood of achieving near-term quantum supremacy in the context of Boson Sampling.

arXiv:1706.01260•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•26 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•0 citations

Faster classical boson sampling

Peter Clifford, Raphaël Clifford A

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•21 citations
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
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.
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.
The strong efforts towards the realization of scalable quantum computing are motivated by the promise of super-polynomial speed-up in several computational tasks. A first fundamental step in this route is to provide concrete evidence of ‘quantum supremacy'. Such a regime is obtained when a quantum device is capable of solving a specific problem faster than the best classical hardware. A serious attempt to provide a first demonstration of quantum speed-up with affordable resources is represented by boson sampling [1,2], a non-universal quantum-computational protocol exploiting indistinguishable single photons and linear optical devices. In this context, strong theoretical evidence has been reported that the interference pattern generated by a boson sampler is hard to simulate with classical resources, this pattern being related to the calculation of a hard-to-compute quantity known as a matrix permanent. Formal achievement of the regime of quantum supremacy will answer two very relevant questions: Are we able to benefit from the power of quantum mechanics or does there exist a fundamental reason why this achievement is forbidden? Once this regime has been achieved, are we able to certify the correct functioning of the quantum boson samplers or do we face an undecidability problem? Starting from these intriguing and promising theoretical results, an experimental race kicked off with the aim of reaching the quantum supremacy regime with boson sampling by employing a photonic platform [3]. A large amount of effort has been devoted to pushing the limits of current photonic systems [1], in order to significantly increase the size (number of photons and optical modes) that can be handled with a quantum device. In parallel to this quest for improved quantum performance, it is fundamental to benchmark the limits of a classical simulation of boson sampling. More specifically, in the race for quantum supremacy, what is the best possible classical simulation that can be performed? Such an analysis would be necessary to define the computational capacity possessed by such a classical agent to perform the task (see Fig. 1). In the race for quantum supremacy, a user who employs the best classical hardware and software, and a second agent who exploits a quantum device compete to solve the boson sampling task faster. In a recent article, Wu et al. [4] have provided a fundamental step to define and push the limits of a classical simulation of boson sampling. The authors have employed Tianhe-2, one of the world's most powerful super-computers, to perform such a task. More specifically, by using such high-performance computing hardware and by employing the fastest algorithm to date, Wu et al. have shown that calculating the permanent of a |50×5050 \times 5050×50| matrix can be performed in 100 min. Recent results [5] have shown that this computation corresponds to the classical hardness of drawing a 50-photon sample from a boson sampling distribution. The strong computational capacity of Tianhe-2 also allowed us to address the precision that the known fastest classical algorithms can reach in such a large-scale calculation. This latter aspect is indeed of fundamental importance, since any reliable classical computation must be accompanied by an appropriate error analysis. The study reported in Ref. [4] represents by far the largest calculation to date related to the classical simulation of boson sampling, whose relevance can be found in two different but related aspects. First, it raises the bar for any quantum implementation aimed at reaching quantum advantage, and provides a fundamental benchmark to which any photonic hardware must compare. This result suggests that a larger effort must be dedicated to pushing quantum technologies in this direction. Second, improved classical simulation also has important consequences in the context of boson sampling certification, i.e. the verification that a quantum device is correctly performing the required task. Indeed, first validation procedures in the quantum advantage regime must be assisted by powerful classical computational resources that, while requiring longer processing time than quantum hardware, will necessarily have to perform complex calculations.
We study the classical complexity of the exact Boson Sampling problem where the objective is to produce provably correct random samples from a particular quantum mechanical distribution. The computational framework was proposed in STOC ’11 by Aaronson and Arkhipov in 2011 as an attainable demonstration of ‘quantum supremacy’, that is a practical quantum computing experiment able to produce output at a speed beyond the reach of classical (that is non-quantum) computer hardware. Since its introduction Boson Sampling has been the subject of intense international research in the world of quantum computing. On the face of it, the problem is challenging for classical computation. Aaronson and Arkhipov show that exact Boson Sampling is not efficiently solvable by a classical computer unless P#P = BPPNP and the polynomial hierarchy collapses to the third level. The fastest known exact classical algorithm for the standard Boson Sampling problem requires time to produce samples for a system with input size n and m output modes, making it infeasible for anything but the smallest values of n and m. We give an algorithm that is much faster, running in time and additional space. The algorithm is simple to implement and has low constant factor overheads. As a consequence our classical algorithm is able to solve the exact Boson Sampling problem for system sizes far beyond current photonic quantum computing experimentation, thereby significantly reducing the likelihood of achieving near-term quantum supremacy in the context of Boson Sampling.
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.
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.