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:1606.05836 · National Science Review

A benchmark test of boson sampling on Tianhe-2 supercomputer

Junjie Wu, Yong Liu, Baida Zhang, Xianmin Jin, Yang Wang, Huiquan Wang, Xuejun Yang

Published Jul 24, 2018• 61 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1093/nsr/nwy079

Related papers

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•5 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

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

Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight

Yuxuan Li, Lin Gan, Ming-Cheng Chen +6 more

Boson sampling is expected to be an important milestone that will demonstrate quantum computational advantage (or quantum supremacy). This work establishes the benchmarking of Gaussian boson sampling (GBS) with threshold detection based on the Sunway TaihuLight supercomputer. To achieve the best performance and provide a competitive scenario for future quantum computing studies, the selected simulation algorithm is fully optimized based on a set of innovative approaches, including a parallel framework with almost perfect load balance and an instruction-level optimizing scheme based on a shortest-path-based instruction scheduling. In addition, data precision is carefully processed by an integer-instruction-based and multiple-precision fixed-point implementation, including 128- and 256-bit precison mode, which can be appropriately selected based on an adaptive precision optimizing scheme. Based on these methods, a highly efficient parallel quantum sampling algorithm is designed. The largest run enables us to obtain one Torontonian function of a$100\times 100$submatrix from 50-photon GBS within 20 hours in 128-bit precision and 2 days in 256-bit precision. To our knowledge, this was the largest quantum computing simulation based on Boson Sampling by using modern supercomputers.

arXiv:2009.01177•IEEE Transactions on Parallel and Distributed Systems•Sep 9, 2021•19 citations

Gaussian boson sampling: Benchmarking quantum advantage

Ned Goodman, Alexander S. Dellios, Margaret D. Reid +1 more

Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.

quant-pharXiv:2604.12330•Apr 15, 2026•0 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
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.
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.
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.
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.
Boson sampling is expected to be an important milestone that will demonstrate quantum computational advantage (or quantum supremacy). This work establishes the benchmarking of Gaussian boson sampling (GBS) with threshold detection based on the Sunway TaihuLight supercomputer. To achieve the best performance and provide a competitive scenario for future quantum computing studies, the selected simulation algorithm is fully optimized based on a set of innovative approaches, including a parallel framework with almost perfect load balance and an instruction-level optimizing scheme based on a shortest-path-based instruction scheduling. In addition, data precision is carefully processed by an integer-instruction-based and multiple-precision fixed-point implementation, including 128- and 256-bit precison mode, which can be appropriately selected based on an adaptive precision optimizing scheme. Based on these methods, a highly efficient parallel quantum sampling algorithm is designed. The largest run enables us to obtain one Torontonian function of a100×100100\times 100100×100submatrix from 50-photon GBS within 20 hours in 128-bit precision and 2 days in 256-bit precision. To our knowledge, this was the largest quantum computing simulation based on Boson Sampling by using modern supercomputers.
Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.
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.