Classical algorithm for simulating experimental Gaussian boson sampling

• URL: http://arxiv.org/abs/2306.03709v2
• Date: Mon, 4 Dec 2023 20:42:40 GMT
• Title: Classical algorithm for simulating experimental Gaussian boson sampling
• Authors: Changhun Oh, Minzhao Liu, Yuri Alexeev, Bill Fefferman, Liang Jiang
• Abstract summary: Gaussian boson sampling is a promising candidate for showing experimental quantum advantage. Despite a high photon loss rate and the presence of noise, they are currently claimed to be hard to classically simulate with the best-known classical algorithm. We present a classical tensor-network algorithm that simulates Gaussian boson sampling and whose complexity can be significantly reduced when the photon loss rate is high.
• Score: 2.1684911254068906
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gaussian boson sampling is a promising candidate for showing experimental quantum advantage. While there is evidence that noiseless Gaussian boson sampling is hard to efficiently simulate using a classical computer, the current Gaussian boson sampling experiments inevitably suffer from loss and other noise models. Despite a high photon loss rate and the presence of noise, they are currently claimed to be hard to classically simulate with the best-known classical algorithm. In this work, we present a classical tensor-network algorithm that simulates Gaussian boson sampling and whose complexity can be significantly reduced when the photon loss rate is high. By generalizing the existing thermal-state approximation algorithm of lossy Gaussian boson sampling, the proposed algorithm allows us to achieve increased accuracy as the running time of the algorithm scales, as opposed to the algorithm that samples from the thermal state, which can give only a fixed accuracy. This generalization enables us to simulate the largest scale Gaussian boson sampling experiment so far using relatively modest computational resources, even though the output state of these experiments is not believed to be close to a thermal state. By demonstrating that our new classical algorithm outperforms the large-scale experiments on the benchmarks used as evidence for quantum advantage, we exhibit evidence that our classical sampler can simulate the ground-truth distribution better than the experiment can, which disputes the experimental quantum advantage claims.

Related papers

• Variational Tensor Network Simulation of Gaussian Boson Sampling and Beyond [0.0]
  We propose a classical simulation tool for general continuous variable sampling problems. We reformulate the sampling problem as that of finding the ground state of a simple few-body Hamiltonian. We validate our method by simulating Gaussian Boson Sampling, where we achieve results comparable to the state of the art.
  arXiv  Detail & Related papers  (2024-10-24T13:43:06Z)
• 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. Noise in experimental implementations poses a significant challenge, potentially rendering boson sampling classically simulable and compromising its classical intractability. 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)
• Classical modelling of a lossy Gaussian bosonic sampler [0.0]
  We propose an algorithm for approximate classical simulation of a lossy GBS instance. The complexity of the algorithm is squeezing the number of modes given the number of terms is fixed. In recent experiments that claim to have demonstrated quantum advantage, these conditions are satisfied.
  arXiv  Detail & Related papers  (2024-04-01T09:19:27Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling [2.5496329090462626]
  We present a quantum-inspired classical algorithm that can be used for graph-theoretical problems. A given graph's adjacency matrix to be encoded in a Gaussian boson sampler is nonnegative, which does not necessitate quantum interference.
  arXiv  Detail & Related papers  (2023-02-01T16:02:31Z)
• On classical simulation algorithms for noisy Boson Sampling [2.8655318786364408]
  We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai Kindler.
  arXiv  Detail & Related papers  (2023-01-27T04:42:59Z)
• 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)
• The Boundary for Quantum Advantage in Gaussian Boson Sampling [44.62475518267084]
  State-of-the-art quantum photonics experiments would require 600 million years to simulate using the best pre-existing classical algorithms. We present substantially faster classical GBS simulation methods, including speed and accuracy improvements. This reduces the run-time of simulating state-of-the-art GBS experiments to several months -- a nine orders of magnitude improvement over previous estimates.
  arXiv  Detail & Related papers  (2021-08-03T16:49:40Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)
• Gaussianization Flows [113.79542218282282]
  We propose a new type of normalizing flow model that enables both efficient iteration of likelihoods and efficient inversion for sample generation. Because of this guaranteed expressivity, they can capture multimodal target distributions without compromising the efficiency of sample generation.
  arXiv  Detail & Related papers  (2020-03-04T08:15:06Z)

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.