Distributed Quantum Interactive Proofs_2

2025-04-27 0 0 709.69KB 25 页 10玖币
侵权投诉
Distributed Quantum Interactive Proofs
François Le Gall !
Graduate School of Mathematics, Nagoya University, Nagoya, Japan
Masayuki Miyamoto !
Graduate School of Mathematics, Nagoya University, Nagoya, Japan
Harumichi Nishimura !
Graduate School of Informatics, Nagoya University, Nagoya, Japan
Abstract
The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC
2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and
has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an
n
-node network
G
can exchange short messages (called certificates) with a powerful prover. The
goal is to decide if the input (including
G
itself) belongs to some language, with as few turns of
interaction and as few bits exchanged between nodes and the prover as possible. There are several
results showing that the size of certificates can be reduced drastically with a constant number of
interactions compared to non-interactive distributed proofs.
In this paper, we introduce the quantum counterpart of distributed interactive proofs: certificates
can now be quantum bits, and the nodes of the network can perform quantum computation. The
first result of this paper shows that by using quantum distributed interactive proofs, the number of
interactions can be significantly reduced. More precisely, our result shows that for any constant
k
,
the class of languages that can be decided by a
k
-turn classical (i.e., non-quantum) distributed
interactive protocol with
f
(
n
)-bit certificate size is contained in the class of languages that can be
decided by a 5-turn distributed quantum interactive protocol with O(f(n))-bit certificate size. We
also show that if we allow to use shared randomness, the number of turns can be reduced to 3-turn.
Since no similar turn-reduction classical technique is currently known, our result gives evidence of
the power of quantum computation in the setting of distributed interactive proofs as well.
As a corollary of our results, we show that there exist 5-turn/3-turn distributed quantum
interactive protocols with small certificate size for problems that have been considered in prior works
on distributed interactive proofs such as [Kol, Oshman, and Saxena PODC 2018, Naor, Parter, and
Yogev SODA 2020].
We then utilize the framework of the distributed quantum interactive proofs to test closeness of
two quantum states each of which is distributed over the entire network.
2012 ACM Subject Classification
Theory of computation
→
Distributed algorithms; Theory of
computation →Quantum computation theory
Keywords and phrases
distributed interactive proofs, distributed verification, quantum computation
Funding
FLG was supported by the JSPS KAKENHI grants JP16H01705, JP19H04066, JP20H00579,
JP20H04139, JP20H05966, JP21H04879 and by the MEXT Q-LEAP grants JPMXS0118067394 and
JPMXS0120319794. MM was supported by JST, the establishment of University fellowships towards
the creation of science technology innovation, Grant Number JPMJFS2120. HN was supported
by the JSPS KAKENHI grants JP19H04066, JP20H05966, JP21H04879, JP22H00522 and by the
MEXT Q-LEAP grants JPMXS0120319794.
arXiv:2210.01390v1 [quant-ph] 4 Oct 2022
2 Distributed Quantum Interactive Proofs
1 Introduction
1.1 Distributed Interactive Proofs
In distributed computing, efficient verification of graph properties of the network is useful
from both theoretical and applied aspects. The study of this notion of verification in the
distributed setting has lead to the notion of "distributed
NP
" in analogy with the complexity
class
NP
in centralized computation: A powerful prover provides certificates to each node of
the network in order to convince that the network has a desired property; If the property is
satisfied, all nodes must output "accept", otherwise at least one node must output "reject".
This concept of "distributed
NP
" has been formulated in several ways, including proof-labeling
schemes (PLS) [
17
], non-deterministic local decision (NLD) [
5
], and locally checkable proofs
(LCP) [8].
As a motivating example, consider the problem of verifying whether the network is
bipartite or not. While this problem cannot be solved in
O
(1) round without prover [
27
],
it can easily be solved with a prover telling to each node to each part it belongs to, which
requires only a 1-bit certificate per node, and then each node broadcasting this information
to its adjacent nodes (here the crucial point is that if the network is non-bipartite, then at
least one node will be able to detect it). On the other hand, it is known that there exist
properties that require large certificate size to decide: Göös and Suomela [
8
] have shown that
recognizing symmetric graphs (Sym) and non 3-colorable graphs (
3Col
) require Ω(
n2
)-bit
certificates per node in the framework of LCP (which is tight since all graph properties are
locally decidable by giving the O(n2)-bit adjacency matrix of the graph).
To reduce the length of the certificate for such problems, the notion of distributed
interactive proofs (also called distributed Arthur-Merlin proofs) was recently introduced by
Kol, Oshman and Saxena [
16
] as a generalization of distributed
NP
. In this model there are
two players, the prover (often called Merlin), who has unlimited computational power and
sees the entire network but is untrusted (i.e., can be malicious), and the verifier (often called
Arthur) representing all the nodes of the network, who can perform only local computation
and brief communication with adjacent nodes. Generalizing the concept of distributed
NP
,
the nodes are now allowed to engage in multiple turns of interaction with the prover. As for
distributed
NP
, there are two requirements of the protocol: if the input is legal (yes-instance)
then all nodes must accept with high probability (completeness), and if the input is illegal
then at least one node must reject with high probability (soundness).
In the setting of [
16
], each node has access to a private source of randomness, and sends
generated random bits to the prover in Arthur’s turn. For instance, a 2-turn protocol contains
two interactions: Arthur first queries Merlin by sending a random string from each node,
and then Merlin provides a certificate to each node. After that, nodes exchange messages
with adjacent nodes to decide their outputs. The main complexity measures when studying
distributed interactive protocols are the size of certificates provided to each node, the size of
the random strings generated at each node and the size of the messages exchanged between
nodes. Let us denote
dAM
[
k
](
f
(
n
)) the class of languages that have
k
-turn distributed Arthur-
Merlin protocols where Merlin provides
O
(
f
(
n
))-bit certificates, Arthur generates
O
(
f
(
n
))-bit
random strings at each node and
O
(
f
(
n
))-bit messages are exchanged between nodes. Kol et
al. [
16
] showed the power of interaction by giving a
dMAM
(
log n
) =
dAM
[3](
log n
)protocol
for graph symmetry (Sym) and a
dAMAM
(
nlog n
) =
dAM
[4](
nlog n
)protocol for graph
non-isomorphism (GNI), which are known to require Ω(
n2
)-bit certificate in LCP (see
Appendix A for the definition of these problems).
This model has been further studied in several works. Naor, Parter and Yogev [
23
]
F. Le Gall, M. Miyamoto and H. Nishimura 3
showed that any
O
(
n
)-time centralized computation can be converted into a
dMAM
(
log n
) =
dAM
[3](
log n
)protocol. Using this compiler, for instance, they constructed a
dMAMAM
(
log log n
) =
dAM
[5](
log log n
)protocol for
SetEquality
and a special case of
Sym
. Crescenzi, Fraigni-
aud and Paz [
3
] initiated the study of distributed Arthur-Merlin protocols with shared
randomness: in each Arthur’s turn, Arthur generates a random string that can be seen from
all nodes. In order to distinguish the two models we use
dAM
for the (standard) private
randomness setting and
dAMsh
for the shared randomness setting. They showed that
dAM
protocols can simulate
dAMsh
protocols by giving additional
O
(
log n
)-size certificates. The
role of shared randomness was further investigated by Montealegre, Ramírez-Romero and
Rapaport [
21
], who showed the computational power of small-certificate
dAMsh
protocols
without private randomness is relatively weak: for any constant
k
,
dAMsh
[
k
]protocols with
message size
m
can be converted to locally checkable proofs (LCPs) with message size
O(2m+ log n).
Lower bounds on distributed Arthur-Merlin protocols for some concrete problems are
known. Kol, Oshman and Saxena [
16
] showed that if the language
Sym
is in the class
dAM
[2](
f
(
n
)), then
f
(
n
)
∈
Ω(
log log n
). As mentioned in [
6
], this lower bound can actually
be improved to
f
(
n
)
∈
Ω(
log n
). On the other hand, there is no known method to prove
lower bounds when the number of turns is three or more.
1.2 Quantum Interactive Proofs
Quantum interactive proofs (
QIP
) were introduced by Watrous [
29
] in the centralized setting
as a variant of classical interactive proofs (
IP
) in which the verifier can perform polynomial-
time quantum computation (instead of polynomial-time classical computation), and the
prover and verifier can exchange quantum bits (instead of classical bits). Kitaev and Watrous
[
15
] first showed that
QIP
, the class of languages that can be decided by a quantum interactive
protocol with polynomial number of interactions, is contained in
EXP
, the class of languages
decided in exponential time. This containment was improved by Jain, Ji, Upadhyay, and
Watrous [
12
], who showed that
QIP
is actually contained in
PSPACE
, which implies that
QIP
collapses to the complexity class IP (QIP =IP =PSPACE).
While the above result shows that quantum interactive proofs are not more powerful
than classical interactive proofs, there is a striking property of quantum interactive proofs
that is not expected to hold for classical interactive proofs: in the quantum case the number
of interactions can be significantly reduced. More precisely, Watrous first showed that any
language in
PSPACE
can be decided by a three-turn
QIP
protocol [
29
]. After that, Kitaev
and Watrous [
15
] showed that any
QIP
protocol with a polynomial number of interaction
can be parallelized to three turns (
QIP
=
QIP
[3]). Marriott and Watrous [
20
] additionally
showed that the verifier’s turn in
QIP
[3] protocols can be replaced by a 1-bit coin flip
(
QIP
[3]=
QMAM
). Kempe, Kobayashi, Matsumoto, and Vidick [
14
] showed an alternative
proof of QIP =QIP[3].
1.3 Our Results
In this paper we introduce the quantum counterpart of distributed interactive proofs, which
we call distributed quantum interactive proofs (or sometimes distributed quantum interactive
protocols) and write
dQIP
, and show their power. Roughly speaking, distributed quantum
interactive proofs are defined similarly to the classical distributed interactive proofs (i.e.,
distributed Arthur-Merlin proofs) defined above, but the messages exchanged between the
prover and the nodes of the network can now contain quantum bits (qubits), the nodes can
4 Distributed Quantum Interactive Proofs
now do any (local) quantum computation (i.e., each node can apply any unitary transform
to the registers it holds), and each node can now send messages consisting of qubits to its
adjacent nodes. In analogy to the classical case, the main complexity measures when studying
distributed quantum interactive protocols are the size of registers exchanged between the
prover and the nodes, and the size of messages exchanged between the nodes. We give the
formal definition of
dQIP
in Section 2. The class
dQIP
[
k
](
f
(
n
)) is defined as the set of all
languages that can be decided by a
k
-turn
dQIP
protocol where both the size of the messages
exchanged between the prover and the nodes, and the size of the messages exchanged between
the nodes are O(f(n)) qubits.
Our first result is the following theorem.
ITheorem 1. For any constant k≥5,dAM[k](f(n)) ⊆dQIP[5](f(n)).
Theorem 1 shows that by using distributed quantum interactive proofs, the number of
interactions in distributed interactive proofs can be significantly reduced. To prove this
result, we develop a generic quantum technique for turn reduction in distributed interactive
proofs. Since no similar turn-reduction classical technique is currently known, our result
gives evidence of the power of quantum computation in the setting of distributed interactive
proofs as well.
We also show that if we allow to use randomness shared to all nodes (we denote this
model by dQIPsh), the number of turns can be further reduced to three turns.
ITheorem 2. For any constant k≥3,dAM[k](f(n)) ⊆dQIPsh[3](f(n)).
On the other hand, in the classical case, it is known that allowing shared randomness does
not change the class [3]: dAMsh[k](f(n)) ⊆dAM[k](f(n)) for all k≥3.1
As mentioned above, for (classical)
dAM
protocols increasing the number of turns is
helpful to reduce the complexity (in particular, the certificate size) for many problems. Our
result thus shows if we allow quantum resource, such protocols can be simulated in five turns,
and in three turns if we allow shared randomness. More precisely, we obtain the following
corollary (see Appendix A for the precise definitions of these problems and Theorems 12 and
13 in Section 4 for a statement of the corresponding classical results):
ICorollary 3. 1. There exist
adQIPsh[3](log n)protocol for Asym,
adQIPsh[3](log n)protocol for GNI,
adQIPsh[3](log log n)protocol for SetEquality,
adQIPsh[3](log log n)protocol for DSym.
adQIP[5](log n)protocol for GNI.
2.
There exists a constant
δ
such that if a language
L
can be decided in
poly
(
n
)time and
nδspace, then L ∈ dQIP[5](log n)and L ∈ dQIPsh[3](log n).
We also introduce a quantum problem (i.e., the inputs are quantum states) which arises
naturally when considering distributed quantum networks. More specifically, we consider
the following task: There are two quantum states
|ψi
and
|φi
as the inputs, each of which is
distributed over the entire network (each node
u∈V
has
Nu
-qubit of
|ψi
and
|φi
, where
1
In fact, the authors of [
3
] showed
dAMsh
[
k
](
f
(
n
))
⊆dAM
[
k
](
f
(
n
) +
log n
)for all
k≥
1where the
additional
log n
comes from constructing a spanning tree, but for
k≥
3, a spanning tree can be
constructed with
O
(1)-sized messages between the prover and the nodes in three turns [
23
], so
log n
can
be removed.
F. Le Gall, M. Miyamoto and H. Nishimura 5
Pu∈VNu
=
N
). The goal of the task is to measure closeness of these states. We call this
problem
N
-qubit Distributed Quantum Closeness Testing (
DQCTN
). For this task, we show
the following theorem.
ITheorem 4.
There is a
dQIP
[5](
O
(1)) protocol for
DQCTN
, where the completeness and
the soundness conditions are defined as follows:
Completeness:
If
|ψi
=
|φi
and the prover is honest, the protocol is accepted with
probability 1.
Soundness:
If the protocol is accepted with probability 1
−
1
/z
,
dist
(
|ψi,|φi
)
≤p2/z
+
ε
for any small constant ε > 0.
Without the prover, a naive approach is to accumulate all of the input to the leader node,
and perform local operations at the leader node to measure their closeness. Obviously this
approach is inefficient in the following sense: (1) it requires Ω(
D
)-round of communication
where
D
is the diameter of the network; (2) the amount of communication is linear in
N
,
the size of the input quantum states. Theorem 4 means that in the
dQIP
setting, (1) it only
needs 1-round of communication between the nodes; (2) the amount of communication (the
size of messages per edge, and the size of messages between each node and the prover) is
O
(1), regardless of the input size. Note that the main result of the recent paper [
4
] (see
Section 1.5 for their result) immediately shows that if the two input quantum states are hold
by some specific two nodes respectively and there is no input for the other nodes,
DQCTN
in
an
n
-node network can be done with
O
(
N·poly
(
n
)) size of quantum proofs and 1-round of
communication between nodes, in the non-interactive setting. Our setting is more general in
the sense that the input quantum states can be distributed over the entire network.
Lastly, in Appendix G, we show how to transform
dQIP
protocols with two-sided (i.e.,
completeness and soundness) bounded error into
dQIP
protocols with perfect completeness.
We show that if we allow the communication between nodes in the middle of interaction (we
call this model as
dQIPc
), achieving perfect completeness is possible. Thus
dQIPc
protocols
can be converted to 5-turn protocols with perfect completeness using parallel repetition with
a fairly small increase of the message size.
1.4 Organization and Overview of our Approach
We start by considering a more powerful model than
dQIP
, which allows nodes to use a
shared randomness. That is, at each turn the network can send a shared random string of
limited length to the prover. We call this model
dQIPsh
. In Section 3.1, we first show how to
reduce the number of turns by half in the
dQIPsh
model. This is shown by adapting to the
distributed setting the method of Kempe et al. [
14
], which reduces the number of turns of
QIP
by half. More precisely, we show that for any
`≥
1,(4
`
+ 1)-turn
dQIPsh
protocols can
be parallelized to (2
`
+ 1)-turn. The main idea of [
14
] is the following. In the first turn the
honest prover provides the verifier with a snapshot state of at the (2
`
+ 1)-th turn, which
includes the state of its private register and the message register in the original protocol. In
the second turn the verifier flips a fair coin and sends it to the prover. In the remaining turns
they perform the forward or backward simulation of the original protocol, according to the
result of the coin flip. We then go back to the
dQIP
model in Section 3.2 and show how to
reduce the number of turns by half in the
dQIP
model by using the same argument as in the
case of
dQIPsh
, by using two additional turns in order to share the result of the coin flip. We
can thus parallelize (4
`
+ 1)-turn
dQIP
protocols to (2
`
+ 3)-turn. Applying recursively this
approach makes possible to reduce the number of turns down to 7(corresponding to
`
= 2),
but not lower. After that, we focus on how to parallelize 7-turn
dQIP
protocols to 5-turn.
摘要：

DistributedQuantumInteractiveProofsFrançoisLeGall!GraduateSchoolofMathematics,NagoyaUniversity,Nagoya,JapanMasayukiMiyamoto!GraduateSchoolofMathematics,NagoyaUniversity,Nagoya,JapanHarumichiNishimura!GraduateSchoolofInformatics,NagoyaUniversity,Nagoya,JapanAbstractThestudyofdistributedinteractivepro...

展开>> 收起<<
Distributed Quantum Interactive Proofs_2.pdf

共25页,预览5页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：25 页 大小：709.69KB 格式：PDF 时间：2025-04-27

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 25
评分 收藏
分享
立即下载
客服
关注