arXiv:1905.12075 · Physical Review Letters

Regimes of Classical Simulability for Noisy Gaussian Boson Sampling

Haoyu Qi, Daniel J. Brod, Nicolás Quesada, Raúl García−Patrón

Published Mar 13, 2020• 87 citations

Abstract

As a promising candidate for exhibiting quantum computational supremacy, Gaussian boson sampling (GBS) is designed to exploit the ease of experimental preparation of Gaussian states. However, sufficiently large and inevitable experimental noise might render GBS classically simulable. In this work, we formalize this intuition by establishing a sufficient condition for approximate polynomial-time classical simulation of noisy GBS-in the form of an inequality between the input squeezing parameter, the overall transmission rate, and the quality of photon detectors. Our result serves as a nonclassicality test that must be passed by any quantum computational supremacy demonstration based on GBS. We show that, for most linear-optical architectures, where photon loss increases exponentially with the circuit depth, noisy GBS loses its quantum advantage in the asymptotic limit. Our results thus delineate intermediate-sized regimes where GBS devices might considerably outperform classical computers for modest noise levels. Finally, we find that increasing the amount of input squeezing is helpful to evade our classical simulation algorithm, which suggests a potential route to mitigate photon loss.

DOI: 10.1103/physrevlett.124.100502

Related papers

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.13291Physical Review AJan 12, 20243 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.07853Nov 12, 20250 citations

Quantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling

Abhinav Deshpande, Arthur Mehta, Trevor J. Vincent +10 more

Photonics is a promising platform for demonstrating quantum computational supremacy (QCS) by convincingly outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing photonics proposals and demonstrations face significant hurdles. Experimentally, current implementations of Gaussian boson sampling lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make significant progress in improving both the theoretical evidence and experimental prospects. On the theory side, we provide strong evidence for the hardness of Gaussian boson sampling, placing it on par with the strongest theoretical proposals for QCS. On the experimental side, we propose a new QCS architecture, high-dimensional Gaussian boson sampling, which is programmable and can be implemented with low loss rates using few optical components. We show that particular classical algorithms for simulating GBS are vastly outperformed by high-dimensional Gaussian boson sampling experiments at modest system sizes. This work thus opens the path to demonstrating QCS with programmable photonic processors.

Feb 24, 20216 citations

Noise thresholds for classical simulability of nonlinear boson sampling

Gabriele Bressanini, Hyukjoon Kwon, M. S. Kim

Boson sampling, a computational problem conjectured to be hard to simulate on a classical machine, is a promising candidate for an experimental demonstration of quantum advantage using bosons. However, inevitable experimental noise and imperfections, such as loss in the interferometer and random counts at the detectors, could challenge the sampling task from entering the regime where quantum advantage is achievable. In this work we introduce higher-order nonlinearities as a means to enhance the computational complexity of the problem and the protocol's robustness against noise, i.e., to increase the noise threshold that allows us to perform an efficient classical simulation of the problem. Using a phase-space method based on the negativity volume of the relevant quasiprobability distributions, we establish a necessary nonclassicality condition that any experimental proof of quantum advantage must satisfy. Our results indicate that the addition of single-mode Kerr nonlinearity at the input-state preparation level, while retaining a linear-optical evolution, makes the boson-sampling protocol more robust against noise and consequently relaxes the constraints on the noise parameters required to show quantum advantage.

arXiv:2202.12052Physical Review AOct 10, 20228 citations

Classical Modeling of a Lossy Gaussian Bosonic Sampler

Mikhail V. Umanskii, Alexey N. Rubtsov

Gaussian boson sampling (GBS) is considered a candidate problem for demonstrating quantum advantage. We propose an algorithm for the approximate classical simulation of a lossy GBS instance. The algorithm relies on the Taylor series expansion, and increasing the number of terms of the expansion that are used in the calculation yields greater accuracy. The complexity of the algorithm is polynomial in the number of modes given the number of terms is fixed. We describe conditions for the input state squeezing parameter and loss level that provide the best efficiency for this algorithm (by efficient, we mean that the Taylor series converges quickly). In recent experiments that claim to have demonstrated quantum advantage, these conditions are satisfied; thus, this algorithm can be used to classically simulate these experiments.

EntropyJun 5, 20240 citations

Gaussian boson sampling with partial distinguishability

Junheng Shi, Tim Byrnes

Gaussian boson sampling (GBS) allows for a way to demonstrate quantum supremacy with the relatively modest experimental resources of squeezed light sources, linear optics, and photon detection. In a realistic experimental setting, numerous effects can modify the complexity of the sampling, in particular loss, partial distinguishability of the photons, and the use of threshold detectors rather than photon counting detectors. In this paper, we investigate GBS with partial distinguishability using an approach based on virtual modes and indistinguishability efficiency. We develop a model using these concepts and derive the probabilities of measuring a specific output pattern from partially distinguishable and lossy GBS for both types of detectors. In the case of threshold detectors, the probability as calculated by the Torontonian is a special case under our framework. By analyzing the expressions of these probabilities we propose an efficient auxiliary classical simulation algorithm which can be used to calculate the probabilities. Our model and the auxiliary algorithm provide foundations for an approximation method for the probability calculation and simulation algorithms not only compatible with existing state-of-the-art simulation algorithms for ideal GBS but also reduce their complexities exponentially depending on the indistinguishability. Using the approximation method and the simulation algorithms we show how the boundary of quantum supremacy in GBS can be pushed further by partial distinguishability.

arXiv:2105.09583May 20, 20213 citations