Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms

2025-04-29 0 0 942.04KB 21 页 10玖币

侵权投诉

Quantum-classical tradeoﬀs and multi-controlled quantum

gate decompositions in variational algorithms

Teague Tomesh1,2, Nicholas Allen1,3, Daniel Dilley4,5, and Zain H. Saleem5

1Princeton University, Princeton, NJ, 08540, USA

2Inﬂeqtion, Chicago, IL, 60604, USA

3University of Waterloo, Institute for Quantum Computing, Waterloo, ON N2L 3G1, Canada

4Quantum Quadrivium Technologies LLP, Evergreen Park , IL, 60805, USA

5Argonne National Laboratory, 9700 S. Cass Avenue, Lemont, IL, 60439, USA

The computational capabilities of near-

term quantum computers are limited by

the noisy execution of gate operations and

a limited number of physical qubits. Hy-

brid variational algorithms are well-suited

to near-term quantum devices because

they allow for a wide range of tradeoﬀs be-

tween the amount of quantum and classical

resources used to solve a problem. This pa-

per investigates tradeoﬀs available at both

the algorithmic and hardware levels by

studying a speciﬁc case — applying the

Quantum Approximate Optimization Al-

gorithm (QAOA) to instances of the Maxi-

mum Independent Set (MIS) problem. We

consider three variants of the QAOA which

oﬀer diﬀerent tradeoﬀs at the algorithmic

level in terms of their required number of

classical parameters, quantum gates, and

iterations of classical optimization needed.

Since MIS is a constrained combinatorial

optimization problem, the QAOA must re-

spect the problem constraints. This can

be accomplished by using many multi-

controlled gate operations which must be

decomposed into gates executable by the

target hardware. We study the tradeoﬀs

available at this hardware level, combining

the gate ﬁdelities and decomposition eﬃ-

ciencies of diﬀerent native gate sets into a

single metric called the gate decomposition

cost.

Teague Tomesh: teague.tomesh@inﬂeqtion.com

Zain H. Saleem: zsaleem@anl.gov

1 Introduction

Today’s quantum computing platforms are ca-

pable of executing single- and two-qubit gates

with ﬁdelities that have steadily improved year

over year Gambetta et al. [2017], Wright et al.

[2019], Arute et al. [2019], Arrazola et al. [2021].

However, implementing multi-qubit operations

between three or more qubits presents signiﬁ-

cant challenges, although some progress has been

made in this direction Monz et al. [2009], Isen-

hower et al. [2011], and it remains unclear what

level of ﬁdelity must be achieved before multi-

qubit operations may outperform one- and two-

qubit operations when executing a quantum al-

gorithm.

The limitations of today’s Noisy Intermediate-

Scale Quantum (NISQ) computers severely re-

strict the set of executable quantum algorithms

Preskill [2018]. Hybrid variational algorithms are

a class of applications which are well-suited to

NISQ systems because they make use of both

quantum and classical resources when solving a

problem, and this allows the quantum computer

to focus on a single, well-deﬁned task Cerezo et al.

[2021]. For a given computational workload, a

variational algorithm may make algorithmic level

tradeoﬀs (e.g., varying the number of classical pa-

rameters, the size of the variational ansatz, or it-

erations of classical optimization) that exchange

quantum and classical resources. Furthermore,

current NISQ computers support a wide variety

of native gate sets which enables diﬀerent choices

for decomposing the algorithmic level circuits into

hardware executables Murali et al. [2019].

The Quantum Approximate Optimization Al-

gorithm (QAOA) Farhi et al. [2014] is a hy-

Accepted in Quantum 2024-09-09, click title to verify. Published under CC-BY 4.0. 1

arXiv:2210.04378v4 [quant-ph] 1 Oct 2024

brid variational algorithm that solves both con-

strained and unconstrained combinatorial opti-

mization problems. For constrained combinato-

rial optimization problems there are two methods

for dealing with the added problem constraints.

One choice is to convert the constrained prob-

lem into an unconstrained one by introducing a

Lagrange multiplier into the objective function.

This can then be executed on quantum hardware

using only single- and two-qubit gates, however,

this method often requires an additional hyper-

parameter optimization step in order to correctly

