Quantum Adversarial Learning in Emulation of Monte-Carlo Methods for
Max-cut Approximation: QAOA is not optimal
- URL: http://arxiv.org/abs/2211.13767v1
- Date: Thu, 24 Nov 2022 19:02:50 GMT
- Title: Quantum Adversarial Learning in Emulation of Monte-Carlo Methods for
Max-cut Approximation: QAOA is not optimal
- Authors: Cem M. Unsal, Lucas T. Brady
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One of the leading candidates for near-term quantum advantage is the class of
Variational Quantum Algorithms, but these algorithms suffer from classical
difficulty in optimizing the variational parameters as the number of parameters
increases. Therefore, it is important to understand the expressibility and
power of various ans\"atze to produce target states and distributions. To this
end, we apply notions of emulation to Variational Quantum Annealing and the
Quantum Approximate Optimization Algorithm (QAOA) to show that QAOA is
outperformed by variational annealing schedules with equivalent numbers of
parameters. Our Variational Quantum Annealing schedule is based on a novel
polynomial 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. Monte-Carlo methods are computer programs that generate
random variables that approximate a target number that is computationally hard
to calculate exactly. While the most well-known Monte-Carlo method is
Monte-Carlo integration (e.g. Diffusion Monte-Carlo or path-integral quantum
Monte-Carlo), QAOA is itself a Monte-Carlo method that finds good solutions to
NP-complete problems such as Max-cut. We apply these statistical Monte-Carlo
notions to further elucidate the theoretical framework around these quantum
algorithms.
Related papers
- Application of Langevin Dynamics to Advance the Quantum Natural Gradient Optimization Algorithm [47.47843839099175]
A Quantum Natural Gradient (QNG) algorithm for optimization of variational quantum circuits has been proposed recently.
In this study, we employ the Langevin equation with a QNG force to demonstrate that its discrete-time solution gives a generalized form, which we call Momentum-QNG.
arXiv Detail & Related papers (2024-09-03T15:21:16Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems.
This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios.
We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
arXiv Detail & Related papers (2023-06-15T15:28:12Z) - Unbiasing time-dependent Variational Monte Carlo by projected quantum
evolution [44.99833362998488]
We analyze the accuracy and sample complexity of variational Monte Carlo approaches to simulate quantum systems classically.
We prove that the most used scheme, the time-dependent Variational Monte Carlo (tVMC), is affected by a systematic statistical bias.
We show that a different scheme based on the solution of an optimization problem at each time step is free from such problems.
arXiv Detail & Related papers (2023-05-23T17:38:10Z) - A Survey of Quantum Alternatives to Randomized Algorithms: Monte Carlo
Integration and Beyond [7.060988518771793]
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.
arXiv Detail & Related papers (2023-03-08T23:39:49Z) - Monte Carlo Tree Search based Hybrid Optimization of Variational Quantum
Circuits [7.08228773002332]
We propose a new variational quantum algorithm called MCTS-QAOA.
It combines a Monte Carlo tree search method with an improved natural policy gradient solver to optimize the discrete and continuous variables in the quantum circuit.
We find that MCTS-QAOA has excellent noise-resilience properties and outperforms prior algorithms in challenging instances of the generalized QAOA.
arXiv Detail & Related papers (2022-03-30T23:15:21Z) - 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) - 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 Approximate Optimization Algorithm Based Maximum Likelihood
Detection [80.28858481461418]
Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
arXiv Detail & Related papers (2021-07-11T10:56:24Z) - Quantum algorithms for multivariate Monte Carlo estimation [0.0]
We consider the problem of estimating the expected outcomes of Monte Carlo processes whose outputs are described by multidimensional random variables.
We design quantum algorithms that provide a quadratic speed-up in query complexity with respect to the precision of the resulting estimates.
We describe several applications of our algorithms, notably in the field of machine learning.
arXiv Detail & Related papers (2021-07-07T18:00:18Z) - Quantum-accelerated multilevel Monte Carlo methods for stochastic
differential equations in mathematical finance [1.128265591164748]
We study quantum algorithms for differential equations (SDEs)
We provide a quantum algorithm that gives a quadratic speed-up for multilevel Monte Carlo methods in a general setting.
We demonstrate the use of this algorithm in a variety of applications arising in mathematical finance.
arXiv Detail & Related papers (2020-12-11T12:34:55Z)
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.