No-Go Bounds for Quantum Seals
Shelby Kimmel Shimon Kolkowitz





1]Shelby Kimmel
[1]Department of Computer Science,
Middlebury College, 
2]Shimon Kolkowitz
[2]Department of Physics, University of Wisconsin-Madison, 





No-Go Bounds for Quantum Seals
    [
    
==============================







We investigate the feasibility of quantum seals. A quantum seal is a state
provided by Alice to Bob along with information which Bob can use to make a measurement, 
“break the seal,” and read the classical message stored inside.
There are two success criteria for a seal: the probability Bob can
successfully read the message without any
further information from Alice must be high, and if Alice asks for the state back from Bob, the
probability Alice can tell if Bob broke the seal without permission must be
high. We build on the work of [Chau, PRA 2007], which gave optimal bounds on these criteria, 
showing that they are mutually exclusive for high probability. We weaken the assumptions of this previous work by providing Bob with only a classical description of a prescribed measurement, rather than classical descriptions of the possible seal states. We show that this weakening does not affect the bounds but does simplify the analysis. We also prove upper and lower bounds on an alternative operational metric for measuring the success criteria.






 






§ INTRODUCTION


With a quantum seal, a sender hopes to communicate classical information using a quantum state and also verify whether that information has been extracted.
This functionality is called a “seal” 
in analogy with the impressions made in wax or clay that have been 
used to ensure the integrity of letters and packages for thousands of years <cit.>. 
Alice wishes to give Bob a message that is only to be opened and read by Bob at a later date when an
agreed upon set of conditions has been met. For example, the conditions might be
“Do not open the message until the third night of Hannukah,” or 
“Only open the message if instructed to do so by Alice.”  
To this end, Alice gives Bob a quantum state and a classical description of a quantum
measurement. If Bob makes the measurement described by Alice, with high
probability he will extract the classical value of the message. Bob should be able
to make this measurement without further information from Alice. 
However, at any time before the agreed upon conditions have been met, 
Alice can request the state back, and she would like to detect with high probability whether Bob has
cheated and read the message, thereby “breaking the seal” prematurely.  
A seal therefore has two success criteria:
1) the probability Bob can successfully read the message if he follows Alice's instructions must be high, 
and 2) the probability Alice can tell if Bob broke the seal without permission must be high. 

Quantum seals were introduced by Bechmann-Pasquinucci <cit.>, giving
rise to a vibrant discussion into their feasibility under
different considerations
<cit.>. The upshot is that without limitations on Bob's
possible measurements, if Alice wants Bob to be able to learn her complete
classical message with high probability, then she
will not be able to detect his breaking of the seal with high probability[In past literature, seals where Alice and Bob needed to be able to succeed in their tasks with certainty were called “perfect” seals while “imperfect” seals allowed for only probabilistic success. When more than a single bit was encoded the seal was called a “string seal.” Here we do not bother with these distinctions, as our results are general and apply to all of these cases.]. However, this does not necessarily mean that quantum seals are entirely useless; for example, to send a very long message Alice can design a quantum seal that gives her a very high probability to catch Bob cheating, while also giving Bob a low but still finite probability of extracting the correct message that is much higher than his vanishingly small chance of randomly guessing it <cit.>.

Quantum seals are related to other quantum cryptographic protocols with no-go results such as 
quantum bit commitment <cit.> and quantum one-time memories <cit.>. In bit commitment, Alice first provides a quantum
state, which is her commitment to a bit, and then she might later be asked to reveal her bit. Note this is in contrast to quantum seal protocols, in that once Alice has provided the seal to
Bob, she is never asked to provide further information. It has been shown that quantum bit commitment can be built from quantum seals, and so is a strictly weaker primitive <cit.>.

On the other hand, a straightforward argument shows that a one-time memory (OTM) can be used to create a nearly perfect seal. An OTM is a
device that contains two messages s,t∈{0,1}^n. Once one message is
read, the other is destroyed. To create a seal from an OTM, Alice
would set s to be the message and t to be a random string. Bob could
therefore learn s perfectly without further input from Alice. However, once he reads s, he destroys t. 
To test if Bob had read the message, Alice could ask for the OTM back, try to learn t, and if
it was inaccessible or not the string she stored, she would know Bob had
cheated. Bob could try to
make a new OTM to give back to Alice as a fake, but he would not
know what string to store as t, so his guess would be inaccurate with high
probability.  Since seals are weaker than OTMs, a no-go for quantum
 seals does not necessarily follow from the no-go for quantum OTMs. However, we note that under certain physically realistic assumptions
 (such as no entangling operations), quantum OTMs can exist
 <cit.>, which implies the existence of quantum seals under
 similar restricted scenarios.

In prior work, Chau <cit.> proved optimal bounds on the success criteria of quantum seals in the case that Bob has knowledge of the different quantum states that he might receive from Alice. In this work, we weaken Bob's advantage by not giving him a description of the seal states, and instead giving him only a classical description of a quantum measurement and instructions for how to associate the possible outcomes with classical messages. Alice promises Bob that if he uses the specified measurement on the seal state, he will obtain the correct message with some guaranteed probability. She does not provide Bob with any further information as to how to implement the quantum measurement; Bob's choice of implementation affects the probability that his measurement can be detected by Alice[Our setup is therefore similar to that in <cit.>, but with the possibility of sealing a message that is longer than a single bit.]. Since Bob does not have information about the underlying states, it is potentially harder for him to design a cheating strategy.

Even with this restriction on Bob's information, we show that Bob can still read the message with high probability without detection. In particular, when we consider the case that Alice never wants to falsely accuse Bob of cheating, which is the same metric used by Chau <cit.>, we achieve the same bounds. Thus it would seem that restricting Bob's information in this way does not have a significant effect, while our analysis is somewhat simplified relative to Chau's. 

We additionally examine an alternative operational metric for Alice's success in detecting whether Bob has broken the seal: we look at Alice's probability of detecting Bob cheating if she makes the optimal measurement to distinguish between the broken and unbroken seal states. This measurement may sometimes cause her to falsely accuse Bob of breaking the seal when he hasn't, but gives her a higher probability of detecting Bob's measurement when he has broken the seal[This is in contrast to the metric used by Chau <cit.>, in which Alice makes a measurement that would never result in a false accusation of cheating against Bob, but which as a result is suboptimal for distinguishing between a broken and unbroken seal state.]. Under this metric we show that Alice's chances of detecting Bob, though improved, are still not good.

In order to obtain some of our results, in Sec. <ref> we prove a variation on 
the Gentle Measurement Lemma <cit.> which may be of independent interest.
The Gentle Measurement Lemma states that if a measurement outcome occurs with high probability, and
if that outcome is measured, then the state after the measurement is difficult
to distinguish from the original state. We
extend the Gentle Measurement Lemma to show that the state after measurement is difficult to distinguish from the original state with high probability even if the outcome of the measurement is not known.






§ PRELIMINARIES




 §.§ Notation and Quantum Measurement



We use  to denote a Hilbert space, and () to denote the set
of positive linear operators acting on  with trace one; ()
is the set of density matrices on . For N∈ℕ, we let [N]={1,…,N}. ℐ_A denotes the identity operator on _A, but
we drop the subscript if clear from context.

A quantum measurement is described by a positive operator value measure (POVM).
A POVM is a set of operators {ℰ_i}_i∈ [N] acting on a Hilbert space
 such that ∑_i=1^Nℰ_i=ℐ and ℰ_i≽ 0. Given a state ρ∈(), the probability of measuring outcome i is (ℰ_iρ).

There are an infinite number of ways to implement a given POVM
<cit.> (see <cit.> for a nice
description of methods to implement a POVM) and the implementation affects the
state the system is left in after the measurement. Here, we think of the implementation as a two step process. In the first step, we apply what we call the standard implementation: if ρ is measured and outcome i is obtained, the state collapses to √(ℰ_i)ρ√(ℰ_i)/(ℰ_iρ ). In the second step, a completely positive trace preserving (CPTP) map is applied to the resultant state, and this map can depend on the outcome i of the first step.

If ρ is measured using a POVM {ℰ_i}, and if the outcome of the measurement is not known, the post-measurement system is described by the density matrix ∑_i√(ℰ_i)ρ√(ℰ_i) <cit.>.

