Classical simulation of bosonic linear-optical random circuits beyond
linear light cone
- URL: http://arxiv.org/abs/2102.10083v2
- Date: Thu, 25 Aug 2022 21:40:12 GMT
- Title: Classical simulation of bosonic linear-optical random circuits beyond
linear light cone
- Authors: Changhun Oh, Youngrong Lim, Bill Fefferman, Liang Jiang
- Abstract summary: We examine classical simulability of sampling from the output photon-number distribution of linear-optical circuits.
We show that the algorithms' error is exponentially small up to a depth less than quadratic in the distance between sources.
- Score: 2.5496329090462626
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sampling from probability distributions of quantum circuits is a
fundamentally and practically important task which can be used to demonstrate
quantum supremacy using noisy intermediate-scale quantum devices. In the
present work, we examine classical simulability of sampling from the output
photon-number distribution of linear-optical circuits composed of random beam
splitters with equally distributed squeezed vacuum states and single-photon
states input. We provide efficient classical algorithms to simulate
linear-optical random circuits and show that the algorithms' error is
exponentially small up to a depth less than quadratic in the distance between
sources using a classical random walk behavior of random linear-optical
circuits. Notably, the average-case depth allowing an efficient classical
simulation is larger than the worst-case depth limit, which is linear in the
distance. Besides, our results together with the hardness of boson sampling
give a lower-bound on the depth for constituting global Haar-random unitary
circuits.
Related papers
- Classical simulability of constant-depth linear-optical circuits with noise [0.0]
Noise is one of the main obstacles to realizing quantum devices that achieve a quantum computational advantage.
In this work, we investigate the complexity of shallow-depth linear-optical circuits under the effects of photon loss and partial distinguishability.
arXiv Detail & Related papers (2024-06-12T11:08:57Z) - 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) - Approximating outcome probabilities of linear optical circuits [0.0]
We propose classical algorithms for approximating outcome probabilities of a linear optical circuit.
Our scheme renders an efficient estimation of outcome probabilities with precision depending on the classicality of the circuit.
Our study sheds light on the power of linear optics, providing plenty of quantum-inspired algorithms for problems in computational complexity.
arXiv Detail & Related papers (2022-11-14T08:21:51Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z) - Learnability of the output distributions of local quantum circuits [53.17490581210575]
We investigate, within two different oracle models, the learnability of quantum circuit Born machines.
We first show a negative result, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable.
We show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable.
arXiv Detail & Related papers (2021-10-11T18:00:20Z) - Classical simulation of boson sampling based on graph structure [2.5496329090462626]
We present classical sampling algorithms for single-photon and Gaussian input states that take advantage of a graph structure of a linear-optical circuit.
We show that when the circuit depth is less than the quadratic in the lattice spacing, the efficient simulation is possible with an exponentially small error.
We implement a likelihood test with a recent numerically Gaussian boson sampling experiment and show that the treewidth-based algorithm with a limited treewidth renders a larger likelihood than the experimental data.
arXiv Detail & Related papers (2021-10-04T17:02:35Z) - Rapid characterisation of linear-optical networks via PhaseLift [51.03305009278831]
Integrated photonics offers great phase-stability and can rely on the large scale manufacturability provided by the semiconductor industry.
New devices, based on such optical circuits, hold the promise of faster and energy-efficient computations in machine learning applications.
We present a novel technique to reconstruct the transfer matrix of linear optical networks.
arXiv Detail & Related papers (2020-10-01T16:04:22Z) - Efficient sampling from shallow Gaussian quantum-optical circuits with
local interactions [0.9786690381850354]
We prove that a classical computer can efficiently sample from the photon-number probability distribution of a Gaussian state prepared by using an optical circuit that is shallow and local.
Since sampling from deep optical circuits with exponential-scaling photon loss is classically simulable, our results pose a challenge to the feasibility of demonstrating quantum supremacy on photonic platforms with local interactions.
arXiv Detail & Related papers (2020-09-24T17:10:42Z) - 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.