Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits Sebastian Leontica1 2and David Amaro1

2025-04-24 0 0 4.75MB 14 页 10玖币

侵权投诉

Exploring the neighborhood of 1-layer QAOA

with Instantaneous Quantum Polynomial circuits

Sebastian Leontica1, 2, ∗and David Amaro1, †

1Quantinuum, Partnership House, Carlisle Place, London SW1P 1BX, United Kingdom

2CMMP Research Group, University College London, Dept of Physics and Astronomy,

Gower Street, London WC1E 6BT, United Kingdom

(Dated: February 13, 2024)

We embed 1-layer QAOA circuits into the larger class of parameterized Instantaneous Quantum

Polynomial circuits to produce an improved variational quantum algorithm for solving combinatorial

optimization problems. The use of analytic expressions to ﬁnd optimal parameters classically makes

our protocol robust against barren plateaus and hardware noise. The average overlap with the

ground state scales as 2−0.31(2)Nwith the number of qubits Nfor random Sherrington-Kirkpatrick

(SK) Hamiltonians of up to 29 qubits, a polynomial improvement over 1-layer QAOA. Additionally,

we observe that performing variational imaginary time evolution on the manifold approximates low-

temperature pseudo-Boltzmann states. Our protocol outperforms 1-layer QAOA on the recently

released Quantinuum H2 trapped-ion quantum hardware and emulator, where we obtain an average

approximation ratio of 0.985 across 312 random SK instances of 7 to 32 qubits, from which almost

44% are solved optimally using only 4 to 1208 shots per instance.

I. INTRODUCTION

Since its introduction by Farhi et al. [1] in 2014,

the Quantum Approximate Optimization Algorithm

(QAOA) has been explored in the quantum computing

literature as one of the most promising heuristics for

achieving quantum advantage on near-term devices [2, 3].

This is only one example of a larger class of variational

quantum optimization algorithms, which attempt to pro-

duce good solutions to combinatorial optimization prob-

lems by sampling a parameterized quantum circuit [4–8].

In the absence of full quantum error correction [9] the re-

quired circuits must be suﬃciently shallow to withstand

noise, yet expressive enough to ﬁnd states with high over-

lap onto the ground state. QAOA is a particularly good

choice for satisfying these criteria, as it has an adjustable

number of layers p. It can be understood as a Trotter-

ized version of the quantum adiabatic algorithm (QAA),

for which compelling theoretical evidence of performance

exists [10]. Additionally, it was shown that even for small

numbers of layers, sampling from the QAOA ansatz is a

hard task for classical computers [11].

In this regime of a small number of layers, the form

of the Trotterized QAOA operators may not be the best

choice. This has motivated [12–15] the addition of extra

parameters to the QAOA ansatz so that, instead of evolv-

ing the state according to the problem Hamiltonian, each

parameter in the ansatz has the freedom to evolve inde-

pendently. By doing this, an ansatz of the same depth

may incorporate corrections that would otherwise require

multiple layers.

In particular, 1-layer QAOA circuits–with and with-

out the additional parameterization–belong to the class

∗sebastian.leontica.22@ucl.ac.uk

†david.amaro@quantinuum.com

FIG. 1. Diagrammatic representation of the algorithm. The

1-layer QAOA ansatz is a submanifold of the IQP ansatz and

provides a warm start in the optimization protocol. The tra-

jectory between the QAOA optimum and the IQP optimum

is deﬁned via the McLachlan variational principle and is com-

puted classically. Color coding the optimization landscape

represents the eﬀective temperature of the associated state,

with lower temperature states (blue) having a higher chance

of sampling the ground state. The quantum computer is only

used during the sampling step, which is known to be diﬃcult

classically.

of parameterized quantum circuits known as Weighted

Graph States (WGS) used to simulate condensed mat-

ter systems [16–22]. For these states, the reduced den-

sity matrix in a subsystem of ﬁxed size can be computed

classically, allowing the eﬃcient evaluation of local ob-

servables on a classical computer. This property per-

mits the derivation of analytic and exact expressions for

1-layer QAOA on arbitrary local Hamiltonians [23] and

for extra-parameterized circuits on some restricted local

Hamiltonians[12, 13]. Such expressions are used to train

the model classically, bypassing typical limitations such

arXiv:2210.05526v3 [quant-ph] 12 Feb 2024

as the appearance of barren plateaus [24].

In this manuscript, we explore the embedding of 1-layer

QAOA into the broader class of parameterized Instan-

taneous Quantum Polynomial (IQP) circuits, for which

similar hardness of sampling theorems exist [25, 26], even

in the presence of moderate noise [27]. IQP circuits also

belong to the class of WGS, but compared to QAOA and

existing extra-parameterized variants our ansatz uses all-

to-all two-qubit interactions, making its implementation

problem-independent and most natural for trapped-ion

quantum computers. We additionally show that analytic

and exact expressions can be obtained for arbitrary local

Hamiltonians, and use them to train the model via robust

classical techniques like the Runge-Kutta method [28].

We emphasize the role of starting the training from the

optimal QAOA and ﬁnding a nearby local minimum

rather than aiming for a global optimum, which avoids

the challenging exploration of non-trivial landscapes [29].

This leaves only the key ingredient of sampling from

the ﬁnal quantum state to be performed on the quantum

device, as illustrated in Fig. 1. A recent investigation

of the states produced by 1-layer QAOA [30] shows that

sampling produces a distribution close to a Boltzmann

distribution, at temperatures beyond the reach of clas-

sical sampling techniques such as Markov Chain Monte

Carlo (MCMC) [31]. We improve on this result by lower-

ing the temperature further, using variational quantum

imaginary time evolution (VarQITE) [32, 33]. However,

the constraint of keeping the state in the variational man-

ifold limits our ability to follow exact imaginary time

evolution, distorting the distribution.

The manuscript is structured as follows. Section II

provides a brief review of QAOA. Our IQP ansatz is

introduced in Section III, where we make the connec-

tion to 1-layer QAOA, describe the derivation of an-

alytical expressions and how to use them for classical

training, and discuss a previous work [34] that challenges

the possibility of quantum advantage with IQP circuits.

In Section IV we describe our protocol for approximat-

ing thermal distributions and solving combinatorial op-

timization problems, while Section V presents numerical

performance results. First, the average overlap with the

ground state obtained with an exact state-vector simula-

tor is polynomially better than for 1-layer QAOA on ran-

dom Sherrington-Kirkpatrick (SK) Hamiltonians of up

to 29 qubits. Second, when approximating thermal dis-

tributions we can reach lower temperatures than 1-layer

QAOA but the approximation quality reduces. Third, we

demonstrate a better performance than 1-layer QAOA

at solving random SK Hamiltonians of up to 32 qubits

in the recently released Quantinuum’s trapped-ion H2

quantum hardware and emulator. Using a reduced num-

ber of shots, the best solution per instance presents a

large approximation ratio and is optimal for a large frac-

tion of instances. Finally, Section VI discusses the meth-

ods, results, and future research directions.

II. THE QUANTUM APPROXIMATE

OPTIMIZATION ALGORITHM

The standard implementation of the QAOA [1] at-

tempts to create states with large overlap onto the ground

eigenspace of some optimization problem, typically de-

ﬁned through an Ising Hamiltonian,

H=X

hiZi+X

i<j

Jij ZiZj,(1)

where the Zivariables can be interpreted as the projec-

tions onto the Z-axis of a classical or quantum mechanical

ensemble of Nspin- 1

2particles and (hi, Jij ) are real co-

eﬃcients. This is achieved by starting with the ground

state |+⟩⊗Nof the trivial transverse ﬁeld mixing Hamil-

tonian Hx=−PiXiand evolving the state under the

alternating application of the propagators of Hand Hx.

The ﬁnal trial state is of the form

|Ψ(γ,β)⟩=

k=1

exp (iβkHx) exp (−iγkH)|+⟩⊗N,(2)

where pis called the level of the QAOA and the sets

β,γof real coeﬃcients βk,γkare used as variational

parameters. The most commonly used cost function in

the optimization of the ansatz is the expectation value of

the problem Hamiltonian

E=⟨Ψ(γ,β)|H|Ψ(γ,β)⟩,(3)

although alternative objective functions have been pro-

posed [35, 36]. For the rest of this work, we will only

consider the 1-layer QAOA, which is suﬃciently shallow

to withstand the eﬀects of moderate noise and obtains

an enhanced average probability of sampling the ground

state quadratically larger than random guessing [30], i.e.,

scaling as 2−0.5N.

III. THE INSTANTANEOUS QUANTUM

POLYNOMIAL CIRCUIT

The IQP is a non-universal model of quantum compu-

tation with similar roots to the boson sampling prob-

lem, whose aim is to strengthen the general belief

that quantum computers are more powerful than clas-

sical machines [25, 26]. Under certain widely believed

complexity-theoretic assumptions, sampling from the

IQP state H⊗Nexp(−iHIQP(⃗

θ)) |+⟩⊗Nin the computa-

tional basis of all qubits is a hard task for a classical

computer [26]. Here the IQP Hamiltonian is deﬁned

as HIQP(⃗

θ) = 1

2PiθiZi+1

2Pi<j θij ZiZjand His the

Hadamard gate.

The IQP ansatz employed in this work is a general-

ization where Hadamard gates are replaced with inde-

pendent parameterized single-qubit rotations Rx(ϕ) =

exp(−iϕX/2), leading to the quantum circuit