set the value of the Lagrange multiplier Saleem

et al. [2023]. Alternatively, the constraint may be

introduced within the ansatz itself which then re-

quires the use of multi-controlled quantum gates

Hadﬁeld [2018], Hadﬁeld et al. [2019], Saleem

[2020]. The constraint-aware ansatz ensures that

the constraints are satisﬁed at all times during

the optimization and the extremization is only

performed over the set of feasible states. In this

paper we focus solely on the latter case which

uses the constraint-aware ansatz and therefore re-

quires the use of multi-controlled gates.

Before the QAOA may be executed, the al-

gorithmically deﬁned multi-qubit gates must be

decomposed into equivalent sets of gate opera-

tions which are natively supported by the quan-

tum hardware. Depending on the speciﬁc native

gate set, the ﬁnal overhead gate cost incurred by

the decomposition may vary greatly. Quantum

gate decompositions are a broad and extensive

area of study Barenco et al. [1995], Vartiainen

et al. [2004], Martinez et al. [2016], Gokhale et al.

[2019], Rakyta and Zimborás [2022]. Strategies

for general unitary decompositions include algo-

rithmic rule-based constructions Barenco et al.

[1995], Vartiainen et al. [2004], Li et al. [2013], di-

rect synthesis via numerical optimization Younis

et al. [2021], and optimal control Shi et al. [2019].

Oftentimes the multi-qubit gates appearing in

the constrained QAOA contain a large amount of

structure (e.g., they may be expressed simply as

sets of single-qubit rotations and multi-controlled

not’s) that allows for more eﬃcient decomposi-

tions Barenco et al. [1995], Gokhale et al. [2019].

In this paper, we study the quantum and classi-

cal tradeoﬀs available to variational quantum al-

gorithms, speciﬁcally focusing on the case of con-

strained QAOA applied to Maximum Indepen-

dent Set (MIS) problems. We consider both al-

gorithmic and hardware level design choices that

inﬂuence the ﬁnal amount of classical and quan-

tum resources that are required.

At the algorithmic level, we consider three vari-

ants of the QAOA which diﬀer in the number of

classical parameters, rounds of optimization, and

gate operations they require. In the original for-

mulation of the QAOA, the ansatz is composed of

alternating layers of parameterized gates and all

of the gates within a single layer are parameter-

ized by the same variable. We refer to this version

as single-angle QAOA (SA-QAOA). Recent work

has shown that, for both unconstrained optimiza-

tion problems, such as MaxCut, and constrained

problems, such as MIS, parameterizing the gates

within each layer by a vector of variables can re-

sult in higher approximation ratios and shorter

circuits at the expense of additional classical pa-

rameters Herrman et al. [2022], Saleem et al.

[2023]. We refer to this implementation of the

QAOA as multi-angle QAOA (MA-QAOA). Fi-

nally, the number of multi-controlled quantum

gates in both the SA-QAOA and MA-QAOA

scales linearly with the problem size. To miti-

gate this large quantum resource requirement, a

new approach called the Dynamic Quantum Vari-

ational Ansatz (DQVA) was introduced in Saleem

et al. [2023]. The DQVA removes this scaling

dependency on the problem size by making the

number of parameters and multi-controlled gates

a tunable hyper-parameter in exchange for addi-

tional iterations of classical optimization.

At the hardware level, we study the cost of de-

composing the large multi-qubit gates into dif-

ferent native gate sets containing diﬀerent levels

of controlled gates and higher dimensional qu-

dits. Our consideration of native gate sets with

higher degree multi-qubit gates is motivated by

the recent emergence of quantum hardware capa-

ble of supporting such operations. These include

neutral atoms Isenhower et al. [2011], Saﬀman

[2016], trapped ions Espinoza et al. [2021], Katz

et al. [2022], Rasmussen et al. [2020], and recent

demonstrations of Toﬀoli gates in superconduct-

ing quantum hardware Kim et al. [2022]. Si-

multaneously, multiple experiments have demon-

strated the viability of using qutrits, containing

three logical states |0⟩,|1⟩, and |2⟩, within quan-

tum computations Morvan et al. [2021], Gokhale

et al. [2020]. Prior work has already shown

that more expressive gate sets, containing mul-

Accepted in Quantum 2024-09-09, click title to verify. Published under CC-BY 4.0. 2

tiple two-qubit entangling operations from diﬀer-

ent gate families, are beneﬁcial for the compila-

tion of quantum applications Lao et al. [2021].

We extend this intuition here by studying the

impact that natively supported multi-controlled

gates and three-level qutrits can have on the de-

composition overheads for the QAOA.

In summary, our contributions include:

•Numerical simulations of the QAOA on 20-

node graphs, highlighting the tradeoﬀs that

can be made between classical and quan-

tum resources while achieving similar perfor-

mance amongst the three QAOA variants.

•Asymptotic gate counts with exact scal-

ing coeﬃcients for the decomposition of the

multi-controlled single-qubit rotations ap-

pearing in the constrained QAOA circuits.

We consider scenarios where varying num-

bers of ancillae and diﬀerent native gate sets

are made available for the decompositions.

•We introduce a new metric, the gate decom-

position cost, which shows that we can use

lower ﬁdelity native gates in one QAOA to

outperform the higher ﬁdelity gates in an-

other.

The goal of this paper is to aid future system

designs by calculating the ﬁdelity of native multi-

qubit (or qutrit) gates that is necessary to achieve

performance improvements over the typical two-

qubit gates for realistic workloads.

The rest of the paper is organized as follows, we

begin in Section 2by introducing the diﬀerent ﬂa-

vors of the constrained QAOA applied to the MIS

problem. Section 3describes the diﬀerent de-

compositions of multi-controlled single-qubit ro-

tations. In Section 4we compare the variants

of the constrained QAOA and perform resource

analysis. Finally, in Section 5we summarize our

conclusions and suggest future directions.

2 Quantum Approximate Optimiza-

tion for Maximum Independent Set

The QAOA is a hybrid quantum-classical algo-

rithm developed for the purpose of ﬁnding ap-

proximate solutions to combinatorial optimiza-

tion problems. The objective of the QAOA is to

prepare the ground state of a problem-dependent

Algorithm

Number of

parameters,

|θ|

Rounds of

variational

optimization

SA-QAOA Constant,

|θ|= 2p

Single

MA-QAOA

Scales with

problem size,

|θ|=up to 2pn

Single

DQVA

Tunable with

problem size,

|θ|=ν

Multiple

Table 1: The three ﬂavors of the QAOA considered in

this work. Each makes diﬀerent tradeoﬀs with respect to

the classical (e.g., number of parameters, rounds of op-

timization) and quantum (e.g., circuit depth) resources

they require. We consider the Maximum Independent

Set (MIS) problem over graphs with nnodes.

quantum operator using a variational ansatz, i.e.,

a parameterized quantum circuit. This quantum

operator is deﬁned on n-bit strings and is diago-

nal in the computational basis

Cobj|b⟩=C(b)|b⟩(1)

where b={b1, b2, b3. . . bn} ∈ {0,1}n. The ex-

pectation value of this operator is measured on a

quantum computer after preparing the state

|ψp(γ,β)⟩=e−iβpMe−iγpC···e−iβ1Me−iγ1C|s⟩

(2)

where |s⟩is the initial state, eiγC is the phase

separator unitary, diagonal in computational ba-

sis, eiβM is the mixing unitary that mixes the

state among one another during optimization and

pcontrols the number of times the unitary oper-

ators are applied. The expectation value of Cobj

with respect to this variational state,

Ep(γ,β) = ⟨ψp(γ,β)|Cobj|ψp(γ,β)⟩,(3)

is evaluated on a quantum computer before be-

ing passed to a classical optimizer which attempts

to ﬁnd the optimal parameters which maximize

Ep(γ,β). This maximization is achieved for the

states corresponding to the optimal solutions of

the original optimization problem.

Accepted in Quantum 2024-09-09, click title to verify. Published under CC-BY 4.0. 3

2.1 Unconstrained QAOA

The Maximum Independent Set (MIS) problem

involves ﬁnding the largest set of nodes in a graph

such that no two nodes are connected to each

other. Only a subset of all possible solutions (i.e.,

all n-bit strings) are feasible solutions which sat-

isfy the problem constraints. However, we may

still apply the QAOA to this problem by adding

a penalty term to the objective function

Cobj =H−λ Cpen =X

i∈V

bi−λX

i,j∈E

bibj,(4)

and

bi=1

2(1 −Zi)(5)

where Vand Eare the set of all the nodes and

edges in the graph, Ziis the Pauli-Z operator

acting on the ith qubit and λis the Lagrange

multiplier. The ﬁrst term His the Hamming

weight of the bit string and the second term Cpen

is the penalty term which penalizes every time

two nodes are connected by an edge. This objec-

tive function deﬁnes an unconstrained optimiza-

tion problem which can be solved by the QAOA

and can be implemented using only single- and

two-qubit gates, but it has the disadvantage that

the optimization is performed over both feasible

and infeasible states. Finding the optimal value

for λ, which eﬀectively balances the trade-oﬀ be-

tween optimality and feasibility in the objective

function, can pose a considerable challenge.

2.2 Constrained QAOA

In constrained versions of the QAOA the struc-

ture of the ansatz is altered to ensure that the

variational optimization takes place only over the

set of feasible solutions Hadﬁeld [2018], Hadﬁeld

et al. [2019], whereas the Lagrange multiplier

method includes optimization over a larger set of

states that may not correspond to an independent

set. Since the problem constraints are handled at

the circuit level, the objective function is simply

the Hamming weight operator,

Cobj =H=X

i∈V

bi.(6)

The initial state may be any feasible state or a

superposition of feasible states. The phase sepa-

rator unitary UC(γ):=eiγH is determined by the

objective function. The mixing unitary is spe-

cially designed to ensure that the “independent

X X

Rx(θ)Rzπ

2Ryθ

2Ry−θ

2Rz−π

2

Figure 1: Decomposition of the partial mixers used in

the constrained QAOA for MIS into two multi-controlled

Toﬀolis and single-qubit rotations Barenco et al. [1995].

The partial mixer enforces the MIS constraint by only

performing the single-qubit rotation if all neighbors are

in the |0⟩state.

set” constraint is maintained at all times dur-

ing optimization. Let UM(β):=QjeiβMj, where

Mj=Xj¯

Band we have deﬁned

B:=

ℓ

k=1

bvk,¯

bvk=1 + Zvk

2,(7)

where vkare the neighbors and ℓis the number

of neighbors for the kth node. We can also write

the mixer as

UM(β) =

j=1

Vj(β)

j=1 I+ (e−iβXj−I)¯

B,

(8)

where we have used ¯

vj=¯

bvj. The unitary mixer

above is a product of Npartial mixers Vi, and in

general they may not all commute with each other

[Vi, Vj]̸= 0. The partial mixers are executed on a

digital quantum computer using the circuit shown

in Figure 1.

Additionally, the mixing unitary may be pa-

rameterized by a list of angles β, such that each

partial mixer can have a diﬀerent classical vari-

able as a parameter, and is deﬁned up to a per-

mutation of the partial mixers:

UM(β)≃ PV1(β1)V2(β2)···VN(βN).(9)

To distinguish between the QAOA whose mixing

unitary has a single angle, Eq. (8), or multiple an-

gles, Eq. (9), we denote these cases as SA-QAOA

and MA-QAOA, respectively.

2.3 Dynamic Quantum Variational Ansatz

An extension of the MA-QAOA, called the Dy-

namic Quantum Variational Ansatz (DQVA),

Accepted in Quantum 2024-09-09, click title to verify. Published under CC-BY 4.0. 4

was introduced in Saleem et al. [2023] which

enables a tradeoﬀ between the number of par-

tial mixers and rounds of classical optimization.

The DQVA may be initialized in any superpo-

sition of feasible states, potentially even using

the output of a classical optimization algorithm

|c⟩=|c1c2···cn⟩. This warm-start approach was

recently proposed for Max-Cut and QUBOs in

Egger et al. [2021]. Then, the phase separator

and mixing unitaries are applied to construct the

state,

ψ(γ,α1,...,αp) =

UC(γp)Uσp

M(αp)···UC(γ1)Uσ1

M(α1)|c⟩(10)

where, similarly to Eq. (9), each of the individual

mixers is given by

Uσk

M(αk) =

Vσk(n)ασk(n)

k···Vσk(1) ασk(1)

k(11)

for k= 1,2,··· , p. Here for simplicity we have

ﬁxed all permutations σ1=σ2=··· =σp, and

henceforth drop the permutation index on mixers.

In Saleem et al. [2023] it was found that the in-

creased expressibility of Eq. (11)resulted in im-

proved performance with smaller circuit depth on

constrained optimization problems, and in Her-

rman et al. [2022] similar results were found for

unconstrained problems. The increased express-

ibility of the unitary mixer has further advan-

tages. We can set some of the partial mixers “oﬀ”

by setting αi= 0, eﬀectively reducing the quan-

tum resources required by the ansatz. In this

paper, we control the number of nonzero param-

eters in the variational ansatz, including both the

phase separator γand mixer βparameters, using

a hyperparameter ν.

The ﬁnal component of the DQVA algorithm

is the dynamic ansatz update. This is a classi-

cal outer loop where in every iteration, called a

mixer round, the order of the partial mixers ap-

pearing in Eq. (11)is randomly permuted. Each

mixer round is composed of multiple inner rounds

where the ansatz is initialized with the best in-

dependent set found thus far, variationally op-

timized, and then uses the output of that opti-

mization as the input for the next inner round.

As more and more nodes become part of the in-

dependent set, the ansatz is continually updated

as detailed in Saleem et al. [2023] until the entire

graph has been traversed, increasing the size of

the independent set at each iteration.

The DQVA algorithm has previously been used

in the quantum local search (QLS) approach in

Tomesh et al. [2022a]. In QLS the DQVA is

applied to local neighbourhoods and the whole

graph is traversed neighbourhood by neighbour-

hood, increasing the size of the independent set

at each step. The DQVA was also applied in the

quantum divide and conquer approach in Tomesh

et al. [2023] in which the graph is ﬁrst parti-

tioned and then the DQVA is implemented on

each of the partitions separately. This allows the

potential for distributed computing as well since

each of the partitions can be run in parallel. The

analysis of multi-controlled gate decompositions

presented in this work is complimentary to these

higher-level algorithmic approaches — enabling

more accurate resource estimates for these algo-

rithms under diﬀerent assumptions of the under-

lying native gate set.

3 Multi-controlled Gate Decomposi-

tions

Many quantum algorithms are expressed using

multi-controlled quantum gates Draper et al.

[2004], Chakrabarti and Sur-Kolay [2008], Arra-

zola et al. [2022], Crow et al. [2016], Perlin et al.

[2023]. However, most currently available hard-

ware platforms, like IBM or Rigetti’s supercon-

ducting systems Murali et al. [2019] or IonQ’s

trapped ion systems IonQ [2022], only expose

single- and two-qubit primitive operations to the

user. Thus, to execute large quantum gates on

physical hardware, one needs to use a sequence

of single- and two-qubit gates whose composite

action is equivalent to the larger gate.

Methods for deriving these gate sequences are

known as gate decomposition schemes. By im-

posing various restrictions on the physical system

available to us (e.g. native gate set, number of

available ancilla qubits), we can analyze the re-

sources required to implement various operations

by analyzing the gate complexity of these decom-

positions. We can then compare the resource ef-

ﬁciency between diﬀerent algorithms or diﬀerent

physical systems, building upon the decomposi-

tion schemes given by Barenco et al. in Barenco

et al. [1995].

Accepted in Quantum 2024-09-09, click title to verify. Published under CC-BY 4.0. 5

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

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

10 玖币 0人已下载

立即下载

摘要：

Quantum-classicaltradeoffsandmulti-controlledquantumgatedecompositionsinvariationalalgorithmsTeagueTomesh1,2,NicholasAllen1,3,DanielDilley4,5,andZainH.Saleem51PrincetonUniversity,Princeton,NJ,08540,USA2Infleqtion,Chicago,IL,60604,USA3UniversityofWaterloo,InstituteforQuantumComputing,Waterloo,ONN2L3G...

展开>> 收起<<

Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms.pdf

共21页,预览5页

还剩页未读，继续阅读

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

Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: