Deep-Circuit QAOA Gereon Komann1aLennart Binkowski1bLauritz van Luijk1Timo Ziegler1 2cand Ren e Schwonnek1d 1Institut f ur Theoretische Physik Leibniz Universit at Hannover

2025-05-06 0 0 5.73MB 19 页 10玖币

侵权投诉

Deep-Circuit QAOA

Gereon Koßmann,1, a) Lennart Binkowski,1, b) Lauritz van Luijk,1Timo Ziegler,1, 2, c) and Ren´e Schwonnek1, d)

1)Institut f¨ur Theoretische Physik, Leibniz Universit¨at Hannover

2)Volkswagen AG, Berliner Ring 2, 38440 Wolfsburg

Despite its popularity, several empirical and theoretical studies suggest that the quantum approximate op-

timization algorithm (QAOA) has persistent issues in providing a substantial practical advantage. So far,

those ﬁndings mostly account for a regime of few qubits and shallow circuits. We ﬁnd clear evidence for a

‘no free lunch’-behavior of QAOA on a general optimization task with no further structure; individual cases

have, however, to be analyzed more carefully.

We propose and justify a performance indicator for the deep-circuit QAOA that can be accessed by solely

evaluating statistical properties of the classical objective function. We further discuss the various favorable

properties a generic QAOA instance has in the asymptotic regime of inﬁnitely many gates, and elaborate on

the immanent drawbacks of ﬁnite circuits. We provide several numerical examples of a deep-circuit QAOA

method based on local search strategies and ﬁnd that – in alignment with our performance indicator – some

special function classes, like QUBO, admit a favorable optimization landscape.

I. INTRODUCTION

Within recent years, variational quantum algorithms

(VQAs)1have become the focus of a signiﬁcant amount

of research. The intuitive idea of this class of algorithms

is to use classical optimization routines in order to vari-

ationally combine small building blocks of quantum cir-

cuits into bigger ones that may give good solutions to

diﬃcult problems.

Due to its simplicity, the quantum approximate opti-

mization algorithm (QAOA)2is one of the most promi-

nent types of algorithms from the growing family of

VQAs. It was designed to tackle the class of combina-

torial optimization problems (see Section II). This class

includes, e.g., problems like MAXCUT, MAX-k-SAT, or

TSP, and can in general be considered to be of high prac-

tical relevance for real world applications. Algorithms for

non-trivial instances of these can already be implemented

on systems with only a few dozen of qubits; e.g. [3, Fig-

ure 4] use up to 23 qubits. This is why QAOA attracted,

beyond a pure academic interest, also a lot of attention

by several of the ﬁrst commercial providers of quantum

software.

Despite the high hopes that are connected to these al-

gorithms, a true proof or demonstration of any practical

advantage coming from applying a VQA like the QAOA

to any real world problem is, however, still pending. Re-

specting the limitations of existing technology, we neither

have large fault tolerant quantum computers nor can we

simulate many qubits, a lot of research focus was put on

implementations with few qubits and shallow quantum

circuits4and therefore basically ‘proofs of concept’.

In this regime the hopes especially put into QAOA

seem to face substantial obstacles: Already in [2] it was

a)Electronic mail: kossmann@stud.uni-hannover.de

b)Electronic mail: lennart.binkowski@itp.uni-hannover.de

c)Electronic mail: timo.ziegler@volkswagen.de

d)Electronic mail: rene.schwonnek@itp.uni-hannover.de

numerically shown, that the MAXCUT problem for 3-

regular graphs is not (reliable) solvable with low-depth

circuits; only increased circuit depths yield decent solu-

tion quality5. Low-depth case studies are done in a broad

way through the literature leading to the, at least empir-

ical, conclusion that low-depth QAOA circuits will not

give reliable results for complicated problem instances6–8.

In this work we extend the investigation of the po-

tential perspectives and limitations of the QAOA to the

regime of deep quantum circuits. Central questions that

guide us on this path are: What are distinctive features of

