The Complexity of Bipartite Gaussian Boson Sampling

• URL: http://arxiv.org/abs/2110.06964v3
• Date: Fri, 11 Nov 2022 21:06:33 GMT
• Title: The Complexity of Bipartite Gaussian Boson Sampling
• Authors: Daniel Grier, Daniel J. Brod, Juan Miguel Arrazola, Marcos Benicio de Andrade Alonso, Nicol\'as Quesada
• Abstract summary: We show that under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient algorithm to sample from ideal GBS unless the hierarchy collapses. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of reach for classical devices. There is therefore significant interest, from the perspective of computational complexity theory, in solidifying the mathematical foundation for the hardness of simulating these devices. We show that, under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from ideal Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof. Crucial to the proof is a new method for programming a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. This technique is a generalization of Scattershot BosonSampling that we call BipartiteGBS. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., the high-collision regime) by showing that the ability to approximate permanents of matrices with repeated rows/columns confers the ability to approximate permanents of matrices with no repetitions. The reduction suffices to prove that GBS is hard in the constant-collision regime.

Related papers

• Realistic photon-number resolution in Gaussian boson sampling [0.0]
  Gaussian boson sampling (GBS) is a model of nonuniversal quantum computation that claims to demonstrate quantum supremacy with current technologies. We derive a the photocounting probability distribution in GBS schemes which is applicable for use with general detectors and photocounting techniques.
  arXiv  Detail & Related papers  (2024-03-05T18:20:59Z)
• Photonic quantum signatures of chaos and boson sampling [0.0]
  In a typical boson sampling experiment, the scattering amplitude is determined by the permanent of a submatrix of a unitary drawn from an ensemble of random matrices. We show that the unitary dynamics of a Floquet system may be exploited to perform sampling tasks with identical particles using single-mode phase shifters and multiport beamsplitters.
  arXiv  Detail & Related papers  (2023-07-25T01:38:57Z)
• Randomized semi-quantum matrix processing [0.0]
  We present a hybrid quantum-classical framework for simulating generic matrix functions. The method is based on randomization over the Chebyshev approximation of the target function. We prove advantages on average depths, including quadratic speed-ups on costly parameters.
  arXiv  Detail & Related papers  (2023-07-21T18:00:28Z)
• Solving Graph Problems Using Gaussian Boson Sampling [22.516585968074146]
  We use a noisy intermediate-scale quantum computer to solve graph problems. We experimentally observe the presence of GBS enhancement with large photon-click number and an enhancement under certain noise. Our work is a step toward testing real-world problems using the existing intermediate-scale quantum computers.
  arXiv  Detail & Related papers  (2023-02-02T08:25:47Z)
• Simulating lossy Gaussian boson sampling with matrix product operators [7.33258560389563]
  We show that efficient tensor network simulations are likely possible under the $N_textoutproptosqrtN$ scaling of the number of surviving photons. We overcome previous challenges due to the large local space dimensions in Gaussian boson sampling with hardware acceleration.
  arXiv  Detail & Related papers  (2023-01-30T12:10:39Z)
• Experimental realization of deterministic and selective photon addition in a bosonic mode assisted by an ancillary qubit [50.591267188664666]
  Bosonic quantum error correcting codes are primarily designed to protect against single-photon loss. Error correction requires a recovery operation that maps the error states -- which have opposite parity -- back onto the code states. Here, we realize a collection of photon-number-selective, simultaneous photon addition operations on a bosonic mode.
  arXiv  Detail & Related papers  (2022-12-22T23:32:21Z)
• 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)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data. We show how one can disprove faked data, and apply this to a classical count algorithm.
  arXiv  Detail & Related papers  (2022-11-07T12:00:45Z)
• Bosonic field digitization for quantum computers [62.997667081978825]
  We address the representation of lattice bosonic fields in a discretized field amplitude basis. We develop methods to predict error scaling and present efficient qubit implementation strategies.
  arXiv  Detail & Related papers  (2021-08-24T15:30:04Z)
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light [32.20791352792308]
  We report a new GBS experiment that produces up to 113 detection events out of a 144-mode photonic circuit. We develop a new high-brightness and scalable quantum light source, exploring the idea of stimulated squeezed photons. The photonic quantum computer, Jiuzhang 2.0, yields a Hilbert space dimension up to $1043$, and a sampling rate $1024$ faster than using brute-force simulation.
  arXiv  Detail & Related papers  (2021-06-29T16:11:29Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

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.