|Ψ(θ)⟩=O

i∈N

Rx(ϕi)·exp −iHIQP(⃗

θ)|+⟩⊗N,(4)

(a) (b)

FIG. 2. Optimization results for 300 randomly generated Sherrington-Kirkpatrick Hamiltonians of up to 29 spins. a) Probability

of sampling the ground state conﬁguration in the optimal IQP ansatz. b) Enhancement factor pIQP/pQAOA for ﬁnding the

ground state in the optimized IQP ansatz compared to the original QAOA. The IQP was optimized until convergence using

simple gradient descent. Using a linear ﬁt, we ﬁnd the average probability of sampling the ground state pIQP ∼2−αN with

α= 0.31±0.02 and the average enhancement factor pIQP/pQAOA ∼2δN with δ= 0.23±0.02. The errors indicate the variability

in gradient at one standard deviation.

where θ= (⃗

ϕ, ⃗

θ) are free, real parameters. The IQP

state is recovered by setting ϕi=π/2 and making the

transformation θi−→ θi−π/2. Since the IQP state can

be brought to this form by modifying the ﬁnal layer of

single qubit rotations, we expect generic states of this

form to be diﬃcult to sample classically as well. We also

make the important observation that, up to single qubit

rotations and energy rescaling, the IQP state in Eq. (4) is

the same as that produced by a 1-layer QAOA designed

to solve for the ground state of HIQP.

This ansatz generalizes the optimization cost function

of Eq. (3) to

E(θ) = ⟨Ψ(θ)|H|Ψ(θ)⟩=⟨H⟩θ,(5)

which we refer to as the optimization landscape. The

task of computing the cost function deﬁned in Eq. (5) is

then reduced to estimating the expectation values of the

spins ⟨Zi⟩θand correlators ⟨ZiZj⟩θin an arbitrary state

|Ψ(θ)⟩. In the Supplemental Material we show that the

latter expression can be reduced to calculating partition

functions of reduced Ising Hamiltonians of the form

Ze=1

2NX

{x}

e−iHe(x),(6)

where e’s are single or two qubit subsets. The reduced

generator Heretains only the terms in HIQP that anti-

commute with the operator Xe=Ni∈eXi. This leads

to a highly restricted graph topology, for which partition

functions can be evaluated exactly. We generalize this

method to show that IQPs have simple analytic expres-

sions for all expectation values of the form ⟨Ze⟩θ, with a

number of terms that scales like O(2|e|).

These properties of the IQP ansatz make it a good can-

didate for solving optimization problems, as it is guaran-

teed to be at least as powerful as 1-layer QAOA and the

training can be performed eﬃciently using only classical

resources. The access to exact, analytic expressions for

the cost function also means we do not need to worry

about ﬁnite sampling or device errors during training.

Barren plateau issues can also be ruled out, as we can

evaluate gradients to arbitrary precision and use adap-

tive step sizes. Access to a quantum computer is only

necessary during the ﬁnal sampling step, so we expect

our protocol to perform well under moderate hardware

noise.

As opposed to the standard QAOA ansatz, the IQP is

suﬃciently ﬂexible to produce all computational states.

In particular, this means that, if a classical algorithm

were able to ﬁnd the global optimum of Eq. (5), it would

also ﬁnd the exact ground state of H. In [34], it is shown

that the optimization landscapes of IQP ansatze with

only polynomially many terms (like our ansatz) are gen-

erally non-convex and computational states other than

the solution may form local minima, which we call triv-

ial minima. Consequently, converging to such local min-

ima would imply the algorithm does not need access to a

quantum computer, as the bits xiof the solution corre-

sponding to the optimal parameters are given by ⟨Zi⟩θ,

which can be eﬃciently computed classically.

We prove that the optimization landscapes can contain

non-trivial minima, and give a minimal example of this

in the Supplemental Material. Remarkably, we provide

numerical evidence that for the SK model such a local

minimum is located in the vicinity of the QAOA param-

eters, and show that sampling the IQP circuit at this

point greatly enhances the chance of ﬁnding the ground

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

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

10 玖币 0人已下载

立即下载

摘要：

Exploringtheneighborhoodof1-layerQAOAwithInstantaneousQuantumPolynomialcircuitsSebastianLeontica1,2,∗andDavidAmaro1,†1Quantinuum,PartnershipHouse,CarlislePlace,LondonSW1P1BX,UnitedKingdom2CMMPResearchGroup,UniversityCollegeLondon,DeptofPhysicsandAstronomy,GowerStreet,LondonWC1E6BT,UnitedKingdom(Date...

展开>> 收起<<

Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits Sebastian Leontica1 2and David Amaro1.pdf

共14页,预览3页

还剩页未读，继续阅读

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

Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits Sebastian Leontica1 2and David Amaro1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: