Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm Yunlong Yu1 2Chenfeng Cao3Xiang-Bin Wang1Nic Shannon4and Robert Joynt5 2

2025-05-03 0 0 989.65KB 18 页 10玖币

侵权投诉

Solution of SAT Problems with the Adaptive-Bias Quantum Approximate

Optimization Algorithm

Yunlong Yu,1, 2 Chenfeng Cao,3Xiang-Bin Wang,1Nic Shannon,4and Robert Joynt5, 2

1State Key Laboratory of Low Dimensional Quantum Physics, Department of Physics,

Tsinghua University, Beijing 100084, China

2Kavli Institute for Theoretical Sciences, University of Chinese Academy of Sciences, Beijing, China

3Department of Physics, The Hong Kong University of Science and Technology,

Clear Water Bay, Kowloon, Hong Kong, China

4Theory of Quantum Matter Unit, Okinawa Institute of Science and

Technology Graduate University, Onna-son, Okinawa 904-0412, Japan

5Department of Physics, University of Wisconsin–Madison,

1150 University Avenue, Madison, Wisconsin 53706, USA

(Dated: April 26, 2023)

The quantum approximate optimization algorithm (QAOA) is a promising method for solving cer-

tain classical combinatorial optimization problems on near-term quantum devices. When employing

the QAOA to 3-SAT and Max-3-SAT problems, the quantum cost exhibits an easy-hard-easy or

easy-hard pattern respectively as the clause density is changed. The quantum resources needed in

the hard-region problems are out of reach for current NISQ devices. We show by numerical simula-

tions with up to 14 variables and analytical arguments that the adaptive-bias QAOA (ab-QAOA)

greatly improves performance in the hard region of the 3-SAT problems and hard region of the Max-

3-SAT problems. For similar accuracy, on average, ab-QAOA needs 3 levels for 10-variable 3-SAT

problems as compared to 22 for QAOA. For 10-variable Max-3-SAT problems, the numbers are 7

levels and 62 levels. The improvement comes from a more targeted and more limited generation

of entanglement during the evolution. We demonstrate that classical optimization is not strictly

necessary in the ab-QAOA since local ﬁelds are used to guide the evolution. This leads us to pro-

pose an optimization-free ab-QAOA that can solve the hard-region 3-SAT and Max-3-SAT problems

eﬀectively with signiﬁcantly fewer quantum gates as compared to the original ab-QAOA. Our work

paves the way for realizing quantum advantages for optimization problems on NISQ devices.

I. INTRODUCTION

We are in the Noisy Intermediate-Scale Quantum

(NISQ) era for quantum computing [1]. NISQ devices

such as Sycamore [2] and Zuchongzhi [3] have demon-

strated a quantum advantage on the random circuit

sampling problem, but this problem is far from prac-

tical applications. Quantum optimization algorithms,

such as the quantum adiabatic algorithm(QAA) [4–8]

and the quantum approximate optimization algorithm

(QAOA) [9,10], or the variational quantum algorithm

(VQA) [11–16] would have much wider impact, if they

could also demonstrate some quantum advantage. There

is hope for this in cases where one has a VQA, in which an

outer classical optimizer is employed to train a sequence

of parameterized quantum circuits. If each such circuit

has relatively low depth, then noise may be minimized.

The QAOA aims to solve combinatorial optimization

problems and even the lowest depth version has the po-

tential to establish quantum advantages [17]. The QAOA

is a generalization of the QAA [9], in which the schedule

of adiabatic evolution can be modiﬁed to produce optimal

results. For the standard QAOA, it has been experimen-

tally implemented [18–21]. There are encouraging results

of the QAOA on the MaxCut problems [9,10,18,22–

25]. Simulations of the QAOA give solutions for MaxCut

problems on sizes up to 20 vertices [10] with the standard

method and up to 54 qubits with a neural network based

method [25]. There have been experimental demonstra-

tions in superconducting systems [18] for 23-qubit graph

MaxCut problems. The QAOA seems to be eﬀective for

MaxCut problems in the sense of greatly improving on

naive adiabatic algorithms. However, there is no evidence

to date of a speedup over classical algorithms. In this pa-

per we do not attempt to give such evidence. Rather we

seek to improve the QAOA to make it more competitive.

For the MaxCut problem we have shown a computa-

tional speedup over the QAOA when adaptive bias ﬁelds

are introduced, a modiﬁcation called the ab-QAOA [26].

In this paper we pinpoint a problem where QAOA ap-

pears to have diﬃculties, and show that the ab-QAOA

greatly outperforms the QAOA. We use the resulting nu-

merical data to pinpoint the strengths of the ab-QAOA.

Speciﬁcally, the QAOA encounters diﬃculties when ap-

plied to random 3-SAT problems [27] and random Max-3-

SAT problems [28]. These problems have been intensely

studied in the framework of classical algorithms [29–34].

Much is known about their complexity. A SAT problem

or its optimization version Max-SAT problem is deﬁned

in terms of nBoolean variables and mclauses. In the

classical computing context, the cost for a given accuracy

varies with the clause density α=m/n. As αincreases,

there is an easy-hard-easy pattern in the random 3-SAT

problems and an easy-hard pattern in the random Max-

3-SAT problems [30–32]. Even for the 10-variable 3-SAT

problems [27] and 6-variable Max-3-SAT problems [28],

arXiv:2210.02822v3 [quant-ph] 25 Apr 2023

the same pattern is evident in the QAOA: in the hard

regions, a very large number of levels is required to ob-

tain an accurate ground state. This means that such

problems are out of reach of the QAOA on current NISQ

devices [18], and prospects are dim for the near future.

It is intriguing that the same easy-hard patterns are evi-

dent in both the QAOA and the classical algorithms, and

that, as we will show, the patterns are nearly absent in

the ab-QAOA.

In the hard-region Max-3-SAT problems, this lack of

convergence in the QAOA is known as the reachability

deﬁcits [28,35]. In physics terms, one can track this

back to a large amount of frustration in the Ising vari-

ables. This happens locally when a triangle of spins has

antiferromagnetic interactions and similar problems re-

peat on multi-variable sets [36]. The overwhelming over-

head of QAOA in the hard-region Max-3-SAT problems,

i.e. the reachability deﬁcits, is not strictly related to

barren plateaus [37–44], deﬁned to be when the variance

of the gradients vanishes exponentially with the system

size n, making the cost function hard to train. Reacha-

bility deﬁcits can occur even in the absence of the barren

plateaus, e.g. for large clause density αwith a ﬁxed n.

Nevertheless, the hard-region SAT problems do seem to

exhibit a small variance of the energy gradients [27].

There is intense research activity to further improve

the performance of QAOA. This includes heuristic ini-

tialization strategies [10,45], modiﬁcations of the mix-

ing Hamiltonian [26,46,47], adjusting the cost func-

tion [48,49], the warm-start strategy [50], utilizing adi-

abaticity [51,52] and using machine learning [53]. How-

ever, little is known about their performances on the

easy-hard-easy or easy-hard transitions on the relevant

SAT problems.

In the ab-QAOA, longitudinal adaptive bias ﬁelds are

incorporated into the mixing Hamiltonian, which are up-

dated based on the expectation values of the Pauli Z

operators [26]. The ab-QAOA is a generalization of the

QAOA and, as stated above, a substantial and scalable

speedup over the QAOA on the MaxCut problem has

been observed. Furthermore, unlike most other adaptive

QAOA variants [47,54], the ab-QAOA requires no more

measurements than the QAOA.

The three main outcomes of this paper are as follows.

1. We show that the ab-QAOA improves over the

QAOA for certain SAT problems with easy-hard-

easy or easy-hard patterns where QAOA does not

perform well. Our strategy is to ﬁrst demonstrate

the speedup of the ab-QAOA over the QAOA for

the relevant SAT problems.

2. We analyze the characteristics of the results and

increase our understanding of the reasons for the

improved performance of the ab-QAOA.

3. We propose an optimization-free ab-QAOA to re-

duce the overhead of gradient calculations and show

that the easy-hard-easy and easy-hard transitions

are not evident in this optimization-free version.

The fact that the ab-QAOA is less subject to the well-

known easy-hard-easy or easy-hard transitions is the ev-

idence that it is qualitatively superior to the QAOA.

Taken together, these features mean that the ab-QAOA

is a considerable step forward. None the less these im-

provements on the QAOA do not imply by themselves

that our algorithm produces a speedup of classical algo-

rithms for SAT problems. Establishing quantum advan-

tages in this context would require a separate analysis,

which lies beyond the scope of the present work.

The paper is organized as follows. In Sec. II, we will

give a detailed description of the QAOA and ab-QAOA,

including some modiﬁcations of the ab-QAOA relative to

the version in Ref. [26]. In Sec. III, a discussion of the

relevant details of the special version of 3-SAT or Max-

3-SAT problems considered in this work , the 1-3-SAT+

or Max-1-3-SAT+problems and the easy-hard-easy or

easy-hard patterns can be found. In Sec. IV, the relative

performances of QAOA and ab-QAOA on the 1-3-SAT+

and Max-1-3-SAT+problems are given. In Sec. Vwe an-

alyze the advantages of the ab-QAOA: its targeted nature

of the entanglement in the evolution, which is related to

many-body localization and the increased adiabaticity in

the discrete time evolution. In Sec. VI, we demonstrate

that an optimization-free version of the ab-QAOA can

solve the hard-region 1-3-SAT+or Max-1-3-SAT+prob-

lems eﬀectively and with much fewer quantum resources.

Our conclusions are summarized in Sec. VII.

II. ADAPTIVE-BIAS QUANTUM

APPROXIMATE OPTIMIZATION ALGORITHM

The standard QAOA is a quantum-classical hybrid al-

gorithm to solve the combinatorial problems [9]. The

problem is encoded in the n-qubit cost Hamiltonian HC,

whose ground state is the desired solution. In the cases

investigated to date, HCis a classical Ising model that

only contains Pauli Zoperators [55]. The quantum part

of the standard QAOA starts from |ψs

0i, the ground state

of the mixing Hamiltonian Hs

M=PjXj, where Xjis the

Pauli Xoperator acting on jth qubit. The unitary op-

erators exp(−iβkHs

M) and exp(−iγkHC) are alternately

applied to |ψs

0iptimes, where pis the level. The output

state of the QAOA is,

|ψs

f(~γ, ~

β)i=

k=1

e−iβkHs

Me−iγkHC|ψs

0i.(1)

Here we use the vector expression ~γ, ~

βto represent a

set of parameters {γ1,··· , γp}and {β1,··· , βp}. The

operators with subscript kare always on the left of those

with k−1. The classical part of the QAOA is the iterative

optimization of ~γ and ~

βaccording to the measurement

of hHCi, the expectation value of HCin |ψs

f(~γ, ~

β)i. Note

that whether |ψs

0iis taken to be |−i⊗nor |+i⊗nhas

no eﬀect on the classical optimization procedure, since

(~γ, ~

β) with |−i⊗nyields the same hHCias (~γ, −~

β) with

|+i⊗n[26].

The recently proposed ab-QAOA is a generalization

of the QAOA [26]. Local longitudinal bias ﬁelds ~

{h1, h2, ..., hn}are incorporated into the mixing Hamil-

tonian, giving,

Hab

M(~

h) = X

Xj−hjZj

q1 + h2

,(2)

where Zjis the Pauli Zoperator acting on the jth qubit.

The choice of the hjis discussed below. The starting

state |ψab

0iis always reinitialized to be the ground state

of Hab

M. This is the key feature of the ab-QAOA that

gives its advantages over the QAOA, as will be discussed

in Sec. V. Thus the output state of the ab-QAOA is,

|ψab

f(~γ, ~

β,~

h)i=

k=1

e−iβkHab

M(~

h)e−iγkHC|ψab

0(~

h)i.(3)

The nextra bias ﬁelds parameters ~

hare not opti-

mized, but rather updated according to the prescription

hj→hj−`(hj− hψab

f|Zj|ψab

fi) in each iteration. `is

the learning rate and we take to be `= 0.4 in this pa-

per. ~γ and ~

βare optimized in the usual way based on

hHCi. Since the energy measurement is in the Zba-

sis, hψab

f|Zj|ψab

fican be obtained without any additional

overhead. When hj→0 and `→0, the ab-QAOA is

equivalent to the QAOA. A schematic the of ab-QAOA

algorithm is shown in Fig. 1.

In Eq. (2), the Schmidt norm of the operator on the jth

qubit is normalized to identity (it squares to the identity

operator). This has the advantage that each βkcan be

restricted to the interval [0, π], unlike in Ref. [26]. On

the jth qubit, we deﬁne the rotation angle djwith the

relationships,

cos dj=1

q1 + h2

,sin dj=hj

q1 + h2

,(4)

and the rotation operator around the ˆyaxis is Rj

y(dj) =

exp(−idjYj/2), where Yjis the Pauli Yoperator on qubit

j. Eq. (2) can then be rewritten as,

Hab

M(~

h) = X

y(dj)XjRj†

y(dj),

=˜

Ry(~

d)Hs

M˜

R†

y(~

d),

(5)

where ˜

Ry(~

d) = NjRj

y(dj). The [0, π] period of βk[9] is

not aﬀected by the update of the bias ﬁelds. The eigen-

values of HCare integers for the models considered in

this paper. Hence γkcan be restricted to [0,2π]. The ab-

QAOA starting state |ψab

0ican be obtained by rotating

|0i⊗naround ˆyaxis in contrast with applying Hadamard

gates to |0i⊗nfor |ψs

0iin the QAOA. Besides the ini-

tial state preparation, no additional quantum gates are

needed to prepare a plevel |ψab

ficompared with |ψs

fi[26],

so again there is no additional overhead.

The energy landscapes of the ab-QAOA at high lev-

els are generally complicated. A good initial guess of

(~γ, ~

β,~

h) can help to reduce the searching space and speed

up the convergence of the classical optimization. Several

heuristic initialization strategies have been proposed for

the QAOA [10,45]. In this paper we modify the Trot-

terized quantum annealing (TQA) initialization strat-

egy [45] as discussed below and in Algorithm 1and the

Fourier strategy [10] as discussed in Appendix Ato make

them more eﬃcient. These methods are then used for

both the QAOA and ab-QAOA in order to compare them

on an equal basis.

Combining the ideas of the TQA method in [45] and

the Fourier strategy in [10], we propose a modiﬁed TQA

method. In level p, the optimization starts from Rpoints

in parallel. Among Roptimized results, the lowest energy

with the corresponding optimal state are taken to be the

outputs in this level as shown in Fig. 1. In the Rinitial

points, the components of all the bias ﬁeld parameters

hr}are randomly chosen from {1,−1}. The ﬁrst set

(~γ1,~

β1) is initialized with the original TQA method and

the other sets diﬀer from (~γ1,~

β1) by a random amount

according to the scheme shown in Algorithm 1. This

modiﬁed TQA is applied to the ab-QAOA and the QAOA

(where the bias ﬁelds and the learning rate `are initial-

ized to be 0). The source codes of this modiﬁed TQA

method are available in [56].

Algorithm 1: Modiﬁed TQA method for

ab-QAOA

Input: level p, total number of samples R

Output: Rinitial points for optimization

for r= 1 to Rdo

Randomly generate bias ﬁelds parameters ~

hrwith

each components to be 1 or −1.

if ris 1 then

Initialize the components of ~γrand ~

βr

according to a linear schedule,

γr

k=k−1

pδt,

βr

k= (1 −k−1

p)δt.

(6)

else

Add some random numbers to the components

of ~γ1and ~

β1,

γr

k=γ1

k+ Ran(γ1

k),

βr

k=β1

k+ Ran(β1

k),(7)

end

Return: Rinitial points {(~γr,~

βr,~

hr)}.

In Algorithm 1, the superscript rruns from 1 to Rand

Yes

Construct 

 =







and 

 

Prepare 

 =







 

Measure in basis and obtain 

Estimate the gradients of each 

and 



Update ,

with gradient-based optimizer

update with 

=

 (

 )

Output and 

 

Output and 

 

Output and 

 

input (,

,)

convergence?

input (,

,)

input (,

,)

optimization



Output the best 

in and the

corresponding |





Figure 1. A schematic of the optimization procedure of the adaptive-bias quantum approximate optimization algorithms (ab-

QAOA) in level p. The optimization of Rsamples can be done in parallel and the lowest energy among Roptimized results

and the corresponding state |ψab

fiare the outputs in this level. For a single sample r, in each optimization iteration, the

updates of ~γ and ~

βare diﬀerent from ~

h. To determine the direction of γkor βkin next iteration, additional preparations and

measurements of |ψab

fiwith slightly moved γkor βkare needed. However, this overhead is not necessary for hj, whose direction

is determined by hZji. This schematic also applies to the QAOA if we set hj= 0 and `= 0.

labels the diﬀerent points of the initialization and the

subscript kmeans the kth component in the vector. The

random number Ran(u) is a normally-distributed number

multiplied by a rescaled factor ξ, Ran(u) = ξNorm(0, u2),

where 0 is the mean value and u2is the variance. In our

calculations, δt =ξ= 0.6 and R= 10.

III. SAT PROBLEMS

A satisﬁability (SAT) problem is deﬁned in terms

of nBoolean variables {xj}n

j=1 taking values from

{0 (False),1 (True)}and mclauses {Ca}m

a=1 [29]. The

negation of variable xjis xj= 1 −xj. A literal yjis

either a variable or its negation xj,i.e. yj∈ {xj, xj}. A

clause Cacan be written as some literals connected by

logical OR (∨), for example C1=y1∨y2∨y3. In the

usual SAT problem a clause Cais satisﬁed if and only if

at least one literal takes value 1. A SAT problem can be

represented by the combination of mclauses connected

by logical AND (∧),

F=C1∧C2∧ ··· ∧ Cm,(8)

which is called conjunctive normal form (CNF). The con-

junctive normal form Fis satisﬁed if and only if all

clauses {Ca}m

a=1 are satisﬁed.

The SAT problem is a decision problem, whose goal is

to answer the question whether there exits an assignment

of {xj}n

j=1 such that the formula Fis satisﬁed (SAT)

or not (UNSAT). The corresponding optimization ver-

sion is the Max-SAT problem which aims to ﬁnd the as-

signment that violates the smallest number of clauses.

Generally, in the Max-SAT problem, each clause can be

assigned a weight and the aim of such weighted Max-

SAT problem is to ﬁnd the assignment that minimizes

the sum of all the weights in the unsatisﬁed clauses [34].

We consider a modiﬁed version of 3-SAT called the 1-

3-SAT+problem, in which each clause contains exactly

3 positive literals, where the positive literal means a lit-

erature yjonly represents the positive variable xj, and

a satisﬁed clause contains exactly one true literal. This

problem is NP-complete in general while its optimization

version Max-1-3-SAT+and weighted Max-1-3-SAT+are

NP-hard [33,34].

Penalty terms are introduced to convert the 1-3-SAT+

problem or Max-1-3-SAT+problem to an Ising cost

Hamiltonian [55,57]. Finding the solution for the origi-

nal problem is equivalent to ﬁnding the ground energy or

the ground state of an Ising-type Hamiltonian. Note that

the QAOA and ab-QAOA are able to solve both Max-1-

3-SAT+and 1-3-SAT+problems. In the former problem,

we need to ﬁnd the exact ground state, while in the lat-

ter problem, we just need to know whether the ground

energy is smaller than a threshold Eth (SAT) or not (UN-

SAT) [27], where the threshold Eth is 0.5 in this paper.

The penalty terms for 1-3-SAT+problems are [27,55,57],

HC=

a=1

(ya1+ya2+ya3−1)2,(9)

where yaj is the jth positive literal in the ath clause Ca.

A satisﬁed clause with only one true literal contributes 0

in the penalty terms in Eq. (9) and an unsatisﬁed clause

contributes 1 or 4. The values 1 and 4 have little eﬀect in

the process of ﬁnding solutions since whether the problem

is SAT or UNSAT is only determined by whether HC= 0

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

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

10 玖币 0人已下载

立即下载

摘要：

SolutionofSATProblemswiththeAdaptive-BiasQuantumApproximateOptimizationAlgorithmYunlongYu,1,2ChenfengCao,3Xiang-BinWang,1NicShannon,4andRobertJoynt5,21StateKeyLaboratoryofLowDimensionalQuantumPhysics,DepartmentofPhysics,TsinghuaUniversity,Beijing100084,China2KavliInstituteforTheoreticalSciences,Univ...

展开>> 收起<<

Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm Yunlong Yu1 2Chenfeng Cao3Xiang-Bin Wang1Nic Shannon4and Robert Joynt5 2.pdf

共18页,预览4页

还剩页未读，继续阅读

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

Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm Yunlong Yu1 2Chenfeng Cao3Xiang-Bin Wang1Nic Shannon4and Robert Joynt5 2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: