arXiv CSopen access

Unconditional Unclonable Encryption

Unconditional Unclonable Encryption Prabhanjan Ananth*

Amit Sahai†

UCSB

UCLA

Abstract

arXiv:2607.21551v1 [quant-ph] 23 Jul 2026

We give an unconditional construction of information-theoretically secure one-time private-key unclonable encryption scheme for one-bit messages, with efficient encryption and decryption and exponentially small unclonable-indistinguishability advantage.

1

Introduction

Unclonable cryptography is a branch of quantum cryptography that leverages the no-cloning principle of quantum mechanics [WZ82; Die82; BL20] to design primitives that are impossible to achieve classically. Within the rapidly growing landscape of unclonable cryptography, unclonable encryption has emerged as an important primitive. Roughly speaking, unclonable encryption (UE) [Got03; BL20] is an encryption scheme whose ciphertexts cannot be copied in a way that remains useful after the decryption key is revealed. In the one-time setting, an adversary receives a single copy of a quantum ciphertext while the key is hidden and then splits it between two non-communicating recipients. The key is then revealed to both the recipients, and the security requires that they cannot both simultaneously recover the hidden message substantially better than a coordinated guess. In more detail, two notions of security have been studied for unclonable encryption: • Search Security: the challenger samples a message m uniformly at random from {0, 1}n and sends an encryption of m to A who then produces a bipartite state shared with B and C . Upon receiving the decryption key, both B and C respectively output mB and mC . (A, B , C) succeed if mB = m and mC = m. The work of [BL20] presented a scheme where they showed that the probability of any adversary (A, B , C) succeeding is at most cos2|m| ( π8 ). • Indistinguishability Security: the challenger samples a bit b at random and then encrypts a message mb , for two adversarially chosen messages (m0 , m1 ), and then sends the ciphertext to A. From here on, the experiment is the same as the search security experiment. Unlike search security, there is always an adversarial strategy that can win with probability 21 . The goal is to design an UE scheme satisfying indistinguishability security where the success probability is as close to 12 as possible. Prior constructions. Over the past few years, many works have studied indistinguishability security for unclonable encryption. We use indUE to denote unclonable encryption satisfying indistinguishability security. • Plain Model: [AKY25] achieved indUE where the decryption keys are quantum states. Recently, there has been progress in designing indUE with classical keys. [Bot+26] achieved indUE with advantage 1 √ and verified its validity upto K = 17. This was improved by [BC26], who achieved indUE with 2 K

* [email protected] † [email protected]

1

inverse polynomial advantage. A follow up work by [BBC26] presents an optimal construction, where the advantage is negligible. However, their construction is not efficient, meaning that the encryption and the decryption algorithms do not run in quantum polynomial time1 . • Idealized Models: [Ana+22; AKL23] presented indUE with optimal advantage in the quantum random oracle model. [BG26] also presented optimal indUE and with stronger security guarantees albeit in the Haar random oracle model. Despite the recent progress, the goal of achieving efficient indUE in the plain model with classical keys and negligible adversary advantage has remained elusive. Indeed, a few works present evidence highlighting the challenges in achieving indistinguishability security. Notably [MST21; Ana+22] showed that indUE with deterministic encryption cannot satisfy negligible security. [CLX25] also highlighted the difficulties in using BB84 states to achieve indUE. Our contribution. We address the main goal of achieving unclonable encryption satisfying indistinguishability security. We show: Theorem 1.1 (Informal). For every n ≥ 1, there exists a one-time private-key quantum encryption scheme for onebit messages with a (2n − 1)-bit classical key and an n-qubit ciphertext. The scheme has perfect correctness, uses only single-qubit Clifford gates for encryption and local Pauli measurements for decryption, and satisfies Pr[bB = bC = b] ≤

1 + 2−(n+1)/2 2

against every information-theoretic pre-key splitting attack in the one-bit unclonable-indistinguishability experiment.

1.1

Technical Overview

From BB84 parity to Pauli parity. It is useful first to recall the natural BB84-based attempt. For each qubit, the encryptor chooses either the X or the Z observable and prepares one of its two eigenstates. The eigenvalue bits on all but one position are chosen at random, while the remaining position is fixed so that the XOR of all eigenvalue bits equals the message. A legitimate decryptor, after learning the basis string, measures every qubit and recovers the message by taking the parity of the outcomes. This construction has a clean search-security interpretation, but the XOR-repetition result of Coladangelo, Liu, and Xie shows that this direct route cannot provide exponentially small indistinguishability error [CLX25]. Our construction replaces the two-basis choice by a random tensor Pauli. The key consists of strings x, z ∈ {0, 1}n subject to x1 = 1, and the jth local observable is Px j ,z j = i x j z j X x j Z z j ∈ { I, X, Y, Z }. Thus the first local Pauli is X or Y, and in particular is nonidentity. The encryptor samples the bits r2 , . . . , rn uniformly and chooses r1 so that the product of the local Pauli eigenvalues equals (−1)m . It then prepares the product state |ψk,m;r ⟩ = Uk |r1 , . . . , rn ⟩, where Uk rotates the computational basis into the appropriate local Pauli eigenbases. After learning the key, the decryptor measures the jth qubit with respect to Px j ,z j and multiplies the resulting signs. The product is exactly (−1)m . Our construction is not new and was first conceived by [Bot+26], although we give a more detailed description of their scheme in this work. We show that the construction of [Bot+26] satisfies indistinguishability security with negligible advantage. 1 Concretely, their scheme has advantage negligible in n, where encryption and decryption can be implemented in time exponential in n.

2

Security. The security proof has two main steps. First, the Choi–Jamiołkowski representation converts an arbitrary pre-key splitting channel into a fixed tripartite state and rewrites the winning probability as2 Pr[Win] =

1 (1 + Tr(Gτ )) , 2

G=

1 (EB + EC + EBC − I ) . 2

Here EB is the averaged correlation between the reference system and Bob’s signed decoder observable, EC is the analogous reference–Charlie correlation, and EBC records Bob–Charlie agreement. The reduction shows that it suffices to upper-bound the positive spectrum of G: Pr[Win] ≤

1 (1 + ∥G+ ∥ ∞ ) . 2

(1)

The second step is therefore to prove an explicit upper bound on ∥G+ ∥∞ . The remainder of the proof develops this operator estimate from the Hilbert–Schmidt orthogonality of the Pauli family and a filteredoverlap argument. Suppose ∥G+ ∥∞ = t. We use the fact that G is Hermitian to show that there exists a unit vector |ψ⟩ such that G|ψ⟩ = t|ψ⟩. By rearranging, we have the following equation:

(EB + EC )|ψ⟩ = (2tI + ( I − EBC ))|ψ⟩ The key is to come up with a well-defined filter F = 2t(2tI + ( I − EBC ))−1 and consider the following quadratic forms: • ⟨ψ|(EB + EC )F(EB + EC )|ψ⟩ • −⟨ψ|(EB − EC )F(EB − EC )|ψ⟩ Adding both gives us the result 4Re⟨ψ|EB FEC |ψ⟩. By suitably lower bounding both the quadratic forms, we can then show that Re⟨ψ|EB FEC |ψ⟩ ≥ t2 . Observe that Re⟨ψ|EB FEC |ψ⟩ ≤ ∥EB FEC ∥∞ . Suppose we show that ∥EB FEC ∥∞ ≤ 2n1−1 then this would imply that t ≤ n1−1 . Substituting this in Equation (1), we then would have the claimed result: Pr[Win] ≤ 12 +

1

n +1 2 2

2

2

.

Thus, the remaining part is to show that ∥EB FEC ∥∞ ≤ 2n1−1 . Instead of calculating ∥EB FEC ∥∞ directly, we instead introduce another operator F N0 , defined for an integer N0 ≥ 1 and then show that ∥EB F N0 EC ∥∞ + ∥EB (F − F N0 )EC ∥∞ is at most 2n1−1 . The advantage of introducing F N0 is that it is relatively easier to upper bound ∥EB F N0 EC ∥∞ and in particular, upper bounding ∥EB F N0 EC ∥∞ boils down to upper bounding ∥EB EℓBC EC ∥∞ , for every ℓ ∈ [ N0 − 1]. In turn, ∥EB EℓBC EC ∥∞ can be upper bounded by ∥EB EC ∥∞ , which is at most 2n1−1 . Comparison with [Bot+26]. We compare our analysis with [Bot+26]. All the steps up until determining the upper bound on G is essentially the same. The difference is that we define G = 12 (EB + EC + EBC − I ) whereas they consider the matrix3 EB + EC + EBC and conjecture an upper bound on the operator norm of this matrix. Statement on AI usage. The human authors take full responsibility for the claims and proofs contained in this paper, and have carefully refined and verified them. The construction and main ideas of the proof were generated entirely by Codex using GPT 5.6 Sol Ultra, using harness ideas generated by the authors based on the UCLA Moonshot Harness [ZHC+26] and [Ope26]. 2 This step is similar to the first step of search security of unclonable encryption by [BL20] once the intermediate abstraction of monogamy of entanglement games is stripped out. Similar to [BL20], arguing security of unclonable encryption reduces to determining an upper bound on the operator norm of a matrix. 3 Technically speaking, they omit the normalization factor in the sum. We ignore this distinction in the current discussion.

3

2

Preliminaries $

The statistical security parameter is denoted by n ∈ N. We write x ← − S for uniform sampling from a finite set S. A function µ : N → R≥0 is negligible if, for every polynomial p, there is an Np such that µ(n) < 1/p(n) for every n ≥ Np . A register R is associated with a finite-dimensional Hilbert space, also denoted R. We write L(R) for the linear operators on R and D(R) for the density operators on R. An operator M is positive/positive semidefinite, written M ≥ 0, if ⟨ψ| M|ψ⟩ ≥ 0 for every vector |ψ⟩. For self-adjoint (or Hermitian4 ) operators M, N, the Loewner order M ≤ N means that N − M ≥ 0. A density operator ρ ∈ D(R) satisfies ρ ≥ 0 and Tr(ρ) = 1. A pure state |ψ⟩ is identified with the rank-one density operator |ψ⟩⟨ψ|. If ρRS is a bipartite state, its reduced state on R is ρR = TrS (ρRS ). All partial traces in this note are unnormalized as linear maps on operators. For an operator M, the operator norm and trace norm are √ ∥ M∥∞ := sup ∥ M|ψ⟩∥, ∥ M∥1 := Tr M† M. ∥ψ∥=1

We will repeatedly use the equivalent characterization

∥ M∥∞ = sup |⟨η | M|ξ ⟩| . ∥ξ ∥=1 ∥η ∥=1

The operator norm is submultiplicative: ∥ MN ∥∞ ≤ ∥ M∥∞ ∥ N ∥∞ . If M = M† , then ∥ M ∥∞ is the largest absolute value of an eigenvalue of M. For a self-adjoint operator M = ∑ j λ j v j v j , define its positive part by M+ := ∑ max{λ j , 0} v j v j . j

Then M ≤ M+ ≤ ∥ M+ ∥∞ I. Consequently, for every density operator ρ, Tr( Mρ) ≤ ∥ M+ ∥∞ . A quantum channel Φ : L(R) → L(S) is a completely positive trace-preserving linear map. We abuse notation and also use IA : L(A) → L(A) to denote the identity channel. A measurement with outcome set X is a POVM { Mx } x∈X satisfying Mx ≥ 0 and ∑ x Mx = I. On input state ρ, the Born rule gives Pr[ x ] = Tr( Mx ρ). A binary POVM { M0 , M1 } can equivalently be represented by the self-adjoint contraction B := M0 − M1 ,

− I ≤ B ≤ I.

Conversely, I+B I−B , M1 = . 2 2 If outcome 0 is assigned value +1 and outcome 1 is assigned value −1, then Tr( Bρ) = Pr[0] − Pr[1] is the signed bias of the outcome. We also use the following standard facts: M0 =

(i) every self-adjoint operator has an orthonormal eigenbasis; 4 We are only concerned with finite-dimensional Hilbert spaces.

4

(ii) if M ≥ rI for some r > 0, then M is invertible and 0 < M−1 ≤ r −1 I; (iii) if two positive operators commute, then their product is positive; (iv) Tr( MN ) = Tr( N M) whenever the products are defined, and trace is multiplicative over tensor products; (v) the ordinary vector Cauchy–Schwarz inequality is |⟨u | v⟩| ≤ ∥u∥ ∥v∥. These conventions are standard; see, for example, Watrous [Wat18]. The normalized Choi–Jamiołkowski identity proved in the next subsection is standard [Jam72; Cho75]; we record the normalization explicitly because conventions differ by factors of the input dimension. Useful Lemma.

We use the following quantum information-theoretic lemma:

Theorem 2.1. Let ΦE→BC : L(E) → L(B ⊗ C) be a quantum channel. Suppose MA ∈ L(A) and NBC ∈ L(B ⊗ C). Let E be a register such that A ≃ E. Define the maximally entangled state to be |Ω⟩AE = √ 1 ∑ j∈[dim(A)] | j⟩A | j⟩E . dim(A)

We have the following:   1 T ⊗ NBC )( IA ⊗ ΦE→BC )(|Ω⟩⟨Ω|AE ) · Tr ( NBC ΦE→BC ( ME )) = Tr ( MA dim(A) Proof. Suppose the ( j, k )th entry of M is α j,k . Thus, the (k, j)th entry of M T is α j,k .

= = =

= =

2.1

  T Tr ( MA ⊗ NBC )( IA ⊗ ΦE→BC )(|Ω⟩⟨Ω|AE )   1 T Tr ( M ⊗ N )( I ⊗ Φ )(| j k ⊗ j k ) ⟩⟨ | | ⟩⟨ | A BC E→BC ∑ A A E dim(A) j,k∈[dim (A)]   1 T Tr M j k | ⟩⟨ | ∑ A A · Tr( NBC ΦE→BC (| j ⟩⟨ k |E )) dim(A) j,k∈[dim (A)] 1 ∑ α j,k · Tr( NBC ΦE→BC (| j⟩⟨k|E )) dim(A) j,k∈[dim (A)]    1 · Tr NBC ΦE→BC  ∑ α j,k | j⟩⟨k|E  dim(A) j,k ∈[dim(A)] 1 · Tr( NBC Φ ( ME )) dim(A)

Paulis and Cliffords

We describe the single-qubit Pauli matrices below:     1 0 0 1 I= , X= , 0 1 1 0

 Y=

The phase gate is  S=

1 0

5

 0 , i

0 i

 −i , 0

 Z=

1 0

 0 . −1

and the Hadamard gate is 1 H= √ 2



1 1

 1 . −1

We state a basic fact below. Fact 2.2. Let P be a single-qubit Pauli and let |ψ⟩ be a single-qubit state such that P|ψ⟩ = θ |ψ⟩, where θ ∈ {+1, −1}. Then measuring  observable P – i.e., measuring |ψ⟩ according to the two-outcome projective  |ψ⟩ according to the      I+P I−P  , – yields the outcome θ with probability 1. measurement  2 } 2 }    {z {z | |   outcome +1 outcome −1

Notation.

We use the following notation. For strings x ∈ {0, 1}n , z ∈ {0, 1}n , Px,z =

O

Px j ,z j ,

j∈[n]

where Px j ,z j = i x j z j X x j Z z j . In other words,  I    X Px j ,z j = Z    Y Identities.

x j = z j = 0, x j = 1, z j = 0, x j = 0, z j = 1, x j = 1, z j = 1

The following are well-known identities:

1. HXH = Z 2. (SH )† Y (SH ) = Z 3. X 2 = Y 2 = Z2 = I 4. Tr( X ) = Tr(Y ) = Tr( Z ) = 0 5. Tr( XY ) = Tr(YX ) = Tr( XZ ) = Tr( ZX ) = Tr(YZ ) = Tr( ZY ) = 0

2.2

Unclonable encryption and unclonable indistinguishability

We recall the definition of unclonable encryption below; our formulation follows the unclonable IND-CPA definition of Ananth, Kaleoglu, Li, Liu, and Zhandry [Ana+22], building on Broadbent–Lord and Ananth– Kaleoglu [BL20; AK21]. Definition 2.3 (One-time private-key unclonable encryption). A one-time private-key unclonable encryption scheme is a triple of quantum algorithms Π = (Gen, Enc, Dec) with message space Mn : • Gen(1n ) outputs a classical secret key k; • Enc(k, m), for m ∈ Mn , outputs a quantum ciphertext state ρct ; • Dec(k, ρct ) outputs a classical message. The scheme is correct if there is a negligible function µ such that, for every m ∈ Mn , h i $ Pr Dec(k, Enc(k, m)) = m : k ← − Gen(1n ) ≥ 1 − µ(n). Perfect correctness means that the probability is 1 for every supported key and every message. 6

Definition 2.4 (One-time unclonable-indistinguishability game). Let Π = (Gen, Enc, Dec) be a private-key quantum encryption scheme. An adversary is a tuple (G , A, B , C), where G chooses two equal-length challenge messages, A is the pre-key splitting algorithm, and B , C are the noncommunicating post-split algorithms. The experiment proceeds as follows: 1. (m0 , m1 , ρS ) ← G(1n ), with m0 , m1 ∈ Mn ; $

2. Sample k ← Gen(1n ) and b ← − {0, 1}; 3. Prepare ρct ← Enc(k, mb ) and give ρct ⊗ ρS to A; 4. A applies a channel and outputs a bipartite state ρBC ; 5. Reveal the same key k to B and C ; they output bits bB and bC without communicating; 6. (G , A, B , C) wins exactly when bB = bC = b. h i We denote the winning probability by Pr WinUI Π,G ,A,B ,C ( n ) . Definition 2.5 (Unclonable indistinguishability). The scheme Π is information-theoretically ε(n)-unclonableindistinguishable if, for every finite-dimensional adversary (G , A, B , C), i h 1 Pr WinUI + ε ( n ). Π,G ,A,B ,C ( n ) ≤ 2 It is computationally secure if the same inequality holds for every QPT adversary with ε = negl. The baseline 1/2 is achieved by sending h i one shared random guess to both recipients. We denote the advantage of (G , A, B , C) to be 1 Pr WinUI Π,G ,A,B ,C ( n ) − 2 .

Remark 2.6. In this work, we consider the message space to be {0, 1}. Hence, we only consider adversaries of the form (A, B , C) since we can without loss of generality assume that G chooses m0 = 0 and m1 = 1.

3

Construction

We describe a construction of an unclonable encryption scheme for 1-bit messages as follows: • Gen(1n ): On input a statistical security parameter n ≥ 1, it does the following: $

– x2 · · · x n ← − {0, 1}n−1 , $

– z← − {0, 1}n Set x1 = 1 and x = x1 · · · xn . Output k = ( x, z). • Enc(k, m ∈ {0, 1}): On input a key k parsed as ( x, z), message m ∈ {0, 1}, do the following: – For every j ∈ [n], set Ux j ,z j as:

Ux j ,z j =

 

I H  SH

Set Uk = Ux1 ,z1 ⊗ · · · ⊗ Uxn ,zn .

7

xj = 0 x j = 1, z j = 0 x j = 1, z j = 1

$

– Sample r2 · · · rn ← − {0, 1}n−1 . Set r1 as follows:  r1 = m

M

n M



 qj · rj  ,

j =2

where q j is defined as follows:  qj =

0 1

Px j ,z j = I, Px j ,z j ̸= I

Output an n-qubit ciphertext state |ψk,m;r ⟩ = Uk |r1 · · · rn ⟩. • Dec(k, σ): On input the secret key k parsed as ( x, z) and an n-qubit ciphertext state σ, do the following: for every j ∈ [n], measure the jth qubit using the Px j ,z j observable. That is, measure the jth qubit using        I + Px j ,z j I − Px j ,z j  the two-outcome projective measurement M j = , to obtain the outcome θ j . If   2 2   | {z } | {z }   outcome +1 outcome −1

∏nj=1 θ j is +1 then output 0, else output 1. Lemma 3.1. The above scheme satisfies correctness. (1)

(n)

Proof. Let |ψk,m;r ⟩ = |ψk,m;r ⟩ ⊗ · · · ⊗ |ψk,m;r ⟩ be a ciphertext state of a message bit m ∈ {0, 1}. Using the well-known identities from Section 2.1, we have that Ux j ,z j Z q j Ux†j ,z j = Px j ,z j . For every j ∈ [n], ( j)

Px j ,z j |ψk,m;r ⟩

Px j ,z j Ux j ,z j |r j ⟩

=

= Ux j ,z j Z q j |r j ⟩ = (−1)q j ·r j Ux j ,z j |r j ⟩ ( j)

= (−1)q j ·r j |ψk,m;r ⟩ ( j)

Thus, |ψk,m;r ⟩ is an eigenvector of Px j ,z j with eigenvalue (−1)q j r j . From Fact 2.2, we have that measuring ( j)

|ψk,m;r ⟩ using M j yields the outcome θ j = (−1)q j ·r j . If we take the product of all θ j ’s we get: n

∏ θ j = (−1)

Ln

j =1 q j r j

= (−1)

r1 ⊕

L

n j =2 q j r j



= (−1)m

j =1

In the above, we are using the fact that q1 = 1 since Px1 ,z1 ̸= I.

3.1

Security

Theorem 3.2. Let Π = (Gen, Enc, Dec), where Gen, Enc and Dec are as defined above. For every n ≥ 1 and every adversary (A, B , C), we have: h i 1 1 Pr WinUI ( n ) ≤ + ( n +1) , Π,G ,A,B ,C 2 2 2 i h where Pr WinUI Π,G ,A,B ,C ( n ) is defined in Theorem 2.4. Proof. The proof is divided into the following parts:

8

• Part 1: we will analyze the density matrix associated with the ciphertext state when the key k and the message m is fixed. • Part 2: we will consider an adversary (A, B , C) and express the winning probability in terms of upper bounding the operator norm of a matrix. • Part 3: we show an upper bound on the operator norm of the matrix constructed in Part 2. Part 1. We first fix the key k and the message bit m and consider the resulting density matrix (over the randomness of r) associated with the ciphertext state: (k,m)

1 2n −1

=

ρct

∑ n

Uk |r1 · · · rn ⟩⟨r1 · · · rn | Uk†

r ∈{0,1  }

Ln

s.t. r1 =m⊕

j =2 q j r j

(2)



Before analyzing the above equation, we first make the following observations: Z q1 ⊗ · · · ⊗ Z q n

∑

=

(−1)⟨q,r⟩ |r1 · · · rn ⟩⟨r1 · · · rn |

r ∈{0,1}n

∑

=

∑

|r1 · · · rn ⟩⟨r1 · · · rn | −

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j

|r1 · · · rn ⟩⟨r1 · · · rn |

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j ⊕1

Moreover, note that:

∑

(−1)m · ( Z q1 ⊗ · · · ⊗ Z qn ) = (−1)m ·

|r1 · · · rn ⟩⟨r1 · · · rn |

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j

−(−1)m ·

∑

|r1 · · · rn ⟩⟨r1 · · · rn |

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j ⊕1

=

∑

|r1 · · · rn ⟩⟨r1 · · · rn | −

∑

|r1 · · · rn ⟩⟨r1 · · · rn | +

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j ⊕m

=

∑

∑

|r1 · · · rn ⟩⟨r1 · · · rn | −

∑

|r1 · · · rn ⟩⟨r1 · · · rn | − I

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j ⊕m

= 2

|r1 · · · rn ⟩⟨r1 · · · rn |

|r1 · · · rn ⟩⟨r1 · · · rn |

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j ⊕m

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j ⊕m

−

∑

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j ⊕1⊕m

∑

|r1 · · · rn ⟩⟨r1 · · · rn |

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j ⊕1⊕m

r ∈{0,1}n s.t. r1 =⊕nj=2 q j r j ⊕m

In other words,

∑ n

|r1 · · · rn ⟩⟨r1 · · · rn | =

r ∈{0,1} s.t. r1 =⊕nj=2 q j r j ⊕m

1 ( I + (−1)m · ( Z q1 ⊗ · · · ⊗ Z qn )) 2

(3)

Another observation we will make is the following: for every j ∈ [n], Ux j ,z j Z q j Ux†j ,z j = Px j ,z j . From this, we can conclude that Uk (

Nn

j =1 Z

qj

)Uk† = Px,z . 9

Let us now revisit Equation (2). We have: (k,m)

ρct

=

1 2n −1

∑ n

Uk |r1 · · · rn ⟩⟨r1 · · · rn | Uk†

r ∈{0,1  }

s.t. r1 =m⊕

Ln

j =2 q j r j





=



  1 Uk   2n −1 

∑

n r ∈{0,1  }

s.t. r1 =m⊕

= = =

Ln

j =2 q j r j

  † |r1 · · · rn ⟩⟨r1 · · · rn |  Uk  

1 U ( I + (−1)m · ( Z q1 ⊗ · · · ⊗ Z qn )) Uk† (from Equation (3)) 2n k  1  · I + (−1)m · Uk ( Z q1 ⊗ · · · ⊗ Z qn )Uk† n 2 1 · ( I + (−1)m Px,z ) 2n

Thus, we have: (k,m)

ρct

=

1 · ( I + (−1)m Px,z ) 2n

(4)

Part 2. Consider an adversary (A, B , C). As mentioned in Theorem 2.6, we can assume without loss of generality that m0 = 0 and m1 = 1 and hence, omit G . We denote A to be the register corresponding to the state received by A. We denote ΦA→BC to be the quantum channel implemented by5 A. That is, Φ maps L(A) to L(B ⊗ C). After splitting, A sends the register B to B and C to C . We can implement B as a set (k)

(k)

of POVMs {ΛB ,0 , ΛB ,1 }, one for each k ∈ {0, 1}2n−1 . Similarly, C can be implemented as a set of POVMs (k)

(k)

{ΛC ,0 , ΛC ,1 }, one for each k ∈ {0, 1}2n−1 . We can define the following:   (k) (k) I +∆B I −∆B (k) (k) (k) (k) (k) • ∆B = ΛB ,0 − ΛB ,1 . Thus, we can rewrite {ΛB ,0 , ΛB ,1 } as . We will view the outcomes 2 , 2 as {+1, −1} rather than {0, 1}. (k) (k) (k) (k) (k) • ∆C = ΛC ,0 − ΛC ,1 . Similarly, we can rewrite {ΛC ,0 , ΛC ,1 } as

We can express the winning probability as follows: " ! (k) I + (−1)m ∆B p = Pr [(A, B , C) wins] = Ek=( x,z),m Tr ⊗ 2 B



(k)

I +∆C 2

I −∆C 2



(k)

!

(k)

,

I + (−1)m ∆C 2

.

ΦA→BC



(k,m) ρct



!# (5)

C

Suppose E be a Hilbert space that is isomorphic to A. Define the Choi state as follows: τABC = ( IA ⊗ ΦE→BC ) |Ω⟩⟨Ω|AE , where |Ω⟩⟨Ω|AE is a multi-dimensional EPR state with the first half A and the second half in E. Invoking Theorem 2.1 and substituting Equation (4) in Equation (5), we have the winning probability to be: " ! ! !#   m ∆(k) m ∆(k) I + (− 1 ) I + (− 1 ) T B C p = Ek=( x,z),m Tr I + (−1)m Px,z ⊗ ⊗ (τABC ) (6) 2 2 A B

C

5 To be more general, A could have some additional auxiliary register Z and then applies the splitting channel on A and Z. We omit

the register Z for the rest of the proof and our analysis goes through even if Z was taken into account.

10

If we expand the tensor product of the three operators above, we will get 8 terms. Among them, exactly 4 of the terms will have the phase (−1)m . Since, we are taking expectation over m, these terms will vanish. The only terms that will remain are the following: (k)

(k)

• IA ⊗ ∆B ⊗ ∆C , (k)

T ⊗I ⊗∆ , • Px,z B C

(k)

T ⊗∆ • Px,z B ⊗ IC ,

• IABC Thus, substituting this in Equation (6), we have: p=

 i h  1 (k) (k) (k) (k) T T Ek=( x,z) Tr IA ⊗ ∆B ⊗ ∆C + Px,z ⊗ IB ⊗ ∆C + Px,z ⊗ ∆B ⊗ IC + IABC (τABC ) 4

(7)

We define Gk , for k = ( x, z), as follows: (k)

(k)

(k)

(k)

T T ⊗ ∆B ⊗ IC − IABC ⊗ IB ⊗ ∆C + Px,z Gk = IA ⊗ ∆B ⊗ ∆C + Px,z

Similarly, we define: G=

1 E [G ] 2 k=( x,z) k

(8)

Using Equation (8), we rewrite Equation (7) as follows: p

= = = = = ≤

h  i 1 (k) (k) (k) (k) T T Ek=( x,z) Tr IA ⊗ ∆B ⊗ ∆C + Px,z ⊗ IB ⊗ ∆C + Px,z ⊗ ∆B ⊗ IC + IABC (τABC ) 4 i  h 1  (k) (k) (k) (k) T T ⊗ ∆B ⊗ IC + IABC (τABC ) ⊗ IB ⊗ ∆C + Px,z Tr Ek=( x,z) IA ⊗ ∆B ⊗ ∆C + Px,z 4 i  h 1  (k) (k) (k) (k) T T ⊗ IB ⊗ ∆C + Px,z ⊗ ∆B ⊗ IC − IABC + 2IABC (τABC ) Tr Ek=( x,z) IA ⊗ ∆B ⊗ ∆C + Px,z 4 1 Tr ((2G + 2IABC ) τABC ) 4 1 (Tr (GτABC ) + 1) 2 1 1 + ∥ G+ ∥ ∞ 2 2

The last inequality follows from the fact that τABC ≥ 0, Tr τABC = 1 and G ≤ G+ ≤ ∥G+ ∥∞ I. The rest of the proof will be devoted for upper bounding ∥G+ ∥∞ .

3.2

Part 3: Upper Bounding ∥G+ ∥∞

The first lemma that we will prove is the following. Lemma 3.3 (Conditional Overlap). Let UAB ∈ L(A ⊗ B) and let VAC ∈ L(A ⊗ C). Let dA = dim(A). Suppose: UAB =

∑ |i⟩⟨ j|A ⊗ (Ui,j )B

i,j∈[dA ]

VAC =

∑

| j⟩⟨k|A ⊗ (Vj,k )C

j,k ∈[dA ]

11

Define: e ABC = U

∑ |i⟩⟨ j|A ⊗ (Ui,j )B ⊗ IC

i,j∈[dA ]

eABC = V

∑

| j⟩⟨k|A ⊗ IB ⊗ (Vj,k )C

j,k ∈[dA ]

Then:

q

e ABC V eABC ∥∞ ≤ ∥U

q

† U † ∥ TrA UAB ∥ TrA VAC VAC ∥∞ ∥ · ∞ AB

Proof. Suppose dim(A) = dA . Fix two unit vectors |ξ ⟩ABC , |η ⟩ABC . Consider the following:   2 e ABC V eABC |ξ ⟩ABC ⟨η |ABC U 2

=

∑





⟨η |ABC |i ⟩⟨k|A ⊗ (Ui,j )B ⊗ (Vj,k )C |ξ ⟩ABC .

i,j,k ∈[dA ]

For every j, k ∈ [dA ], define AB Tj,k :=

∑ |i⟩⟨k|A ⊗ (Ui,j )B ∈ L(A ⊗ B).

(9)

i ∈[dA ]

The block multiplication above can then be regrouped as eABC = e ABC V U

∑

AB Tj,k ⊗ (Vj,k )C .

(10)

j,k ∈[dA ]

No inequality has been used in Equation (10); it is only a regrouping of the matrix blocks. For j, k ∈ [dA ], define the two vectors   † |α j,k ⟩ABC := IA ⊗ IB ⊗ (Vj,k )C |η ⟩ABC ,   AB | β j,k ⟩ABC := Tj,k ⊗ IC |ξ ⟩ABC .

(11) (12)

Because the two displayed operators act on disjoint tensor factors,    AB ⟨α j,k | β j,k ⟩ = ⟨η | IA ⊗ IB ⊗ (Vj,k )C Tj,k ⊗ IC |ξ ⟩   AB = ⟨η | Tj,k ⊗ (Vj,k )C |ξ ⟩. Hence Equation (10) implies

∑ ⟨α j,k | β j,k ⟩ .

e ABC V eABC |ξ ⟩ = ⟨ η |U

(13)

j,k ∈[dA ]

Applying the ordinary Cauchy–Schwarz inequality to the two families of vectors gives 2

∑⟨α j,k | β j,k ⟩ j,k

≤

∑⟨α j,k | α j,k ⟩ j,k

We now identify the two sums on the right-hand side. 12

!

∑⟨ β j,k | β j,k ⟩ j,k

! .

(14)

First,

∑⟨α j,k | α j,k ⟩

IA ⊗ IB ⊗ ∑

= ⟨η |

j,k

! † (Vj,k )C (Vj,k )C

| η ⟩.

j,k

† and tracing out A gives Expanding VAC VAC   † TrA VAC VAC =

∑ (Vj,k )C (Vj,k )C† .

(15)

j,k ∈[dA ]

Therefore, because |η ⟩ is a unit vector, 

† ∑⟨α j,k | α j,k ⟩ ≤ TrA VAC VAC j,k

 ∞

.

(16)

Second,

∑⟨ β j,k | β j,k ⟩

∑

= ⟨ξ |

! AB † AB ( Tj,k ) Tj,k ⊗ IC

| ξ ⟩.

j,k

j,k

From Equation (9), AB † AB ( Tj,k ) Tj,k

=

∑ |k⟩⟨k|A ⊗ (Ui,j )B† (Ui,j )B .

i ∈[dA ]

Summing over j, k yields

∑(Tj,kAB )† Tj,kAB = IA ⊗ ∑(Ui,j )B† (Ui,j )B .

(17)

i,j

j,k

† U On the other hand, expanding UAB AB and tracing out A gives   † TrA UAB UAB = ∑ (Ui,j )B† (Ui,j )B .

(18)

i,j∈[dA ]

Combining Equations (17) and (18) and using that |ξ ⟩ is a unit vector,   † UAB . ∑⟨ β j,k | β j,k ⟩ ≤ TrA UAB ∞

j,k

(19)

Substituting Equations (16) and (19) into Equation (14), we obtain, for every pair of unit vectors |ξ ⟩, |η ⟩, q
† U e ABC V eABC |ξ ⟩ ≤ TrA UAB ⟨ η |U AB ∞ q
† · TrA VAC VAC . ∞ Finally, for every operator W,

∥W ∥ ∞ =

sup

|⟨η |W |ξ ⟩| .

∥ξ ∥=∥η ∥=1

Taking the supremum over the two unit vectors proves q
q
† U † e ABC V eABC U ≤ TrA UAB TrA VAC VAC . AB ∞ ∞ ∞

13

(20)

We now complete Part 3. The precise quantitative security statement proved below is 1 + 2−(n+1)/2 . 2

Pr[(A, B , C) wins] ≤

(21)

For the rest of the proof, let d : = 2n ,

Kn := {( x, z) ∈ {0, 1}n × {0, 1}n : x1 = 1} ,

L := |Kn | = 22n−1 =

d2 . 2

For k = ( x, z) ∈ Kn , use the shorthand T Θk := ( Px,z )A ,

(k)

(k)

Bk := ∆B ∈ L(B),

Ck := ∆C ∈ L(C).

(22)

The operators Bk , Ck are the decoder observables already defined in Part 2. Since they arise from binary POVMs, they are self-adjoint contractions: Bk = Bk† ,

Ck = Ck† ,

− IB ≤ Bk ≤ IB ,

− IC ≤ Ck ≤ IC .

(23)

We prove some helpful lemmas and propositions below. 2 = I. Lemma 3.4 (Pauli half-frame properties). For every k = ( x, z) ∈ Kn , Px,z is Hermitian, has trace 0 and Px,z ′ ′ ′ Moreover, for k = ( x, z) and k = ( x , z ),
Tr Px,z Px′ ,z′ = d · 1[k = k′ ]. (24)

The same statements hold for the reference operators Θk . Proof. For one qubit, the four matrices i xz X x Z z are I, Z, X, Y for ( x, z) = (0, 0), (0, 1), (1, 0), (1, 1), respectively. Each is Hermitian and squares to the identity. Tensor products preserve these properties, so Px,z = † and P2 = I. Px,z x,z Because x1 = 1, the first local factor is X or Y, and therefore has trace zero. Trace is multiplicative over tensor products, so Tr( Px,z ) = 0. The one-qubit Paulis are Hilbert-Schmidt orthogonal: Tr( PP′ ) = 21[ P = P′ ]. Hence   n
Tr Px,z Px′ ,z′ = ∏ Tr Px j ,z j Px′ ,z′ j

j =1

j

= 2n 1[( x, z) = ( x ′ , z′ )] = d1[k = k′ ]. T = ± P , so P T is also Hermitian with trace 0. Finally, Every tensor Pauli satisfies Px,z x,z x,z    
T T Tr Px,z Px′ ,z′ = Tr ( Px′ ,z′ Px,z ) T = Tr Px′ ,z′ Px,z ,

which proves the orthogonality statement for Θk . Define three averaged operators on A ⊗ B ⊗ C, displaying every tensor factor: EB

:=

1 ∑ Θk ⊗ Bk ⊗ IC , L k∈K

(25)

1 ∑ Θk ⊗ IB ⊗ Ck , L k∈K

(26)

1 ∑ IA ⊗ Bk ⊗ Ck . L k∈K

(27)

n

EC

:=

n

EBC

:=

n

The operator G defined in Equation (8) can equivalently be written as G=

1 (EB + EC + EBC − IABC ) . 2 14

(28)

Proposition 3.5 (Endpoint overlap). The endpoint-correlation operators satisfy

∥ E B EC ∥ ∞ ≤

d . L

(29)

Proof. Temporarily remove the spectator identity registers and define UAB :=

1 ∑ Θk ⊗ Bk , L k∈K

VAC :=

n

1 ∑ Θk ⊗ Ck . L k∈K n

Their canonical embeddings in A ⊗ B ⊗ C are exactly EB and EC . Using Equation (24) and preserving the order of the Bob operators,   † TrA UAB UAB

=

1 ∑′ Tr(Θk Θk′ ) Bk Bk′ L2 k,k

=

d d Bk2 ≤ IB . L L2 ∑ k

Bk2 ≤ IB follows from the fact that Bk is Hermitian and moreover, − IB ≤ Bk ≤ IB . (from Equation (23)). Similarly,   d d † TrA VAC VAC = 2 ∑ Ck2 ≤ IC . L L k Applying the conditional-overlap lemma (Lemma 3.3) proved above gives r r d d d = . ∥ E B EC ∥ ∞ ≤ L L L

Proposition 3.6 (Propagation through agreement moments). For every integer ℓ ≥ 0, EB EℓBC EC

∞

≤ ∥ E B EC ∥ ∞ ≤

d . L

(30)

Proof. For ℓ ≥ 1, direct expansion while preserving the order inside each recipient register gives EB EℓBC EC

=

1 IA ⊗ IB ⊗ Ck1 · · · Ckℓ (EB EC ) ∑ ℓ L k ,...,k ∈Kn 1 ℓ
· IA ⊗ Bk1 · · · Bkℓ ⊗ IC .

(31)

For k = (k1 , . . . , k ℓ ), define Wk,B and Wk,C as follows: Wk,B = IA ⊗ Bk1 · · · Bkℓ ⊗ IC

Wk,C = IA ⊗ IB ⊗ Ck1 · · · Ckℓ

We upper bound the operator norm of the above matrices below. ℓ

∥Wk,B ∥∞ ≤ ∥ IA ∥∞ · ∥ Bk1 · · · Bkℓ ∥∞ · ∥ IC ∥∞ ≤ ∏ ∥ Bki ∥∞ ≤ 1 i =1

The last inequality follows from the fact that for every i, Bki has operator norm at most 1 (from Equation (23)). Similarly, we have ∥Wk,C ∥∞ ≤ 1. 15

Let us revisit Equation (31) and take the operator norm on both the sides:

∥EB EℓBC EC ∥∞

=

1 ∑ Wk,C EB EC Wk,B Lℓ k ,...,k ∈Kn

≤

1 ∑ ∥Wk,C EB EC Wk,B ∥∞ Lℓ k ,...,k ∈Kn

≤

1 ∑ ∥Wk,C ∥∞ ∥EB EC ∥∞ ∥Wk,B ∥∞ Lℓ k ,...,k ∈Kn

≤

1 ∑ ∥ E B EC ∥ ∞ Lℓ k ,...,k ∈Kn

1

1

1

1

ℓ

∞

ℓ

ℓ

ℓ

= ∥ E B EC ∥ ∞

Proposition 3.7 (Four positive correctness-pattern effects). For every u, v ∈ {+1, −1}, define Γu,v :=

1 + uEB + vEC + uvEBC ) . (I 4 ABC

(32)

Then Γu,v ≥ 0 and ∑u,v∈{±1} Γu,v = IABC . Proof. For a fixed key k, define Wk,B := Θk ⊗ Bk ⊗ IC ,

Wk,C := Θk ⊗ IB ⊗ Ck .

These are Hermitian operators and with operator norm at most 1. They commute, because Wk,B Wk,C = Θ2k ⊗ Bk ⊗ Ck = IA ⊗ Bk ⊗ Ck = Wk,C Wk,B . Thus I + uWk,B and I + vWk,C are commuting positive semi-definite operators (which means that they can be simultaneously diagonalized), so Γu,v k :=

1 ( I + uWk,B )( I + vWk,C ) ≥ 0. 4

Expanding and averaging uniformly over k gives Equation (32). Averaging preserves positivity. Summing the four choices of (u, v) cancels every term containing u or v and leaves the identity. How the remaining argument fits together. Let t = ∥G+ ∥∞ . The proof below has two halves, joined by one filtered overlap. First, a unit eigenvector of G with eigenvalue t, the four positive effects, and a weighted polarization identity imply t2 ≤ Re⟨ψ|EB FEC |ψ⟩ for a positive filter F (to be defined later). Second, the agreement-moment bounds from Proposition 3.6 imply d ∥EB FEC ∥∞ ≤ . L Combining these two estimates gives t2 ≤ Re⟨ψ|EB FEC |ψ⟩ ≤ ∥EB FEC ∥∞ ≤

d . L

Every auxiliary operator introduced below is chosen to establish one of these three inequalities. 16

Proposition 3.8 (Positive-part bound). Let γ := d/L. Then

∥G+ ∥2∞ ≤ γ.

(33)

Proof. Set t : = ∥G+ ∥ ∞ . If t = 0, there is nothing to prove. Suppose t > 0. Since the Hilbert space is finite-dimensional and G is Hermitian, there is a unit vector6 |ψ⟩ABC such that G| ψ ⟩ = t | ψ ⟩.

(34)

We first extract the order information contained in the four positive effects. From Equation (32), Γ +,+ + Γ +,− =

1 ( I + E B ), 2

Γ −,+ + Γ −,− =

1 ( I − E B ), 2

1 ( I + EC ) , 2

Γ +,− + Γ −,− =

1 ( I − EC ) , 2

so − I ≤ EB ≤ I. Similarly, Γ +,+ + Γ −,+ = and

1 1 ( I + EBC ), Γ+,− + Γ−,+ = ( I − EBC ). 2 2 The above observations combined with Proposition 3.7, we have that EB , EC , and EBC are Hermitian with operator norm at most 1. Define the following operators: Γ +,+ + Γ −,− =

D := I − EBC ,

R : = E B − EC .

(35)

Fomr the above definition of D, we have 21 D = Γ+,− + Γ−,+ ≥ 0. That is, D is positive semi-definite. Moreover, 4Γ+,− = D + R, 4Γ−,+ = D − R. From Proposition 3.7, recall that Γ+,− ≥ 0 and Γ−,+ ≥ 0. Thus, we have:

−D ≤ R ≤ D.

(36)

Using Equation (28), the eigenvector equation becomes

(EB + EC )|ψ⟩ = (2tI + D)|ψ⟩.

(37)

Since D is a positive semi-definite matrix, we can consider the spectral decomposition of D as follows: D = ∑ dj vj vj ,

d j ≥ 0.

j

Then we can define the positive filter F to be: F := 2t(2tI + D)−1 = ∑ j

2t v v . 2t + d j j j

(38)

Every eigenvalue 2t/(2t + d j ) lies in (0, 1], so 0 < F ≤ I. The same diagonal representation gives

(2tI + D)F = F(2tI + D) = 2tI. 6 Without the finite-dimensional and Hermitian conditions, such a vector | ψ ⟩

17

ABC need not exist.

(39)

In particular, F commutes with D and with EBC = I − D; no commutation with EB or EC is asserted. For a vector |w⟩, define the nonnegative quadratic form QF (w) := ⟨w|F|w⟩. Expanding the sum gives QF ((EB + EC )ψ) = ⟨ψ|EB FEB |ψ⟩ + ⟨ψ|EB FEC |ψ⟩

+ ⟨ψ|EC FEB |ψ⟩ + ⟨ψ|EC FEC |ψ⟩, whereas QF ((EB − EC )ψ) = ⟨ψ|EB FEB |ψ⟩ − ⟨ψ|EB FEC |ψ⟩

− ⟨ψ|EC FEB |ψ⟩ + ⟨ψ|EC FEC |ψ⟩. The diagonal terms cancel upon subtraction. Since EB , EC , and F are self-adjoint,

⟨ψ|EC FEB |ψ⟩ = ⟨ψ|EB FEC |ψ⟩. Therefore QF ((EB + EC )ψ) − QF ((EB − EC )ψ) = 4 Re⟨ψ|EB FEC |ψ⟩.

(40)

Using Equations (37) and (39), QF ((EB + EC )ψ) = 4t2 + 2t⟨ψ|D|ψ⟩.

(41)

We use the following quadratic estimate. Claim 3.9 (Quadratic sandwich). From Equation (35) and Equation (36), D ≥ 0, R = R† , −D ≤ R ≤ D and moreover, t > 0. This implies: RFR ≤ 2tD. Proof. Let |ξ ⟩ and |η ⟩ be arbitrary. Since D+R ≥ 0

and

D − R ≥ 0,

we have 1 1 (⟨ξ | + ⟨η |)(D + R)(|ξ ⟩ + |η ⟩) + (⟨ξ | − ⟨η |)(D − R)(|ξ ⟩ − |η ⟩) 2 2 = ⟨ξ |D|ξ ⟩ + 2 Re⟨ξ |R|η ⟩ + ⟨η |D|η ⟩.

0≤

Adding 2t∥η ∥2 ≥ 0 gives

⟨ξ |D|ξ ⟩ + 2 Re⟨ξ |R|η ⟩ + ⟨η |(D + 2tI )|η ⟩ ≥ 0. For a fixed |ξ ⟩, choose

|η ⟩ = −(D + 2tI )−1 R|ξ ⟩.

Substituting this choice into Equation (42), the middle term becomes7

−2⟨ξ |R(D + 2tI )−1 R|ξ ⟩, while the final term becomes Therefore,

⟨ξ |R(D + 2tI )−1 R|ξ ⟩.   0 ≤ ⟨ξ | D − R(D + 2tI )−1 R |ξ ⟩.

7 Since R(D + 2tI )−1 R is Hermitian, ⟨ ξ |R(D + 2tI )−1 R| ξ ⟩ is real and hence we can omit the usage of Re.

18

(42)

Since this holds for every |ξ ⟩, R(D + 2tI )−1 R ≤ D. Multiplying by 2t > 0 and using F = 2t(D + 2tI )−1 gives RFR ≤ 2tD.

Consequently, QF ((EB − EC )ψ) ≤ 2t⟨ψ|D|ψ⟩. Subtracting this from Equation (41) and using Equation (40), t2 ≤ Re⟨ψ|EB FEC |ψ⟩.

(43)

It remains to upper-bound the same filtered overlap. Put q := 1/(1 + 2t) ∈ (0, 1). Since D = I − EBC , F = (1 − q)( I − qEBC )−1 . A NALYZING FN0 : For an integer N0 ≥ 1, define N0 −1

F N0 := (1 − q) ∑ qℓ EℓBC .

(44)

ℓ=0

By the definition of F N0 ,

N0 −1

EB F N0 EC = (1 − q) ∑ qℓ EB EℓBC EC . ℓ=0

The coefficients are nonnegative, so the triangle inequality and Proposition 3.6 give N0 −1

EB F N0 EC ∞

≤ (1 − q) ∑ qℓ EB EℓBC EC ℓ=0 N0 −1

∞

≤ (1 − q ) ∑ q ℓ γ ℓ=0

= (1 − q ) ·

(1 − q N0 ) ·γ 1−q

= (1 − q N0 )γ. Thus EB F N0 EC ∞ ≤ (1 − q N0 )γ.

(45)

We can alternately define F N0 as follows: First consider the following telescoping sum identity: N0 −1

N0 ( I − qEBC ) ∑ qℓ EℓBC = I − q N0 EBC

ℓ=0

Multiplying by (1 − q)( I − qEBC )−1 on both the sides. On the left hand side, the result is F N0 . Thus, we have: N F N0 = (1 − q)( I − qEBC )−1 ( I − q N0 EBC0 ) 19

U PPER BOUNDING ∥EB FEC ∥∞ : Using F = (1 − q)( I − qEBC )−1 gives F − F N0

N0 ) = (1 − q)( I − qEBC )−1 − (1 − q)( I − qEBC )−1 ( I − q N0 EBC N0 = (1 − q)( I − qEBC )−1 q N0 EBC N0 = q N0 FEBC

Note that ( I − qEBC ) and EBC commute. Hence, ( I − qEBC )−1 and EBC commute as well which further implies that F and EBC commute. Thus, N

F − F N0 = q N0 EBC0 F.

(46)

N

Since all the four operators EB , EBC0 , F and EC are contractions, we have the following: EB (F − F N0 )EC ∞

=

N

EB (q N0 EBC0 F)EC

∞

N0 ≤ q N0 ∥EB ∥∞ · ∥EBC ∥ ∞ · ∥ F ∥ ∞ · ∥ EC ∥ ∞

≤ q N0 . Therefore

∥EB FEC ∥∞

≤

EB (F − F N0 )EC ∥∞ + ∥EB F N0 EC ∞

≤ (1 − q N0 )γ + q N0 . Since q ∈ (0, 1), N0 → ∞ gives

∥EB FEC ∥∞ ≤ γ.

(47)

Finally, t2 ≤ Re⟨ψ|EB FEC |ψ⟩ ≤ ∥EB FEC ∥∞ ≤ γ. Since t = ∥G+ ∥∞ , this proves the proposition. By Propositions 3.6–3.8, r

∥ G+ ∥ ∞ ≤

d = L

r

2 . d

Substituting this into the bound at the end of Part 2 gives r 1 1 2 p ≤ + 2 2 d 1 = + 2−(n+1)/2 , 2 where the last equality uses d = 2n . This proves Equation (21) and completes the proof.

20

References [AK21]

Prabhanjan Ananth and Fatih Kaleoglu. “Unclonable Encryption, Revisited”. In: Theory of Cryptography. Vol. 13042. Lecture Notes in Computer Science. Springer, 2021, pp. 299–329. DOI: 10.1007/978-3-030-90459-3_11.

[AKL23]

Prabhanjan Ananth, Fatih Kaleoglu, and Qipeng Liu. “Cloning Games: A General Framework for Unclonable Primitives”. In: Advances in Cryptology—CRYPTO 2023, Part V. Vol. 14085. Lecture Notes in Computer Science. Springer, 2023, pp. 66–98. DOI: 10.1007/978-3-031-385544_3.

[AKY25]

Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen. “Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography”. In: 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Vol. 325. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025, 7:1–7:23. DOI: 10.4230/ LIPIcs.ITCS.2025.7.

[Ana+22]

Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry. “On the Feasibility of Unclonable Encryption, and More”. In: Advances in Cryptology—CRYPTO 2022, Part II. Vol. 13508. Lecture Notes in Computer Science. Springer, 2022, pp. 212–241. DOI: 10.1007/ 978-3-031-15979-4_8.

[BBC26]

Archishna Bhattacharyya, Anne Broadbent, and Eric Culf. The Uncloneable Bit Exists. 2026. arXiv: 2603.08916 [quant-ph].

[BC26]

Archishna Bhattacharyya and Eric Culf. “Uncloneable Encryption from Decoupling”. In: Nature Physics 22.2 (2026), pp. 315–318. DOI: 10.1038/s41567-025-03154-7.

[BG26]

James Bartusek and Eli Goldin. “Unclonable Encryption in the Haar Random Oracle Model”. In: arXiv preprint arXiv:2603.11437 (2026).

[BL20]

Anne Broadbent and Sébastien Lord. “Uncloneable Quantum Encryption via Oracles”. In: 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Vol. 158. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl–LeibnizZentrum für Informatik, 2020, 4:1–4:22. DOI: 10.4230/LIPIcs.TQC.2020.4.

[Bot+26]

Pierre Botteron, Anne Broadbent, Eric Culf, Ion Nechita, Clément Pellegrini, and Denis Rochette. “Towards Unconditional Uncloneable Encryption”. In: Quantum 10 (2026), p. 2157. DOI: 10.22331/q-2026-07-08-2157.

[Cho75]

Man-Duen Choi. “Completely Positive Linear Maps on Complex Matrices”. In: Linear Algebra and its Applications 10.3 (1975), pp. 285–290. DOI: 10.1016/0024-3795(75)90075-0.

[CLX25]

Andrea Coladangelo, Qipeng Liu, and Ziyi Xie. On the Security of XOR Repetition for Unclonable Encryption. Preprint. 2025.

[Die82]

Dennis Dieks. “Communication by EPR Devices”. In: Physics Letters A 92.6 (1982), pp. 271–272. DOI: 10.1016/0375-9601(82)90084-6.

[Got03]

Daniel Gottesman. “Uncloneable Encryption”. In: Quantum Information and Computation 3.6 (2003), pp. 581–602. DOI: 10.26421/QIC3.6-2.

[Jam72]

Andrzej Jamiołkowski. “Linear Transformations Which Preserve Trace and Positive Semidefiniteness of Operators”. In: Reports on Mathematical Physics 3.4 (1972), pp. 275–278. DOI: 10 . 1016/0034-4877(72)90011-0.

[MST21]

Christian Majenz, Christian Schaffner, and Mehrdad Tahmasbi. “Limitations on uncloneable encryption and simultaneous one-way-to-hiding”. In: arXiv preprint arXiv:2103.14510 (2021).

[Ope26]

OpenAI. Prompt Used for “A Proof of the Cycle Double Cover Conjecture”. July 9, 2026. URL: https: / / cdn . openai . com / pdf / 04d1d1e4 - bc75 - 476a - 97cf - 49055cd98d31 / cdc _ prompt . pdf (visited on 07/22/2026). 21

[Wat18]

John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. DOI: 10. 1017/9781316848142.

[WZ82]

William K. Wootters and Wojciech H. Zurek. “A Single Quantum Cannot Be Cloned”. In: Nature 299 (1982), pp. 802–803. DOI: 10.1038/299802a0.

[ZHC+26]

Junyi Zhang* , Xinjie He* , Hyunsik Chae, Ethan Ji, Eric Jiang, Rushil Raghavan, Yiwen Kou, Alex Taylor, Kai-Wei Chang† , Raghu Meka† , Violet Peng† , Amit Sahai† , Terence Tao† , and Wei Wang† . UCLA Moonshot Harness. * Co-first authors with equal contribution. The remaining students are ordered by contribution to the harness. † Principal investigators, listed at the end in alphabetical order by last name. 2026.

22

A

Glossary of notation Symbol

Formal definition

Informal meaning

n

The security parameter.

The number of qubits in the ciphertext.

d

d : = 2n .

Dimension of the ciphertext Hilbert space.

m

m ∈ {0, 1}.

Kn L k = ( x, z) Px j ,z j Px,z

The plaintext bit. n

n

Kn := {( x, z) ∈ {0, 1} × {0, 1} : x1 = 1} . d2 L := |Kn | = 22n−1 = . 2 A uniformly sampled element of Kn . Px j ,z j := i Px,z :=

xj zj

n O

xj

zj

The set of possible secret keys. The number of possible keys. The secret key.

X Z ∈ { I, X, Y, Z }.

The local Pauli on qubit j.

Px j ,z j .

The n-qubit Pauli selected by the key.

j =1

(

qj

Ux j ,z j

Uk

0, Px j ,z j = I, 1, Px j ,z j ̸= I.   x j = 0,  I, Ux j ,z j := H, x j = 1, z j = 0,   SH, x j = z j = 1. q j :=

Uk :=

n O

Indicates whether the j-th local Pauli is nonidentity. Local change from the computational basis to the eigenbasis of Px j ,z j .

Ux j ,z j .

The complete product basis-change unitary.

j =1

r

r := (r2 , . . . , rn ) ∈ {0, 1}n−1 , sampled uniformly.

r1

r1 : = m ⊕

n M

qj rj .

The first preparation bit, chosen to enforce the required parity.

j =2

|ψk,m;r ⟩

The private encryption randomness.

|ψk,m;r ⟩ := Uk |r1 , r2 , . . . , rn ⟩.

The pure ciphertext emitted for one fixed private random string.

ΦE→BC

1 ψk,m;r . Equivalently, ∑ ψ 2n−1 r2 ,...,rn k,m;r 1 (k,m) ρct = ( I + (−1)m Px,z ) . d Φ : L(E) −→ L(B ⊗ C).

τABC

τABC := (idA ⊗ΦE ) (|Ω⟩⟨Ω|AE ) .

The normalized Choi state of the splitting channel.

Θk

T Θk := ( Px,z )A .

The key-dependent Pauli acting on the Choi reference register.

Bk

Bk := ∆B = ΛB ,0 − ΛB ,1 ∈ L(B).

Ck

Ck := ∆C = ΛC ,0 − ΛC ,1 ∈ L(C).

EB

EB :=

(k,m)

ρct

(k,m)

ρct

:=

The ciphertext density operator after the private randomness is discarded. The adversary’s ciphertext-splitting channel.

(k)

(k)

(k)

Bob’s signed binary-decoder observable for key k.

(k)

(k)

(k)

Charlie’s signed binary-decoder observable for key k.

1 ∑ Θk ⊗ Bk ⊗ IC . L k∈K

Average reference–Bob correlation.

n

23

Symbol EC

Formal definition 1 EC : = ∑ Θk ⊗ IB ⊗ Ck . L k∈K

Informal meaning Average reference–Charlie correlation.

n

EBC

EBC :=

1 ∑ IA ⊗ Bk ⊗ Ck . L k∈K

Average Bob–Charlie agreement correlation.

n

1 (E + EC + EBC − I ) . 2 B

G

G :=

G+

The positive part of G.

Γu,v

Γu,v :=

γ

γ :=

t

t : = ∥G+ ∥ ∞ .

The largest positive eigenvalue of G.

|ψ⟩

A unit vector satisfying G|ψ⟩ = t|ψ⟩.

A top positive-eigenvalue direction of G.

D

D := I − EBC .

The Bob–Charlie disagreement operator.

R

R : = E B − EC .

The difference between Bob’s and Charlie’s reference correlations.

F

F := 2t(2tI + D)−1 .

A filter that emphasizes directions where Bob and Charlie agree.

QF ( w )

QF ( w ) : = ⟨ w |F| w ⟩.

The quadratic form induced by the filter F.

The centered operator whose positive spectrum controls the winning advantage. The portion of G that can increase the success probability above 1/2.

1 ( I + uEB + vEC + uvEBC ) , 4

d 2 = . L d

u, v ∈ {±1}.

The four positive Bob/Charlie correctness-pattern operators. The endpoint and agreement-moment upper bound.

1 ∈ (0, 1). 1 + 2t

q

q :=

F N0

F N0 := (1 − q) ∑ qℓ EℓBC .

The geometric-series parameter used to approximate F.

N0 −1

A finite polynomial approximation to F.

ℓ=0

24