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:2403.15339 · PRX Quantum

Linear Cross-Entropy Certification of Quantum Computational Advantage in Gaussian Boson Sampling

Javier Martínez-Cifuentes, Hubert de Guise, Nicolás Quesada

Published Oct 24, 2024• 8 citations
arXivHTMLPDF

Abstract

Validation of quantum advantage claims in the context of Gaussian boson sampling (GBS) currently relies on providing evidence that the experimental samples genuinely follow their corresponding ground truth, i.e., the theoretical model of the experiment that includes all the possible losses that the experimenters can account for. This approach to verification has an important drawback: it is necessary to assume that the ground truth distributions are computationally hard to sample, that is, that they are sufficiently close to the distribution of the ideal, lossless experiment, for which there is evidence that sampling, either exactly or approximately, is a computationally hard task. This assumption, which cannot be easily confirmed, opens the door to classical algorithms that exploit the noise in the ground truth to efficiently simulate the experiments, thus undermining any quantum advantage claim. In this work, we argue that one can avoid this issue by validating GBS implementations using their corresponding ideal distributions directly. We explain how to use a modified version of the linear cross-entropy, a quantity that we call the LXE score, to find reference values that help us assess how close a given GBS implementation is to its corresponding ideal model. Finally, we analytically compute the score that would be obtained by a lossless GBS implementation. Published by the American Physical Society 2024

DOI
10.1103/prxquantum.5.040312

Related papers

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

Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target

Alexander S. Dellios, Bogdan Opanchuk, Ned Goodman +2 more

Computational validation is vital for large-scale quantum computers. One needs computers that are both fast and accurate along with tests that encapsulate the complexity of such networks. Here, we utilize positive-P phase-space simulations of grouped count probabilities (GCPs) as a fingerprint for verifying multi-mode data from large Gaussian boson sampling (GBS) quantum computers that claim quantum computational advantage. Such simulations allow one to distinguish between true non-classical correlations generated by an experiment, and those obtained from a classical algorithm that replicates the photo-detection measurements. We use these methods to verify the outputs of a 144-channel GBS experiment, where we show data is far enough from the ideal ground truth distribution that it is beaten by a classical algorithm implemented using purely classical states, although it fails against a best-fit ground truth that includes decoherence. This gives evidence consistent with quantum computational advantage for a modified problem: a non-classical, partly thermalized ground truth model. Even with this model, discrepancies are present, indicating possible parameter estimation errors. Randomly generated tests from multiple high-order grouped counts are also performed. Each of these can be measured and simulated, providing a verification method that may be hard to replicate classically.

arXiv:2211.03480•Physics Letters A•Apr 10, 2025•6 citations

Quantum information processing: quantum advantage and information recovery

Gabriele Bressanini

Quantum computing holds the promise of enabling algorithms that are beyond the reach of classical computation, hence demonstrating quantum computational advantage. However, current quantum devices face significant limitations, primarily due to the lack of error correction. In this context, the following question arises: can quantum computational advantage be demonstrated with today's noisy hardware? Recently, Gaussian boson sampling (GBS) has emerged as a leading candidate to achieve this milestone, due to its relative experimental feasibility. The first part of this thesis focuses on two central challenges associated with GBS. The first one is the impact of noise on the computational complexity of the task. Using a phase-space approach, we establish a necessary non-classicality condition that any experimental proof of quantum advantage must satisfy, and demonstrate that there exists a threshold temperature at which quantum sampling experiments become classically simulable. We then investigate the possibility of introducing higher-order non-linearities as a mean to enhance the protocol’s robustness against noise. Then, we turn our attention to the problem of validating a GBS experiment, and propose the use binned-detector probability distributions as a suitable quantity to perform efficient statistical validation. In the second part of the thesis, we present a novel approach to protect a quantum observable from a given noise model.We start by introducing the concept of quantum observables over time, an operator that jointly describes two observables at two distinct time points, and use the latter to establish a notion of time-reversal for non-unitary quantum channels with respect to a reference observable, enabling the systematic construction of recovery maps that preserve the latter. These recovery maps, although generally non-physical, can still be used in noiseless expectation value estimation tasks and can achieve optimal performance in terms of sampling overhead, outperforming known error mitigation protocols.

•Jan 17, 2025•0 citations

Gaussian boson sampling at finite temperature

Gabriele Bressanini, Hyukjoon Kwon, M. S. Kim

