Complexity-theoretic foundations of BosonSampling with a linear number of modes

• URL: http://arxiv.org/abs/2312.00286v1
• Date: Fri, 1 Dec 2023 02:03:09 GMT
• Title: Complexity-theoretic foundations of BosonSampling with a linear number of modes
• Authors: Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, Michal Oszmaniec
• Abstract summary: BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. This paper brings the hardness evidence for the low-mode experiments to the same level as had been previously established for the high-mode regime.
• Score: 2.128045365872403
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of photons to modes: all current hardness evidence assumes a "high-mode" regime in which the number of linear optical modes scales at least quadratically in the number of photons. By contrast, current experiments operate in a "low-mode" regime with a linear number of modes. In this paper we bridge this gap, bringing the hardness evidence for the low-mode experiments to the same level as had been previously established for the high-mode regime. This involves proving a new worst-to-average-case reduction for computing the Permanent that is robust to large numbers of row repetitions and also to distributions over matrices with correlated entries.

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)
• Parallel simulation for sampling under isoperimetry and score-based diffusion models [56.39904484784127]
  As data size grows, reducing the iteration cost becomes an important goal. Inspired by the success of the parallel simulation of the initial value problem in scientific computation, we propose parallel Picard methods for sampling tasks. Our work highlights the potential advantages of simulation methods in scientific computation for dynamics-based sampling and diffusion models.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• Crosstalk-Robust Quantum Control in Multimode Bosonic Systems [34.03303487556571]
  High-coherence superconducting cavities offer a hardware-efficient platform for quantum information processing. To achieve universal operations of bosonic modes, the requisite nonlinearity is realized by coupling them to a transmon ancilla. We employ quantum optimal control to engineer ancilla pulses that are robust to the frequency shifts.
  arXiv  Detail & Related papers  (2024-03-01T04:33:12Z)
• Simultaneous measurement of multimode squeezing [1.2349871196144497]
  Multimode squeezed light is an increasingly popular tool in photonic quantum technologies. Here, we demonstrate experimentally how the squeezing can be measured in multiple spatial modes simultaneously. We obtain highest squeezing and anti-squeezing values of $-5.2 pm 0.2$ dB and $8.6 pm 0.3$ dB, respectively.
  arXiv  Detail & Related papers  (2024-02-24T11:01:49Z)
• Iterated Denoising Energy Matching for Sampling from Boltzmann Densities [109.23137009609519]
  Iterated Denoising Energy Matching (iDEM) iDEM alternates between (I) sampling regions of high model density from a diffusion-based sampler and (II) using these samples in our matching objective. We show that the proposed approach achieves state-of-the-art performance on all metrics and trains $2-5times$ faster.
  arXiv  Detail & Related papers  (2024-02-09T01:11:23Z)
• 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)
• Multimode physics of the unimon circuit [0.0]
  We consider a superconducting half-wavelength resonator that is grounded at its both ends and contains a single Josephson junction. Inspired by the promising first experimental results, we develop here a theoretical and numerical model for the detailed understanding of the multimode physics of the unimon circuit.
  arXiv  Detail & Related papers  (2023-09-18T12:54:29Z)
• A Geometric Perspective on Diffusion Models [57.27857591493788]
  We inspect the ODE-based sampling of a popular variance-exploding SDE. We establish a theoretical relationship between the optimal ODE-based sampling and the classic mean-shift (mode-seeking) algorithm.
  arXiv  Detail & Related papers  (2023-05-31T15:33:16Z)
• Collective Radiative Interactions in the Discrete Truncated Wigner Approximation [0.0]
  Superradiance of atomic arrays at sub-wavelength spacings has regained substantial interest. We develop a semiclassical approach to this problem that allows to describe the coherent and dissipative many-body dynamics of interacting spins. For small arrays we compare to exact simulations and a second order cumulant expansion. We conclude by studying the radiative properties of a spatially extended three-dimensional, coherently driven gas.
  arXiv  Detail & Related papers  (2023-05-31T13:11:32Z)
• 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)
• Quantum emulation of the transient dynamics in the multistate Landau-Zener model [50.591267188664666]
  We study the transient dynamics in the multistate Landau-Zener model as a function of the Landau-Zener velocity. Our experiments pave the way for more complex simulations with qubits coupled to an engineered bosonic mode spectrum.
  arXiv  Detail & Related papers  (2022-11-26T15:04:11Z)
• Improving Diffusion Models for Inverse Problems using Manifold Constraints [55.91148172752894]
  We show that current solvers throw the sample path off the data manifold, and hence the error accumulates. To address this, we propose an additional correction term inspired by the manifold constraint. We show that our method is superior to the previous methods both theoretically and empirically.
  arXiv  Detail & Related papers  (2022-06-02T09:06:10Z)
• Plug-&-play generation of non-Gaussian states of light at a telecom wavelength [48.7576911714538]
  This work marks an important progress towards practical quantum optical technologies in the continuous variable regime. Non-Gaussian state generation entirely relies on plug-&-play components from guided-wave optics technologies.
  arXiv  Detail & Related papers  (2022-05-31T11:08:08Z)
• Ultra-long photonic quantum walks via spin-orbit metasurfaces [52.77024349608834]
  We report ultra-long photonic quantum walks across several hundred optical modes, obtained by propagating a light beam through very few closely-stacked liquid-crystal metasurfaces. With this setup we engineer quantum walks up to 320 discrete steps, far beyond state-of-the-art experiments.
  arXiv  Detail & Related papers  (2022-03-28T19:37:08Z)
• A simple way to incorporate loss when modelling multimode entangled state generation [0.0]
  We show that the light generated via spontaneous four-wave mixing or parametric down conversion in multiple, coupled, lossy cavities is a multimode squeezed thermal state. Requiring this state to be the solution of the Lindblad master equation results in a set of coupled first-order differential equations.
  arXiv  Detail & Related papers  (2021-12-22T17:14:27Z)
• The Complexity of Bipartite Gaussian Boson Sampling [0.0]
  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.
  arXiv  Detail & Related papers  (2021-10-13T18:08:37Z)
• 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)
• Visualizing spinon Fermi surfaces with time-dependent spectroscopy [62.997667081978825]
  We propose applying time-dependent photo-emission spectroscopy, an established tool in solid state systems, in cold atom quantum simulators. We show in exact diagonalization simulations of the one-dimensional $t-J$ model that the spinons start to populate previously unoccupied states in an effective band structure. The dependence of the spectral function on the time after the pump pulse reveals collective interactions among spinons.
  arXiv  Detail & Related papers  (2021-05-27T18:00:02Z)
• One-photon Solutions to Multiqubit Multimode quantum Rabi model [5.602634858883526]
  We find a solution with at most one photon for arbitrary number of qubits and photon modes. This corresponds to a horizontal line in the spectrum, while still being a qubit-photon entangled state. As a possible application, we propose an adiabatic scheme for the fast generation of arbitrary single-photon multimode W states.
  arXiv  Detail & Related papers  (2021-02-22T15:57:54Z)

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.