Iteration Complexity of Variational Quantum Algorithms
- URL: http://arxiv.org/abs/2209.10615v2
- Date: Sun, 5 Nov 2023 14:23:20 GMT
- Title: Iteration Complexity of Variational Quantum Algorithms
- Authors: Vyacheslav Kungurtsev and Georgios Korpas and Jakub Marecek and Elton
Yechao Zhu
- Abstract summary: We argue that noise makes evaluations of the objective function via quantum circuits biased.
We derive the missing guarantees and find that the rate of convergence is unaffected.
- Score: 5.684122393859336
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There has been much recent interest in near-term applications of quantum
computers, i.e., using quantum circuits that have short decoherence times due
to hardware limitations. Variational quantum algorithms (VQA), wherein an
optimization algorithm implemented on a classical computer evaluates a
parametrized quantum circuit as an objective function, are a leading framework
in this space. An enormous breadth of algorithms in this framework have been
proposed for solving a range of problems in machine learning, forecasting,
applied physics, and combinatorial optimization, among others.
In this paper, we analyze the iteration complexity of VQA, that is, the
number of steps that VQA requires until its iterates satisfy a surrogate
measure of optimality. We argue that although VQA procedures incorporate
algorithms that can, in the idealized case, be modeled as classic procedures in
the optimization literature, the particular nature of noise in near-term
devices invalidates the claim of applicability of off-the-shelf analyses of
these algorithms. Specifically, noise makes the evaluations of the objective
function via quantum circuits biased. Commonly used optimization procedures,
such as SPSA and the parameter shift rule, can thus be seen as derivative-free
optimization algorithms with biased function evaluations, for which there are
currently no iteration complexity guarantees in the literature. We derive the
missing guarantees and find that the rate of convergence is unaffected.
However, the level of bias contributes unfavorably to both the constant
therein, and the asymptotic distance to stationarity, i.e., the more bias, the
farther one is guaranteed, at best, to reach a stationary point of the VQA
objective.
Related papers
- Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems.
In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems.
We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
arXiv Detail & Related papers (2024-04-17T11:00:12Z) - Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
We study the coherent version of the phase estimation problem.
The goal is to estimate the phases of $U$ in superposition.
We propose an improved version of the well-known standard quantum phase estimation algorithm.
arXiv Detail & Related papers (2024-03-27T18:17:23Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Challenges of variational quantum optimization with measurement shot noise [0.0]
We study the scaling of the quantum resources to reach a fixed success probability as the problem size increases.
Our results suggest that hybrid quantum-classical algorithms should possibly avoid a brute force classical outer loop.
arXiv Detail & Related papers (2023-07-31T18:01:15Z) - 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) - Faster variational quantum algorithms with quantum kernel-based
surrogate models [0.0]
We present a new method for small-to-intermediate scale variational algorithms on noisy quantum processors.
Our scheme shifts the computational burden onto the classical component of these hybrid algorithms, greatly reducing the number of queries to the quantum processor.
arXiv Detail & Related papers (2022-11-02T14:11:25Z) - Stochastic optimization algorithms for quantum applications [0.0]
We review the use of first-order, second-order, and quantum natural gradient optimization methods, and propose new algorithms defined in the field of complex numbers.
The performance of all methods is evaluated by means of their application to variational quantum eigensolver, quantum control of quantum states, and quantum state estimation.
arXiv Detail & Related papers (2022-03-11T16:17:05Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices.
We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT)
Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
arXiv Detail & Related papers (2020-10-01T18:14:11Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z)
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.