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
- Simulating lossy and partially distinguishable quantum optical circuits: theory, algorithms and applications to experiment validation and state preparation [0.0]
We prove that computation of photon number distributions can be done in exponential time, providing a speedup.
Results offer significant speed-up and accuracy improvements to validation tests of both Fock and Gaussian boson samplers.
They pave the way to a more efficient simulation of realistic photonic circuits.
arXiv Detail & Related papers (2024-12-23T17:45:37Z) - The quantum magic of fermionic Gaussian states [0.0]
We introduce an efficient method to quantify nonstabilizerness in fermionic Gaussian states.
We reveal an extensive leading behavior equal to that of Haar random states, with logarithmic subleading corrections.
Applying the sampling algorithm to a two-dimensional free-fermionic topological model, we uncover a sharp transition in magic at the phase boundaries.
arXiv Detail & Related papers (2024-12-06T19:00:16Z) - Unitary-transformed projective squeezing: applications for circuit-knitting and state-preparation of non-Gaussian states [0.15833270109954137]
Continuous-variable (CV) quantum computing is a promising candidate for quantum computation.
This work extends the projective squeezing method to establish a formalism for projecting quantum states onto the states that are unitary-transformed from the squeezed vacuum.
arXiv Detail & Related papers (2024-11-29T06:53:47Z) - 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) - 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) - 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) - 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) - Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
Community detection in graphs that are generated according to symmetric block models (SBMs) has received much attention lately.
We show that in the logarithmic sparsity regime of the problem, with high probability the proposed two-stage method can exactly recover the two communities down to the information-theoretic limit in $mathcalO(nlog2n/loglog n)$ time.
We also conduct numerical experiments on both synthetic and real data sets to demonstrate the efficacy of our proposed method and complement our theoretical development.
arXiv Detail & Related papers (2020-06-29T07:03:27Z) - 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.