Bounds on oblivious multiparty quantum communication complexity Fran cois Le Gall Daiki Suruga October 28 2022

2025-04-30 0 0 504.24KB 13 页 10玖币

侵权投诉

Bounds on oblivious multiparty quantum communication complexity

Fran¸cois Le Gall Daiki Suruga

October 28, 2022

Abstract

The main conceptual contribution of this paper is investigating quantum multiparty communication com-

plexity in the setting where communication is oblivious. This requirement, which to our knowledge is satisﬁed

by all quantum multiparty protocols in the literature, means that the communication pattern, and in particular

the amount of communication exchanged between each pair of players at each round is ﬁxed independently of

the input before the execution of the protocol. We show, for a wide class of functions, how to prove strong lower

bounds on their oblivious quantum k-party communication complexity using lower bounds on their two-party

communication complexity. We apply this technique to prove tight lower bounds for all symmetric functions

with AND gadget, and in particular obtain an optimal Ω(k√n) lower bound on the oblivious quantum k-party

communication complexity of the n-bit Set-Disjointness function. We also show the tightness of these lower

bounds by giving (nearly) matching upper bounds.

1 Introduction

1.1 Background

Communication complexity. Communication complexity, ﬁrst introduced by Yao in a seminal paper [1] to

investigate circuit complexity, has become a central concept in theoretical computer science with a wide range

of applications (see [2, 3] for examples). In its most basic version, called two-party (classical) communication

complexity, two players, usually called Alice and Bob, exchange (classical) messages in order to compute a function

of their inputs. More precisely, Alice and Bob are given inputs x1∈ {0,1}nand x2∈ {0,1}n, respectively, and their

goal is to compute a function f: (x1, x2)7→ {0,1}by communicating with each other, with as little communication

as possible.

There are two important ways of generalizing the classical two-party communication complexity: one is to

consider classical multiparty communication complexity and the other one is to consider quantum two-party com-

munication complexity. In (classical) multiparty communication complexity, there are kplayers P1,P2,. . .,Pk,

each player Piis given an input xi∈ {0,1}n. The players seek to compute a given function f: (x1, . . . , xk)7→ {0,1}

using as few (classical) communication as possible.1The other way of generalizing the classical two-party com-

munication complexity is quantum two-party communication complexity, where Alice and Bob are allowed to use

quantum communication, i.e., they can exchange messages consisting of quantum bits. Since its introduction by

Yao [4], the notion of quantum two-party communication complexity has been the subject of intensive research in

the past thirty years, which lead to several signiﬁcant achievements, e.g., [5, 6, 7, 8, 9, 4].

In this paper, we consider both generalizations simultaneously: we consider quantum multiparty communication

complexity for k > 2 parties. This generalization has been the subject of several works [10, 11, 12, 13] but, compared

to the two-party case, is still poorly understood.

Set-Disjointness. One of the most studied functions in communication complexity is Set-Disjointness. For

any k≥2 and any n≥1, the k-party n-bit Set-Disjointness function, written DISJn,k, has for input a k-tuple

(x1, . . . , xk), where xi∈ {0,1}nfor each i∈ {1, . . . , k}. The output is 1 if there exists an index j∈ {1, . . . , n}such

1This way of distributing inputs is called the number-in-hand model. There exists another model, called the number-on-the-forehead

model, which we do not consider in this paper.

arXiv:2210.15402v1 [quant-ph] 27 Oct 2022

that x1[j] = x2[j] = ··· =xk[j] = 1, where xi[j] denotes the j-th bit of the string xi, and 0 otherwise. The output

can thus be written as

DISJn,k(x1, . . . , xk) =

j=1

(x1[j]∧ ··· ∧ xk[j]).

Set-Disjointness plays a central role in communication complexity since a multitude of problems can be analyzed

via a reduction from or to this function (see [14] for a good survey). In the two party classical setting, the

communication complexity of Set-Disjointness is Θ(n): while the upper bound O(n) is trivial, the proof of the lower

bound Ω(n), which holds even in the randomized setting, is highly non-trivial [15, 16]. The k-party Set-Disjointness

function with k > 2 has received much attention as well, especially since it has deep applications to distributed

computing [17]. Proving strong lower bounds on multiparty communication complexity, however, is signiﬁcantly

more challenging than in the two-party model. After much eﬀort, a tight lower bound for k-party Set-Disjointness

was nevertheless obtained in the classical setting: recent works [18, 19] were able to show a lower bound Ω(kn) for

DISJn,k, which is (trivially) tight.

In the quantum setting, Buhrman et al. [6] showed that the two-party quantum communication complexity of the

Set-Disjointness function is O(√nlog n), which gives a nearly quadratic improvement over the classical case. The

logarithmic factor was then removed by Aaronson and Ambainis [20], who thus obtained an O(√n) upper bound. A

matching lower bound Ω(√n) was then proved by Razborov [21]. For k-party quantum communication complexity,

an O(k√nlog n) upper bound is easy to obtain from the two-party upper bound from [6].2An important open

problem, which is fundamental to understand the power of quantum distributed computing, is showing the tightness

of this upper bound. In view of the diﬃculty in proving the Ω(kn) lower bound in the classical setting, proving a

Ω(k√n) lower bound in the quantum setting is expected to be challenging.

1.2 Our contributions

Our model. The main conceptual contribution of this paper is investigating quantum multiparty communication

complexity in the setting where communication is oblivious. This requirement means that the communication

pattern, and in particular the amount of communication exchanged between each pair of players at each round is

ﬁxed independently of the input before the execution of the protocol. (See Section 2.1 for the formal deﬁnition.) This

requirement is widely used in classical networking systems (e.g., [22, 23, 24]) and classical distributed algorithms

(e.g., [25]), and to our knowledge is satisﬁed by all known quantum communication protocols (for any problem)

that have been designed so far. It has also been considered in the quantum setting by Jain et al. [26, Result 3],

who gave an Ω(n/r2) bound on the quantum communication complexity of r-round k-party oblivious protocols for

a promise version of Set-Disjointness.

Our results. The main result of this paper holds for a class of functions which has a property that we call

k-party-embedding. We say that a k-player function fkis a k-party-embedding function of a two-party function f2

if the function f2can be “embedded” in fkby embedding the inputs of f2in any position among the inputs of

fk. Many important functions such as any k-party symmetric function (including as important special cases the

Set-Disjointness function DISJn,k and the k-party Inner-Product function) or the k-party equality function have

this property. For a formal deﬁnition of the embedding property, we refer to Deﬁnition 2 in Section 3. Our main

result is as follows.

Theorem 1 (informal) Let fkbe a k-party function that is a k-party-embedding function of a two-party function

f2. Then the oblivious k-party quantum communication complexity of fkis at least ktimes the two-party quantum

communication complexity of f2.

Theorem 1 enables us to prove strong lower bounds on oblivious quantum k-party communication complexity

using the quantum two-party communication complexity. 3This is useful since two-party quantum communication

2We will show later (in Theorem 3 in Section 5) how to obtain an improved O(k√n) upper bound based on the protocol from [20].

3Note that in the two-party setting, the notions of oblivious communication complexity and non-oblivious communication complexity

essentially coincide, since any non-oblivious communication protocol can be converted into an oblivious communication protocol by

increasing the complexity by a factor at most two. To see this, without loss of generality assume that each player sends only one qubit

complexity is a much more investigated topic than k-party quantum communication complexity, and many tight

bounds are known in the two-party setting. For example, we show how to use Theorem 1 to analyze the oblivious

quantum k-party communication complexity of DISJn,k and obtain a tight Ω(k√n) bound:

Corollary 1. In the oblivious communication model, the k-party quantum communication complexity of DISJn,k is

Ω(k√n).

More generally, Theorem 1 enables us to derive tight bounds for the oblivious quantum k-party communication

complexity of arbitrary symmetric functions. Since symmetric functions play an important role in communication

complexity [27, 28, 21, 29, 30], our results might thus have broad applications. Additionally, we also give lower

bounds for non-symmetric functions that have the k-party-embedding property, such as the equality function. Our

results are summarized in Table 1.

To complement our lower bounds, we show tight (up to possible poly-log factors) upper bounds for these

functions. The upper bounds are summarized in Table 1 as well. Note that if we apply our generic O(klog n·Gn(f))

bound in Table 1 to DISJn,k, we only get the upper bound O(klog n·√n). We thus prove directly an optimal

O(k√n) upper bound (Theorem 3) by showing how to adapt the optimal two-party protocol from [20] to the k-party

setting.

Functions 2-party protocols k-party oblivious protocols

Lower Upper Lower Upper

Symmetric functions Ω(Gn(f)) O(log n·Gn(f)) Ω(k·Gn(f)) O(klog n·Gn(f))

in [21] in [21] Proposition 3 Theorem 4

Set-Disjointness Ω(√n)O(√n) Ω(k√n)O(k√n)

in [21] in [20] Corollary 1 Theorem 3

Set-Disjointness ˜

Ω(n/M)O(n/M)˜

Ω(k·n/M)O(k·n/M)

in M-round

(M≤O(√n)) in [31] (folklore) Proposition 5 Corollary 2

Equality function Ω(1) O(1) Ω(k)O(k)

(trivial) e.g., [2] Proposition 4 Proposition 6

Table 1: Our results for oblivious quantum k-party communication complexity, along with known bounds for the

two-party setting. For a symmetric function f, the notation Gn(f) refers to the quantity deﬁned in Equation (1).

2 Models of Quantum Communication

Notations: All logarithms are base 2 in this paper. We denote [k] = {1, . . . , k}. For any set Xand k≥1,

Xk:= X × ··· × X

| {z }

Here we formally deﬁne the quantum multiparty communication model. As mentioned in Section 1.2, this

communication model satisﬁes the oblivious routing condition (or simply the oblivious condition), meaning that the

number of qubits used in communication at each round is predetermined (independent of inputs, private randomness,

public randomness and outcome of quantum measurements). Since details of the model are important especially

when proving lower bounds, we explain the model in detail below.

2.1 Quantum multiparty communication model

In k-party quantum communication model, at each round, players are allowed to send quantum messages4to all of

the players but the number of qubits used in communication is predetermined. This condition is called oblivious.

at each round.

4Trivially, players can send classical messages using quantum communication in this communication model.

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

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

10 玖币 0人已下载

立即下载

摘要：

BoundsonobliviousmultipartyquantumcommunicationcomplexityFrancoisLeGallDaikiSurugaOctober28,2022AbstractThemainconceptualcontributionofthispaperisinvestigatingquantummultipartycommunicationcom-plexityinthesettingwherecommunicationisoblivious.Thisrequirement,whichtoourknowledgeissatisedbyallquantum...

展开>> 收起<<

Bounds on oblivious multiparty quantum communication complexity Fran cois Le Gall Daiki Suruga October 28 2022.pdf

共13页,预览3页

还剩页未读，继续阅读

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

Bounds on oblivious multiparty quantum communication complexity Fran cois Le Gall Daiki Suruga October 28 2022

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: