A Survey of Quantum Alternatives to Randomized Algorithms: Monte Carlo Integration and Beyond

• URL: http://arxiv.org/abs/2303.04945v1
• Date: Wed, 8 Mar 2023 23:39:49 GMT
• Title: A Survey of Quantum Alternatives to Randomized Algorithms: Monte Carlo Integration and Beyond
• Authors: Philip Intallura and Georgios Korpas and Sudeepto Chakraborty and Vyacheslav Kungurtsev and Jakub Marecek
• Abstract summary: We focus on the potential to obtain a quantum advantage in the computational speed of Monte Carlo procedures using quantum circuits. We revisit the quantum algorithms that could replace classical Monte Carlo and then consider both the existing quantum algorithms and the potential quantum realizations.
• Score: 7.060988518771793
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Monte Carlo sampling is a powerful toolbox of algorithmic techniques widely used for a number of applications wherein some noisy quantity, or summary statistic thereof, is sought to be estimated. In this paper, we survey the literature for implementing Monte Carlo procedures using quantum circuits, focusing on the potential to obtain a quantum advantage in the computational speed of these procedures. We revisit the quantum algorithms that could replace classical Monte Carlo and then consider both the existing quantum algorithms and the potential quantum realizations that include adaptive enhancements as alternatives to the classical procedure.

Related papers

• Power Characterization of Noisy Quantum Kernels [52.47151453259434]
  We show that noise may make quantum kernel methods to only have poor prediction capability, even when the generalization error is small. We provide a crucial warning to employ noisy quantum kernel methods for quantum computation.
  arXiv  Detail & Related papers  (2024-01-31T01:02:16Z)
• Quantum Algorithms for the computation of quantum thermal averages at work [0.0]
  We consider the practical implementation of the so-called Quantum-Quantum Metropolis algorithm. We simulate a basic system of three frustrated quantum spins and discuss its systematics.
  arXiv  Detail & Related papers  (2023-08-02T17:05:10Z)
• Quantum Adversarial Learning in Emulation of Monte-Carlo Methods for Max-cut Approximation: QAOA is not optimal [0.0]
  We apply notions of emulation to Variational Quantum Annealing and the Quantum Approximate Algorithm Optimization (QAOA) Our Variational Quantum Annealing schedule is based on a novel parameterization that can be optimized in a similar gradient-free way as QAOA, using the same physical ingredients. In order to compare the performance of ans"atze types, we have developed statistical notions of Monte-Carlo methods.
  arXiv  Detail & Related papers  (2022-11-24T19:02:50Z)
• Improved maximum-likelihood quantum amplitude estimation [0.0]
  Quantum estimation is a key subroutine in a number of powerful quantum algorithms, including quantum-enhanced Monte Carlo simulation and quantum machine learning. In this article, we deepen the analysis of Maximum-likelihood quantum amplitude estimation (MLQAE) to put the algorithm in a more prescriptive form, including scenarios where quantum circuit depth is limited. We then propose and numerically validate a modification to the algorithm to overcome this problem, bringing the algorithm even closer to being useful as a practical subroutine on near- and mid-term quantum hardware.
  arXiv  Detail & Related papers  (2022-09-07T17:30:37Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Circuit Symmetry Verification Mitigates Quantum-Domain Impairments [69.33243249411113]
  We propose circuit-oriented symmetry verification that are capable of verifying the commutativity of quantum circuits without the knowledge of the quantum state. In particular, we propose the Fourier-temporal stabilizer (STS) technique, which generalizes the conventional quantum-domain formalism to circuit-oriented stabilizers.
  arXiv  Detail & Related papers  (2021-12-27T21:15:35Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases. We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
  arXiv  Detail & Related papers  (2021-07-03T16:07:30Z)
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer [4.762232147934851]
  We introduce a novel non-variational algorithm using quantum simulation as a subroutine to accelerate quantum Monte Carlo. The proposed quantum algorithm is applicable to near-term noisy quantum hardware.
  arXiv  Detail & Related papers  (2021-06-18T02:45:14Z)

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.