Gaussian boson sampling (GBS) is a promising candidate for an experimental demonstration of quantum advantage using photons. However, sufficiently large noise might hinder a GBS implementation from entering the regime where quantum speedup is achievable. Here, we investigate how thermal noise affects the classical intractability of generic quantum optical sampling experiments, GBS being a particular instance of the latter. We do so by establishing sufficient conditions for an efficient simulation to be feasible, expressed in the form of inequalities between the relevant parameters that characterize the system and its imperfections. We demonstrate that the addition of thermal noise—modeled by (passive) linear optical interaction between the system and a Markovian thermal bath—has the effect of tightening the constraints on the remaining noise parameters, required to show quantum advantage. Furthermore, we show that there exists a threshold temperature, under the assumption of a uniform loss rate, at which quantum sampling experiments become classically simulable, and provide an intuitive physical interpretation by relating this occurrence with the disappearance of the quantum state's nonclassical properties. Published by the American Physical Society 2024

arXiv:2308.13291•Physical Review A•Jan 12, 2024•3 citations

Validation tests of Gaussian boson samplers with photon-number resolving detectors

Alexander S. Dellios, M. D. Reid, P. D. Drummond

Abstract An important challenge with the current generation of noisy, large-scale quantum computers is the question of validation. Does the hardware generate correct answers? If not, what are the errors? This issue is often combined with questions of computational advantage, but it is a fundamentally distinct issue. In current experiments, complete validation of the output statistics is generally not possible because it is exponentially hard to do so. Here, we apply phase-space simulation methods to partially verify recent experiments on Gaussian boson sampling (GBS) implementing photon-number resolving detectors. The positive-P phase-space distribution is employed, as it uses probabilistic sampling to reduce complexity. It is ∼ 10 18 times faster than direct classical simulation for experiments on 288 modes where quantum computational advantage is claimed. When combined with binning and marginalization to improve statistics, multiple validation tests are efficiently computable, of which some tests can be carried out on experimental data. We show that the data as a whole has discrepancies with theoretical predictions for perfect squeezing. However, a modification of the GBS parameters greatly improves agreement for some tests. We suggest that such validation tests could form the basis of feedback methods to improve GBS experiments.

arXiv:2411.11228•Quantum Science and Technology•Aug 21, 2025•2 citations

Sufficient conditions for hardness of lossy Gaussian boson sampling

Byeongseon Go, Changhun Oh, Hyunseok Jeong

Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage. However, while the current implementations of GBS are unavoidably subject to noise, the robustness of the classical intractability of GBS against noise remains largely unexplored. In this work, we establish the complexity-theoretic foundations for the classical intractability of noisy GBS under photon loss, which is a dominant source of imperfection in current implementations. We identify the loss threshold below which lossy GBS maintains the same complexity-theoretic level as ideal GBS, and show that this holds when at most a logarithmic fraction of photons is lost. We additionally derive an intractability criterion for the loss rate through a direct quantification of the statistical distance between ideal and lossy GBS. This work presents the first rigorous characterization of classically intractable regimes of lossy GBS, thereby serving as a crucial step toward demonstrating quantum advantage with near-term implementations.

