Lattice-Based Quantum Advantage from Rotated Measurements

2025-05-03 0 0 1.05MB 36 页 10玖币

侵权投诉

Lattice-Based Quantum Advantage from Rotated

Measurements

Yusuf Alnawakhtha1, Atul Mantri1,2, Carl A. Miller1,3, and Daochen Wang1,4

1Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742, USA

2Department of Computer Science, Virginia Tech, Blacksburg, VA 24060, USA

3Computer Security Division, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA

4Department of Computer Science, University of British Columbia, Vancouver, V6T 1Z4, Canada

Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic inter-

actions between a classical client and a quantum server. Typically, a protocol has the

quantum server prepare a superposition of two bit strings of a claw and then measure

it using Pauli-Xor Zmeasurements. In this paper, we demonstrate a new technique

that uses the entire range of qubit measurements from the XY -plane. We show the ad-

vantage of this approach in two applications. First, building on (Brakerski et al. 2018,

Kalai et al. 2022), we show an optimized two-round proof of quantumness whose secu-

rity can be expressed directly in terms of the hardness of the LWE (learning with errors)

problem. Second, we construct a one-round protocol for blind remote preparation of

an arbitrary state on the XY -plane up to a Pauli-Zcorrection.

1 Introduction

The ﬁeld of quantum cryptography has its origins [BB14,Wie83] in the idea that quantum states

can be transmitted between two parties (e.g., through free space or through an optical ﬁber)

to perform cryptographic tasks. Properties of the transmitted states, including no-cloning and

entanglement, are the basis for interactive protocols that enable a new and qualitatively diﬀerent

type of security. However, a recent trend in the ﬁeld has shown that quantum cryptography can

be done even when quantum communication is not available. If one or more parties involved in

a protocol possess a suﬃciently powerful quantum computer, then certain cryptographic tasks

can be performed — while still taking advantage of uniquely quantum properties — using strictly

classical communication. This approach relieves the users of the diﬃculties associated with reliable

quantum communication and puts the focus instead on the problem of building a more powerful

quantum computer, a goal that has seen tremendous investments during the past several years

[Nat19].

At the center of this new type of quantum cryptography are cryptographic hardness assump-

tions. Certain problems, such as factoring numbers, are believed to be diﬃcult for classical com-

puters but not for quantum computers. Other problems, such as ﬁnding the shortest vector in a

lattice, are believed to be hard for both types of computers. These hardness assumptions are used

to prove soundness claims for quantum interactive protocols.

Two of the seminal papers in quantum cryptography with classical communication [Mah18,

BCM+21] used trapdoor claw-free functions [GMR84] as the basis for their protocol designs, and

created a model that has been followed by many other authors. A trapdoor claw-free function

(TCF), roughly speaking, is a family of triples

(

f0, f1, t

)

, where f0and f1are injective functions

with the same domain and same range, and tis a trapdoor that allows eﬃcient inversion of either

function. To say that this family is claw-free means that without the trapdoor t, it is believed to be

hard for any (quantum or classical) adversary to ﬁnd values x0and x1such that f0(x0) = f1(x1).

The TCF construction illustrates how a cryptographic hardness assumption that is made for

both quantum and classical computers can nonetheless permit a quantum computer to show its

unique capabilities. A quantum computer can perform an eﬃcient process that will output a

Accepted in Quantum 2024-05-27, click title to verify. Published under CC-BY 4.0. 1

arXiv:2210.10143v3 [quant-ph] 2 Jul 2024

random element yin the range of f0, f1together with a claw state of the form

|ψ⟩=1

√2(|x0⟩|0⟩+|x1⟩|1⟩),(1)

where f0

(

) =

(

) =

y(see section 2 of [Mah18]). If this state is measured in the Z-basis, one

obtains a pair

(

x, c

)

such that fc

(

) =

y. Alternatively, assuming that x0and x1are expressed as

bit strings of length ℓ, and thus |ψ⟩is an

(

ℓ

+ 1)

-qubit state, one can measure in the X-basis to

obtain a bit string dthat must satisfy

d·(x0⊕x1||1) = 0.(2)

(Here, || denotes string concatenation.) This equation is signiﬁcant because we have used a quantum

process to obtain information about both x0and x1, even though we have assumed that it would be

impossible for any eﬃcient computer to recover x0and x1entirely. This fact is the basis for using

TCFs to verify that a server that one is interacting with is able to perform quantum computation

[BCM+21,KMCVY22]. The same concept was also used in cryptographic constructions that

delegate the preparation of a quantum state to a server without revealing its classical description

[CCKW19,GV19] and in other cryptographic protocols [MV21,Mah18].

The majority of papers utilizing TCFs in their cryptographic constructions have applied only

Pauli measurements and classical operations to the state |ψ⟩.1What would happen if we considered

the full range of single-qubit measurements on the state |ψ⟩? We note that since single-qubit

rotation gates are physically native in some platforms (for example, ion traps [NC10,DLF+16,

Mas17]), realizing a continuous single-qubit rotation is not much more diﬃcult than realizing a

single-qubit Cliﬀord gate, and so this direction is a natural one to study.

In this work, we use an inﬁnite family of qubit measurements to prove new performance and

security claims for quantum server protocols. We discuss two applications: proofs of quantumness

and blind remote state preparation.

1.1 Our Contribution

Proof of Quantumness.

With increasing eﬀorts in recent years towards building quantum

computers, the task of verifying the quantum behavior of such computers is particularly important.

Integer factorization, one of the oldest theoretical examples of a quantum advantage [Sho94], is

one possible approach to this kind of veriﬁcation. However, building quantum computers that are

able to surpass classical computers in factoring is experimentally diﬃcult and a far-oﬀ task. Hence,

it is desirable to ﬁnd alternative proofs of quantumness2that are easier for a quantum computer

to perform.

The authors of [BCM+21] did groundbreaking work in this direction by oﬀering an interactive

proof of quantumness based on the hardness of LWE (learning with errors). Follow-up work

[BKVV20,KMCVY22,KLVY23] used their technical ideas to optimize some aspects or provide

trade-oﬀs under diﬀerent assumptions. In this work we provide a proof of quantumness that utilizes

rotated measurements on claw states (Eq. (1)) to achieve some new tradeoﬀs. The advantage

achieved in our protocol by a quantum device is described in the following theorem.

Theorem 1.1 (Informal).Let

denote the security parameter. Suppose that

n, m, q, σ, τ

are

functions of

that satisfy the constraints given in Fig. 1 from Section 3, and suppose that the

LWEn,q,G(σ,τ)

problem is hard. Then, there exists a two round interactive protocol between a veriﬁer

and a prover such that the following holds:

•For any eﬃcient classical prover, the veriﬁer accepts with probability at most 3

4+ negl(λ).

•

For any quantum prover that follows the protocol honestly, the veriﬁer accepts with probability

at least cos2π

8−5mσ2

q2−mσ

2τ.

Two exceptions are as [

GV19

] and [

CCKW21

]. In [

GV19

], the server applies Fourier transforms to the quantum

state

|ψ⟩

. In [

CCKW21

], the server applies measurements from a small set in the

-plane and the protocol only

provides security against honest-but-curious adversaries. See Section 1.2 for a comparison.

By proof of quantumness, we mean a speciﬁc test, administered by a classical veriﬁer, which an eﬃcient quantum

device can pass at a noticeably higher rate than any eﬃcient classical device.

Accepted in Quantum 2024-05-27, click title to verify. Published under CC-BY 4.0. 2

The protocol for this theorem is referred to as Protocol

and is given in Fig. 4. Noting that

cos2

