Sufficient conditions for hardness of lossy Gaussian boson sampling

• URL: http://arxiv.org/abs/2511.07853v1
• Date: Wed, 12 Nov 2025 01:24:07 GMT
• Title: Sufficient conditions for hardness of lossy Gaussian boson sampling
• Authors: Byeongseon Go, Changhun Oh, Hyunseok Jeong,
• Abstract summary: Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage.<n>We establish the complexity-theoretic foundations for the classical intractability of noisy GBS under photon loss.<n>This work presents the first rigorous characterization of classically intractable regimes of lossy GBS.
• Score: 0.49764328892172127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection [16.336658164004657]
  We investigate whether Gaussian Boson Sampling (GBS) can provide a computational advantage for solving the planted biclique problem.<n>This is a graph problem widely believed to be classically hard when the planted structure is small.<n>We show that when the planted biclique size falls within the conjectured hard regime, the natural fluctuations in node weights dominate the bias signal.
  arXiv  Detail & Related papers  (2025-10-14T17:51:31Z)
• Extended validations on photon number resolving detector based Gaussian boson sampling with low noises [9.951451779672698]
  We extend the pattern recognition validation, together with the correlation approach as a comparison, on GBS.<n>Our simulation indicates that the pattern recognition protocol is robust on noise evaluations of GBS even when noises are sufficiently low.
  arXiv  Detail & Related papers  (2025-10-07T14:42:05Z)
• Bayesian Quantum Amplitude Estimation [46.03321798937855]
  We present BAE, a problem-tailored and noise-aware Bayesian algorithm for quantum amplitude estimation.<n>In a fault tolerant scenario, BAE is capable of saturating the Heisenberg limit; if device noise is present, BAE can dynamically characterize it and self-adapt.<n>We propose a benchmark for amplitude estimation algorithms and use it to test BAE against other approaches.
  arXiv  Detail & Related papers  (2024-12-05T18:09:41Z)
• Heisenberg-Limited Quantum Lidar for Joint Range and Velocity Estimation [0.40964539027092906]
  We propose a quantum lidar protocol to jointly estimate the range and velocity of a target by illuminating it with a single beam of pulsed displaced squeezed light.<n>We show that the mean-squared errors of both range and velocity estimations are inversely proportional to the squared number of signal photons, simultaneously attaining the Heisenberg limit.
  arXiv  Detail & Related papers  (2023-11-24T15:29:03Z)
• Gaussian boson sampling at finite temperature [4.437382576172235]
  We investigate how thermal noise affects the classical intractability of generic quantum optical sampling experiments. We show that there exist a threshold temperature at which any quantum sampling experiment becomes classically simulable.
  arXiv  Detail & Related papers  (2023-08-25T10:33:06Z)
• Gaussian-boson-sampling-enhanced dense subgraph finding shows limited advantage over efficient classical algorithms [0.0]
  We investigate the effects of sources of error including loss and spectral impurity on GBS applied to dense subgraph finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to errors, to such an extent that there exist efficient classical algorithms that can simulate the underlying GBS.
  arXiv  Detail & Related papers  (2023-01-30T19:00:03Z)
• Protecting the quantum interference of cat states by phase-space compression [45.82374977939355]
  Cat states with their unique phase-space interference properties are ideal candidates for understanding quantum mechanics. They are highly susceptible to photon loss, which inevitably diminishes their quantum non-Gaussian features. Here, we protect these non-Gaussian features by compressing the phase-space distribution of a cat state.
  arXiv  Detail & Related papers  (2022-12-02T16:06:40Z)
• Suppressing Amplitude Damping in Trapped Ions: Discrete Weak Measurements for a Non-unitary Probabilistic Noise Filter [62.997667081978825]
  We introduce a low-overhead protocol to reverse this degradation. We present two trapped-ion schemes for the implementation of a non-unitary probabilistic filter against amplitude damping noise. This filter can be understood as a protocol for single-copy quasi-distillation.
  arXiv  Detail & Related papers  (2022-09-06T18:18:41Z)
• High-Order Qubit Dephasing at Sweet Spots by Non-Gaussian Fluctuators: Symmetry Breaking and Floquet Protection [55.41644538483948]
  We study the qubit dephasing caused by the non-Gaussian fluctuators. We predict a symmetry-breaking effect that is unique to the non-Gaussian noise.
  arXiv  Detail & Related papers  (2022-06-06T18:02:38Z)
• Enhanced nonlinear quantum metrology with weakly coupled solitons and particle losses [58.720142291102135]
  We offer an interferometric procedure for phase parameters estimation at the Heisenberg (up to 1/N) and super-Heisenberg scaling levels. The heart of our setup is the novel soliton Josephson Junction (SJJ) system providing the formation of the quantum probe. We illustrate that such states are close to the optimal ones even with moderate losses.
  arXiv  Detail & Related papers  (2021-08-07T09:29:23Z)
• Conditional preparation of non-Gaussian quantum optical states by mesoscopic measurement [62.997667081978825]
  Non-Gaussian states of an optical field are important as a proposed resource in quantum information applications. We propose a novel approach involving displacement of the ancilla field into the regime where mesoscopic detectors can be used. We conclude that states with strong Wigner negativity can be prepared at high rates by this technique under experimentally attainable conditions.
  arXiv  Detail & Related papers  (2021-03-29T16:59:18Z)
• Experimental certification of nonclassicality via phase-space inequalities [58.720142291102135]
  We present the first experimental implementation of the recently introduced phase-space inequalities for nonclassicality certification. We demonstrate the practicality and sensitivity of this approach by studying nonclassicality of a family of noisy and lossy quantum states of light.
  arXiv  Detail & Related papers  (2020-10-01T09:03:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.