quant-pharXiv:2511.07853•Nov 12, 2025•0 citations
Validation of quantum advantage claims in the context of Gaussian boson sampling (GBS) currently relies on providing evidence that the experimental samples genuinely follow their corresponding ground truth, i.e., the theoretical model of the experiment that includes all the possible losses that the experimenters can account for. This approach to verification has an important drawback: it is necessary to assume that the ground truth distributions are computationally hard to sample, that is, that they are sufficiently close to the distribution of the ideal, lossless experiment, for which there is evidence that sampling, either exactly or approximately, is a computationally hard task. This assumption, which cannot be easily confirmed, opens the door to classical algorithms that exploit the noise in the ground truth to efficiently simulate the experiments, thus undermining any quantum advantage claim. In this work, we argue that one can avoid this issue by validating GBS implementations using their corresponding ideal distributions directly. We explain how to use a modified version of the linear cross-entropy, a quantity that we call the LXE score, to find reference values that help us assess how close a given GBS implementation is to its corresponding ideal model. Finally, we analytically compute the score that would be obtained by a lossless GBS implementation. Published by the American Physical Society 2024
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.
Computational validation is vital for large-scale quantum computers. One needs computers that are both fast and accurate along with tests that encapsulate the complexity of such networks. Here, we utilize positive-P phase-space simulations of grouped count probabilities (GCPs) as a fingerprint for verifying multi-mode data from large Gaussian boson sampling (GBS) quantum computers that claim quantum computational advantage. Such simulations allow one to distinguish between true non-classical correlations generated by an experiment, and those obtained from a classical algorithm that replicates the photo-detection measurements. We use these methods to verify the outputs of a 144-channel GBS experiment, where we show data is far enough from the ideal ground truth distribution that it is beaten by a classical algorithm implemented using purely classical states, although it fails against a best-fit ground truth that includes decoherence. This gives evidence consistent with quantum computational advantage for a modified problem: a non-classical, partly thermalized ground truth model. Even with this model, discrepancies are present, indicating possible parameter estimation errors. Randomly generated tests from multiple high-order grouped counts are also performed. Each of these can be measured and simulated, providing a verification method that may be hard to replicate classically.
Quantum computing holds the promise of enabling algorithms that are beyond the reach of classical computation, hence demonstrating quantum computational advantage. However, current quantum devices face significant limitations, primarily due to the lack of error correction. In this context, the following question arises: can quantum computational advantage be demonstrated with today's noisy hardware? Recently, Gaussian boson sampling (GBS) has emerged as a leading candidate to achieve this milestone, due to its relative experimental feasibility. The first part of this thesis focuses on two central challenges associated with GBS. The first one is the impact of noise on the computational complexity of the task. Using a phase-space approach, we establish a necessary non-classicality condition that any experimental proof of quantum advantage must satisfy, and demonstrate that there exists a threshold temperature at which quantum sampling experiments become classically simulable. We then investigate the possibility of introducing higher-order non-linearities as a mean to enhance the protocol’s robustness against noise. Then, we turn our attention to the problem of validating a GBS experiment, and propose the use binned-detector probability distributions as a suitable quantity to perform efficient statistical validation. In the second part of the thesis, we present a novel approach to protect a quantum observable from a given noise model.We start by introducing the concept of quantum observables over time, an operator that jointly describes two observables at two distinct time points, and use the latter to establish a notion of time-reversal for non-unitary quantum channels with respect to a reference observable, enabling the systematic construction of recovery maps that preserve the latter. These recovery maps, although generally non-physical, can still be used in noiseless expectation value estimation tasks and can achieve optimal performance in terms of sampling overhead, outperforming known error mitigation protocols.
Gaussian boson sampling (GBS) is a promising candidate for an experimental demonstration of quantum advantage using photons. However, sufficiently large noise might hinder a GBS implementation from entering the regime where quantum speedup is achievable. Here, we investigate how thermal noise affects the classical intractability of generic quantum optical sampling experiments, GBS being a particular instance of the latter. We do so by establishing sufficient conditions for an efficient simulation to be feasible, expressed in the form of inequalities between the relevant parameters that characterize the system and its imperfections. We demonstrate that the addition of thermal noise—modeled by (passive) linear optical interaction between the system and a Markovian thermal bath—has the effect of tightening the constraints on the remaining noise parameters, required to show quantum advantage. Furthermore, we show that there exists a threshold temperature, under the assumption of a uniform loss rate, at which quantum sampling experiments become classically simulable, and provide an intuitive physical interpretation by relating this occurrence with the disappearance of the quantum state's nonclassical properties. Published by the American Physical Society 2024
Abstract An important challenge with the current generation of noisy, large-scale quantum computers is the question of validation. Does the hardware generate correct answers? If not, what are the errors? This issue is often combined with questions of computational advantage, but it is a fundamentally distinct issue. In current experiments, complete validation of the output statistics is generally not possible because it is exponentially hard to do so. Here, we apply phase-space simulation methods to partially verify recent experiments on Gaussian boson sampling (GBS) implementing photon-number resolving detectors. The positive-P phase-space distribution is employed, as it uses probabilistic sampling to reduce complexity. It is ∼ 10 18 times faster than direct classical simulation for experiments on 288 modes where quantum computational advantage is claimed. When combined with binning and marginalization to improve statistics, multiple validation tests are efficiently computable, of which some tests can be carried out on experimental data. We show that the data as a whole has discrepancies with theoretical predictions for perfect squeezing. However, a modification of the GBS parameters greatly improves agreement for some tests. We suggest that such validation tests could form the basis of feedback methods to improve GBS experiments.
Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage. However, while the current implementations of GBS are unavoidably subject to noise, the robustness of the classical intractability of GBS against noise remains largely unexplored. In this work, we establish the complexity-theoretic foundations for the classical intractability of noisy GBS under photon loss, which is a dominant source of imperfection in current implementations. We identify the loss threshold below which lossy GBS maintains the same complexity-theoretic level as ideal GBS, and show that this holds when at most a logarithmic fraction of photons is lost. We additionally derive an intractability criterion for the loss rate through a direct quantification of the statistical distance between ideal and lossy GBS. This work presents the first rigorous characterization of classically intractable regimes of lossy GBS, thereby serving as a crucial step toward demonstrating quantum advantage with near-term implementations.