Threshold and Parity BosonSampling in the Linear-Mode Regime

• URL: http://arxiv.org/abs/2608.24008v1
• Date: Tue, 25 Aug 2026 02:56:05 GMT
• Title: Threshold and Parity BosonSampling in the Linear-Mode Regime
• Abstract summary: We investigate the computational complexity of BosonSampling with threshold and parity measurements in the linear-mode regime.<n>In particular, we establish average-case #P-hardness of estimating typical output probabilities in threshold and parity BosonSampling.<n>The resulting imprecision bounds match those obtained in prior hardness results for standard photon-number-resolving BosonSampling.
• Score: 0.49764328892172127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: BosonSampling is among the most prominent candidates for demonstrating quantum advantage. However, while the hardness of BosonSampling relies on photon-number-resolving detection, many experimentally relevant settings and applications instead use binary readout based on threshold or parity measurements, whose computational complexity has not yet been rigorously characterized. In this work, we investigate the computational complexity of BosonSampling with threshold and parity measurements in the linear-mode regime, where the number of modes scales linearly with the number of photons and is most relevant to current experiments. In particular, we establish average-case #P-hardness of estimating typical output probabilities in threshold and parity BosonSampling, a crucial ingredient in proving the classical hardness of the corresponding sampling problems. The resulting imprecision bounds match those obtained in prior hardness results for standard photon-number-resolving BosonSampling in the linear-mode regime. The key technical ingredient is a Fourier-coefficient extraction method, induced by coherent beam-splitter rotations, that extracts hidden hard components within coarse-grained output probabilities. These results indicate that the hard output-probability structure of photon-number-resolving BosonSampling can persist under natural binary coarse-grainings, even in collision-dominant regimes.

Related papers

• The trainability of photonic quantum circuits [34.13373752364321]
  Variational quantum algorithms are a leading approach to near-term quantum computing, but their scalability can be limited by barren plateaus and the sampling cost of resolving small changes in the loss landscape.<n>Here, we study the trainability of passive linear-optical quantum circuits and introduce a framework based on the ratio of variance to circuit variance.<n>These results establish photonic variational quantum computing as a promising platform for near-term applications.
  arXiv  Detail & Related papers  (2026-07-23T17:31:09Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition.<n>We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Quantum computational advantage of noisy boson sampling with partially distinguishable photons [0.0]
  In this work, we identify the level of partial distinguishability noise that upholds the classical intractability of boson sampling.<n>We find that boson sampling with on average $O(log N)$ number of distinguishable photons out of $N$ input photons maintains the equivalent complexity to the ideal boson sampling case.
  arXiv  Detail & Related papers  (2025-01-23T07:37:29Z)
• Boundaries for quantum advantage with single photons and loop-based time-bin interferometers [37.28808413070634]
  Loop-based boson samplers interfere photons in the time degree of freedom using a sequence of delay lines.<n>We propose a method to exploit this loop-based structure to more efficiently classically sample from such systems.
  arXiv  Detail & Related papers  (2024-11-25T19:13:20Z)
• On computational complexity and average-case hardness of shallow-depth boson sampling [0.0]
  Boson sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage.<n>Noise in experimental implementations poses a significant challenge, potentially rendering boson sampling classically simulable and compromising its classical intractability.<n>We explore the viability of achieving quantum computational advantage through boson sampling with shallow-depth linear optical circuits.
  arXiv  Detail & Related papers  (2024-05-03T00:12:48Z)
• Transition of Anticoncentration in Gaussian Boson Sampling [0.0]
  We develop a graph-theoretic framework for analyzing the moments of the Gaussian Boson Sampling distribution. We show that when the number of initially squeezed modes scales sufficiently slowly with the number of photons, there is a lack of anticoncentration.
  arXiv  Detail & Related papers  (2023-12-13T19:00:00Z)
• Complexity-theoretic foundations of BosonSampling with a linear number of modes [2.0509187556246444]
  We bridge the gap between complexity-theoretic hardness arguments and current experiments.<n>We prove a new worst-to-average-case reduction for computing the Permanent.<n>We also apply similar arguments to give evidence for hardness of Gaussian BosonSampling in the saturated regime.
  arXiv  Detail & Related papers  (2023-12-01T02:03:09Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• A Novel Adaptive Causal Sampling Method for Physics-Informed Neural Networks [35.25394937917774]
  Informed Neural Networks (PINNs) have become a kind of attractive machine learning method for obtaining solutions of partial differential equations (PDEs) We introduce temporal causality into adaptive sampling and propose a novel adaptive causal sampling method to improve the performance and efficiency of PINs. We demonstrate that by utilizing such a relatively simple sampling method, prediction performance can be improved up to two orders of magnitude compared with state-of-the-art results.
  arXiv  Detail & Related papers  (2022-10-24T01:51:08Z)
• Testing randomness of series generated in Bell's experiment [62.997667081978825]
  We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle. Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent. The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
  arXiv  Detail & Related papers  (2022-08-31T17:39:29Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Universally Quantized Neural Compression [25.808505103655687]
  We show that a uniform noise channel can be implemented at test time using universal quantization. This allows us to eliminate the mismatch between training and test phases while maintaining a completely differentiable loss function.
  arXiv  Detail & Related papers  (2020-06-17T15:59:24Z)
• Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
  We propose an easy-to-use and general-purpose approach for fast posterior sampling. We demonstrate how decoupled sample paths accurately represent Gaussian process posteriors at a fraction of the usual cost.
  arXiv  Detail & Related papers  (2020-02-21T14:03:16Z)
• Boson Sampling with Gaussian input states: toward efficient scaling and certification [0.0]
  We present a practically achievable pathway to scale Boson Sampling experiments. We propose the combination of switchable dual-homodyne and single-photon detections, the temporal loop technique, and scattershot-based Boson Sampling.
  arXiv  Detail & Related papers  (2018-12-21T07:15:03Z)

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.