Classical modelling of a lossy Gaussian bosonic sampler
- URL: http://arxiv.org/abs/2404.01004v1
- Date: Mon, 1 Apr 2024 09:19:27 GMT
- Title: Classical modelling of a lossy Gaussian bosonic sampler
- Authors: M. V. Umanskii, A. N. Rubtsov,
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Gaussian boson sampling (GBS) is considered a candidate problem for demonstrating quantum advantage. We propose an algorithm for approximate classical simulation of a lossy GBS instance. The algorithm relies on the Taylor series expansion, and increasing the number of terms of the expansion that are used in the calculation yields greater accuracy. The complexity of the algorithm is polynomial in the number of modes given the number of terms is fixed. We describe conditions for the input state squeezing parameter and loss level that provide the best efficiency for this algorithm (by efficient we mean that the Taylor series converges quickly). In recent experiments that claim to have demonstrated quantum advantage, these conditions are satisfied; thus, this algorithm can be used to classically simulate these experiments.
Related papers
- Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs [0.8192907805418583]
Ising models on heavy-hex graphs are examined for their classical computational hardness via empirical time scaling.
Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances.
arXiv Detail & Related papers (2024-12-20T05:09:30Z) - Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
We propose quantum algorithms for linear differential equations.
The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.
The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
arXiv Detail & Related papers (2024-12-19T14:04:11Z) - Gaussian boson sampling for binary optimization [0.0]
We propose to use a parametrized Gaussian Boson Sampler (GBS) with threshold detectors to address binary optimization problems.
Numerical experiments on 3-SAT and Graphing problems show significant performance gains over random guessing.
arXiv Detail & Related papers (2024-12-19T12:12:22Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Classical algorithm for simulating experimental Gaussian boson sampling [2.1684911254068906]
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.
arXiv Detail & Related papers (2023-06-06T14:19:48Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity.
We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
arXiv Detail & Related papers (2022-03-01T19:47:16Z) - Bregman divergence based em algorithm and its application to classical
and quantum rate distortion theory [61.12008553173672]
We address the minimization problem of the Bregman divergence between an exponential subfamily and a mixture subfamily in a Bregman divergence system.
We apply this algorithm to rate distortion and its variants including the quantum setting.
arXiv Detail & Related papers (2022-01-07T13:33:28Z) - Noisy Bayesian optimization for variational quantum eigensolvers [0.0]
The variational quantum eigensolver (VQE) is a hybrid quantum-classical algorithm used to find the ground state of a Hamiltonian.
This work proposes an implementation of GPR and BO specifically tailored to perform VQE on quantum computers already available today.
arXiv Detail & Related papers (2021-12-01T11:28:55Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression.
We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
arXiv Detail & Related papers (2020-11-09T01:13:07Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems.
We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms.
Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
arXiv Detail & Related papers (2020-02-21T17:45:32Z)
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.