this regime? Are there eﬀects and methods that become

present for deep circuits that are not possible in a low-

depth regime? And most importantly, on what classes of

problems could QAOA perform well when circuit depth

is not a hard limitation?

By this work we try to provide at least some clear an-

swers to those questions. These answers should, when-

ever possible, admit a certain aspiration of mathematical

rigor and will be backed up by clear intuitions of possi-

ble mechanisms and numerical case study evidence oth-

erwise. For a bigger picture we can, however, only make

a beginning.

A distinctive feature for the deep-circuit regime con-

cerns the types of classical variational methods that could

be employed. In the deep-circuit regime, we are con-

fronted with a rapidly growing range of classical control

parameters. Here the classical variation routines that

are typically employed in low-depth QAOA quickly run

out of their eﬃciency range. Instead, we will consider

local search routines as the characteristic class of varia-

tion methods of the deep-circuit regime, since they are

naturally suited for optimizations in this situation.

In the ﬁrst part of Section III, we give a clariﬁed view

on the QAOA optimization landscape on state space that

is, to our surprise, unexpectedly seldom employed. How-

ever, it ﬁts well for analyzing local search routines which

notably do not admit for a ﬁxed circuit length. The basic

QAOA Hamiltonians are treated as generators of a Lie

algebra whereby the optimization landscape is given by

an orbit of its Lie group. The resulting landscape reveals

arXiv:2210.12406v2 [quant-ph] 3 Feb 2023

a nice geometry that can be analyzed by basic tools from

diﬀerential geometry. In contrast to the QAOA context,

this view is well investigated in the ﬁeld of optimal con-

trol theory from which we borrow methods and results.

In the second part of Section III, we start our investi-

gations by studying the limit of asymptotic circuits. Here

we ﬁnd that a generic QAOA instance has many favor-

able properties: for example, a unique local minimum

that gives us the optimal solution of the underlying clas-

sical optimization problem. This vaguely means that a

local search that could exploit arbitrary circuit depths

and employ second order gradient methods will succeed

in solving almost any problem. This result can be seen in

line with ﬁndings that were, e.g., reported in [9] showing

that variational quantum algorithms with an exponential

amount of control parameters can avoid local traps.

These regimes are, however, far from any practical use.

In Section IV, we turn our attention to deep, but not

asymptotically deep, circuits. Here many of the nice

asymptotic properties vanish. Saddle points turn into

eﬀective local minima, and we get a landscape with a

continuum of local attractors and potentially exponen-

tially many local traps. However, a characterization of

local traps reveals that statistical distribution proper-

ties of traps, like amount, sizes, and depths, only de-

pend on the classical objective function, and can be used

to predict the performance of the deep-circuit QAOA in

this generically unfavorable setting. Our method gives

strongly problem-dependent quantities that serve as an

evaluation basis for the success of the QAOA, and we col-

lect them in a single performance indicator. Especially

the lack of success in many QAOA instances could be

explained from this perspective. As an example for a ’no

free lunch’-behavior we come up with, in a very simple

way, randomly generated target functions that impose

an optimization landscape with unfavorably distributed

traps. In contrast, we see that certain special problem

classes, like QUBO, have the tendency to admit a favor-

able landscape.

In Section V we look at our results from a practi-

cal perspective by numerically simulating deep-circuit

QAOA (up to 1000 layers of non-decomposed QAOA-

gates) based on a simple downhill simplex method. Re-

sults indicate the QAOA performs well only on some

classes of optimization problems. Most notably, the nu-

merical results are in line with the prior introduced per-

formance indicator. Furthermore, we numerically justify

the basic intuitions regarding traps and their inﬂuence on

local search strategies. An exemplary step size analysis

also shows that, unexpectedly, the same problem instance

can lead to very diﬀerent results when approached with

diﬀerent auxiliary parameters.

II. PRELIMINARIES

For the readers convenience we will start by a brief

review of the VQA approach, elaborate on the speciﬁc

form of the QAOA, and outline our view on optimization

landscapes, which we will use throughout this work.

1. Variational Quantum Algorithms

Consider a generic unconstrained combinatorial mini-

mization problem:

min

z∈BNf(z),(1)

where BN:={0,1}Ndenotes the set of bit strings of

length N. We follow the standard encoding procedure:

identify each bit string zwith a computational basis state

|ziof the N-qubit space H:=C2Nand translate the ob-

jective function finto an objective Hamiltonian, diagonal

in the computational basis

f7→ H:=X

z∈BN

f(z)|zihz|.(2)

Despite mainly working with pure states, we will advo-

cate to describe the state of a quantum system within the

formalism of density matrices, i.e. positive matrices ρ≥0

of unit trace. We denote the state space by S(H). An

immediate consequence of using this natural formalism

is that the expectation value of an observable H

F(ρ):= tr(ρH) (3)

deﬁnes a linear functional F:S(H)→R. Note that

by the Rayleigh-Ritz principle, the original minimization

task (1) is equivalent to ﬁnding a minimum of F. For

our study of derivatives, critical points, and minima of

F, this linearity will turn out as very beneﬁcial.

In order to approximately minimize F, a general VQA

now utilizes parameterized trial states obtained by apply-

ing a parameterized quantum circuit to an initial state.

For the QAOA, the initial state is given by the pure state

|+ih+|, where

|+i=

n=1

√2(|0i+|1i) = 1

√2NX

z∈BN|zi.(4)

It is the non-degenerate ground state of the Hamil-

tonian10

B=−

n=1

σ(n)

x.(5)

The unitary evolution generated from Bis commonly

referred to as ‘mixing’.

For the QAOA, we have two basic families of gates

UB(β) = e−iβB and (6a)

UC(γ) = e−iγC ,(6b)

where we used the convention of taking C=H−tr(H)1

as a traceless generator for our second unitary which is

usually coined the ‘phase separator’. Note that taking

all generators traceless does not change the evolution on

the level of density matrices.

A full QAOA circuit is then combined from these basic

families. The corresponding parameters are typically la-

beled by ~

β= (β1, . . . , βp)∈[0, π)pand ~γ = (γ1, . . . , γp)∈

Rpwith p∈N, where the quantity pspeciﬁes the circuit

depth. A fully parameterized QAOA circuit is therefore

given by

V(~

β, ~γ) =

q=1

UB(βq)UC(γq).(7)

2. The Deep-Circuit Regime

In the majority of the existing literature circuits with a

depth p≈10 or less are taken into account. One practical

reason for this restriction is the still too high gate noise

in existing quantum computers.

In this work we will refer to deep circuits as those that

substantially exceed the scale of p≈10, potentially by or-

ders of magnitudes. For example, the circuit depths used

in our numerical simulations ranged from 100 to 3 ·104.

From a technological perspective, this regime is not yet

reliably realizable on most existing devices, but clearly

at the edge of what we can expect from the technological

developments in the near and midterm future. The key

achievements we are here hoping for are improved gate

ﬁdelities that could, e.g. be enabled by improved error

mitigation techniques11 or even a full implementation of

(few) error corrected qubits12.

A central ingredient in any VQA are the classical rou-

tines involved in optimizing the circuit parameters. Here

the types of classical optimization algorithms that can

be used for shallow or deep circuits might diﬀer substan-

tially. In shallow circuits all variational parameters can

be actively optimized at the same time. Typical optimiz-

ers in use are for example COBYLA, Gradient Descent,

and Nelder-Mead. Those may however not perform well

for deep circuits. An optimization of a largely growing

amount of parameters might quickly become unpractical,

either by an increase of computational hardness or by the

commonly observed barren plateaus13,14.

For deep circuits, we will therefore focus on optimiza-

tion routines that follow local search strategies, i.e. those

which successively only vary a few parameters at the

same time within a small range of variation. We tend

to mark the necessity of these routines as another distin-

guishing feature of the deep-circuit regime. As a naive

prototype, we use a very simple downhill simplex method

in our numerical studies in Section V, being fully aware

that a huge variety of very elaborated and versatile local

search routines exist. For layer-wise optimization, the

phenomenon of barren plateaus has also been reported

in some particular instances15. These instances, how-

ever, substantially diﬀer from our setting, and we can

attribute the phenomenon of vanishing gradients to ‘lo-

cal traps’ instead.

3. Optimization Landscapes

In the context of the QAOA, the term optimization

landscape commonly refers to the ‘landscape’ of values

that the functional Ftakes on a parameter space which

is a subset of R2p(or on a two dimensional subspace

whenever a graphical illustration is provided). However,

for local search strategies, the ﬁnal length pof a circuit,

and therefore the parameter space, is typically not ﬁxed.

Hence, the above notion of ‘optimization landscape’ does

not really apply here. This motivates us to think of op-

timization landscapes in a diﬀerent way:

We simply regard the functional Fas a function that

deﬁnes a ‘landscape’ on the state space S(H), or more

precisely on the subset of the states that are potentially

accessible by a sequence of QAOA gates. To our big

surprise, this perspective is rather rare to ﬁnd within

the existing literature on VQAs. It’s indeed very nice

geometry will therefore be fully clariﬁed within the next

section.

In order to properly distinguish notions we will from

now on refer to landscape in R2pas the parameter land-

scape of Fand to the latter one as the state space land-

scape of F. Using the state space landscape to determine

properties of an QAOA algorithm has at least three im-

mediate advantages:

(i) Circuits with varying length can be properly ex-

pressed and compared within the same picture.

(ii) Local overparameterization is avoided. Diﬀerent

sets of parameters could refer to almost the same

point in statespace in no obvious way. This can,

for example, lead to a situation in which there are

many diﬀerent local minima in the parameter land-

scape that however only correspond to one and the

same minimum in the statespace landscape.

(iii) The behavior of diﬀerent classes of VQAs can be

compared within the same picture.

In this work, especially the points (i) and (ii) will be

essential for analyzing the performance perspectives of

deep QAOA circuits by characterizing the distribution

properties of local minima and critical points.

III. ASYMPTOTIC CIRCUITS

As starting point of our investigation we will discuss

the perspectives of the QAOA in an asymptotic regime.

This is, we consider inﬁnite sequences of gates with po-

tentially inﬁnitesimally small parameters. By includ-

ing inﬁnitesimal elements, the analysis of the asymptotic

QAOA becomes drastically more structured since we now

can make direct use of tools from diﬀerential geometry,

i.e. Lie groups and their algebras.

In the ﬁrst part of this section we will clarify this ge-

ometry. Here the key points are:

•Accessible states form a diﬀerentiable manifold Ω

•The target functional corresponds to a diﬀeren-

tiable scalar ﬁeld on Ω

•The two families of QAOA gates correspond to two

vector ﬁelds on Ω

We will then turn our attention to the classiﬁcation of

minima and critical points of F. Here our key ﬁndings

for generic instances are:

•We have a one-to-one correspondence between the

possible solution space BNof the classical optimiza-

tion problems and critical points of F.

•Within these critical points there is only one local

minimum. This minimum is the solution of the

underlying optimization problem.

Thematically, our investigations and results belong to

the ﬁeld of dynamical Lie algebras (see [16] for a compre-

hensive review). However, we see our analysis as more

tangible than the general case discussed there.

1. The Geometry of Accessible States

The ﬁrst question that arises when considering asymp-

totic gate sequences is: Which states can be reached by

the QAOA when starting from an initial state ψ0? This

set, from now on denoted by Ω, will be the ground for the

geometrical picture we want to outline in this section.

Let Hbe the target Hamiltonian that encodes an

optimization problem and let UB(β) and UC(γ) with

C=H−tr(H)1be our basic families of QAOA unitaries

as described in the previous section. The set Ω will be

obtained from considering the set G(B, C) of all circuits

that could be asymptotically generated by the QAOA. In

the following, we will drop the explicit dependence on B

and Cand write G=G(B, C) whenever it is clear from

the context.

Circuits

As described in the previous section, circuits of a ﬁxed

depth pare parameterized by ﬁnite sequences of angles

~γ and ~

β. For any p, these can be captured by the set

Gp=(p

i=1

UC(γi)UB(βi)∈SU(2N)

(~γ, ~

β)∈R2p).

(8)

There are now some technicalities to respect when con-

sidering circuits of inﬁnite depth. A naive limit p→ ∞ of

inﬁnite angles sequences in (8) will lead to inﬁnite prod-

ucts of unitaries, which is not necessarily a well-deﬁned

object.

However, on the level of sets we observe that the Gp

form a monotone sequence, i.e. we have Gp⊆Gp+1. Here

a well-deﬁned set-theoretic limit exists. From this limit

we obtain Gby taking the topological closure in L(H),

i.e. by

G=lim

p→∞ Gp⊂SU(2N).(9)

Intuitively, Gcontains all circuits of ﬁnite depth such as

all unitary transformations that can be approximated by

them up to arbitrary precision. Here proximity is mea-

sured in the operator norm, meaning that two unitaries

will be close to each other whenever their images are close

to each other for any input state.

States

Applying these circuits to a ﬁxed initial state Ψ0, i.e.

taking the G-orbit around Ψ0, will then give us the set

Ω of accessible states

Ω := {UΨ0U∗:U∈G} ⊆ S(H).(10)

Corresponding to our intuition on G, those are all states

that can be generated from Ψ0by a ﬁnite circuit such

as all states that are approximately close to them. The

central observation for the following analyses is that the

set Gnaturally carries the structure of a Lie group, which

will also carry over to a corresponding structure on Ω.

On one hand, a Lie group has the structure of a group,

which in this case simply reﬂects that QAOA circuits

have some of the basic properties a complete set of quan-

tum circuits should have. The group action, here given

by multiplying the corresponding unitaries, reﬂects that

concatenating two possible circuits gives again a valid

circuit. The existence of a neutral element, the identity

operator, is obtained by setting all angles ~γ and ~

βto

zero. This corresponds to an empty circuit, i.e. doing

nothing. The existence of an inverse17, here provided by

taking the adjoint of a unitary, reﬂects the often adver-

tised property that quantum circuits are reversible and

that the set of QAOA circuits is complete with respect

to this property.

On the other hand, the Lie group Ghas the structure of

a manifold. This structure will be crucial for rigorously

talking about optimization landscapes in what follows.

Even though the manifold structure of a Lie group is

given in a quite abstract manner in the ﬁrst place18, it

will carry over to a concrete structure on Ω, giving us

the playground for deﬁning optimization landscapes and

analyzing the behavior of optimization routines.

For ω∈Ω and U∈G, the map

πω(U) := UωU∗(11)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Deep-CircuitQAOAGereonKomann,1,a)LennartBinkowski,1,b)LauritzvanLuijk,1TimoZiegler,1,2,c)andReneSchwonnek1,d)1)InstitutfurTheoretischePhysik,LeibnizUniversitatHannover2)VolkswagenAG,BerlinerRing2,38440WolfsburgDespiteitspopularity,severalempiricalandtheoreticalstudiessuggestthatthequantumapproxi...

展开>> 收起<<

Deep-Circuit QAOA Gereon Komann1aLennart Binkowski1bLauritz van Luijk1Timo Ziegler1 2cand Ren e Schwonnek1d 1Institut f ur Theoretische Physik Leibniz Universit at Hannover.pdf

共19页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Deep-Circuit QAOA Gereon Komann1aLennart Binkowski1bLauritz van Luijk1Timo Ziegler1 2cand Ren e Schwonnek1d 1Institut f ur Theoretische Physik Leibniz Universit at Hannover

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: