Iteration Complexity of Variational Quantum Algorithms

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00377736" target="_blank" >RIV/68407700:21230/24:00377736 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.22331/q-2024-10-10-1495" target="_blank" >https://doi.org/10.22331/q-2024-10-10-1495</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.22331/q-2024-10-10-1495" target="_blank" >10.22331/q-2024-10-10-1495</a>

Result language

angličtina

Original language name

Iteration Complexity of Variational Quantum Algorithms

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Quantum

ISSN

2521-327X

e-ISSN

2521-327X

Volume of the periodical

8

Issue of the periodical within the volume

September

Country of publishing house

AT - AUSTRIA

Number of pages

42

Pages from-to

1-42

UT code for WoS article

001332250500001

EID of the result in the Scopus database

2-s2.0-85207352964