The trace distance between quantum states ρ,σ∈() is
1/2ρ-σ_1, where A_1 = (√(A^† A)). The
trace distance has an important operational meaning: given a state promised to be either
ρ or σ with equal probability, the maximum probability of correctly
distinguishing which state one has is 1/2+1/4ρ-σ_1.

Finally, let

    Z(x)=([   x   0;   0 1-x ]).






 §.§ Set-Up


We assume the message protected by the seal takes a value m∈[M] for M≥ 2.
Alice encodes the message into a pure state |ψ_m⟩∈_A⊗_B where _A refers to System A, the part of the system
that Alice retains, while _B refers to System B, the part of the system Alice
gives to Bob as the sealed message. (If Alice instead would prefer to encode into a mixed
state, we can always purify the state without loss of generality. See e.g.
<cit.>.) Thus Alice sends to Bob the state
ρ_m∈(_B), where ρ_m is the reduced density matrix of
|ψ_m⟩ on _B.

In addition to the state ρ_m, Alice gives Bob a classical description of a POVM ℰ⃗={ℰ_i,j}_i∈[M],j∈ [M_i]. She promises Bob that if he
performs the POVM ℰ⃗  on ρ_m, he will get an outcome (i,j) such that i=m with probability at least p. This promise implies

    ∑_j∈ [M_m](ℰ_m,jρ_m)≥ p.


After giving System B to Bob, Alice may ask for it to be returned to her at any point. Bob's goal in our scenario is to make a measurement on ρ_m that allows him to determine m, but when he returns the system to Alice, she can not detect his measurement. Alice's goal is to design a state ρ_m and a POVM ℰ⃗, with the properties described above, such that Bob can not learn m without significantly altering |ψ_m⟩, so that when Alice asks for System B to be returned, she can reliably determine whether Bob has cheated.

We use two metrics to judge Alice's success in detecting Bob's potential
breaking of the seal. First, suppose Alice has no prior knowledge as to whether Bob has cheated, so her a priori belief is that she either has her original state or a broken state with equal probability. We call p_dist her maximum success probability in distinguishing whether or not Bob made a measurement that allowed him to learn the message with probability at least p. Second, suppose Alice would like to detect
if Bob made a measurement that allowed him to learn the message with probability at least p, but never wants to falsely accuse Bob
of cheating if he didn't actually read the message. We call p_NFP (NFP
for “no false positives”) her maximum success probability in this task. This metric was previously used by Chau to quantify Alice's ability to detect cheating, but without the “no false positives” interpretation <cit.>. If Alice chooses her message state |ψ_m⟩ from some distribution of states, we take p_dist and p_NFP to be her success probabilities averaged over her choice of state.

For the quantum seal to behave as desired, we would like to have a protocol
in which p is large, and p_dist or p_NFP are large, so that Bob can read the message correctly with high probability, 
but also Alice can detect if he read it or not. However, we show that if p
is large, Bob can implement a POVM on ρ_m in such a way that p_dist and
p_NFP will be small.




 §.§ A Variation of the Gentle Measurement Lemma



The Gentle Measurement Lemma <cit.> says that if a state has high overlap with a POVM operator and that outcome is measured, then the post-measurement state will not differ considerably from the pre-measurement state. While there are several different formulations of the Lemma, the one that is most relevant to this work is formulated as follows: given a POVM operator E_j on 
and a state ρ∈ D(), where (ℰ_jρ)≥ 1-ϵ, then

    ρ-√(ℰ_j)ρ√(ℰ_j)_1≤ 2√(ϵ).


Here we consider a variation of this Lemma for the case where an initial state ρ is measured with a POVM, ℰ⃗, where one of the POVM operators E_j has high overlap with ρ, but where the outcome of the measurement is unknown. 
This scenario occurs, for example, if Alice knows that Bob has made a measurement, but he hasn't told her what the outcome of his measurement is. When the outcome of a measurement is unknown, the best description of the post-measurement state is given by a probabilistic combination of all possible outcomes of the measurement. In particular, as discussed in <ref>, if the POVM { E_i} is applied to a state ρ, but the outcome is unknown, the density matrix of the resultant state is given by ∑_i√(ℰ_i)ρ√(ℰ_i). 

We show that the trace distance between the original state and the post measurement state is still small, even in the case that the outcome of the measurement is unknown. In particular, we prove the following:

Given a state ρ∈ D() and a POVM {ℰ_i} on  such that there is one POVM
operator ℰ_j where (ℰ_jρ)≥ 1-ϵ, then the trace distance between the pre-measurement state and the post-measurement state when the measurement outcome is unknown is bounded as

    ρ-∑_i√(ℰ_i)ρ√(ℰ_i)_1≤ 2√(ϵ)+ϵ.



Using the triangle inequality:

    ρ-∑_i√(ℰ_i)ρ√(ℰ_i)_1   ≤ρ-√(ℰ_j)ρ√(ℰ_j)_1+∑_i≠ j√(ℰ_i)ρ√(ℰ_i)_1
       ≤ 2√(ϵ)+∑_i≠ j√(ℰ_i)ρ√(ℰ_i)_1,

where we've applied <ref>. Because √(ℰ_i)ρ√(ℰ_i) is positive semidefinite, and using properties of the trace,

    ∑_i≠ j√(ℰ_i)ρ√(ℰ_i)_1=∑_i≠ j(√(ℰ_i)ρ√(ℰ_i))=∑_i≠ j(ℰ_iρ)=(∑_i≠ jℰ_iρ).

Now since ∑_iℰ_i=ℐ and (ρ)=1,

    (∑_i≠ jℰ_iρ)=1-(ℰ_jρ)≤ϵ.

Combining <ref> and <ref> and plugging into <ref>, we have

    ρ-∑_i√(ℰ_i)ρ√(ℰ_i)_1≤ 2√(ϵ)+ϵ.





§ A NAIVE APPROACH THAT FAILS



In this section, we present a straightforward strategy that seems promising[Indeed, this strategy resembles the initial proposal for a quantum seal by Bechmann-Pasquinucci <cit.>.], yet ultimately fails.

Let M=2, so Alice wants to encode a binary message. Suppose Alice creates a state on 3q qubits that she plans to send entirely to Bob; that is, she sets _A=1, and _B=ℂ^2^3q. She chooses σ,τ∈ S_3q uniformly at random, where S_n is the symmetric
group of degree n. Then Alice gives one of the following states to Bob, depending on whether she wants the message to be “1” or “2”:

    |ψ_1⟩   =U_σ|0⟩^⊗ 2q|+⟩^⊗ q,
    |ψ_2⟩   =U_τ|1⟩^⊗ 2q|+⟩^⊗ q,

where U_σ (respectively U_τ) is a unitary that
acts on a Hilbert space of 3q qubits, and permutes the qubit registers
according to the permutation σ (resp. τ).

Alice tells Bob to measure each qubit using the POVM {0,1} (i.e. the standard basis projective measurement), and if the number of 0 outcomes is at least 3q/2, he should decide m=1, and
otherwise, he should decide m=2.
If Bob uses the standard implementation of Alice's POVM, he will perform a projective measurement, and he will be able to read the message perfectly, since the the number of 0 outcomes will be at most q when m=1, and at least 2q
when m=2.

After the standard implementation, Bob is left with a standard basis state, which will be nearly orthogonal to the
original state. Thus if Alice asked for the state back, she would with high
probability be able to detect Bob's measurement. 

Bob could try to disguise his measurement by applying a CPTP map to alter his state after measurement.
Let's assume, without loss of generality, that m=1, and also that Bob knows that Alice
originally sent a state of the form U_σ|0⟩^⊗
2q|+⟩^⊗ q for some σ∈ S_3q. (This extra information can only help Bob.) Bob can replace
qubits in registers where he got outcome 1 with states |+⟩, to try to
make his state closer to Alice's original state. However with extremely high
probability in the limit of large q (using e.g. Hoeffding's inequality
<cit.>), he will measure 0's in about half of the registers that originally contained
the state |+⟩. For large q, Bob has a vanishingly small probability of correctly
guessing where these “false 0” registers are, and if he guesses
incorrectly, it will make his overlap worse. Thus, there is very little Bob
can do to recover from the measurement; the seal has been broken, and Alice will detect his measurement. 

So why does this protocol fail? While Alice told Bob that he should measure in
the standard basis, Bob can instead use Alice's instructions to make a different but related measurement. He measures using the standard implementation of the POVM {Π_1,Π_2} where Π_1 is the projector onto standard
basis states whose strings have more than 3q/2 zeros, and Π_2 is the
projector onto the remaining standard basis states. Bob has thereby combined all of the measurement operators that correspond to a given outcome into a single measurement operator.
For any choice of σ,τ∈ S_3q,
Π_1|ψ_1⟩=|ψ_1⟩ and
Π_2|ψ_2⟩=|ψ_2⟩. Thus Bob can deterministically distinguish the value of the message without disturbing the state and breaking the seal, and Alice will be completely unaware of his measurement.

In the next section, we show that there is always a way for Bob to cheat in a
manner similar to this, as long as Alice wants Bob to be able to read the message
with high probability.




§ NO-GO FOR QUANTUM SEALS



We will show that a good strategy for Bob is to apply the standard implementation of the POVM {F_i}_i∈ [M], for 

    ℱ_i=∑_j∈ [M_i]ℰ_i,j,

where ℰ_i,j are the elements of Alice's recommended POVM. If outcome ℱ_i occurs, Bob decides the message is i. Averaged over Bob's outcome, the full state on _A⊗_B after
measurement is (see Section <ref>)

    ∑_i=1^Mℐ_A⊗√(ℱ_i)ψ_mℐ_A⊗√(ℱ_i).


Now if Alice asks for Bob to return his system, and he did not make a measurement, she will have the state ψ_m. If he did make the measurement using the POVM in <ref>, the state will be that in <ref>. 

We first bound p_dist. Alice's goal is to determine
which state she possesses. We assume Alice knows that if Bob made a
measurement, he measured using the standard implementation of the POVM in <ref>,
as this information can only help her. Then using <ref>, we have

    p_dist≤   1/2+1/4ψ_m-∑_i=1^Mℐ_A⊗√(ℱ_i)ψ_mℐ_A⊗√(ℱ_i)_1≤1/2+1/4(2√(1-p)+1-p)),
 
which we plot in <ref>.




Next we bound p_NFP.
If Bob is honest, when he returns System B to Alice, she will have the state |ψ_m⟩. Therefore, Alice needs a two-outcome POVM, such that one outcome will never occur if Bob is honest. The POVM that achieves this is {ℐ_AB-ψ_m,ψ_m}, where the first outcome will only be observed if Bob is dishonest. Thus

    p_NFP=   ((ℐ_AB-ψ_m)(∑_i∈ [W](ℐ_A⊗√(ℱ_i)ψ_mℐ_A⊗√(ℱ_i))))
    
    =    1-∑_i∈ [M]|⟨ψ_m|ℐ_A⊗√(ℱ_i)|ψ_m⟩|^2


Now

    ⟨ψ_m|ℐ_A⊗√(ℱ_i)|ψ_m⟩≥⟨ψ_m|ℐ_A⊗ℱ_i|ψ_m⟩=(ℱ_iρ_m)

because the eigenvalues of ℱ_i are between 0 and 1. Plugging in and using Cauchy-Schwarz, we have

    p_NFP≤ 1-(ℱ_mρ_m)^2-(∑_i∈ [M]∖ m(ℱ_iρ_m))^2/M-1=1-(ℱ_mρ_m)^2-(1-(ℱ_mρ_m))^2/M-1.

For values of (ℱ_mρ_m)≥ 1/M, this expression is decreasing in (ℱ_mρ_m), so since (ℱ_mρ_m)≥ p, we have

    p_NFP≤ 1-p^2-(1-p)^2/M-1.
 
 Bounds on p_NFP for several values of M are shown in <ref>. This formula is identical to Chau's bound <cit.>[In Chau's case, he deals with two probabilities, p and p_max, which result from Bob having knowledge of the seal state. In our case Bob has no knowledge of the seal state, so effectively p=p_max.]. Thus unfortunately we find Alice can not boost her success of detecting Bob's breaking of the seal by withholding information about the seal states.



By either metric (p_dist or p_NFP), we see that there is a trade off. If Alice wants Bob to be able to read the message with probability close to 1, then she will not be able to detect with high probability whether he has broken the seal.





§ ACHIEVABILITY



In order to lower bound the achievability of the upper bounds of <ref>, it is sufficient to analyze the case that Alice not only provides a classical description of a POVM (and information about how to associate outcomes with classical messages), but additionally gives Bob information about the quantum seal states. Since this additional information can only help Bob, it will allow us to put lower bounds on p_dist and p_NFP.

This is precisely the scenario that Chau analyzed, and he showed that his bounds are achievable <cit.>. Since our p_NFP is the same as his bounds, this implies that our p_NFP bound is optimal (see Fig <ref>). 
It is interesting to note that when M≫ 1, for which Bob will have a negligibly small probability of randomly guessing the correct message, quantum seals still offer some rather non-trivial capabilities. For example, Alice can create a quantum seal where Bob has a 10% chance of correctly reading the entire message, but Alice can detect if Bob has cheated with 99% probability and no false positives. 

We next investigate whether Alice can achieve the bounds of <ref> for the metric p_dist for the case of a single bit message (M=2). We consider a specific strategy for Alice and determine the probability with which she can detect Bob's cheating. This allows us to put a lower bound on p_dist, but the specific strategy we choose might not be optimal.

Consider the case that _A=1, _B=ℂ^2, and M=2,

    |ψ_1⟩=   √(p)|0⟩+e^iϕ√(1-p)|1⟩,
    |ψ_2⟩=   √(1-p)|0⟩+e^iϕ√(p)|1⟩,

for ϕ that Alice has chosen uniformly at random from [0,2π], and 
ℰ⃗={ℰ_1,ℰ_2} where

    ℰ_1=([ 1 0; 0 0 ]),
        ℰ_2=([ 0 0; 0 1 ]).

Alice provides all of this information to Bob, as well as telling him the value of p (we assume p>1/2). As discussed above, since we are putting a lower bound on p_dist, it is acceptable for Alice to give Bob this extra information about the seal states, since that information can only help him.

Alice's success probability p_dist is always analyzed in the case that Bob makes a measurement that obtains the correct outcome with probability at least p. But note that the unique optimal POVM for distinguishing |ψ_1⟩ and |ψ_2⟩ is the POVM ℰ_1 and ℰ_2 from <ref> <cit.>, and this measurement only succeeds with probability p. Thus Bob must use this POVM to achieve the desired success probability.

Bob wants to minimize p_dist on average over Alice's choice of ϕ. Using the fact that the trace norm is equal to the Euclidean norm on the Bloch sphere <cit.>, and using the fact that the position with the smallest distance on average to any point on a circle is in the center of the circle, we have that Bob would ideally like to return Z(p) if m=1, and Z(1-p) if m=2 (see <ref>). 
Luckily for Bob, if he simply returns the the result of his standard implementation of E (either the state |0⟩ or |1⟩) to Alice, on average over his measurement outcomes, he will return precisely Z(p) in the case that m=1, and Z(1-p) when m=2. Thus Bob's optimal strategy for minimizing p_dist is to do a projective measure in the standard basis and return the outcome state if Alice requests it.

We can now bound p_dist (assuming Alice knows Bob implements the optimal strategy, since there is no reason for Bob to use any other strategy):

    p_dist,(M=2)≥1/2+1/2Z(p)-|ψ_1⟩⟨ψ_1|_1=1/2+√(2p(1-p))/4.

This lower bound is shown in Fig. <ref>. Note that it exceeds the tight bounds for p_NFP for M=2, meaning that, unsurprisingly, Alice can better detect cheating if she can tolerate occasionally falsely accusing Bob. We leave for future investigation whether it is possible to improve upon this lower bound for p_dist, the lower bounds on p_dist for longer messages, and the related question of whether the upper bound of <ref> is achievable or not.  




§ ACKNOWLEDGMENTS

We're grateful to Guang Ping He for making us aware of past work in this subject and for valuable insights. 
We would particularly like to thank Maxwell Schleck for many helpful suggestions.
We'd also like acknowledge many people who discussed this work or provided feedback:
Matthias Christandl, Paul Hess, Yi-Kai Liu, Mikhail Lukin, Carl Miller, Roee
Ozeri, Anders Sorenson, Jeff Thompson, Stephanie Wehner, Jun Ye, and Terry Rudolph. Kimmel
completed some of this work while at the Joint Center for Quantum Information
and Computer Science at the University of Maryland. Kolkowitz gratefully
acknowledges support from NIST, JILA, CU Boulder, and the NRC postdoctoral
program.




unsrt