(

π/

4, we deduce that as long as the error term 5mσ2

mσ

2τvanishes as λ→ ∞,

a constant gap is achieved between the best possible quantum winning probability and the best

possible classical winning probability. In Section 3.3, we show that this vanishing condition can

be achieved while taking the modulus qto be only slightly asymptotically larger than n2σ(where

the parameter nis the dimension of the LWE problem, and σis the noise parameter). Our

approach thus allows us to base the security of our protocol on the LWE problem for a broad range

of parameters, including parameters that are comparable to those used in post-quantum lattice-

based cryptography. (For example, in the public-key cryptosystem in [Reg09], the modulus is taken

to be on the order of n2.) Previous works on interactive lattice-based proofs of quantumness have

tended to use a modulus that is either very large or not explicitly given.

Our proof builds on recent work, and most directly builds on [KLVY23]. In comparison to

the proof of quantumness described in [KLVY23], our protocol involves preparing and measur-

ing only one TCF claw state at each iteration, whereas the proof described in ([KLVY23], Sec-

tion 4.1) requires preparing and measuring three TCF claw states (while maintaining quantum

memory throughout). Additionally, whereas [KLVY23] requires the use of quantum homomorphic

encryption schemes proved by other authors (and does not give explicit parameters) our proof is

self-contained and directly relates the security of our protocol to the hardness of the underlying

LWE problem. At the same time, our approach inherits the following merits from [KLVY23]: our

protocol involves only

rounds of interaction, it requires only one qubit to be stored in memory

in between rounds, and it does not require any cryptographic assumptions beyond LWE.

As far as we are aware, the combination of features in our work has not been achieved before (see

Section 1.2), and our results thus bring the community closer to establishing the minimal require-

ments for a lattice-based proof of quantumness. As experimental progress continues [ZKML+23],

there is good reason to think that these proofs of quantumness may be realizable in the near future.

Remote State Preparation.

Remote state preparation (RSP) is a protocol where a compu-

tationally weak client delegates the preparation of a quantum state to a remote server. An RSP

protocol is blind if the server does not learn a classical description of the state in the process of

preparing it [DKL12]. Recently, [CCKW19] and [GV19] introduced blind RSP with a completely

classical client, based on the conjectured quantum hardness of the LWE problem. Blind RSP has be-

come an essential subroutine to dequantize the quantum channel in various quantum cryptographic

applications including blind and veriﬁable quantum computations [BFK09,GV19,BCC+20], quan-

tum money [RS22], unclonable quantum encryption [GMP23], quantum copy protection [GMP23],

and proofs of quantumness [MY23].

All previous RSP protocols prepare a single-qubit state 1

√2

(

|0⟩

eiθ |1⟩

)

, where θbelongs to

some ﬁxed set S⊆

)

. However, a common feature among all the schemes is that either the

size of Smust be small, or the basis determined by θis not ﬁxed a priori. Therefore, a natural

question in this context is:

Can a completely classical client delegate the preparation of arbitrary single-qubit states to a

quantum server while keeping the basis ﬁxed?

Ideally, we would like to achieve this task in a single round of interaction. Note that the previous

RSP protocols along with computing on encrypted data protocols such as [BFK09,FBS+14] can

realize this task in two rounds of interaction. In this work, we provide a simple scheme for de-

terministic blind RSP that achieves this task without incurring any additional cost compared to

previous randomized RSP schemes. Our protocol only requires one round of interaction to prepare

any single qubit state in the XY -plane (modulo a phase ﬂip). This is particularly helpful for

applications which require a client to delegate an encrypted quantum input, as it gives the client

more control over the state being prepared. The correctness and blindness of the protocol are

summarized in the theorem below.

Theorem 1.2 (Informal).Let

denote the security parameter. Suppose that

n, m, q, σ, τ

are

functions of the security parameter

that satisfy the constraints given in Fig. 1 from Section 3

and τ≥2mσ, and suppose that the LWEn,q,G(σ,τ)problem is hard. Then there exists a one-round

Accepted in Quantum 2024-05-27, click title to verify. Published under CC-BY 4.0. 3

client-server remote state preparation protocol such that for any

α∈Zq

, the client can delegate the

preparation of the state |α⟩=1

√2|0⟩+ei2πα/q |1⟩with the following guarantees:

•

If the server follows the protocol honestly, then they prepare a state

|β⟩

such that



|α⟩⟨α| −

Zb|β⟩⟨β|Zb

1≤4πmσ

, where

∥·∥1

denotes the trace norm and

b∈ {

}

is a random bit that

the client can compute after receiving the server’s response.

•The server gains no knowledge of αfrom interacting with the client.

Additional Applications and Future Directions.

The techniques in this paper invite applica-

tion to other cryptographic tasks, including veriﬁable random number generation, semi-quantum

money, and encrypted Hamiltonian simulation. In Section 7, we discuss possible future research

directions for these three topics, and we oﬀer some preliminary results.

There is ample room for further optimization of our results on lattice-based proofs of quan-

tumness. One of the advantages of our proof of soundness for Protocol

(Theorem 5.3) is that

it is based directly on the security of a simple lattice-based encryption scheme (Fig. 2). (This

is in contrast to the proof of quantumness in [BCM+21], in which the soundness proof is based

on the “adaptive hardcore bit property” and its relationship to the security of LWE encryption

schemes is more indirect.) A natural next step to improve our results would be to try to replace

the encryption scheme in Fig. 2 with a more eﬃcient single-bit encryption scheme. In particular,

a Ring-LWE or Module-LWE based encryption scheme could allow for substantially less quantum

computation time for an honest prover in Protocol Q.

1.2 Related Works

Proof of quantumness.

The study of proofs of quantumness based on LWE was initiated by

Brakerski et al. [BCM+21] who proposed a four-message (two-round) interactive protocol between

a classical veriﬁer and a prover. Their protocol also involves constructing only a single TCF claw

state (like in our protocol), although it requires holding the entire claw state in memory between

rounds, and it uses an exponentially large modulus.3Later, [BKVV20] gave a two-message (one-

round) proof of quantumness with a simpler and more general security proof, but at the cost

of requiring the random oracle assumption. More recently, [KMCVY22] introduced a proof of

quantummness with some of the same features as [BKVV20] without the random oracle assumption,

but they require up to

messages in their protocol (

rounds of interaction). Both [AGKZ20] and

[YZ22] present constructions of publicly veriﬁable proofs of quantumness, albeit with diﬀerent

assumptions or models. Further works have based proofs of quantumness on diﬀerent assumptions

[MY23], optimized the depth required for implementing TCFs [LG22,HLG21], and even achieved

prototype experimental realization [ZKML+23].

The paper [KLVY23] (which is the main predecessor to this work) presented a generic compiler

that turns any non-local game into a proof of quantumness and gave an explicit scheme that only

requires

messages (

rounds of interaction). These results assume the existence of a quantum fully

homomorphic encryption scheme that satisﬁes certain conditions (see Deﬁnition 2.3 in [KLVY23]),

and the authors sketch proofs that two known schemes [Mah18,Bra18] satisfy such conditions.

An alternative route to proving a result similar to Theorem 1.1 would be to expand the afore-

mentioned proof sketches (see the appendix of the full version of [KLVY23]) and use them to create

a proof of quantumness with explicit parameters. However, we expect this approach to be less op-

timal both in mathematical complexity and computational complexity. Combining [KLVY23] with

[Mah18] would involve an exponentially sized modulus q, and would require preparing and mea-

suring three claw-states during a single iteration of the central protocol. Combining [KLVY23]

with [Bra18] would also require preparing three states of size similar to claw states, and would

involve performing a q-ary Fourier transform on each state. In contrast, our approach involves

only preparing a single-claw state and then performing single qubit operations on it.

One eﬀect of using an exponentially large modulus is on hardness assumptions. If we phrase our hardness

asssumptions in terms of the shortest vector problem in a lattice, then [

BCM+21

] assumes the hardness of sub-

exponential approximation of the shortest vector, while in the current work we only assume that polynomial

approximation is hard. See Section 3.3.

Accepted in Quantum 2024-05-27, click title to verify. Published under CC-BY 4.0. 4

Blind RSP.

Remote state preparation over a classical channel comes in two security ﬂavors —

blind RSP and blind-veriﬁable RSP (in this work, we give a protocol for the former). Such a primi-

tive was ﬁrst introduced in [CCKW21] for honest-but-curious adversaries. This was later extended

to fully malicious adversaries in [CCKW19], where the authors present two blind RSP protocols,

one of which allows the client to delegate the preparation of a BB84 state ({|0⟩,|1⟩,|+⟩,|−⟩})

and the other allows the client to delegate the preparation of one of

states in the XY -plane.

The former protocol has the advantage of allowing the client to choose if the server is preparing

a computational ({|0⟩,|1⟩})or a Hadamard ({|+⟩,|−⟩})basis state. However, it is not clear how

to generalize the scheme to prepare quantum states from a large set while maintaining control

over the choice of basis. Independently, [GV19] gives a blind-veriﬁable RSP scheme that general-

izes [BCM+21], where the blindness is based on the adaptive hardcore bit property. The protocol

in [GV19] can prepare one of

states:

in the XY -plane and the two computational basis states.

There is a natural way to generalize [GV19] to prepare states of the form 1

√2

(

|0⟩

exp(i2πx/q)|1⟩

)

with x, q ∈N. However, the naturally generalized protocol requires an honest quantum server

to apply a Fourier transform over Zqon the claw state, whereas we only require the server to

perform single-qubit gates on the claw state for any q. Moreover, the quantity xin the prepared

state is randomly chosen in [GV19] whereas our protocol allows the client to choose x. More re-

cently, [MY23] constructs an RSP protocol from diﬀerent cryptographic assumptions (full domain

trapdoor permutations); however, the blindness is only shown against classical adversaries.

Previous RSP protocols have proven to be immensely useful in several cryptographic ap-

plications, ranging from proofs of quantumness [MY23] and veriﬁcation of quantum computa-

tion [GV19,Zha22] to computing on encrypted data [BCC+20,GMP23], secure two-party quan-

tum computation [CCKM20] and more. Finally, RSP protocols have been extended to self-testing

protocols [MV21,MTH+22,FWZ23]. A self-testing protocol characterizes not only the state

prepared but also the measurements made upon them.

2 Technical Overview

Our protocol involves performing rotated measurements on the claw states put forward by [BCM+21]

to steer the ﬁnal qubit of the claw state into a speciﬁc form, while keeping this form secret by hid-

ing it using LWE. Suppose that n, m, q are positive integers. The Learning With Errors (LWE)

hardness assumption implies that if a classical client chooses a uniformly random vector s∈Zn

and a uniformly random matrix A∈Zm×n

q, and computes v:

ewhere e∈Zm

qis a small

noise vector, then a quantum server cannot recover sfrom

(

A, v

)

. Following [BCM+21] the server

can (for certain parameters) nonetheless approximately prepare a superposed claw state of the

form |γ⟩

√2|x1⟩|1⟩

|x0⟩|0⟩,where x0∈Zn

qand x1

s, along with a vector y∈Zm

which is close to both Ax0and Ax1. We will assume that x0and x1are written out in base-

using

little-endian order.

At this point, rather than having the server measure |γ⟩in the X-basis, we can go in a diﬀerent

direction: suppose that the client instructs the server to measure the kth qubit of |γ⟩in the basis

(

cos θk

)

+ (

sin θk

)

Ywhere θkare real numbers for k

= 1

, . . . , n⌈log q⌉, and report the result as

a binary vector u

= (

u1, . . . , un⌈log q⌉

)

.Once this is done, the state of the ﬁnal remaining qubit will

be 1

√2(|0⟩+eiϕ |1⟩), where

ϕ:=⟨θ, [x0]⟩−⟨θ, [x1]⟩+⟨u, [x0]⊕[x1]⟩ · π.

Here ⟨·,·⟩ denotes the dot product, and

[

]

and

[

]

denote the base-

representations of x0and x1.

Since the quantum server cannot know both x0and x1, they cannot compute ϕfrom this formula.

However, if the client possesses a trapdoor to the original matrix A, then they can recover x0and

x1from yand compute ϕ.

We can go further: if the client chooses a vector t

= (

t1, . . . , tn

)

∈Zn

qand sets θby the formula

θ(i−1)n+j:= 2jtiπ/q for i∈ {1,2, . . . , n}and j∈ {1,2,...,⌈log q⌉}, then

ϕ=⟨t, x0−x1⟩ · (2π/q) + ⟨u, [x0]⊕[x1]⟩ · π

=−⟨t, s⟩ · (2π/q) + ⟨u, [x0]⊕[x1]⟩ · π.

Accepted in Quantum 2024-05-27, click title to verify. Published under CC-BY 4.0. 5

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

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

10 玖币 0人已下载

立即下载

摘要：

Lattice-BasedQuantumAdvantagefromRotatedMeasurementsYusufAlnawakhtha1,AtulMantri1,2,CarlA.Miller1,3,andDaochenWang1,41JointCenterforQuantumInformationandComputerScience,UniversityofMaryland,CollegePark,MD20742,USA2DepartmentofComputerScience,VirginiaTech,Blacksburg,VA24060,USA3ComputerSecurityDivisi...

展开>> 收起<<

Lattice-Based Quantum Advantage from Rotated Measurements.pdf

共36页,预览5页

还剩页未读，继续阅读

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

Lattice-Based Quantum Advantage from Rotated Measurements

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: