Quantum divide and conquer Andrew M. ChildsRobin KothariMatt Kovacs-DeakAarthi SundaramDaochen Wang Abstract

2025-04-26 0 0 745.93KB 24 页 10玖币

侵权投诉

Quantum divide and conquer

Andrew M. Childs∗Robin Kothari†Matt Kovacs-Deak‡Aarthi Sundaram§Daochen Wang¶

Abstract

The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks

a problem of size ninto smaller subproblems (say, acopies of size n/b each), along with some auxiliary

work of cost Caux(n), to give a recurrence relation

C(n)≤a C(n/b) + Caux(n)

for the classical complexity C(n). We describe a quantum divide-and-conquer framework that, in certain

cases, yields an analogous recurrence relation

CQ(n)≤√a CQ(n/b) + O(Caux

Q(n))

that characterizes the quantum query complexity. We apply this framework to obtain near-optimal

quantum query complexities for various string problems, such as (i) recognizing regular languages; (ii)

decision versions of String Rotation and String Suﬃx; and natural parameterized versions of (iii) Longest

Increasing Subsequence and (iv) Longest Common Subsequence.

1 Introduction

Classically, divide and conquer is a basic algorithmic framework that applies widely to many problems (see,

e.g., [Hoa62,KO63,CT65,Str69,CW90,CLRS09,AW21]). This technique solves a problem by recursively

solving smaller instances of the same problem together with some auxiliary problem. In this paper, we

develop a quantum analog of this framework that can provide quantum query complexity speedups relative

to classical computation.

To motivate this investigation, consider a simple application of classical divide and conquer. Consider

the problem of computing the OR function on nbits. The classical deterministic query complexity of this

problem is well known to be n, since an algorithm must read all nbits in the worst case to check if any of

the bits equals 1. This upper bound is trivial since any query problem on nbits can be solved by querying

all nbits, but to illustrate the quantum idea, we ﬁrst consider re-deriving this classical upper bound using

divide and conquer.

It is easy to see that for an n-bit string x,OR(x) = 1 if and only if either OR(xleft) = 1 or OR(xright) = 1,

where xleft and xright are the left and right halves of x. Thus we have divided the original problem into two

smaller instances of the same problem, and given solutions to the two smaller instances, no further queries

need to be made to solve the larger instance. Letting C(n) denote the classical query complexity of this

problem, this argument yields the recurrence relation

C(n)≤2C(n/2),(1)

which, noting C(1) = 1, solves to C(n)≤n, as desired.

Now notice that the last step that combines the solutions of the smaller instances to solve the larger

instance is also an OR function, but on 2 bits, since OR(x) = OR(xleft)∨OR(xright). We know that the

quantum query complexity of the OR function on nbits is O(√n) due to Grover’s algorithm [Gro96], so we

∗University of Maryland. amchilds@umd.edu

†Microsoft Quantum. robin@robinkothari.com

‡University of Maryland. kovacs@umd.edu

§Microsoft Quantum. aarthi.sundaram@microsoft.com

¶University of Maryland. wdaochen@gmail.com

arXiv:2210.06419v1 [quant-ph] 12 Oct 2022

might be tempted to say that the OR of 2 bits should be faster to compute, potentially even quadratically

faster. Thus we might like to write the following recurrence relation for the quantum query complexity Q(n)

of computing the OR function:

Q(n)≤“√2” Q(n/2).(2)

Here the quotes around the “√2” convey that this is not really justiﬁed. First, the complexity of Grover’s

algorithm is not exactly √n, but only √nup to a constant factor. Even if it were exactly √n, Grover’s

algorithm is a bounded-error algorithm, so if used as a subroutine that calls itself many times, the error will

become unbounded very quickly. And of course, it does not make sense to imagine that the query complexity

is a non-integer.

Even though we have just argued that Equation (2) is questionable, if we solve this recurrence anyway,

we ﬁnd Q(n)≤√n.1Up to a multiplicative constant, this is the correct answer for the quantum query

complexity of the OR function on nbits!

This is not a coincidence. As we show in this paper, this can be seen as a simple instance of a quantum

algorithmic framework that we call “quantum divide and conquer.” More generally, a classical divide-and-

conquer algorithm typically yields a recurrence relation of the form

C(n)≤a C(n/b) + Caux(n),(3)

where Caux(n) is the classical query complexity of the auxiliary problem.

The main conceptual takeaway of our paper is that, in many settings, the quantum query complexity

equals (up to a multiplicative constant) the solution, CQ(n), of the analogous recurrence relation,

CQ(n)≤√a CQ(n/b) + Caux

Q(n),(4)

where the quantum query complexity of the auxiliary problem is O(Caux

Q(n)). We show that this framework

easily recovers and improves non-trivial quantum speedups that were previously known. Furthermore, we

show it yields previously unknown quantum speedups that do not seem to be achievable by standard ap-

plications of techniques such as Grover search [Gro96], amplitude ampliﬁcation and estimation [BHMT02],

and quantum walk search [Amb07].

1.1 Results

We apply quantum divide and conquer to the following decision problems, which we have ordered in roughly

increasing diﬃculty. In all of these problems, we are given query access to a string s∈Σaover some set Σ,

i.e., query access to a function f:{1, . . . , a} → Σ, with f(i) = si.

Recognizing regular languages. We recover the key algorithmic result in [AGS19] that is used to upper

bound the quantum query complexity of recognizing star-free languages. (The latter result is, in turn, the

key result used by [AGS19] to establish a quantum query complexity trichotomy for recognizing regular

languages.) In particular, we show that O(√nlog n) quantum queries suﬃce to decide whether a string

x∈ {0,1,2}ncontains a substring of the form 20∗2, i.e., two 2s on either side of an arbitrarily long string of

0s. Having established our framework, the analysis is simpler than that of [AGS19].

String Rotation and String Suﬃx. Let x∈Σnand i∈ {1, . . . , n}. In String Rotation, the problem is

to decide whether the lexicographically minimal rotation of xstarts at i. In String Suﬃx, the problem is

to decide whether the lexicographically minimal suﬃx of xstarts at i. These problems are natural decision

versions of problems studied in [AJ22]. We obtain an ˜

O(√n) upper bound on the quantum query complexity

for these problems, improving the previous best bound of O(n1/2+o(1)), which follows from the algorithms

of [AJ22] for the search versions. Furthermore, the analysis is again simpler using our framework.

1This may be familiar to readers who know the quantum adversary method. However, our divide-and-conquer framework

generalizes this phenomenon to a scenario that cannot be captured using adversary machinery alone, as discussed below.

k-Increasing Subsequence (k-IS). Given a string x∈Σnover some ordered set Σ and an integer k≥1,

the k-IS problem asks us to decide whether xhas an increasing subsequence2of length at least k. We obtain

a bound of ˜

O(√n) for any constant k. The k-IS problem is a natural parameterized version of Longest

Increasing Subsequence (LIS), which is well-studied classically (see, e.g., [Fre75,AD99,SS10,RSSS19]). We

consider this version because the quantum query complexity of LIS is easily seen to be3Ω(n), so we cannot

hope for a quantum speedup without a bound on k. Somewhat surprisingly, any constant bound on kallows

for a quadratic speedup over classical algorithms.

k-Common Subsequence (k-CS). Given two strings x, y ∈Σnover some set Σ and integer k≥1, the

k-CS problem asks us to decide whether xand yshare a common subsequence of length at least k. We

obtain a bound of ˜

O(n2/3) for any constant k. The k-CS problem is a natural parametrized version of

Longest Common Subsequence (LCS), which is well-studied classically (see, e.g., [WF74,LMS98,CLRS09,

AKO10,ABW15,RSSS19]). Again, we consider this version because the quantum query complexity of LCS

is easily seen to be4Ω(n).

Note that LCS is closely connected to Edit Distance (ED), which asks us to compute the number of

insertions, deletions, and substitutions required to convert xinto y. In fact, if substitutions were disallowed,

the edit distance between xand ywould equal ED(x, y)=2n−2LCS(x, y) (a proof can be found in, e.g.,

[AVW21, Lemma 6]).

All of our quantum query complexity upper bounds are tight up to logarithmic factors and represent

quantum-over-classical speedups since the classical (randomized) query complexities of all problems consid-

ered are Ω(n).

1.2 Techniques

To derive the quantum recurrence relation in Equation (4), we employ the quantum adversary method as

an upper bound on quantum query complexity [Rei11,LMR+11]. The adversary quantity Adv(P(n)) is

a real number that can be associated with any query problem P(n) of size n. For convenience, we write

Adv(n):= Adv(P(n)) when Pis clear from context. It is well-known that Adv(n) is upper and lower

bounded by the (two-sided bounded error) quantum query complexity, Q(n), of P(n) up to multiplicative

constants.

If a problem can be expressed as the composition of smaller problems, then the adversary quantity of the

larger problem can be expressed in terms of those of the smaller problems [Rei11,LMR+11]. For example,

suppose P(n) is the OR of acopies of P(n/b) together with another problem Paux(n), corresponding to the

auxiliary work performed in a divide-and-conquer algorithm. Then the composition theorem implies

Adv(n)2≤aAdv(n/b)2+ Adv(Paux(n))2.(5)

(For a more precise statement, see Section 2.) Taking square roots5and using the fact that Adv(Paux(n))

is bounded by O(Qaux(n)), where Qaux(n):=Q(Paux(n)), we obtain precisely Equation (4), i.e.,

Adv(n)≤√aAdv(n/b) + O(Qaux(n)).(6)

We then bound Qaux(n) by constructing an explicit quantum algorithm for the auxiliary work and bounding

its quantum query complexity. Finally, we solve Equation (6) either directly or by appealing to the Master

Theorem [BHS80] to obtain a bound on Adv(n) and hence a bound on Q(n). Note that this bound is

2Recall that a subsequence of a string is obtained by taking a subset of the elements without changing their order. Note

that this is more general than a substring, in which the chosen elements must be consecutive.

3This follows by reduction from a threshold function such as majority [BBC+01]. Given a string z∈ {0,1}n, deﬁne

x∈ {0,1,...,n}nsuch that xi=izifor all i∈ {1,...,n}. Then we can determine the Hamming weight |z|of zby classically

querying z1and adding z1−1 to the length of the LIS of x.

4This also follows by reduction from a threshold function such as majority. Given a string z∈ {0,1}n, deﬁne x= 1n. Then

we can determine the Hamming weight |z|of zas the length of the longest common subsequence of zand x.

5Note that while taking square roots gives a closer analogy with the classical recurrence, in some cases we can get a slightly

tighter bound by instead directly solving the recurrence for Adv(n)2.

insensitive (up to a multiplicative constant) to the constant implicit in O(Qaux(n)), whereas it is highly

sensitive to the constant in front of Adv(n/b).

We emphasize that the recurrence in Equation (6) involves both the adversary quantity and the quantum

query complexity. At a high level, this is why the bound on Q(n) resulting from solving Equation (6) does

not follow directly from adversary techniques alone nor from quantum algorithmic techniques alone. Indeed,

when we solve Equation (6) as a recurrence relation, we mix adversary and algorithmic techniques at each step

of the recursion. In principle, it is possible to use Equation (6) to construct an explicit quantum algorithm

for P(n) because there is a constructive, complexity-preserving, and two-way correspondence between span

programs—whose complexity is characterized by the adversary quantity—and quantum algorithms [Rei09b,

CJOP20,Jef22]. However, this correspondence is involved.

This quantum divide-and-conquer framework allows us to use classical divide-and-conquer thinking to

come up with a classical recurrence relation that we can easily convert to a corresponding quantum recurrence

relation in the form of Equation (6). Bounding Q(n) then reduces to bounding Qaux(n), which can be easier

than the original problem. In our applications to k-IS and k-CS, we bound Qaux(n) by using quantum

algorithms for the i<kversions of these problems, whose query complexities we can bound inductively.

Note that the base cases (k= 1) of these problems are trivial, being equivalent to search and (bipartite)

element distinctness, respectively.

The form of Equation (6) depends on the way we divide and conquer. Strikingly, in our application

to k-CS, we ﬁnd that an optimal (up to logarithmic factors) quantum query complexity can be derived by

breaking the problem into seven parts (so that b= 7) but not fewer. Classically, the number of parts we

break the problem into makes no diﬀerence as any choice leads to an O(n) classical query complexity.

In the discussion above, we have assumed that the OR function relates P(n) to P(n/b) and Paux(n).

However, this is only to simplify our exposition. In fact, we can use quantum divide and conquer for any

function relating P(n) to P(n/b) and Paux(n). Functions that we use to obtain quantum speedups include

combinations of OR and AND. In our application of quantum divide and conquer to k-CS, the function is a

combination of SWITCH-CASE and OR. While SWITCH-CASE alone yields no quantum speedup, our analysis

relies on an adversary composition theorem that we prove, which allows us to preserve the speedup yielded

by OR. We remark that there are many other functions that could yield quantum speedups, but which we

have not yet considered in applications. Examples include EQUAL (which decides if the subproblems all

return the same answer or not) and EXACT2 of 3 (which decides if exactly 2 of 3 subproblems return 1)—see

[Rˇ

S12, Table 1]—and their combinations with OR,AND, and SWITCH-CASE. We leave the consideration of

such functions for future work.

1.3 Related work

The technique of using adversary composition theorems (and their relatives) to establish upper bounds

on quantum query complexity has been applied in several previous works, beginning with the setting of

formula evaluation [Rei09a,Rˇ

S12]. In [Kim13], an adversary composition theorem is used to bound the

quantum query complexity of a function fgiven a bound on that of fcomposed with itself dtimes. More

generally, the adversary quantity has been used to upper bound the quantum query complexity of problems

including k-distinctness [Bel12a], triangle ﬁnding [Bel12b,LMS17], undirected st-connectivity [BR12], and

learning symmetric juntas [Bel14]. In contrast to our work, these prior results typically bound the adversary

quantity using only tools from the adversary world, such as span programs, semideﬁnite programming, and

composition theorems, without constructing quantum algorithms to use as subroutines.

The ﬁrst two application areas of quantum divide and conquer that we consider (recognizing regular

languages and String Rotation and String Suﬃx) arise in [AGS19,AJ22] as discussed above. Turning to

k-IS and k-CS, we ﬁrst note that, despite the importance of these problems, there have been no signiﬁcant

works on their quantum complexities. Directly using Grover search [Gro96] over all possible positions of a

1-witness gives trivial O(n) bounds as soon as k≥2. Directly using quantum walk search [Amb07] also

yields highly sub-optimal bounds of O(nk/(k+1)) for k-IS and O(n2k/(2k+1)) for k-CS.

Classically, LIS and LCS are typically solved using dynamic programming. There are many recent works

on quantum speedups for dynamic programming, e.g., [ABI+19,Abb19,GKMV21,ABI+20,KPV22]. The

main idea of these works is to classically query a part of the input and to repeatedly use the result together

with a quantum algorithm to solve many overlapping subproblems. However, we found it diﬃcult to apply

this idea to k-IS and k-CS.

Given the generality of the results in [AGS19] and the fact that we can recover some of its results, one

might ask if the converse holds, i.e., if [AGS19] can recover our results on k-IS and k-CS. Indeed, the results

of [AGS19] do apply6to k-IS and k-CS when the set size |Σ|is constant. However, under that assumption,

these problems can be easily solved by Grover search [Gro96] and quantum minimum ﬁnding [DH96] using

O(√n) queries. Moreover, k-CS becomes qualitatively easier when |Σ|is constant as its complexity drops to

O(√n), down from the ˜

Θ(n2/3) bound that we establish when |Σ|is unbounded. Note that ˜

Θ(n2/3) is not

in the trichotomy of [AGS19], i.e., not one of Θ(1), ˜

Θ(√n), or Θ(n).

Organization. This paper is organized as follows. We ﬁrst introduce background material and describe

how to use the quantum divide-and-conquer framework for certain scenarios in Section 2. Then we apply

the framework to four string problems in Section 3, obtaining near-optimal quantum query complexities for

each. In particular, we consider recognizing regular languages in Section 3.1, String Rotation and String

Suﬃx in Section 3.2,k-Increasing Subsequence in Section 3.3, and k-Common Subsequence in Section 3.4.

Finally, we conclude by presenting some open problems in Section 4.

2 Framework

In this section we introduce some notation and explain how to apply the quantum divide-and-conquer

framework in speciﬁc scenarios.

Let Ndenote the positive integers. We reserve m, n ∈Nfor positive integers and Σ for a ﬁnite set.

For m∈N, we write [m]:={1, . . . , m}. For any two matrices Aand Bof the same size, A◦Bdenotes

their entrywise product, also known as their Hadamard product. For any matrix A, let (A)ij denote the

element in the ith row and jth column. For a function f:D→E, let its Gram matrix Fbe deﬁned as

(F)xy :=δf(x),f (y)for all x, y ∈D, where δis the Kronecker delta function. For a length-nstring x∈Σn, we

write x[i] for the ith element of xand x[i . . j] for the substring of xthat ranges from its ith to jth elements

(inclusive). We write x(i . . j]:=x[i+ 1 . . j] and x[i . . j):=x[i . . j −1]. When Σ is equipped with a total

order, and x∈Σmand y∈Σn, we write inequalities between xand y(e.g., x≤y) to refer to inequalities

with respect to the lexicographic order.

We write Q(f) for Q1/3(f) (the quantum query complexity of fwith failure probability at most 1/3).

A closely related quantity that is also used widely, and serves as both a lower and upper bound for the

quantum query complexity of function computation, is the adversary quantity, Adv(·).

Deﬁnition 1 (Adversary quantity).Let D,E, and Σbe ﬁnite sets and n∈Nwith D⊆Σn. Let f:D→E

be a function with Gram matrix Fand ∆ = {∆1,...,∆n}with (∆j)x,y∈D= 1 −δxj,yj. Then the adversary

quantity for fis

Adv(f) := max nkΓk:∀j∈[n],kΓ◦∆jk ≤ 1o,

where the maximization is over |D|×|D|real, symmetric matrices Γsatisfying Γ◦F= 0.

The following result connecting Adv(·) and Q(·) will be useful.

Theorem 1 ([HLˇ

S07,LMR+11]).Let f:D→Ebe a function. Then Q(f) = Θ(Adv(f)).

The adversary quantity for a composite function can be expressed in terms of the adversary quantities

of its components. In this work, we speciﬁcally consider cases where (i) g=f1∨f2; (ii) g=f1∧f2;

or (iii) a SWITCH-CASE scenario on functions f:D→Eand {gs:D→ {0,1} | s∈E}deﬁned as

h:= (IF f(x) = s) THEN h(x) = gs(x) for s∈E,x∈D.

Lemma 1 (Adversary composition for OR and AND).Let a, b ∈Nand let Σbe a ﬁnite set. Let f1: Σa→

{0,1}and f2: Σb→ {0,1}. Let g∧, g∨: Σa×Σb→ {0,1}be such that g∧(x, y) = f1(x)∧f2(y)and

g∨(x, y) = f1(x)∨f2(y). Then Adv(g∧)2= Adv(g∨)2≤Adv(f1)2+ Adv(f2)2.

6For example, k-IS can be expressed in ﬁrst-order logic as Wa1<a2<···<ak∃i1,...,ik(i1<···< ik)Vk

j=1 πaj(ij) where πa(i)

indicates that the ith element is a. Expressibility in ﬁrst-order logic is equivalent to being in a star-free language, which can

be recognized with quantum query complexity ˜

Θ(√n) by [AGS19].

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

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

10 玖币 0人已下载

立即下载

摘要：

QuantumdivideandconquerAndrewM.Childs*RobinKothariMattKovacs-DeakAarthiSundaram§DaochenWang¶AbstractThedivide-and-conquerframework,usedextensivelyinclassicalalgorithmdesign,recursivelybreaksaproblemofsizenintosmallersubproblems(say,acopiesofsizen=beach),alongwithsomeauxiliaryworkofcostCaux(n),togi...

展开>> 收起<<

Quantum divide and conquer Andrew M. ChildsRobin KothariMatt Kovacs-DeakAarthi SundaramDaochen Wang Abstract.pdf

共24页,预览5页

还剩页未读，继续阅读

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

Quantum divide and conquer Andrew M. ChildsRobin KothariMatt Kovacs-DeakAarthi SundaramDaochen Wang Abstract

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: