Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications_2

2025-04-27 0 0 742.54KB 25 页 10玖币

侵权投诉

Distributed Merlin-Arthur Synthesis of Quantum

States and Its Applications

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 generation and veriﬁcation of quantum states are fundamental tasks for quantum information

processing that have recently been investigated by Irani, Natarajan, Nirkhe, Rao and Yuen [CCC

2022], Rosenthal and Yuen [ITCS 2022], Metger and Yuen [FOCS 2023] under the term state

synthesis. This paper studies this concept from the viewpoint of quantum distributed computing,

and especially distributed quantum Merlin-Arthur (dQMA) protocols. We ﬁrst introduce a novel

task, on a line, called state generation with distributed inputs (SGDI). In this task, the goal is

to generate the quantum state

U|ψ⟩

at the rightmost node of the line, where

|ψ⟩

is a quantum

state given at the leftmost node and

is a unitary matrix whose description is distributed over

the nodes of the line. We give a dQMA protocol for SGDI and utilize this protocol to construct

a dQMA protocol for the Set Equality problem studied by Naor, Parter and Yogev [SODA 2020],

and complement our protocol by showing classical lower bounds for this problem. Our second

contribution is a dQMA protocol, based on a recent work by Zhu and Hayashi [Physical Review A,

2019], to create EPR-pairs between adjacent nodes of a network without quantum communication.

As an application of this dQMA protocol, we prove a general result showing how to convert any

dQMA protocol on an arbitrary network into another dQMA protocol where the veriﬁcation stage

does not require any quantum communication.

2012 ACM Subject Classiﬁcation Theory of computation

→

Distributed algorithms; Theory of

computation →Quantum computation theory

Keywords and phrases distributed quantum Merlin-Arthur, distributed veriﬁcation, quantum com-

putation

1 Introduction

While quantum computational complexity has so far mostly investigated the complexity

of classical problems (e.g., computing Boolean functions) in the quantum setting, recent

works [

] have started investigating the complexity of quantum problems

(e.g., generating quantum states). For instance, Ji, Liu and Song [

] and Kretschmer [

]

have investigated the concept of quantum pseudorandom states from complexity-theoretic

and cryptographic perspectives. Irani, Natarajan, Nirkhe, Rao, and Yuen [

] have made

in-depth investigations of the complexity of the state synthesis problem in a setting ﬁrst

introduced by Aaronson [

] where the goal is to generate a quantum state by making queries

to a classical oracle encoding the state. Rosenthal and Yuen [

] and Metger and Yuen [

]

have considered interactive proofs for synthesizing quantum states (and also for implementing

unitaries). Here the main goal is to generate complicated quantum states (e.g., quantum

states described by an exponential-size generating quantum circuit) eﬃciently with the help

of an all-powerful but untrusted prover. Note that in settings where an all-powerful prover

is present, the task of quantum state synthesis is closely related to the task of quantum

state veriﬁcation (since the prover can simply send the quantum state that needs to be

arXiv:2210.01389v2 [quant-ph] 10 Aug 2023

2 Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications

synthesized).

In this paper, we investigate the task of state generation and veriﬁcation in the setting of

quantum distributed computing. Quantum distributed computing is a fairly recent research

topic: despite early investigations in the 2000s and the 2010s [

], it is only in

the past ﬁve years that signiﬁcant advances have been done in understanding the power of

quantum distributed algorithms [

]. Fraigniaud, Le Gall, Nishimura,

and Paz [

], in particular, have investigated the power of distributed quantum proofs in

distributed computing, which is the natural quantum version of the concept of distributed

classical proofs (also called locally-checkable proofs [

] or proof-labeling schemes [

]): each

node of the network receives, additionally to its input, a quantum state (called a quantum

proof) from an all-powerful but untrusted party called the prover. The main result from [

]

shows that there exist classical problems that can be solved by quantum protocols using

quantum proofs of length exponentially smaller than in the classical case.

We present two main results about state generation and veriﬁcation in the setting where

an all-powerful but untrusted prover helps the nodes in a non-interactive way, and apply

these results to design new quantum protocols for concrete problems studied recently in

[10, 35].

1.1 First result and applications: State Generation with Distributed

Inputs

One of the main conceptual contributions of this paper is introducing the following problem:

In a network of

+ 1 nodes

v0, v1, . . . , vr

, node

is given as input an

-qubit quantum

state

|ψ⟩

. The goal is to generate the quantum state

U|ψ⟩

at node

, where

is a unitary

matrix whose description is distributed over the nodes of the network. For concreteness, in

this paper we focus on the case where the network is a path of length

and the nodes

v0, vr

are both extremities of the path.1

Here is the precise description of the problem. The parties

v0, v1, . . . , vr

are the nodes of

a line graph of length

: the left-end extremity is

, the right-end extremity is

, and nodes

and

vj+1

are connected for

= 0

, . . . , r −

1. Node

receives as input the classical

description of an

-qubit state

|ψ⟩

, as a 2

-dimensional vector.

The other nodes

for

= 1

, . . . , r

receive as input the description of an

-qubit unitary transformation: each

node

receives the description of a unitary transformation

acting on

qubits. In this

setting, the aim is to generate the quantum state

|φr⟩:= Ur···U1|ψ⟩

at the right-end extremity

. We call this problem

-qubit State Generation with Distributed

Inputs on the line of length

(

-qubit

SGDIr

). Without a prover, this problem is clearly not

solvable in less than

rounds of communications between neighbors (this can be seen easily

by considering the case where U1=··· =Ur=I).

We consider the setting where a prover (an all-powerful but untrusted party) helps the

nodes in a non-interactive way: at the very beginning of the protocol the prover sends to

In distributed computing it is standard to ﬁrst investigate the complexity of computational problems on

simple network topologies such as a path or a ring. A solution on the path can often be extended to

networks of more complex topology, or be used as a building block for solving problems on network of

arbitrary topology.

Our protocol actually only requires

to be able to generate many copies of

|ψ⟩

, and thus also works

when the input is a description of a quantum circuit generating

|ψ⟩

, or even a black box generating

|ψ⟩

F. Le Gall, M. Miyamoto and H. Nishimura 3

node

a quantum state

ρj

of at most

qubits, for each

j∈ {

, . . . , r}

. Here

is called

the certiﬁcate size of the protocol and the state

ρj

is called the certiﬁcate to

. The nodes

then run a one-round

distributed quantum algorithm (called the veriﬁcation algorithm).

More precisely, the nodes ﬁrst perform one round of (synchronous) communication: each

node sends one quantum message of at most

qubits to its neighbors (

is called the

message size of the protocol). Each node then decides to either accept or reject. Such

protocols, which have been introduced and studied in [

], are called distributed Quantum

Merlin-Arthur (dQMA) protocols (see Section 2.2 for details). Additionally, when considering

dQMA protocols for

-qubit

SGDIr

, we add the requirement that node

outputs an

-qubit

quantum state at the end of the protocol.

Here is our main result:

▶

Theorem 1. For any constant

ε >

0, there exists a dQMA protocol for

-qubit

SGDIr

with

certiﬁcate size

(

n2r5

)and message size

(

nr2

)satisfying the following: (completeness)

There are certiﬁcates

ρ0, . . . , ρr

such that all the nodes accept and node

outputs

|φr⟩

with

probability 1; (soundness) If all the nodes accept with probability at least

, then the output

state ρof node vrsatisﬁes ⟨φr|ρ|φr⟩ ≥ 1−ε.

The protocol of Theorem 1 is a dQMA protocol with perfect completeness and soundness

. Indeed, when receiving appropriate certiﬁcates from the prover, all nodes accept with

probability 1 and node

outputs the state

|φr⟩

. On the other hand, if the state

is far

from

|φr⟩

, the soundness condition guarantees that for any certiﬁcates

ρ0, . . . , ρr

received

from the prover (including the case of entangled certiﬁcates), the probability that at least

one node rejects is at least 1

−ε

(remember that the quantity

⟨φr|ρ|φr⟩

represents the square

root of the ﬁdelity between |φr⟩⟨φr|and ρ— see Section 2.1 for details).

As an application of Theorem 1, we construct a quantum protocol for a concrete computa-

tional task called Set Equality, which was introduced in Ref. [

]. Here is the formal deﬁnition

over a network of arbitrary topology (represented by an arbitrary graph G= (V, E)).

▶

Deﬁnition 1 (

SetEqualityℓ,U

[

]).Let

ℓ

be a positive integer and

be a ﬁnite set. Each

node

of a graph

= (

V, E

)holds two lists of

ℓ

elements (

au,1, . . . , au,ℓ

)and (

bu,1, . . . , bu,ℓ

)as

input, where

au,i, bu,i ∈U

for all

i∈ {

, . . . , ℓ}

. Deﬁne

{au,i |u∈V, i ∈ {

, . . . , ℓ}}

and

{bu,i |u∈V, i ∈ {

, . . . , ℓ}}

. The output of

SetEqualityℓ,U

is 1(yes), if

as multisets and 0(no) otherwise.

Using Theorem 1 we obtain the following result:

▶

Theorem 2. For any small enough constant

ε >

0, there exists a dQMA protocol for

SetEqualityℓ,U

on the line graph of length

with completeness 1

−ε

and soundness

that has

certiﬁcate size O(r5log2(ℓr) log2|U|)and message size O(r2log(ℓr) log |U|).

While Ref. [

] considered the special case of

SetEqualityℓ,U

and showed eﬃcient distributed

interactive protocols with small certiﬁcate and message size (see Section 1.4), no (nontrivial)

classical dMA protocol (or lower bound) is known before this paper to our best knowledge.

We complement the result in Theorem 2 by showing classical lower bounds and upper bounds

of distributed Merlin-Arthur (dMA) protocols for SetEqualityℓ,U .

▶

Theorem 3. For any dMA protocol for

SetEqualityℓ,U

on a line graph of length

with

certiﬁcate size sc, completeness 3/4, and soundness 1/4,

As in almost all prior works on (classical or quantum) distributed proofs, in this paper we consider only

one-round veriﬁcation algorithms.

4 Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications

if |U|< ℓ, then sc= Ω(|U|log(ℓ/|U|));

if |U|= Ω(ℓ), then sc= Ω(ℓ);

if |U|= Ω(rℓ), then sc= Ω(rℓ).

▶

Theorem 4. There exists a dMA protocol for

SetEqualityℓ,U

on a line graph of length

with completeness 1and soundness 0whose certiﬁcate size and message size are both

O(min{rℓ log |U|,|U|log(rℓ)}).

Although the dependence in

is worse than in the classical dMA protocol of Theorem 4, the

dependence of the dQMA protocol of Theorem 2 in

ℓ

(the number of elements each node

receives) and

|U|

(the size of the universal set) are polylogarithmic. On the other hand,

in classical case, we have linear lower bounds with respect to

ℓ

and

|U|

as in Theorem 3.

Therefore Theorem 2 gives a signiﬁcant improvement for suﬃciently large

ℓ

and

|U|

. This

assumption about the input parameters seems reasonable when considering applications

similar to those of the dQMA protocol for the equality problem proposed in Ref. [

]. Note

that our bounds of classical certiﬁcate size in Theorem 3 and Theorem 4 are tight up to

poly log(ℓ, |U|, r)factors when |U|< ℓ or |U|= Ω(rℓ).

1.2 Second result and applications: EPR-pairs generation and LOCC

dQMA protocols

Our second contribution is a protocol, based on a recent work by Zhu and Hayashi [

], to

create EPR-pairs between adjacent nodes of a network without quantum communication

in the same setting as above, where a prover helps the nodes in a non-interactive way.

As an application of this protocol, we prove a general result showing how to convert any

dQMA protocol on an arbitrary network into another dQMA protocol where the veriﬁcation

algorithm uses only classical communication (instead as quantum communication, as allowed

in the deﬁnition of dQMA protocols and used in all dQMA protocols of Ref. [

] and Theorems

1 and 2 above).

More precisely, we say a dQMA protocol is an LOCC (Local Operation and Classical

Communication) dQMA protocol if the veriﬁcation algorithm can be implemented only by

local operations at each node and classical communication between neighboring nodes (i.e.,

no quantum communication is allowed). Our protocol for generating EPR-pairs enables us

to show the following theorem:

▶

Theorem 5. For any constant

and

such that 0

≤ps< pc≤

1, let

be a dQMA

protocol for some problem on a network

with completeness

, soundness

, certiﬁcate size

and message size

. For any small enough constant

γ >

0, there exists an LOCC dQMA

protocol

P′

for the same problem on

with completeness

, soundness

, certiﬁcate

size

(

dmaxsP

msP

), and message size

(

msP

), where

dmax

is the maximum degree of

G, and sP

tm is the total number of qubits sent in the veriﬁcation stage of P.

As an application of Theorem 5, we consider the equality problem studied in Ref. [

]. In

this problem, denoted

EQt

, a collection of

-bit strings

x1, x2, . . . , xt

is given as input to

speciﬁc nodes

u1, u2, . . . , ut

(called terminals) of an arbitrary network

= (

V, E

)as follows:

node

receives

, for

i∈ {

, . . . , t}

. The goal is to check whether the

strings are equal,

i.e., whether

···

. By applying Theorem 5 to the main result in Ref. [

] (a dQMA

protocol for

EQt

with certiﬁcate size

(

tr2log n

)and message size

(

tr2log

(

))), we

obtain the following corollary:

F. Le Gall, M. Miyamoto and H. Nishimura 5

▶

Corollary 1. For any small enough constant

ε >

0, there is an LOCC dQMA protocol

for

EQt

with completeness 1, soundness

, certiﬁcate size

(

dmax|V|t2r4log2

(

)) and

messages size

(

|V|t2r4log2

(

)), where

is the radius of the set of the

terminals and

|V|is the number of nodes of the network G= (V, E).

We can also apply Theorem 5 to the dQMA protocol of Theorem 2, leading to the

following corollary:

▶

Corollary 2. For any small enough constant

ε >

0, there is an LOCC dQMA protocol for

SetEqualityℓ,U

on the line graph of length

with completeness 1

−ε

, soundness

, certiﬁcate

size O(r5log2(ℓr) log2|U|)and messages size O(r5log2(ℓr) log2|U|).

Note that these LOCC dQMA protocols still have good dependence in the main parameters

we are interested in: the parameter

for

EQt

(for which the dependence is still exponentially

better than any classical dMA protocols) and the parameters

ℓ

and

|U|

for

SetEqualityℓ,U

(for which the dependence is still exponentially better than any classical dMA protocols, due

to Theorem 3).

1.3 Overview of our proofs

To explain the proof idea of Theorem 1, we only consider the simpliﬁed case

···

The general case can be proved similarly by a slightly more complicated analysis.

The dQMA protocol to prove Theorem 1 is based on the dQMA protocol on the line

of length

by Fraigniaud et al. [

]. In the setting of Ref. [

], the left-end extremity

has an

-bit string

, the right-end extremity

has an

-bit string

, and the other

intermediate nodes have no input. The goal is to verify whether

. The dQMA protocol

in Ref. [

] checks whether the ﬁngerprint state

|ψ0⟩

|ψx⟩

[

] prepared by

is equal to

the ﬁngerprint state

|ψr⟩

|ψy⟩

prepared by

(

), or

|ψ0⟩

is almost orthogonal to

|ψr⟩

(

x̸

). For this, node

≤j≤r−

1) receives a subsystem whose reduced state is

ρj

as a certiﬁcate from the prover. At the veriﬁcation stage, any node (except for

) chooses

keeping its certiﬁcate by itself, or sending it to the right neighboring node with probability

2to check if the reduced states of the two neighboring nodes,

ρj

and

ρj+1

, are close, which

can be checked by the SWAP test [

] (using Lemma 7). If

, then the prover can send

|ψ0⟩

|ψr⟩

)for every intermediate node to pass all the SWAP tests done at the veriﬁcation

stage, which means accept. Otherwise, the SWAP test done at some node rejects with a

reasonable probability since

|ψx⟩

is very far from

|ψy⟩

, and hence the distance between

ρj

and ρj+1 should be far at some j.

Now the case that

···

(which means that all nodes except

have no

input) in the setting of

SGDIr

(then the goal state

|φr⟩

is the same as the state

|ψ⟩

) is similar to the setting of Ref. [

], except that

also has no input. The diﬃculty is

that

has no state that can be generated by itself, and thus the analysis of Ref. [

] cannot

be used as it is.

To overcome this diﬃculty, we utilize an idea from the veriﬁcation of graph states [

in particular, the idea by Morimae, Takeuchi, and Hayashi [

]. They used the following

basic idea for their protocol in order to verify an arbitrary graph state

|G⟩

sent from the

prover (or prepared by a malicious party): (i) the veriﬁer receives (

+ 1) subsystems,

in which each subsystem ideally contains

|G⟩

, from the prover; (ii) the veriﬁer chooses

subsystems uniformly at random, and discards them; (iii) the veriﬁer chooses one subsystem,

and some test that

|G⟩

should pass (stabilizer test) is done for each of the remaining

subsystems; and (iv) if all the tests passed, the chosen subsystem in (iii) should be close

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

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

10 玖币 0人已下载

立即下载

摘要：

DistributedMerlin-ArthurSynthesisofQuantumStatesandItsApplicationsFrançoisLeGall#GraduateSchoolofMathematics,NagoyaUniversity,Nagoya,JapanMasayukiMiyamoto#GraduateSchoolofMathematics,NagoyaUniversity,Nagoya,JapanHarumichiNishimura#GraduateSchoolofInformatics,NagoyaUniversity,Nagoya,JapanAbstractTheg...

展开>> 收起<<

Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications_2.pdf

共25页,预览5页

还剩页未读，继续阅读

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

Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: