---
author:
- |
    Yi-Kai Liu\
    Applied and Computational Mathematics Division\
    National Institute of Standards and Technology\
    Gaithersburg, MD, USA\
    yi-kai.liu@nist.gov
title: 'Building one-time memories from isolated qubits'
---

Introduction
============

One-time memories (OTM’s) are a simple type of tamper-resistant cryptographic hardware [@GKR]. An OTM device behaves as follows: one party (Alice) can write two messages $s,t\in{{\lbrace{0,1}\rbrace}}^k$ into the device, and then give the device to another party (Bob); after receiving the device, Bob can then choose to read either $s$ or $t$, but not both. An OTM is far simpler than a general-purpose processor, but it can be used to implement sophisticated forms of secure computation, such as one-time programs[^1] [@GKR; @goyal; @bellare] (and, more recently, quantum one-time programs [@broadbent]). The remarkable fact about these constructions is that the OTM is the *only* piece of hardware that has to be tamper-resistant; everything else consists of cryptographic software running on untrusted general-purpose processors.

Intuitively, it seems much easier to build an OTM, rather than a general-purpose tamper-proof processor. Indeed, there are many practical approaches to building such devices. However, from a theoretical perspective, it would be nice if one could build *provably-secure* OTM’s based on some clear *physical principle*, in the same way that one can build provably-secure encryption and signature schemes based on assumptions that certain problems are computationally intractable. But this line of investigation runs into a number of obstacles. OTM’s cannot exist in a fully classical world, because information can always be copied without destroying it. One might hope to build OTM’s in a quantum world, where the no-cloning principle limits an adversary’s ability to copy an unknown quantum state. However, this is also impossible, because an OTM can be used to perform oblivious transfer with information-theoretic security, and there are strong no-go theorems for quantum oblivious transfer, quantum bit commitment, and many other kinds of two-party secure computation in a quantum world [@nogo1; @nogo2; @nogo3; @nogo4].

One way around these no-go theorems is to try to construct protocols that are secure against a restricted class of quantum adversaries. The adversaries in the no-go theorems (that break quantum bit commitment, oblivious transfer, etc.) seem to require the full power of a quantum computer, i.e., the ability to perform arbitrary quantum circuits with entangling gates. However, a number of authors have shown protocols for bit commitment and other functionalities that are secure against adversaries who can only perform $k$-local measurements [@salvail], or adversaries who only have bounded or noisy quantum storage [@bounded05; @bounded06; @bounded07; @noisy07].

In this paper, we propose a new model of this type, called the *isolated qubits* model. This model allows the adversary to perform *local operations and classical communication* (LOCC); intuitively, this is the class of operations that can generate classical correlations between the qubits, but not entanglement. We then aim to construct OTM’s that are secure in this model.

The main challenge in this paper arises from the fact that OTM’s are non-interactive: after Alice gives the OTM to Bob, there is no further communication between them. Thus, they cannot use standard cryptographic tools, such as privacy amplification, to give Bob an advantage over the adversary. This makes OTM’s very different from most other protocols for bit-commitment and oblivious transfer. [^2]

For our OTM’s, we instead use an old idea called *conjugate coding*, which is due to Wiesner [@wiesner], and which works in this non-interactive setting. Conjugate coding uses quantum states that are not entangled, hence they can be prepared by honest parties in our model. Wiesner argued that conjugate coding *is* secure against non-adaptive adversaries who can only perform single-qubit destructive measurements, but that it is *not* secure against adversaries who can perform many-qubit entangled measurements. However, apart from those two extreme cases, little seems to be known about the security of conjugate coding. It is a natural question, then, whether conjugate coding *is* secure against the more general class of LOCC adversaries (which may be adaptive, and may perform repeated weak measurements on the same qubit). If the answer turned out to be yes, this would be a fairly realistic scenario in which conjugate coding provides useful security.

Unfortunately, proving good upper bounds on the power of LOCC adversaries is a long-standing open problem. Previous results in this area include demonstrations of “nonlocality without entanglement” (NLWE) [@nlwe99] (see [@nlwe12] for a recent survey), and constructions of data-hiding states [@qdh02; @eggeling02; @hqd02; @mpdhqi05]. However, these results do not seem to apply to our OTM’s. We are only able to prove partial results on the security of our OTM’s, but given that strong bounds of this type are quite rare, we believe this is significant progress.

On a conceptual level, we show that information can be hidden from an LOCC adversary in a stronger and more sophisticated way, such that the adversary can retrieve one of the messages contained in the OTM, but not both. This contrasts with previous work on NLWE and data-hiding states. On a technical level, we prove security of our OTM’s against “1-pass” LOCC adversaries (which may be adaptive, but are still restricted to destructive single-qubit measurements). This extends Wiesner’s original claim, though not all the way to general LOCC adversaries. The techniques used to prove this result are quite nontrivial: we construct our OTM’s using random codes, and we prove security using entropy chaining (also called Dudley’s inequality for suprema of empirical processes [@talagrand], or “using correlations to beat the union bound”).

Isolated qubits
---------------

In this paper we consider a model with *isolated qubits*, where all parties are only allowed to perform local quantum operations (on each qubit) and classical communication (between qubits). This class of operations is known as *$n$-partite LOCC*, where $n$ is the number of qubits. (See Section \[sec-rhinoceros\] for details.) We will construct an OTM that consists of $n$ isolated qubits. When Alice prepares the device, she can perform $n$-partite LOCC operations on the qubits, and likewise, when Bob reads the device, he can perform $n$-partite LOCC operations on the qubits. However, there is no communication or interaction between Alice and Bob, apart from the step where Alice gives the device (containing the $n$ qubits) to Bob.

Note that this is a different scenario from most previous work on the power of LOCC operations [@nlwe99; @qdh02], where Alice and Bob share some *bipartite* quantum system, and a “local operation” refers to an arbitrary operation on either Alice’s subsystem or Bob’s subsystem, and “classical communication” refers to communication between Alice and Bob.

Our model of isolated qubits is motivated by recent experimental work on nitrogen vacancy centers in diamond [@jelezko]. Nitrogen vacancy (NV) centers can be used to implement single qubits that have relatively long coherence times (on the order of seconds or minutes), at room temperature in a solid-state material. Individual NV centers can be read out and manipulated optically, but it is difficult to perform entangling operations on pairs of NV centers, due to variations in their emission spectra. (Recent experiments have demonstrated entanglement between distant NV centers [@bernien2013], but for our purposes there are natural ways of designing a device to prevent such entangling operations.) NV centers have been studied in connection with quantum money [@pastawski], and they are a plausible candidate to implement our model of isolated qubits.

Isolated qubits are similar (but not directly comparable) to Salvail’s $k$-local measurement model [@salvail]. In Salvail’s model, the adversary can perform entangled measurements on up to $k$ qubits, where $k$ is proportional to $n$; however, the adversary is only allowed to perform projective measurements, not repeated weak measurements (which are allowed in LOCC).

We also argue that isolated qubits can exist in a world with quantum computers. Isolated qubits are simply designed to satisfy different requirements than the qubits in a quantum computer. More specifically, recall that in any quantum device, there is a tradeoff between two conflicting requirements: first, protecting the device from unwanted interactions with the environment, such as noise and decoherence; and second, providing strong coherent interactions between the device and an external probe, in order to perform some useful task. Isolated qubits represent one possible compromise between these requirements, namely strong protection from noise and decoherence, and only classical (not entangling) gates and measurements. (Note that one cannot teleport information to or from an isolated qubit.) In contrast, quantum computers and quantum memories must satisfy both of the above requirements, which is a different, possibly more difficult task. (Indeed, the bounded / noisy storage model [@bounded05; @noisy07] assumes that it is hard to build large, high-fidelity quantum memories.)

In some sense, our isolated qubits model is complementary to the bounded / noisy storage model. In the bounded / noisy storage model, the honest parties Alice and Bob use qubits that may allow entangled measurements, but cannot be stored for a long time. In our model, Alice and Bob use qubits that can be stored for a long time, but do not allow entangled measurements.

Data-hiding states
------------------

Our first main result is a construction for data hiding states (see Section \[sec-triceratops\]). These states are simpler to analyze than our one-time memories, and they demonstrate the basic point that a sender can use LOCC operations to “hide” information from a LOCC receiver. We consider a system of $n$ isolated qubits, and we construct a set of $2^{{\tilde{n}}}$ states, where ${\tilde{n}}:= n-\Theta(1)$, by sampling independently at random from the set ${{\lbrace{{{\left| 0 \right\rangle}},{{\left| 1 \right\rangle}},{{\left| + \right\rangle}},{{\left| - \right\rangle}}}\rbrace}}^{{\otimes}n}$. (Here, ${{\left| + \right\rangle}} := ({{\left| 0 \right\rangle}}+{{\left| 1 \right\rangle}})/\sqrt{2}$ and ${{\left| - \right\rangle}} := ({{\left| 0 \right\rangle}}-{{\left| 1 \right\rangle}})/\sqrt{2}$ are the Hadamard basis states.) These states are all tensor products of single-qubit pure states, hence they can be prepared using only LOCC operations.

First, we show that these states can be distinguished almost perfectly using an entangled quantum measurement (the “pretty good measurement,” see Section \[sec-triceratops-pgm\]). Then we consider “one-pass” LOCC measurement strategies, i.e., measurement strategies that measure each qubit at most once. (For comparison, a general LOCC measurement strategy may perform many weak measurements on the same qubit. Note that bounding the power of general LOCC measurement strategies is a difficult open problem.) We show that a one-pass LOCC measurement strategy using 2-outcome measurements can extract at most $\approx n/2$ bits of information about which state was prepared[^3] (see Section \[sec-triceratops-locc2\]). Note that there exists a trivial LOCC measurement strategy that can extract $n/2$ bits of information, by measuring each qubit in the ${{\lbrace{{{\left| 0 \right\rangle}},{{\left| 1 \right\rangle}}}\rbrace}}$ basis, for instance; hence the above bound is tight. In addition, we show that a one-pass LOCC measurement strategy using $q$-outcome measurements (for any constant $q$) can extract at most $\approx (0.7067)n$ bits of information (see Section \[sec-triceratops-loccq\]).

The main point of this data-hiding result is to develop the proof techniques for our one-time memories, which will use a similar idea of sampling random states from the set ${{\lbrace{{{\left| 0 \right\rangle}},{{\left| 1 \right\rangle}},{{\left| + \right\rangle}},{{\left| - \right\rangle}}}\rbrace}}^{{\otimes}n}$, but will restrict access to the data in a more subtle way. We use two proof techniques: *entropy chaining*, and a bound on the *collision entropy*. We will describe these techniques below.

In addition, our data-hiding states may also be of independent interest, as they differ from previous work in some significant ways. On one hand, most previous constructions of data-hiding states [@qdh02; @eggeling02; @hqd02; @mpdhqi05] are secure against a much stronger class of LOCC adversaries (with infinite LOCC rather than one-pass LOCC). On the other hand, almost all of those constructions use entangled states, which cannot be realized in our isolated qubits model. (An exception is [@eggeling02], which uses separable Werner states. This approach too is quite different from ours.)

We remark that another line of work has focused on “nonlocality without entanglement” [@nlwe99], where one considers a bipartite system, and one constructs sets of separable states that are orthogonal but cannot be perfectly distinguished using LOCC; see [@nlwe12] for a recent survey. Finally, there are a number of elegant results about unambiguous state discrimination using multipartite LOCC, which are applicable when the number of states to be distinguished is relatively small [@walgate1; @chen03; @walgate2].

Entropy chaining
----------------

One of our proof techniques is “entropy chaining,” aka Dudley’s inequality for empirical processes [@talagrand]. This is similar to a union bound over the set of all one-pass adaptive LOCC measurement strategies, but it takes advantage of the positive correlations between the performance of strategies that are similar. This approach gives a tight bound for adversaries that use 2-outcome measurements, but it performs poorly when applied to adversaries that use $q$-outcome measurements for large $q$ (see Section \[sec-triceratops-locc2\]).

The basic idea is as follows. Let $E$ denote the random choices made in the construction of our data-hiding states. Let the resulting collection of data-hiding states be denoted by ${{\left| E(u) \right\rangle}}$ (for all $u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$). We imagine a game, where a referee chooses $u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$ uniformly at random, and prepares the state ${{\left| E(u) \right\rangle}}$, then an adversary performs some measurement strategy, and outputs a string of measurement outcomes $z$. The adversary’s goal is to maximize the mutual information $I(Z;U)$ (where $Z$ and $U$ are random variables containing the strings $z$ and $u$).

As a first step, note that if we fix a particular adversary strategy, then with high probability over $E$, $I(Z;U) \approx n/2$. To see this, write $I(Z;U) = H(Z) - H(Z|U)$; note that for 1-pass LOCC strategies using 2-outcome measurements, $H(Z) \leq n$; and note that $H(Z|U) = 2^{-{\tilde{n}}} \sum_u H(Z|U=u)$ is a sum of independent random variables with respect to $E$; hence by Hoeffding’s inequality, with high probability over $E$, $H(Z|U)$ will be close to its expected value, which is roughly $n/2$.

We want to prove a much stronger statement, however. We want to estimate the probability (over the random choice of $E$) that the *best* LOCC strategy (chosen with knowledge of the states ${{\left| E(u) \right\rangle}}$) can extract more than $n/2$ bits of information about $U$. To achieve this, we can try to use the union bound over all possible LOCC strategies. However, note that adaptive LOCC strategies can be described by *decision trees*, and in the case of 1-pass LOCC strategies using 2-outcome measurements, there are $2^{\Theta(2^n)}$ such decision trees. Meanwhile, the quantity $H(Z|U)$ is a sum of only $2^{{\tilde{n}}}$ independent random variables, so the failure probability in Hoeffding’s inequality is only exponentially small in $n$, not doubly-exponentially small in $n$. Thus the union bound fails to give a useful result.

Entropy chaining fixes this problem by exploiting correlations among the different strategies — the fact that two strategies that make similar measurements will produce similar results, and hence their failure probabilities do not add up in the worst-case fashion described by the union bound. The term “entropy chaining” refers to the fact that one must use a sequence of these arguments, to capture both strong correlations between very similar strategies and weak correlations between less-similar strategies. Each such argument involves covering the set of strategies with an ${\varepsilon}$-net at a different resolution, which can be interpreted as bounding the entropy of the set.

Bounding the collision entropy
------------------------------

Our second proof technique involves calculating the collision entropy of the unknown message $U$, conditioned on every possible sequence of measurement outcomes. This approach does not give a tight bound, but it works fairly well for all values of $q$ (see Section \[sec-triceratops-loccq\]).

Here we take a different perspective: instead of considering LOCC measurement strategies (which correspond to decision trees), we consider measurement outcomes (which correspond to tensor products of single-qubit POVM elements). That is, a measurement outcome is described by a POVM element of the form $M_A = {\bigotimes}_{i\in A} M_i$, where $A \subset [n]$ is the set of qubits that were measured, and $M_i$ is a POVM element acting on qubit $i$. (Measurement outcomes have this form when the adversary performs separable measurements, which include LOCC measurements as a special case; but this does not hold when the adversary performs entangled measurements.)

The basic idea is to fix some measurement outcome $M_A$, then lower-bound the collision entropy $H_2(U|M_A)$ (with high probability over $E$), and then use the union bound over all measurement outcomes $M_A$. To lower-bound $H_2(U|M_A)$, we proceed as follows. Essentially we want to upper-bound the collision probability $$\Pr[\text{col}|M_A] = \sum_u \Pr[U=u|M_A]^2 = 4^{-{\tilde{n}}} \Pr[M_A]^{-2} \sum_u \Pr[M_A|U=u]^2.$$ To do this, we note that both $\Pr[M_A] = 2^{-{\tilde{n}}} \sum_u \Pr[M_A|U=u]$ and $\sum_u \Pr[M_A|U=u]^2$ are sums of independent random variables (with respect to $E$), and we use large deviation bounds. Finally, to take the union bound over all $M_A$, we note that we only have to include those $M_A$ that are of tensor product form, hence the number of $M_A$ is exponential in $|A|$, rather than doubly exponential in $|A|$.

One-time memories
-----------------

We now describe our construction for one-time memories (see Section \[sec-stegosaurus-construction\]). We consider a system of $n$ isolated qubits, and we pick two random error-correcting codes, $C: {{\lbrace{0,1}\rbrace}}^k \rightarrow {{\lbrace{0,1}\rbrace}}^n$ and $D: {{\lbrace{0,1}\rbrace}}^k \rightarrow {{\lbrace{0,1}\rbrace}}^n$. (That is, each codeword is chosen independently and uniformly at random in ${{\lbrace{0,1}\rbrace}}^n$.) Given two messages $s$ and $t$ in ${{\lbrace{0,1}\rbrace}}^k$, we prepare each qubit $i$ (for $i=1,2,\ldots,n$) as follows. Let $C(s)_i$ and $D(t)_i$ denote the $i$’th bit in the strings $C(s)$ and $D(t)$, respectively. We prepare the $i$’th qubit in a pure state that has the following properties: first, if the qubit is measured in the ${{\lbrace{{{\left| 0 \right\rangle}},{{\left| 1 \right\rangle}}}\rbrace}}$ basis, the outcome is more likely to be ${{\left| 0 \right\rangle}}$ if $C(s)_i = 0$, and ${{\left| 1 \right\rangle}}$ if $C(s)_i = 1$; and second, if the qubit is measured in the ${{\lbrace{{{\left| + \right\rangle}},{{\left| - \right\rangle}}}\rbrace}}$ basis, the outcome is more likely to be ${{\left| + \right\rangle}}$ if $D(t)_i = 0$, and ${{\left| - \right\rangle}}$ if $D(t)_i = 1$. This is similar to Wiesner’s idea of quantum conjugate coding [@wiesner]. We refer to these states as one-time memory (OTM) states.

It is straightforward to check that these OTM states can be prepared using only LOCC operations, and that an honest party can recover either $s$ or $t$ using only LOCC operations (see Section \[sec-stegosaurus-correct\]).

However, the security of these OTM states is somewhat problematic. For instance, an LOCC adversary can always obtain partial information about both $s$ and $t$, by measuring some of the qubits in the ${{\lbrace{{{\left| 0 \right\rangle}},{{\left| 1 \right\rangle}}}\rbrace}}$ basis and some of the qubits in the ${{\lbrace{{{\left| + \right\rangle}},{{\left| - \right\rangle}}}\rbrace}}$ basis. Also, these OTM states can “leak” extra information: there is a one-pass LOCC strategy that can extract $n/2 \approx (1.2528)k$ bits of information about $s$ and $t$. [^4]

To address this issue, we define a notion of a “leaky OTM,” which we believe is still strong enough to construct one-time programs (see Section \[sec-stegosaurus-leaky\]). Essentially, we conjecture that one-time programs can be built using Yao’s garbled circuits [@GKR], leaky OTM’s, and a leak-resistant encryption scheme [@AGV].

We then present some evidence that our OTM states satisfy this notion of “leaky security”. Essentially, we prove that our OTM states satisfy a weaker notion of security, in which the smoothed min-entropy $H_\infty^{\varepsilon}$ is replaced by the Shannon entropy $H$ (see Section \[sec-stegosaurus-construction\]). We believe it should be possible to strengthen this result to show “leaky security.” In particular, we note that certain parts of the proof already use the collision entropy $H_2$, which is stronger than $H$, and implies bounds on $H_\infty^{\varepsilon}$.

Our technical result is that no 1-pass LOCC adversary using 2-outcome measurements can extract more than $\approx (1.9189)k < 2k$ bits of information about $(s,t)$ (see Section \[sec-stegosaurus-secure\]). (We believe that this constant factor can be improved.) The proof uses a two-stage argument that applies both the collision entropy bound and entropy chaining; we will describe this below.

We remark that there is a subtle point involving the difference between 1-pass LOCC measurements and general LOCC measurements, when applied to our OTM’s based on conjugate coding. For our OTM’s, there is a 1-pass LOCC measurement that can reconstruct $s$ (and there is a similar measurement for $t$). Also, Winter’s “gentle measurement lemma” [@gentle] implies that, if there is a *nondestructive* measurement that reconstructs $s$, and there is a similar measurement for $t$, then there is a measurement that reconstructs both $s$ and $t$ simultaneously. However, this does *not* imply the existence of a 2-pass LOCC measurement that can reconstruct both $s$ and $t$ simultaneously.

The reason is that, in order to reconstruct $s$ (or $t$) using 1-pass LOCC operations, the measurement must be destructive (i.e., one must perform a projective measurement on each qubit, obtain a string of classical measurement outcomes, and then run the classical decoding algorithm). If one wants to reconstruct $s$ (or $t$) using a nondestructive measurement, one must use entangling operations (i.e., one must run the classical decoding algorithm on a superposition of many different inputs). Thus the gentle measurement lemma cannot be applied to these particular 1-pass LOCC measurements, and it does not rule out the possibility that our OTM’s are secure against 2-pass or general LOCC adversaries.

Two-stage argument
------------------

Let us denote our OTM states by ${{\left| E(s,t) \right\rangle}}$ (for $s,t\in{{\lbrace{0,1}\rbrace}}^k$). These states resemble the data-hiding states studied previously, but there are some important differences. First, there are fewer OTM states (there are $4^k$ states in dimension $2^n$, where $k \approx (0.3991)n$), hence the states are easier to distinguish. Also, the OTM states are not constructed independently at random: there are $4^k$ states ${{\left| E(s,t) \right\rangle}}$, but only $2\cdot 2^k$ independent random variables (consisting of the codewords $C(s)$ and $D(t)$). As a result, there are positive correlations between states ${{\left| E(s,t) \right\rangle}}$ that have the same $s$ but different $t$.

To deal with the correlations among the states ${{\left| E(s,t) \right\rangle}}$, we use large-deviation bounds for sums of locally dependent random variables [@janson; @dubhashi]. However, these large-deviation bounds are not as strong as the ones we had for data-hiding states, and so neither of our proof techniques (i.e., entropy chaining and collision entropy) gives a useful result by itself.

To get around this difficulty, we combine the two techniques in sequence. Let $S$ and $T$ be random variables containing the messages $s$ and $t$. We use the collision entropy technique to analyze the first few steps taken by the adversary; this yields a lower-bound on $H_2(S,T|M_A)$, for any measurement outcome $M_A$ observed by the adversary thus far. Then we use entropy chaining to prove bounds on the adversary’s subsequent steps; this yields an upper-bound on $I(\tilde{Z};S,T|M_A)$, where $\tilde{Z}$ is the adversary’s output from subsequent measurements. It is necessary to apply the two techniques in this order, because the collision entropy technique yields an upper-bound on $\sum_{st} \Pr[S=s,T=t|M_A]^2$; this helps us to get stronger large-deviation bounds for the quantity $$H(\tilde{Z}|S,T,M_A) = \sum_{st} H(\tilde{Z}|S=s,T=t,M_A) \Pr[S=s,T=t|M_A],$$ which is crucial for entropy chaining.

Outlook
-------

We think it is an interesting challenge to develop our OTM construction into a useful primitive for secure computation. In this paper we have taken a first step, by constructing OTM’s based on isolated qubits, and analyzing their security in a simple information-theoretic framework (e.g., using random codes in the OTM’s, and describing the adversary’s knowledge in terms of mutual information). The next step is to make our OTM’s efficient, and prove a stronger security guarantee that allows composition of OTM’s to implement one-time programs.

First, we conjecture that the random codes $C$ and $D$ can be replaced by some class of efficiently-decodable codes, to construct computationally-efficient one-time memories that are secure against computationally-bounded LOCC adversaries. For comparison, note that the present construction, while not computationally efficient, also makes no assumptions about the adversary’s computational power, i.e., it is secure against one-pass LOCC adversaries that have unbounded computational power.

Second, we conjecture that our OTM’s satisfy a particular notion of “leaky security,” which can be combined with leak-resistant encryption schemes [@AGV] to construct one-time programs. This notion of “leaky security” uses the smoothed min-entropy to quantify the adversary’s uncertainty about the messages $s$ and $t$. Here we presented bounds that support this conjecture, using the Shannon entropy and the collision entropy.

Finally, it is an open problem to better understand the security of Wiesner’s conjugate coding technique against general LOCC strategies (rather than the one-pass LOCC strategies considered here).

Notation
--------

For any integer $n \geq 1$, we define the set $[n] := {{\lbrace{1,2,\ldots,n}\rbrace}}$. For any vector $v \in {\mathbb{C}}^n$, we define the $\ell_2$ norm ${{\lVert v \rVert}}_2 = (\sum_i {{\lvert v_i \rvert}}^2)^{1/2}$.

For any matrix $M \in {\mathbb{C}}^{m\times n}$, with singular values $\lambda_1(M) \geq \lambda_2(M) \geq \cdots$, we define the operator norm ${{\lVert M \rVert}} := \lambda_1(M)$ and the Frobenius norm ${{\lVert M \rVert}}_F := (\sum_i \lambda_i(M)^2)^{1/2}$. The notation $M \succeq 0$ means $M$ is positive semidefinite.

An ${\varepsilon}$-net $E$ (for a set $S$, with respect to some metric $d$) is a subset $E \subseteq S$ such that, for all $x\in S$, there exists some $x'\in E$, such that $d(x,x') \leq {\varepsilon}$. The covering number $N(S,d,{\varepsilon})$ is the minimum cardinality of any such ${\varepsilon}$-net $E$.

Logarithms are denoted as follows: $\ln(\cdot)$ is the natural logarithm, $\lg(\cdot)$ is the base-2 logarithm, and $\log(\cdot)$ is the logarithm when the base does not matter (because the log appears inside a big-O expression).

The Hamming distance between two binary strings $s,t\in{{\lbrace{0,1}\rbrace}}^n$ is denoted $d_H(s,t)$.

The $L_1$ or total variation distance between two random variables $X$ and $X'$ is denoted by $\Delta(X,X') = \sum_x {{\lvert \Pr[X=x] - \Pr[X'=x] \rvert}}$.

The Shannon entropy of a random variable $X$ is denoted by $H(X) = -\sum_x \Pr[X=x] \lg\Pr[X=x]$, and the mutual information between random variables $X$ and $Y$ is denoted by $I(X;Y) = H(X) - H(X|Y)$. (Note that $I$ without parentheses denotes the identity operator. It will be clear from the context which one is meant.)

The Renyi collision entropy of $X$ is denoted $H_2(X) = -\lg\bigl( \sum_x \Pr[X=x]^2 \bigr)$. The min-entropy of $X$ is given by $H_\infty(X) = -\lg\bigl( \max_x \Pr[X=x] \bigr)$, and the smoothed min-entropy of $X$ is given by $H_\infty^{\varepsilon}(X) = \max_{X' \;:\; \Delta(X,X')\leq{\varepsilon}} H_\infty(X')$.

Isolated qubits, and LOCC measurement strategies {#sec-rhinoceros}
================================================

In this section we introduce the model of isolated qubits, and the class of LOCC measurement strategies. Essentially, in a system of $n$ isolated qubits, the allowed operations are local (single-qubit) quantum operations, and classical communication between qubits. These are $n$-party LOCC operations, where each party holds a single qubit.

Any $n$-party LOCC measurement strategy can be described as a sequence of steps, which outputs a sequence of measurement outcomes, as follows:

> Begin at step 1.\
> At step $a$, conditioned on the output of the previous steps $1,2,\ldots,a-1$:\
> Choose one of the parties, specified by $i\in{{\lbrace{1,2,\ldots,n}\rbrace}}$.\
> Choose some measurement $M$. [^5]\
> Perform the measurement $M$ on the $i$’th party’s qubits; this yields some outcome $j$.\
> Output $j$, and proceed to step $a+1$.

LOCC measurement strategies can use an unbounded number of steps, and can measure each qubit many times, for instance by using a sequence of weak measurements (which may be chosen adaptively). Strategies using unbounded LOCC are difficult to analyze; in particular, it is a long-standing open problem to prove strong quantitative bounds on the amount of information returned by strategies using unbounded LOCC.

Here we consider a restricted class of LOCC strategies: those that measure each qubit *at most once*. We will refer to these as *1-pass* LOCC strategies.

Let us introduce some notation. A 1-pass LOCC strategy consists of $n$ steps, labeled by $a \in [n]$ (where we define $[n] := {{\lbrace{1,2,\ldots,n}\rbrace}}$). Suppose the strategy uses single-qubit measurements that have at most $q$ outcomes. At step $a$, let $z_{<a} := (z_1,z_2,\ldots,z_{a-1}) \in [q]^{a-1}$ be the output of the previous steps; let $Q_a(z_{<a}) \in [n]$ be the choice of which qubit to measure next; let $M_a(z_{<a},\zeta) \in {\mathbb{C}}^{2\times 2}$ (for all $\zeta \in [q]$) be the POVM elements corresponding to the choice of measurement in this step; and let $z_a$ be the actual measurement outcome that is obtained, so that $M_a(z_{\leq a})$ is the corresponding POVM element. We can write the complete strategy as a POVM measurement on $n$ qubits, whose elements are given by $$M(z) := {\bigotimes}_{a=1}^n M_a(z_{\leq a}), \quad \forall z\in[q]^n,$$ where $M_a(z_{\leq a})$ acts on the qubit indicated by $Q_a(z_{<a})$.

A state discrimination game
---------------------------

Consider a collection of $n$-qubit quantum states ${{\left| E(u) \right\rangle}}$, indexed by $u \in \mathcal{U}$. How well can an LOCC adversary distinguish among these states? To make this question precise, one can define the following *state discrimination game*: first the referee chooses $u \in \mathcal{U}$ uniformly at random, then prepares the corresponding state ${{\left| E(u) \right\rangle}}$, and gives it to the adversary; then the adversary carries out some LOCC measurement strategy, and outputs some string $z\in[q]^n$. We can measure the adversary’s success in terms of the *mutual information* $I(Z;U)$, where $U$ and $Z$ are the random variables describing the referee’s choice and the adversary’s output.

Note that, in the isolated qubits model, each party holds a single qubit (rather than a higher-dimensional quantum system). We can make use of this fact, to further simplify the set of possible LOCC strategies.

\[lem-locc-rank1\] Let ${\mathcal{M}}$ be any 1-pass LOCC strategy in the isolated qubits model, which uses $q$-outcome measurements and returns output $Z$. Then there exists ${\mathcal{M}}'$, a 1-pass LOCC strategy in the isolated qubits model, which uses $q$-outcome measurements and returns output $Z'$, and has the following additional properties:

1.  $I(Z';U) \geq I(Z;U)$ (when playing the state discrimination game shown above).

2.  In every measurement performed by ${\mathcal{M}}'$, the POVM elements all have rank 1.

Proof: See Appendix \[app-locc-epsnet\].

Discretization of LOCC strategies
---------------------------------

Let ${\mathcal{S}}$ be the set of all single-qubit measurements with $q$ outcomes, where every POVM element has rank 1: $${\mathcal{S}}= {{\lbrace{(M_1,\ldots,M_q) \;|\; M_i \in {\mathbb{C}}^{2\times 2}, \; M_i \succeq 0, \; \sum_{i=1}^q M_i = I, \; \operatorname{rank}(M_i) = 1}\rbrace}}.$$ This is a continuous set. In our proofs, we would like to approximate it by a finite ${\varepsilon}$-net $L$, with respect to some appropriate metric $t$. It will be convenient to define $t$ as follows: $$t(M,\tilde{M}) := \max_{i\in[q]} {{\lVert M_i - \tilde{M}_i \rVert}}.$$ (Here ${{\lVert \cdot \rVert}}$ denotes the operator norm.) The following two lemmas bound the size of the ${\varepsilon}$-net $L$, first in the special case where $q=2$ (for which we have a better bound), and then in the general case where $q \geq 2$.

\[lem-epsnet-2\] Let $q = 2$. For any $0 < {\varepsilon}\leq 1$, there exists an ${\varepsilon}$-net $L$ for ${\mathcal{S}}$, with respect to the metric $t$, that has cardinality $|L| \leq C/{\varepsilon}^2$ (where $C$ is some numerical constant). Equivalently, we have $N({\mathcal{S}},t,{\varepsilon}) \leq C/{\varepsilon}^2$.

Proof: See Appendix \[app-locc-epsnet\].

\[lem-epsnet-q\] Let $q \geq 2$. For any $0 < {\varepsilon}\leq 1$, there exists an ${\varepsilon}$-net $L$ for ${\mathcal{S}}$, with respect to the metric $t$, that has cardinality $|L| \leq (C/{\varepsilon})^{3q}$ (where $C$ is some numerical constant). Equivalently, we have $N({\mathcal{S}},t,{\varepsilon}) \leq (C/{\varepsilon})^{3q}$.

Proof: See Appendix \[app-locc-epsnet\].

We now bound the effect of this discretization when applied to a complete LOCC strategy. Essentially, if we choose ${\varepsilon}\leq O(1/qn)$, then the discretization has a negligible effect on the amount of information returned by the strategy.

\[lem-locc-epsnet\] Let ${\mathcal{M}}$ be any 1-pass LOCC strategy in the isolated qubits model, which uses $q$-outcome measurements, where all POVM elements have rank 1, and which has output $Z$. Fix some $0 < {\varepsilon}\leq 1/(qne)$, and let $L$ be the ${\varepsilon}$-net for ${\mathcal{S}}$ defined above. Let ${\mathcal{M}}'$ be the strategy that is obtained by duplicating the strategy ${\mathcal{M}}$, and replacing each measurement $M \in {\mathcal{S}}$ with the best approximating measurement $\tilde{M} \in L$. Let $Z'$ be the output of the strategy ${\mathcal{M}}'$. Then $${{\lvert I(Z';U) - I(Z;U) \rvert}} \leq 2qn^2{\varepsilon}+ 2\eta(qn{\varepsilon}),$$ where $\eta(x) := -x\lg x$.

Proof: See Appendix \[app-locc-epsnet\].

Data-hiding states {#sec-triceratops}
==================

Consider a system of $n$ qubits. We will construct a set $B$ of $2^{{\tilde{n}}}$ quantum states, with ${\tilde{n}}\geq n - O(1)$, that has the following properties:

1.  The states are pure and unentangled (i.e., they are tensor products of pure single-qubit states).

2.  There exists an entangled quantum measurement that distinguishes these states almost perfectly. In particular, given a state chosen uniformly at random from $B$, this measurement recovers nearly ${\tilde{n}}$ bits of information about the identity of the state.

3.  No $n$-party LOCC measurement strategy can distinguish these states very well. In particular, given a state chosen uniformly at random from $B$, no $n$-party LOCC measurement strategy using 2-outcome measurements can recover more than about $n/2$ bits of information about the identity of the state. Similar bounds hold for $n$-party LOCC measurement strategies using $q$-outcome measurements, for constant $q$.

We construct the set of states $B$ as follows. Set ${\tilde{n}}= n - \Theta(1)$. Briefly, $B$ is a set of $2^{{\tilde{n}}}$ states chosen independently and uniformly at random from the set ${{\lbrace{{{\left| 0 \right\rangle}},{{\left| 1 \right\rangle}},{{\left| + \right\rangle}},{{\left| - \right\rangle}}}\rbrace}}^{{\otimes}n}$. To state this more explicitly, we define the following single-qubit states: $${{\left| \alpha_{00} \right\rangle}} := {{\left| 0 \right\rangle}}, \quad
{{\left| \alpha_{11} \right\rangle}} := {{\left| 1 \right\rangle}}, \quad
{{\left| \alpha_{01} \right\rangle}} := {{\left| + \right\rangle}} = \tfrac{1}{\sqrt{2}} ({{\left| 0 \right\rangle}}+{{\left| 1 \right\rangle}}), \quad
{{\left| \alpha_{10} \right\rangle}} := {{\left| - \right\rangle}} = \tfrac{1}{\sqrt{2}} ({{\left| 0 \right\rangle}}-{{\left| 1 \right\rangle}}).$$ Choose a random mapping $E: {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}} \rightarrow {{\lbrace{00,01,10,11}\rbrace}}^n$, i.e., for each $u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$, assign $E(u)$ a value chosen independently and uniformly at random in ${{\lbrace{00,01,10,11}\rbrace}}^n$. Also, for $a=1,2,\ldots,n$, let $E(u)_a \in {{\lbrace{00,01,10,11}\rbrace}}$ denote the $a$’th entry in the string $E(u)$. Then let $B$ be the set of states ${{\left| E(u) \right\rangle}}$ defined as follows: $${{\left| E(u) \right\rangle}} := {\bigotimes}_{a=1}^n {{\left| \alpha_{E(u)_a} \right\rangle}}, \quad \forall u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}.$$

We will consider the following state discrimination problem, which we describe as a game between a referee and a distinguisher. First, the referee chooses a random string $u$ in ${{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$, and prepares the state ${{\left| E(u) \right\rangle}}$. Given this state, the distinguisher performs some measurement, and outputs a string $z$ (over some alphabet). The goal of the distinguisher is to maximize the *mutual information* $I(Z;U)$, where $U$ and $Z$ are the random variables representing the referee’s choice of the state and the distinguisher’s output.

The pretty good measurement {#sec-triceratops-pgm}
---------------------------

In this section we show that the states ${{\left| E(u) \right\rangle}}$ can be distinguished almost perfectly by a measurement that uses entanglement among the $n$ qubits. In particular, we will consider the “pretty good measurement” [@pgm], which is defined as follows. Let $\rho$ be the mixed state $\rho := 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} {{\left| E(u) \right\rangle}}{{\left\langle E(u) \right|}}$. Then the “pretty good measurement” is given by the following set of POVM elements: $$M_{\text{PGM}} := {{\lbrace{{{\left| M(z) \right\rangle}}{{\left\langle M(z) \right|}}, \; z\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}}\rbrace}}, \text{ where } 
{{\left| M(z) \right\rangle}} := 2^{-{\tilde{n}}/2}\rho^{-1/2}{{\left| E(z) \right\rangle}}.$$ (If $\rho$ is not full-rank, then $\rho^{-1/2}$ is defined on the support of $\rho$.)

We will show that, with high probability over the choice of the states ${{\left| E(u) \right\rangle}}$, the pretty good measurement works well. In particular, let $Z$ be the output of the pretty good measurement; we will show that $Z=U$ with probability close to 1, and the mutual information $I(Z;U)$ is close to ${\tilde{n}}$.

Let $C \geq 1$. With probability $\geq 1-\frac{1}{C}$ (over the choice of $E$), we have $$\label{eq-gecko-0}
\Pr[Z=U] \geq 1 - 2\sqrt{C} \cdot 2^{({\tilde{n}}-n)/2}.$$ In particular, for any ${\varepsilon}>0$, suppose that ${\tilde{n}}$ satisfies ${\tilde{n}}\leq n-\lg(C/{\varepsilon}^2)-2$. Then equation (\[eq-gecko-0\]) implies that $$\Pr[Z=U] \geq 1-{\varepsilon}.$$

Proof: First, we will give a lower-bound for $\Pr[Z=U]$ in terms of the eigenvalues of the Gram matrix of the states ${{\left| E(u) \right\rangle}}$, using an argument due to Montanaro [@montanaro]. We write $$\Pr[Z=U] = 2^{-{\tilde{n}}} \sum_{u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} {{\lvert {{\left\langle M(u) \middle| E(u) \right\rangle}} \rvert}}^2
 = 4^{-{\tilde{n}}} \sum_{u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} {{\lvert {{\left\langle E(u) \right|}} \rho^{-1/2} {{\left| E(u) \right\rangle}} \rvert}}^2.$$ We define the matrix $P \in {\mathbb{C}}^{2^{{\tilde{n}}} \times 2^{{\tilde{n}}}}$, whose entries are $P_{uv} = {{\left\langle E(u) \right|}} \rho^{-1/2} {{\left| E(v) \right\rangle}}$. In addition, we define the Gram matrix $G \in {\mathbb{C}}^{2^{{\tilde{n}}} \times 2^{{\tilde{n}}}}$, whose entries are $G_{uv} = {{\left\langle E(u) \middle| E(v) \right\rangle}}$. It is easy to see that both $P$ and $G$ are positive semidefinite, and that $P^2 = 2^{{\tilde{n}}} G$; hence we can write $P = 2^{{\tilde{n}}/2} \sqrt{G}$. So we have $$\Pr[Z=U] = 4^{-{\tilde{n}}} \sum_u {{\lvert P_{uu} \rvert}}^2
 = 2^{-{\tilde{n}}} \sum_u ((\sqrt{G})_{uu})^2.$$ We can lower-bound this as follows, using the convexity of the square function, and letting $\lambda_u(G)$ denote the eigenvalues of $G$: $$\Pr[Z=U] \geq \Bigl( 2^{-{\tilde{n}}} \sum_u (\sqrt{G})_{uu} \Bigr)^2
 = \Bigl( 2^{-{\tilde{n}}} \operatorname{tr}\sqrt{G} \Bigr)^2
 = \Bigl( 2^{-{\tilde{n}}} \sum_u \sqrt{\lambda_u(G)} \Bigr)^2.$$

Next, define $$\nu_u(G) := \begin{cases}
\lambda_u(G) &\text{if } 0 \leq \lambda_u(G) \leq 1 \\
1 &\text{if } \lambda_u(G) \geq 1
\end{cases}$$ and observe that $\sqrt{\lambda_u(G)} \geq \nu_u(G)$. So we have $$\begin{split}
\Pr[Z=U] &\geq \Bigl( 2^{-{\tilde{n}}} \sum_u \nu_u(G) \Bigr)^2
 = \Bigl( 1 - 2^{-{\tilde{n}}} \sum_u (1-\nu_u(G)) \Bigr)^2 \\
 &\geq 1 - 2\cdot 2^{-{\tilde{n}}} \sum_u (1-\nu_u(G))
 \geq 1 - 2\cdot 2^{-{\tilde{n}}} 2^{{\tilde{n}}/2} {{\lVert \vec{1} - \vec{\nu}(G) \rVert}}_2.
\end{split}$$ Also note that ${{\lvert 1-\nu_u(G) \rvert}} \leq {{\lvert 1-\lambda_u(G) \rvert}}$, hence ${{\lVert \vec{1} - \vec{\nu}(G) \rVert}}_2 \leq {{\lVert \vec{1} - \vec{\lambda}(G) \rVert}}_2 = {{\lVert G-I \rVert}}_F$. So we have $$\label{eq-gecko}
\Pr[Z=U] \geq 1 - 2\cdot 2^{-{\tilde{n}}/2} {{\lVert G-I \rVert}}_F.$$

Finally, we will use Markov’s inequality to show that, with high probability (over the choice of $E$), ${{\lVert G-I \rVert}}_F$ is not too large. We write: $$\operatorname{\mathbb{E}}_E[{{\lVert G-I \rVert}}_F^2] = \operatorname{\mathbb{E}}_E\Bigl[ \sum_{u\neq v \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} {{\lvert G_{uv} \rvert}}^2 \Bigr],$$ $$\operatorname{\mathbb{E}}_E[{{\lvert G_{uv} \rvert}}^2] = \operatorname{\mathbb{E}}_E\Bigl[ \prod_{a=1}^n {{\lvert {{\left\langle \alpha_{E(u)_a} \middle| \alpha_{E(v)_a} \right\rangle}} \rvert}}^2 \Bigr]
 = \prod_{a=1}^n (\tfrac{1}{4}(1+0+\tfrac{1}{2}+\tfrac{1}{2})) = 2^{-n} \quad (\forall u\neq v),$$ $$\operatorname{\mathbb{E}}_E[{{\lVert G-I \rVert}}_F^2] = 2^{{\tilde{n}}} (2^{{\tilde{n}}}-1) 2^{-n} < 4^{{\tilde{n}}} 2^{-n}.$$ Hence, by Markov’s inequality, for any $C\geq 1$, $$\Pr_E[{{\lVert G-I \rVert}}_F^2 \geq C\cdot 4^{{\tilde{n}}} 2^{-n}] \leq \tfrac{1}{C}.$$ That is, with probability $\geq 1-\tfrac{1}{C}$ (over the choice of $E$), we have ${{\lVert G-I \rVert}}_F \leq \sqrt{C}\cdot 2^{{\tilde{n}}} 2^{-n/2}$. Combining this with equation (\[eq-gecko\]) completes the proof. $\square$

We have just shown a lower-bound on the success probability $\Pr[Z=U]$; this now implies a lower-bound on the mutual information $I(Z;U)$.

\[lem-ostrich\] Suppose that $\Pr[Z=U] \geq 1-{\varepsilon}$, and ${\varepsilon}$ is sufficiently small that $2\sqrt{{\varepsilon}} + 2^{-{\tilde{n}}} \leq 1/e$. Then $I(Z;U) \geq (1-5\sqrt{{\varepsilon}}) {\tilde{n}}- \eta(2\sqrt{{\varepsilon}})$, where $\eta(x) := -x \lg x$.

Proof: See Appendix \[app-ostrich\].

1-pass LOCC strategies with 2-outcome measurements {#sec-triceratops-locc2}
--------------------------------------------------

In this section, we prove that the states ${{\left| E(u) \right\rangle}}$ ($u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$) cannot be fully distinguished by any 1-pass LOCC strategy that uses 2-outcome measurements. In particular, we show that any such strategy cannot extract more than about $n/2$ bits of information about $U$. This claim holds with high probability over the randomized construction of the states ${{\left| E(u) \right\rangle}}$; more precisely, the claim holds with high probability over the choice of the map $E: {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}} \rightarrow {{\lbrace{00,01,10,11}\rbrace}}^n$, which we view as a random variable.

The proof uses an entropy chaining argument, which is stated in Lemma \[lem-dudley\]. This is essentially Dudley’s inequality for bounding the supremum of an empirical process with Gaussian decaying correlations [@talagrand], with some minor technical modifications (in particular, the result is stated as a tail bound for the supremum, rather than a bound on the expected supremum); the proof is given in Appendix \[app-entropy-chaining\].

\[thm-willow\] Let ${\mathbb{M}}$ be the set of all 1-pass LOCC strategies in the isolated qubits model using 2-outcome measurements. Let $t_0 > 0$ and $u \geq 1$. Then, with probability $\geq 1 - \exp(-2t_0^2) - 2\cdot 2^{-u^2}$ (over the choice of $E$), the following statement holds: $$\forall {\mathcal{M}}\in {\mathbb{M}}, \; I(Z;U) \leq (0.54)n + O(1) + t_0{\tilde{n}}2^{-{\tilde{n}}/2} + u\cdot O(\sqrt{\log n}),$$ where $Z$ denotes the output of the strategy ${\mathcal{M}}$.

Proof: First, let $L$ be an ${\varepsilon}$-net for the set of single-qubit measurements with 2 outcomes where all POVM elements have rank 1, as described in Lemma \[lem-epsnet-2\]; and set ${\varepsilon}= 1/(100n)$. Let ${\mathbb{M}}'$ be the set of all strategies that use measurements chosen from the set $L$. By Lemmas \[lem-locc-rank1\] and \[lem-locc-epsnet\], any strategy in ${\mathbb{M}}$ can be approximated by one in ${\mathbb{M}}'$.

For any strategy ${\mathcal{M}}$, let $Z$ denote its output. Note that $Z$ takes values in ${{\lbrace{0,1}\rbrace}}^n$, and we can split its output into two pieces, $Z = (Z_{1,\ldots,{\tilde{n}}}, Z_{{\tilde{n}}+1,\ldots,n})$. So we can write $$\label{eq-sparrow-1}
I(Z;U) = H(Z) - H(Z|U) \leq n - H(Z_{1,\ldots,{\tilde{n}}}|U).$$ We want to show that $H(Z_{1,\ldots,{\tilde{n}}}|U)$ is not too small.

Let ${\mathbb{M}}''$ be the set of all strategies with ${\tilde{n}}$ steps, whose behavior matches the first ${\tilde{n}}$ steps of some strategy in ${\mathbb{M}}'$. For any ${\mathcal{M}}\in {\mathbb{M}}''$, we now define $$Q_{\mathcal{M}}:= H(Z_{1,\ldots,{\tilde{n}}}|U),$$ which is a random variable depending on $E$. Let $\mu_{\mathcal{M}}:= \operatorname{\mathbb{E}}_E Q_{\mathcal{M}}$; we will prove a lower bound for $\mu_{\mathcal{M}}$ below. We will then use entropy chaining (Lemma \[lem-dudley\]) to lower-bound the quantity $$\inf_{{\mathcal{M}}\in {\mathbb{M}}''} (Q_{\mathcal{M}}- \mu_{\mathcal{M}}).$$

First, we evaluate $\mu_{\mathcal{M}}$: $$\mu_{\mathcal{M}}= \operatorname{\mathbb{E}}_E \bigl[ H(Z_{1,\ldots,{\tilde{n}}}|U) \bigr]
 = 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} \sum_{z\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}}
 \operatorname{\mathbb{E}}_E \bigl[ -\Pr(z|u) \lg \Pr(z|u) \bigr],$$ where for convenience we wrote $\Pr(z|u)$ in place of $\Pr[Z_{1,\ldots,{\tilde{n}}}=z|U=u]$. Consider any fixed $u, z \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$. Recall that ${{\left| E(u) \right\rangle}}$ is chosen uniformly at random in $A^{{\otimes}n}$, where $A := {{\lbrace{{{\left| \alpha_{00} \right\rangle}}, {{\left| \alpha_{01} \right\rangle}}, {{\left| \alpha_{10} \right\rangle}}, {{\left| \alpha_{11} \right\rangle}}}\rbrace}}$. So we have $$\operatorname{\mathbb{E}}_E \bigl[ -\Pr(z|u) \lg \Pr(z|u) \bigr]
 = 4^{-{\tilde{n}}} \sum_{{{\left| \psi \right\rangle}} \in A^{{\otimes}{\tilde{n}}}} -{{\left\langle \psi \right|}}M(z){{\left| \psi \right\rangle}} \lg {{\left\langle \psi \right|}}M(z){{\left| \psi \right\rangle}}.$$ Furthermore, we know that ${{\left\langle \psi \right|}}M(z){{\left| \psi \right\rangle}} = \prod_{a=1}^{{\tilde{n}}} {{\left\langle \psi_{Q_a(z_{<a})} \right|}} M_a(z_{\leq a}) {{\left| \psi_{Q_a(z_{<a})} \right\rangle}}$, where we used the notation introduced in Section \[sec-rhinoceros\]. Hence we can write $$\begin{split}
\operatorname{\mathbb{E}}_E \bigl[ & -\Pr(z|u) \lg \Pr(z|u) \bigr] \\
 &= \sum_{a=1}^{{\tilde{n}}} 4^{-{\tilde{n}}} \sum_{{{\left| \psi \right\rangle}} \in A^{{\otimes}{\tilde{n}}}} -{{\left\langle \psi \right|}}M(z){{\left| \psi \right\rangle}} \lg {{\left\langle \psi_{Q_a(z_{<a})} \right|}} M_a(z_{\leq a}) {{\left| \psi_{Q_a(z_{<a})} \right\rangle}} \\
 &= \sum_{a=1}^{{\tilde{n}}} 4^{-{\tilde{n}}} \Bigl[ \sum_{\psi_a \in A} -{{\left\langle \psi_a \right|}} M_a(z_{\leq a}) {{\left| \psi_a \right\rangle}} \lg {{\left\langle \psi_a \right|}} M_a(z_{\leq a}) {{\left| \psi_a \right\rangle}} \Bigr] 
\prod_{b\neq a} \Bigl[ \sum_{\psi_b \in A} {{\left\langle \psi_b \right|}} M_b(z_{\leq b}) {{\left| \psi_b \right\rangle}} \Bigr] 
\end{split}$$ Recall that we are considering single-qubit measurements with 2 outcomes, where each outcome corresponds to a rank-1 POVM element. Hence each $M_b(z_{\leq b})$ is a rank-1 projector, i.e., it can be viewed as a density matrix of a quantum state. Hence we can write $$\sum_{\psi_b \in A} {{\left\langle \psi_b \right|}} M_b(z_{\leq b}) {{\left| \psi_b \right\rangle}} = 2\operatorname{tr}M_b(z_{\leq b}) = 2.$$ Also, suppose we let $R_0$ be the result of measuring the state $M_a(z_{\leq a})$ in the orthonormal basis ${{\lbrace{{{\left| \alpha_{00} \right\rangle}}, {{\left| \alpha_{11} \right\rangle}}}\rbrace}}$, and we let $R_1$ be the result of measuring the same state in the orthonormal basis ${{\lbrace{{{\left| \alpha_{01} \right\rangle}}, {{\left| \alpha_{10} \right\rangle}}}\rbrace}}$. Then we can write $$\sum_{\psi_a \in A} -{{\left\langle \psi_a \right|}} M_a(z_{\leq a}) {{\left| \psi_a \right\rangle}} \lg {{\left\langle \psi_a \right|}} M_a(z_{\leq a}) {{\left| \psi_a \right\rangle}}
 = H(R_0) + H(R_1) \geq 1,$$ using an entropic uncertainty relation of Maassen and Uffink [@maassen-uffink; @wehner-winter]. Substituting into the previous equations, we get $$\operatorname{\mathbb{E}}_E \bigl[ -\Pr(z|u) \lg \Pr(z|u) \bigr] \geq 2^{-{\tilde{n}}-1} \cdot {\tilde{n}},$$ $$\mu_{\mathcal{M}}\geq {\tilde{n}}/2.$$

We now show several technical facts which are needed in order to apply the entropy chaining argument (Lemma \[lem-dudley\]). First, fix some particular strategy ${\mathcal{M}}_0 \in {\mathbb{M}}''$. We will show that $Q_{{\mathcal{M}}_0}$ is tightly concentrated around its mean. Observe that $Q_{{\mathcal{M}}_0} = 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} H(Z_{1,\ldots,{\tilde{n}}}|U=u)$ is a sum of $2^{{\tilde{n}}}$ independent random variables, since the strings $E(u)$ for different $u$ are chosen independently at random. Using Hoeffding’s inequality, we get that $$\Pr_E[Q_{{\mathcal{M}}_0} < \mu_{{\mathcal{M}}_0} - t] \leq \exp\Bigl( -\frac{2t^2}{2^{{\tilde{n}}} (n/2^{{\tilde{n}}})^2} \Bigr)
= \exp\Bigl( -\frac{2t^2 \cdot 2^{{\tilde{n}}}}{{\tilde{n}}^2} \Bigr) \quad (\forall t>0),$$ or equivalently $$\Pr_E\Bigl[Q_{{\mathcal{M}}_0} < \mu_{{\mathcal{M}}_0} - \frac{t_0 {\tilde{n}}}{2^{{\tilde{n}}/2}}\Bigr] \leq \exp(-2t_0^2), \quad (\forall t_0>0).$$

Next, we show that when two strategies ${\mathcal{M}}$ and ${\mathcal{M}}'$ are “similar,” the random variables $Q_{\mathcal{M}}$ and $Q_{{\mathcal{M}}'}$ are positively correlated. In particular, suppose that ${\mathcal{M}}$ and ${\mathcal{M}}'$ behave identically for the first $\ell$ steps. Let $Z_{1,\ldots,{\tilde{n}}}$ and $Z'_{1,\ldots,{\tilde{n}}}$ be the output of these two strategies; then $(Z_{1,\ldots,\ell},U)$ and $(Z'_{1,\ldots,\ell},U)$ have the same distribution. So we can write $$\begin{split}
Q_{\mathcal{M}}- Q_{{\mathcal{M}}'}
 &= H(Z_{\ell+1,\ldots,{\tilde{n}}}|Z_{1,\ldots,\ell},U) - H(Z'_{\ell+1,\ldots,{\tilde{n}}}|Z'_{1,\ldots,\ell},U) \\
 &= 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} H(Z_{\ell+1,\ldots,{\tilde{n}}}|Z_{1,\ldots,\ell},U=u) - H(Z'_{\ell+1,\ldots,{\tilde{n}}}|Z'_{1,\ldots,\ell},U=u), 
\end{split}$$ which again is a sum of $2^{{\tilde{n}}}$ independent random variables. By Hoeffding’s inequality, $$\Pr_E[Q_{\mathcal{M}}- Q_{{\mathcal{M}}'} - \mu_{\mathcal{M}}+ \mu_{{\mathcal{M}}'} \geq t]
 \leq \exp\Bigl( -\frac{2t^2}{2^{{\tilde{n}}} (2({\tilde{n}}-\ell)/2^{{\tilde{n}}})^2} \Bigr)
 = \exp\Bigl( -\frac{t^2 \cdot 2^{{\tilde{n}}}}{2 ({\tilde{n}}-\ell)^2} \Bigr).$$ We can rewrite this bound in terms of a metric $d$ that measures the “distance” between strategies. We define $d$ as follows: [^6] $$d({\mathcal{M}},{\mathcal{M}}') := \sqrt{2} \cdot 2^{-{\tilde{n}}/2} ({\tilde{n}}-\ell({\mathcal{M}},{\mathcal{M}}')), \text{ where}$$ $$\ell({\mathcal{M}},{\mathcal{M}}') := \max {{\lbrace{\ell \;|\; \text{$0\leq\ell\leq{\tilde{n}}$, and ${\mathcal{M}}$ and ${\mathcal{M}}'$ behave identically on steps $1,2,\ldots,\ell$}}\rbrace}}.$$ We then have $$\Pr_E[Q_{\mathcal{M}}- Q_{{\mathcal{M}}'} - \mu_{\mathcal{M}}+ \mu_{{\mathcal{M}}'} \geq t]
 \leq \exp\Bigl( -\frac{t^2}{d({\mathcal{M}},{\mathcal{M}}')^2} \Bigr).$$

Next, we bound the covering numbers of ${\mathbb{M}}''$ with respect to the metric $d$. We use a simple bound: $$N({\mathbb{M}}'', d, \sqrt{2} \cdot 2^{-{\tilde{n}}/2}{\varepsilon})
 \leq \begin{cases}
(n{{\lvert L \rvert}})^{2^{\lceil{\tilde{n}}-{\varepsilon}\rceil}} &\text{if } {\varepsilon}\leq{\tilde{n}}\\
1 &\text{if } {\varepsilon}>{\tilde{n}}.
\end{cases}$$ (This bound simply counts the number of possible strategies with $\lceil{\tilde{n}}-{\varepsilon}\rceil$ steps. Each such strategy is described by a binary tree of depth $\lceil{\tilde{n}}-{\varepsilon}\rceil$, and at every node there is a choice of which of the $n$ qubits to measure next, and which of the measurements in the set $L$ to perform.) We now bound the integral appearing in Lemma \[lem-dudley\] (“Dudley’s entropy integral”): (here $C_0$ is a numerical constant) $$\begin{split}
S &\leq C_0 \int_0^\infty \sqrt{\log N({\mathbb{M}}'',d,{\varepsilon})} d{\varepsilon}\\
 &= C_0 \int_0^\infty \sqrt{\log N({\mathbb{M}}'',d,\sqrt{2} \cdot 2^{-{\tilde{n}}/2} {\varepsilon})} \cdot \sqrt{2} \cdot 2^{-{\tilde{n}}/2} d{\varepsilon}\\
 &\leq C_0 \int_0^{{\tilde{n}}} \sqrt{2^{{\tilde{n}}-{\varepsilon}+1} \log(n{{\lvert L \rvert}})} \cdot \sqrt{2} \cdot 2^{-{\tilde{n}}/2} d{\varepsilon}\\
 &= C_0 \int_0^{{\tilde{n}}} 2^{-{\varepsilon}/2} d{\varepsilon}\cdot 2\sqrt{\log(n{{\lvert L \rvert}})} \\
 &= C_0 (\tfrac{2}{\ln 2}) (1-2^{-{\tilde{n}}/2}) \cdot 2\sqrt{\log(n{{\lvert L \rvert}})} \\
 &< C_0 (\tfrac{2}{\ln 2}) \cdot 2\sqrt{\log(n{{\lvert L \rvert}})}.
\end{split}$$ Recall that ${{\lvert L \rvert}} \leq O(1/{\varepsilon}^2) = O(n^2)$. Hence we have: $$S \leq O(\sqrt{\log n}).$$

Finally, using Lemma \[lem-dudley\], we have that: for all $t_0>0$ and $u \geq 1$, with probability $\geq 1 - \exp(-2t_0^2) - 2\cdot 2^{-u^2}$, the following holds: $$\forall {\mathcal{M}}\in {\mathbb{M}}'', \; Q_{{\mathcal{M}}} - \mu_{{\mathcal{M}}} > - \frac{t_0{\tilde{n}}}{2^{{\tilde{n}}/2}} - uS.$$ This implies that $$\forall {\mathcal{M}}\in {\mathbb{M}}'', \; Q_{{\mathcal{M}}} > \frac{{\tilde{n}}}{2} - \frac{t_0{\tilde{n}}}{2^{{\tilde{n}}/2}} - u\cdot O(\sqrt{\log n}).$$ Plugging into equation (\[eq-sparrow-1\]), we get that $$\forall {\mathcal{M}}\in {\mathbb{M}}', \; I(Z;U) < n - \frac{{\tilde{n}}}{2} + \frac{t_0{\tilde{n}}}{2^{{\tilde{n}}/2}} + u\cdot O(\sqrt{\log n}).$$ Finally, using Lemmas \[lem-locc-rank1\] and \[lem-locc-epsnet\], we get that $$\forall {\mathcal{M}}\in {\mathbb{M}}, \; I(Z;U) < n - \frac{{\tilde{n}}}{2} + \frac{n}{25} + O(1) + \frac{t_0{\tilde{n}}}{2^{{\tilde{n}}/2}} + u\cdot O(\sqrt{\log n}).$$ This proves the claim. $\square$

1-pass LOCC strategies with $q$-outcome measurements {#sec-triceratops-loccq}
----------------------------------------------------

In this section, we consider a more general class of 1-pass LOCC strategies, that use $q$-outcome measurements (for any constant $q$). Again we show that the states ${{\left| E(u) \right\rangle}}$ ($u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$) cannot be perfectly distinguished by such an adversary. Quantitatively, we show that such an adversary can extract at most $\approx (0.71){\tilde{n}}$ bits of information about $U$; we do not believe this bound is optimal, but it does nonetheless show that a constant fraction of the information in $U$ is hidden from the adversary.

We use a different proof technique from the previous section: here we show an explicit lower bound on the Renyi collision entropy of $U$ conditioned on the output $Z_{\leq m}$ of the first $m$ steps of the adversary. This “collision entropy” proof is a useful alternative to the “entropy chaining” proof of the previous section. The collision entropy proof works quite well when $q$ is large, whereas the entropy chaining proof has some difficulty because the number of possible measurement strategies grows rapidly with $q$. However, the collision entropy proof does not give a tight bound for any value of $q$, while the entropy chaining approach does give a tight bound when $q=2$.

\[thm-flounder\] Let ${\mathbb{M}}$ be the set of all 1-pass LOCC strategies in the isolated qubits model, using q-outcome measurements. Then, with probability $\geq 1 - e^{-\Omega(n)}$ (over the choice of $E$), the following statement holds: $$\forall {\mathcal{M}}\in {\mathbb{M}}, \; I(Z;U) \leq (0.7067)n + O(1) + O(\lg(qn)),$$ where $Z$ denotes the output of the strategy ${\mathcal{M}}$.

Proof: First, let $L$ be an ${\varepsilon}$-net for the set of single-qubit measurements with $q$ outcomes where all POVM elements have rank 1, as described in Lemma \[lem-epsnet-q\]; and set ${\varepsilon}= 1/(200qn)$. Let ${\mathbb{M}}'$ be the set of all strategies that use measurements chosen from the set $L$. By Lemmas \[lem-locc-rank1\] and \[lem-locc-epsnet\], any strategy in ${\mathbb{M}}$ can be approximated by one in ${\mathbb{M}}'$.

We will analyze the first $m$ steps of any strategy in ${\mathbb{M}}'$, where $m = \lfloor {\tilde{n}}/\lg(8/3) \rfloor \approx (0.7067){\tilde{n}}$. We will show the following bound:

\[lem-flatfish\] With probability $\geq 1 - e^{-\Omega(n)}$ (over the choice of $E$), $$\label{eq-flatfish}
\forall {\mathcal{M}}\in {\mathbb{M}}', \; \forall z_{1,\ldots,m}\in[q]^m, \;
H_2(U | Z_{1,\ldots,m}=z_{1,\ldots,m}) \geq {\tilde{n}}- m\lg(\tfrac{3}{2}) - \lg(O(qn\lg(qn))),$$ where $Z_{1,\ldots,m}$ denotes the output of the first $m$ steps of the strategy ${\mathcal{M}}$, $H_2$ denotes the Renyi collision entropy, and $\lg(\tfrac{3}{2}) \approx 0.5850$.

Proof (of Lemma \[lem-flatfish\]): Note that the lemma is equivalent to the following statement: with high probability (over the choice of $E$),

> for all subsets of qubits $A \subset [n]$, of size ${{\lvert A \rvert}} = m$,\
> for all possible measurement outcomes $M_A$ that correspond to measuring the qubits in the set $A$ using any measurements in the set $L$,\
> $H_2(U | M_A)$ (where we condition on observing the measurement outcome $M_A$) is large.

Note that a measurement outcome $M_A$ is uniquely represented by a rank-1 POVM element of the form $M_A = {\bigotimes}_{i\in A} M_i$, where each $M_i$ is a POVM element acting on qubit $i$, that corresponds to one possible outcome of some measurement in the set $L$.

We will now proceed as follows. First, we will show that, for every $A$ and $M_A$, $\Pr[M_A]$ is approximately $\operatorname{tr}(M_A)/2^m$. Secondly, we will show that, for every $A$ and $M_A$, $\sum_u \Pr[M_A|U=u]^2$ is small. (To show these claims, we will use large-deviation bounds for every fixed choice of $A$ and $M_A$, followed by the union bound over all $A$ and $M_A$.) Finally, we will combine these two claims to get a lower-bound on $H_2(U|M_A)$.

First, fix some subset of qubits $A\subset [n]$, of size ${{\lvert A \rvert}} = m$. Let $\rho$ be the mixed state presented to the adversary, $\rho := 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} {{\left| E(u) \right\rangle}}{{\left\langle E(u) \right|}}$, and let $\rho_A$ be the reduced state on the subset $A$, $$\rho_A := \operatorname{tr}_{[n]\setminus A}(\rho) = 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} {{\left| E(u)_A \right\rangle}}{{\left\langle E(u)_A \right|}}, 
\text{ where } {{\left| E(u)_A \right\rangle}} := {\bigotimes}_{a\in A} {{\left| \alpha_{E(u)_a} \right\rangle}}.$$ Note that $\operatorname{\mathbb{E}}_E \rho_A = I/2^m$. We claim that, with high probability (over the choice of $E$), $\rho_A$ is close to the maximally mixed state $I/2^m$, and hence any measurement outcome $M_A$ on the subset $A$ will be observed with probability approximately $\operatorname{tr}(M_A)/2^m$. To show this, we will use the matrix Bernstein inequality [@tropp].

For convenience, define $H := \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} H_u$, where $H_u := {{\left| E(u) \right\rangle}}_A{{\left\langle E(u) \right|}}_A$. Note that $\operatorname{\mathbb{E}}_E H = 2^{{\tilde{n}}-m}I$ and $\operatorname{\mathbb{E}}_E H_u = 2^{-m}I$. Note that the $H_u$ are bounded: $${{\lVert H_u - \operatorname{\mathbb{E}}_E H_u \rVert}} = \max{{\lbrace{1-2^{-m}, 2^{-m}}\rbrace}} < 1 =: R.$$ The variance of $H$ is described by $$\begin{split}
\operatorname{\mathbb{E}}_E[(H - \operatorname{\mathbb{E}}_E H)^2] &= \operatorname{\mathbb{E}}_E[H^2] - (\operatorname{\mathbb{E}}_E H)^2 \\
 &= \operatorname{\mathbb{E}}_E[\sum_u H_u^2 + \sum_{u\neq v} H_u H_v] - 4^{{\tilde{n}}-m}I \\
 &= \sum_u \operatorname{\mathbb{E}}_E[H_u^2] + \sum_{u\neq v} \operatorname{\mathbb{E}}_E[H_u] \operatorname{\mathbb{E}}_E[H_v] - 4^{{\tilde{n}}-m}I \\
 &= 2^{{\tilde{n}}-m}I + (4^{{\tilde{n}}}-2^{{\tilde{n}}}) 4^{-m}I - 4^{{\tilde{n}}-m}I \\
 &= 2^{{\tilde{n}}-m}(1-2^{-m})I.
\end{split}$$ In particular, note that $$\sigma^2 := {{\lVert \operatorname{\mathbb{E}}_E[(H - \operatorname{\mathbb{E}}_E H)^2] \rVert}} < 2^{{\tilde{n}}-m}.$$ Then the matrix Bernstein inequality [@tropp] implies that, for any $t>0$, $$\Pr_E[{{\lVert H - \operatorname{\mathbb{E}}_E H \rVert}} \geq t] \leq 2\cdot 2^m \exp\biggl( -\frac{t^2}{2(\sigma^2+\tfrac{1}{3}Rt)} \biggr)
= 2\cdot 2^m \exp\biggl( -\frac{t^2}{2(2^{{\tilde{n}}-m}+\tfrac{1}{3}t)} \biggr).$$ Now set $$t := t_0\sqrt{m}2^{({\tilde{n}}-m)/2}, \text{ for any } t_0 \geq 1.$$ Recall that $0 \leq m \leq {\tilde{n}}- \lg{\tilde{n}}$. This implies that $\lg{\tilde{n}}\leq {\tilde{n}}-m$, hence $t < t_0 \sqrt{{\tilde{n}}} 2^{({\tilde{n}}-m)/2} \leq t_0 2^{{\tilde{n}}-m}$, and hence $2^{{\tilde{n}}-m}+\tfrac{1}{3}t \leq \tfrac{4}{3} t_0 2^{{\tilde{n}}-m}$. Substituting into the above equation, we get that $$\Pr_E[{{\lVert H - \operatorname{\mathbb{E}}_E H \rVert}} \geq t_0\sqrt{m}2^{({\tilde{n}}-m)/2}] \leq 2\cdot 2^m \exp(-\tfrac{3}{8} t_0 m).$$ Recall that $\rho_A = 2^{-{\tilde{n}}} H$, hence this implies a large-deviation bound for $\rho_A$: $$\Pr_E[{{\lVert \rho_A - 2^{-m}I \rVert}} \geq 2^{-{\tilde{n}}} t_0\sqrt{m}2^{({\tilde{n}}-m)/2}] \leq 2\cdot 2^m \exp(-\tfrac{3}{8} t_0 m).$$

Now use the union bound over all subsets $A\subset[n]$ of size ${{\lvert A \rvert}}=m$. (There are $\binom{n}{m} < 2^n$ such sets.) So with probability $\geq 1 - 2^{n+m+1} \exp(-\tfrac{3}{8} t_0 m)$ (over the choice of $E$), we have that $$\label{eq-treefrog}
\text{for all subsets $A$ of size $m$, } {{\lVert \rho_A - 2^{-m}I \rVert}} \leq 2^{-{\tilde{n}}} t_0\sqrt{m}2^{({\tilde{n}}-m)/2} = 2^{-m} 2^{-({\tilde{n}}-m)/2} t_0 \sqrt{m}.$$ By setting $t_0$ to be a sufficiently large constant, we can make the failure probability exponentially small in $n$. Finally, equation (\[eq-treefrog\]) implies that, for any subset $A$ of size $m$, and any measurement outcome $M_A$, the probability of observing $M_A$ (which is given by $\Pr[M_A] = \operatorname{tr}(M_A\rho_A)$) satisfies the bound $$\label{eq-toad1}
{{\lvert \Pr[M_A] - 2^{-m}\operatorname{tr}(M_A) \rvert}} \leq 2^{-m}\operatorname{tr}(M_A) 2^{-({\tilde{n}}-m)/2} t_0 \sqrt{m}.$$

Next, fix some subset of qubits $A\subset[n]$, ${{\lvert A \rvert}}=m$, and some measurement outcome $M_A$. We will use Bernstein’s inequality to upper-bound the quantity $$F := \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} F_u, \quad 
\text{where } F_u := (\operatorname{tr}(M_A))^{-2} \Pr[M_A|U=u]^2.$$ Recall that $M_A$ is a tensor product of rank-1 operators acting on single qubits, and so $M_A/\operatorname{tr}(M_A)$ can be written in the form $$\tfrac{M_A}{\operatorname{tr}(M_A)} = {{\left| \psi_A \right\rangle}}{{\left\langle \psi_A \right|}}, \quad 
\text{where } {{\left| \psi_A \right\rangle}} = {\bigotimes}_{a\in A} {{\left| \psi_a \right\rangle}}, \; {{\left| \psi_a \right\rangle}} \in {\mathbb{C}}^2, \; 
{{\left\langle \psi_a \middle| \psi_a \right\rangle}} = 1.$$ So we can write $$F_u = \Bigl( {{\left\langle E(u)_A \right|}} \, \tfrac{M_A}{\operatorname{tr}(M_A)} \, {{\left| E(u)_A \right\rangle}} \Bigr)^2
= {{\lvert {{\left\langle \psi_A \middle| E(u)_A \right\rangle}} \rvert}}^4.$$

First, we will calculate $\operatorname{\mathbb{E}}_E F = \sum_u \operatorname{\mathbb{E}}_E F_u$. Note that $\operatorname{\mathbb{E}}_E F_u = \prod_{a\in A} {{\lvert {{\left\langle \psi_a \middle| E(u)_a \right\rangle}} \rvert}}^4$. We can upper-bound this as follows: $$\label{eq-hamster-a}
\operatorname{\mathbb{E}}_E\bigl[ {{\lvert {{\left\langle \psi_a \middle| E(u)_a \right\rangle}} \rvert}}^4 \bigr] 
= \tfrac{1}{4}\bigl[ {{\lvert {{\left\langle \psi_a \middle| \alpha_{00} \right\rangle}} \rvert}}^4 + {{\lvert {{\left\langle \psi_a \middle| \alpha_{01} \right\rangle}} \rvert}}^4 + {{\lvert {{\left\langle \psi_a \middle| \alpha_{10} \right\rangle}} \rvert}}^4 + {{\lvert {{\left\langle \psi_a \middle| \alpha_{11} \right\rangle}} \rvert}}^4 \bigr]
= \tfrac{1}{4} {{\left\langle \psi_a \right|}}^{{\otimes}2} T {{\left| \psi_a \right\rangle}}^{{\otimes}2},$$ where we define the matrix $T \in {\mathbb{C}}^{4\times 4}$ to be $$T := 
\Bigl({{\left| 0 \right\rangle}}{{\left\langle 0 \right|}}\Bigr)^{{\otimes}2} + \Bigl({{\left| 1 \right\rangle}}{{\left\langle 1 \right|}}\Bigr)^{{\otimes}2} + 
\Bigl({{\left| + \right\rangle}}{{\left\langle + \right|}}\Bigr)^{{\otimes}2} + \Bigl({{\left| - \right\rangle}}{{\left\langle - \right|}}\Bigr)^{{\otimes}2}.$$ Now write the spectral decomposition of $T$: $$T = {{\left| \Psi^+ \right\rangle}}{{\left\langle \Psi^+ \right|}} + 2{{\left| \Phi^+ \right\rangle}}{{\left\langle \Phi^+ \right|}} + {{\left| \Phi^- \right\rangle}}{{\left\langle \Phi^- \right|}},$$ where ${{\left| \Psi^\pm \right\rangle}} = \tfrac{1}{\sqrt{2}}({{\left| 01 \right\rangle}}\pm{{\left| 10 \right\rangle}})$ and ${{\left| \Phi^\pm \right\rangle}} = \tfrac{1}{\sqrt{2}}({{\left| 00 \right\rangle}}\pm{{\left| 11 \right\rangle}})$ are the Bell states. Now write ${{\left| \psi_a \right\rangle}}$ in the form ${{\left| \psi_a \right\rangle}} = \alpha{{\left| 0 \right\rangle}} + \beta{{\left| 1 \right\rangle}}$. This implies $${{\left| \psi_a \right\rangle}}^{{\otimes}2} = \sqrt{2}\alpha\beta{{\left| \Psi^+ \right\rangle}} + \tfrac{1}{\sqrt{2}}(\alpha^2+\beta^2){{\left| \Phi^+ \right\rangle}} + \tfrac{1}{\sqrt{2}}(\alpha^2-\beta^2){{\left| \Phi^- \right\rangle}}.$$ Now we calculate $$\label{eq-hamster-z}
\begin{split}
{{\left\langle \psi_a \right|}}^{{\otimes}2} (2T) {{\left| \psi_a \right\rangle}}^{{\otimes}2}
&= 4{{\lvert \alpha \rvert}}^2{{\lvert \beta \rvert}}^2 + 2(\alpha^2+\beta^2)^*(\alpha^2+\beta^2) + (\alpha^2-\beta^2)^*(\alpha^2-\beta^2) \\
&= 4{{\lvert \alpha \rvert}}^2{{\lvert \beta \rvert}}^2 + 3{{\lvert \alpha \rvert}}^4 + (\alpha^2)^*\beta^2 + (\beta^2)^*\alpha^2 + 3{{\lvert \beta \rvert}}^4 \\
&= 2({{\lvert \alpha \rvert}}^2+{{\lvert \beta \rvert}}^2)^2 + {{\lvert \alpha^2+\beta^2 \rvert}}^2 \\
&\leq 3({{\lvert \alpha \rvert}}^2+{{\lvert \beta \rvert}}^2)^2 = 3.
\end{split}$$ This implies that $\operatorname{\mathbb{E}}_E\bigl[ {{\lvert {{\left\langle \psi_a \middle| E(u)_a \right\rangle}} \rvert}}^4 \bigr] \leq \tfrac{3}{8}$, and hence $\operatorname{\mathbb{E}}_E F_u \leq (\tfrac{3}{8})^m$ and $\operatorname{\mathbb{E}}_E F \leq 2^{{\tilde{n}}}(\tfrac{3}{8})^m$.

In addition, we bound the variance of $F_u$ as follows (using the fact that $0\leq F_u\leq 1$): $\operatorname{Var}_E F_u \leq \operatorname{\mathbb{E}}_E (F_u^2) \leq \operatorname{\mathbb{E}}_E F_u \leq (\tfrac{3}{8})^m$.

Now Bernstein’s inequality [@dubhashi] implies that, for all $t>0$, $$\Pr_E[F > \operatorname{\mathbb{E}}_E F + t] \leq \exp\biggl( -\frac{t^2}{2\cdot 2^{{\tilde{n}}} (\tfrac{3}{8})^m + \tfrac{2}{3} t} \biggr).$$ Recall that $m\leq {\tilde{n}}/\lg(\tfrac{8}{3})$, and note that this implies $2^{{\tilde{n}}} (\tfrac{3}{8})^m \geq 1$. Now set $$t = t_1 [2^{{\tilde{n}}} (\tfrac{3}{8})^m]^{1/2}, \text{ for any } t_1 \geq 1.$$ This implies $2\cdot 2^{{\tilde{n}}} (\tfrac{3}{8})^m + \tfrac{2}{3} t \leq (2+\tfrac{2}{3}) t_1 2^{{\tilde{n}}} (\tfrac{3}{8})^m$. Substituting into the above equation, we get $$\Pr_E[F > 2^{{\tilde{n}}} (\tfrac{3}{8})^m + t_1 [2^{{\tilde{n}}} (\tfrac{3}{8})^m]^{1/2}] \leq \exp(-\tfrac{3}{8}t_1).$$

Now take the union bound over all subsets $A\subset[n]$ of size ${{\lvert A \rvert}}=m$, and all measurement outcomes $M_A$ that correspond to measurements chosen from the set $L$ and performed on the qubits in the set $A$. (There are $\binom{n}{m} < 2^n$ such sets, and $(q{{\lvert L \rvert}})^m \leq (q O(1/{\varepsilon})^{3q})^m \leq (q O(qn)^{3q})^m \leq 2^{O(qn\lg(qn))}$ such measurement outcomes.) Then, with probability $\geq 1 - 2^{O(qn\lg(qn))} \exp(-\tfrac{3}{8}t_1)$, we have that $$\label{eq-toad2}
\text{for all subsets $A$ of size $m$, and all measurement outcomes $M_A$, } 
F \leq 2^{{\tilde{n}}} (\tfrac{3}{8})^m + t_1 [2^{{\tilde{n}}} (\tfrac{3}{8})^m]^{1/2}.$$ By setting $t_1 := \Theta(qn\lg(qn))$, we can make the failure probability exponentially small in $n$.

Finally, we will combine equations (\[eq-toad1\]) and (\[eq-toad2\]) to get a lower bound on $H_2(U|M_A)$. For any $A$ and $M_A$, we write $$\begin{split}
2^{-H_2(U|M_A)} &= \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} \Pr[U=u|M_A]^2 \\
 &= \Pr[M_A]^{-2} 4^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} \Pr[M_A|U=u]^2 \\
 &= \Pr[M_A]^{-2} 4^{-{\tilde{n}}} (\operatorname{tr}(M_A))^2 F \\
 &\leq [2^{-m} \operatorname{tr}(M_A) (1 - 2^{-({\tilde{n}}-m)/2} t_0 \sqrt{m})]^{-2} 4^{-{\tilde{n}}} (\operatorname{tr}(M_A))^2 [2^{{\tilde{n}}} (\tfrac{3}{8})^m + t_1 [2^{{\tilde{n}}} (\tfrac{3}{8})^m]^{1/2} ] \\
 &\leq 4^m (1 - 2^{-({\tilde{n}}-m)/2} t_0 \sqrt{m})^{-2} 4^{-{\tilde{n}}} 2^{{\tilde{n}}} (\tfrac{3}{8})^m (1+t_1) \\
 &\leq 2^{-{\tilde{n}}} (\tfrac{3}{2})^m O(qn\lg(qn)).
\end{split}$$ This implies $$\begin{split}
H_2(U|M_A) &\geq {\tilde{n}}- m\lg(\tfrac{3}{2}) - \lg(O(qn\lg(qn))) \\
 &\approx {\tilde{n}}- (0.5850)m - \lg(O(qn\lg(qn))).
\end{split}$$ This completes the proof of Lemma \[lem-flatfish\]. $\square$

We now return to the proof of Theorem \[thm-flounder\]. Consider any strategy ${\mathcal{M}}\in {\mathbb{M}}'$. We want to bound the mutual information $$I(U;Z) = I(U; Z_{1,\ldots,m}) + I(U; Z_{m+1,\ldots,n} | Z_{1,\ldots,m}).$$

We bound the first term using Lemma \[lem-flatfish\]. First we write $$\begin{split}
I(U; Z_{1,\ldots,m}) &= H(U) - H(U | Z_{1,\ldots,m}) \\
 &\leq {\tilde{n}}- \sum_{z_{1,\ldots,m}\in[q]^m} \Pr[Z_{1,\ldots,m}=z_{1,\ldots,m}] H(U | Z_{1,\ldots,m}=z_{1,\ldots,m}).
\end{split}$$ For any particular string of measurement outcomes $z_{1,\ldots,m} \in [q]^m$, let $A \subset [n]$ be the set of qubits that were measured, and let $M_A$ be the corresponding POVM element. Then, by Lemma \[lem-flatfish\], we have $$\begin{split}
H(U | Z_{1,\ldots,m}=z_{1,\ldots,m}) &\geq H_2(U | Z_{1,\ldots,m}=z_{1,\ldots,m}) \\
 &\geq {\tilde{n}}- {\tilde{n}}\tfrac{\lg(3/2)}{\lg(8/3)} - O(\lg(qn)).
\end{split}$$

We bound the second term using Holevo’s inequality [@NC]. First we write $$I(U; Z_{m+1,\ldots,n} | Z_{1,\ldots,m})
 = \sum_{z_{1,\ldots,m}\in[q]^m} \Pr[Z_{1,\ldots,m}=z_{1,\ldots,m}] I(U; Z_{m+1,\ldots,n} | Z_{1,\ldots,m}=z_{1,\ldots,m}).$$ For any particular string of measurement outcomes $z_{1,\ldots,m} \in [q]^m$, let $A \subset [n]$ be the set of qubits that were measured, and let $p(u) = \Pr[U=u | Z_{1,\ldots,m}=z_{1,\ldots,m}]$. Then we have $$\begin{split}
I(U; Z_{m+1,\ldots,n} | Z_{1,\ldots,m}=z_{1,\ldots,m}) 
 &\leq S\biggl( \sum_{u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} p(u) {{\left| E(u) \right\rangle}}{{\left\langle E(u) \right|}}_{[n] \setminus A} \biggr) 
     - \sum_{u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} p(u) S\Bigl( {{\left| E(u) \right\rangle}}{{\left\langle E(u) \right|}}_{[n] \setminus A} \Bigr) \\
 &\leq n-m \leq n - \tfrac{{\tilde{n}}}{\lg(8/3)} + 1.
\end{split}$$

Combining these bounds, we get $$\begin{split}
I(U;Z) &\leq {\tilde{n}}- {\tilde{n}}+ {\tilde{n}}\tfrac{\lg(3/2)}{\lg(8/3)} + O(\lg(qn)) + n - \tfrac{{\tilde{n}}}{\lg(8/3)} + 1 \\
 &\leq n - {\tilde{n}}\tfrac{\lg(4/3)}{\lg(8/3)} + O(\lg(qn)) \\
 &\approx n - (0.2933){\tilde{n}}+ O(\lg(qn)).
\end{split}$$ $\square$

One-time memories from isolated qubits {#sec-stegosaurus}
======================================

A one-time memory (OTM) is a device that implements the following functionality [@GKR]: one party (Alice) can write two messages $s,t\in{{\lbrace{0,1}\rbrace}}^k$ into the device, and then give the device to another party (Bob); after receiving the device, Bob can then choose to read either $s$ or $t$, but not both. The main application of OTM’s is to construct one-time programs [@GKR; @goyal; @bellare].

In this section, we will construct devices which are similar to OTM’s, in the isolated qubits model. Our devices will not implement the ideal OTM functionality described above, but we conjecture that they do provide a weaker “leaky OTM” functionality that is still sufficient to construct one-time programs. We will first define this “leaky OTM” functionality, and then describe our construction based on isolated qubits.

Leaky OTM’s {#sec-stegosaurus-leaky}
-----------

Fix some class of adversary strategies ${\mathbb{M}}$, some leakage parameter $\delta \in [0,1]$, and some failure probability ${\varepsilon}\in [0,1]$. A *leaky one-time memory (leaky OTM)* with parameters $({\mathbb{M}},\delta,{\varepsilon})$ is a device that has the following behavior. Suppose that the device is programmed with two messages $s$ and $t$ chosen uniformly at random in ${{\lbrace{0,1}\rbrace}}^k$; and let $S$ and $T$ be the random variables containing these messages. Then:

1.  Correctness: There exists an honest strategy ${\mathcal{M}}^{(1)} \in {\mathbb{M}}$ that interacts with the device and recovers the message $s$ with probability $\geq 1-{\varepsilon}$. Likewise, there exists an honest strategy ${\mathcal{M}}^{(2)} \in {\mathbb{M}}$ that recovers the message $t$ with probability $\geq 1-{\varepsilon}$.

2.  Leaky security: For every strategy ${\mathcal{M}}\in {\mathbb{M}}$, if $Z$ is the random variable containing the classical information output by ${\mathcal{M}}$, then with probability $\geq 1-{\varepsilon}$, $Z$ takes on a value $z$ such that $H_\infty^{\varepsilon}(S,T|Z=z) \geq (1-\delta)k$. (Here $H_\infty^{\varepsilon}$ is the smoothed min-entropy.)

This leaky OTM is weaker than the ideal OTM in two important respects: it assumes that the messages $s$ and $t$ are chosen uniformly at random, independent of all other variables; and it allows the adversary to obtain partial information about both $s$ and $t$, so long as the adversary still has $(1-\delta)k$ bits of uncertainty (as measured by the smoothed min-entropy).

Also, note that when we choose ${\mathbb{M}}$ to be the class of LOCC adversaries, the above definition yields information-theoretic (rather than computational) notions of correctness and security. In particular, the honest strategies are not required to be computationally efficient, but at the same time, security holds against LOCC adversaries with unbounded computational power.

We remark that this definition is mostly classical, rather than quantum. In particular, this definition assumes that the party who programs the OTM is classical, so that the messages $s$ and $t$ are classical bit strings. This definition also assumes that the party who reads the OTM may make (quantum) LOCC measurements, but immediately outputs a classical string $z$. These assumptions are reasonable, since the isolated qubits model is mostly classical, as LOCC operations can never generate quantum entanglement.

We conjecture that one can construct one-time programs from (computationally-efficient) leaky OTM’s, provided the leakage parameter $\delta$ is a sufficiently small constant, and the failure probability ${\varepsilon}$ is negligible. To see why this is plausible, consider the one-time programs in [@GKR], which are based on Yao’s garbled circuits. Here, the OTM’s contain keys for an encryption scheme. These keys are chosen independently at random, and are never re-used. Furthermore, one can use a leak-resistant encryption scheme, which can tolerate leakage of a constant fraction of the bits of the key [@AGV]. Here, the adversary’s remaining uncertainty about the key is expressed using the (smoothed) min-entropy. This suggests that leaky OTM’s will be sufficient for this construction.

Construction using isolated qubits {#sec-stegosaurus-construction}
----------------------------------

We consider a system of $n$ isolated qubits, and we construct a set of states ${{\left| E(s,t) \right\rangle}}$ (for $s,t\in{{\lbrace{0,1}\rbrace}}^k$), where $k \approx (0.3991)n$. First, choose a random function $C: {{\lbrace{0,1}\rbrace}}^k \rightarrow {{\lbrace{0,1}\rbrace}}^n$, i.e., for each $s \in {{\lbrace{0,1}\rbrace}}^k$, choose $C(s) \in {{\lbrace{0,1}\rbrace}}^n$ independently and uniformly at random. Similarly, choose a random function $D: {{\lbrace{0,1}\rbrace}}^k \rightarrow {{\lbrace{0,1}\rbrace}}^n$. Now define $${{\left| E(s,t) \right\rangle}} := {\bigotimes}_{a=1}^n {{\left| \alpha_{C(s)_a D(t)_a} \right\rangle}},$$ where the single-qubit states ${{\left| \alpha_{00} \right\rangle}}$, ${{\left| \alpha_{01} \right\rangle}}$, ${{\left| \alpha_{10} \right\rangle}}$, ${{\left| \alpha_{11} \right\rangle}}$ are defined in the same way as in the previous section: $${{\left| \alpha_{00} \right\rangle}} = {{\left| 0 \right\rangle}}, \quad
{{\left| \alpha_{11} \right\rangle}} = {{\left| 1 \right\rangle}}, \quad
{{\left| \alpha_{01} \right\rangle}} = \tfrac{1}{\sqrt{2}} ({{\left| 0 \right\rangle}}+{{\left| 1 \right\rangle}}), \quad
{{\left| \alpha_{10} \right\rangle}} = \tfrac{1}{\sqrt{2}} ({{\left| 0 \right\rangle}}-{{\left| 1 \right\rangle}}).$$ Note that these states can be prepared using single-qubit operations in the isolated qubits model.

We now describe the “honest” measurement strategies, that can be used to learn either $s$ or $t$. The states ${{\left| E(s,t) \right\rangle}}$ are reminiscent of Wiesner’s conjugate coding [@wiesner], in that measuring in one basis reveals information about $s$, while measuring in another basis reveals information about $t$. Let us define the states $${{\left| \beta_\phi \right\rangle}} := \cos(\phi){{\left| 0 \right\rangle}} + \sin(\phi){{\left| 1 \right\rangle}}, \quad \phi \in {\mathbb{R}}.$$ Then measuring each qubit in the basis ${{\lbrace{{{\left| \beta_{\pi/8} \right\rangle}}, {{\left| \beta_{5\pi/8} \right\rangle}}}\rbrace}}$ returns a “noisy” copy of the string $C(s)$, which can be decoded to recover $s$ (since, with high probability, $C$ is a good error-correcting code). Likewise, measuring each qubit in the basis ${{\lbrace{{{\left| \beta_{-\pi/8} \right\rangle}}, {{\left| \beta_{3\pi/8} \right\rangle}}}\rbrace}}$ returns a “noisy” copy of the string $D(t)$, which can be decoded to recover $t$.

Is there some measurement strategy that will reveal both $s$ and $t$? Wiesner pointed out that there does exist a joint measurement on the $n$ qubits that can recover both $s$ and $t$; this also follows from the “gentle measurement lemma” of Winter [@gentle]. However, when the codes $C$ and $D$ are “unstructured,” one may expect this measurement to be highly entangled, hence impossible to perform using only LOCC operations. We will give rigorous evidence that this is indeed the case.

We will show that these states partially satisfy the definition of a leaky OTM. In particular, with high probability over the random choice of $C$ and $D$, the following statements hold:

1.  Suppose $s$ and $t$ are chosen uniformly at random. There exists a sequence of single-qubit projective measurements that can reconstruct $s$ with probability $\geq 1 - e^{-\Omega(n)}$. Likewise, there exists a sequence of single-qubit projective measurements that can reconstruct $t$ with probability $\geq 1 - e^{-\Omega(n)}$.

2.  Suppose $s$ and $t$ are chosen uniformly at random. No 1-pass LOCC measurement strategy using 2-outcome measurements can recover more than $\approx (1.9190)k$ bits of information about $s$ and $t$. That is, if $S$ and $T$ are the random variables containing the strings $s$ and $t$, and $Z$ is the output of the measurement strategy, then $$I(Z;S,T) \leq (1.9190)k + O(\sqrt{n} \log n).$$ Note that we can write $I(Z;S,T) = H(S,T) - H(S,T|Z)$, hence this implies $$H(S,T|Z) \geq (0.081)k - O(\sqrt{n} \log n).$$

These statements are similar to the definition of a leaky OTM, where ${\mathbb{M}}$ is the set of 1-pass LOCC measurement strategies using 2-outcome measurements, the leakage parameter is $\delta \approx 0.9190$, the failure probability is ${\varepsilon}= e^{-\Omega(n)}$, and the security condition is relaxed by replacing the smoothed min-entropy $H_\infty^{\varepsilon}$ with the Shannon entropy $H$. (Also, we set aside the requirement that the honest strategies must be computationally efficient.)

We believe it should be possible to prove much stronger results of this type. In particular, it should be possible to improve our bound on the leakage parameter $\delta$, as our current proof technique is somewhat ad hoc. Also, we remark that some parts of our proof already imply bounds on the smoothed min-entropy $H_\infty^{\varepsilon}$. Specifically, in Lemma \[lem-cuttlefish\], we actually lower-bound the collision entropy $H_2(S,T|Z_{1,\ldots,m}=z_{1,\ldots,m})$, where $Z_{1,\ldots,m}$ represents the measurement outcomes of the first $m$ qubits measured by the adversary, where $m \approx (0.7067)k$. This directly implies a lower-bound on the smoothed min-entropy $H_\infty^{\varepsilon}(S,T|Z_{1,\ldots,m}=z_{1,\ldots,m})$, using a standard argument.[^7]

Correctness for honest parties {#sec-stegosaurus-correct}
------------------------------

First, we show that the honest strategies for recovering either $s$ or $t$ (as described above) do succeed with high probability. Without loss of generality, suppose we want to recover $s$. Let $S$ and $T$ be random variables, distributed independently and uniformly on ${{\lbrace{0,1}\rbrace}}^k$. We are given the state ${{\left| E(S,T) \right\rangle}}$, and we measure each qubit in the basis ${{\lbrace{{{\left| \beta_{\pi/8} \right\rangle}}, {{\left| \beta_{5\pi/8} \right\rangle}}}\rbrace}}$. Let $Z$ be the random variable containing the string of measurement outcomes, i.e., $Z$ takes values in ${{\lbrace{0,1}\rbrace}}^n$.

We decode $Z$ as follows: we output any string $t \in {{\lbrace{0,1}\rbrace}}^k$ such that $d_H(C(t),Z) \leq r$, where $d_H$ denotes the Hamming distance, and $r$ is a parameter that we will set below. If there are multiple candidate strings $t$, we pick one of them in some arbitrary fashion. Let ${\hat{S}}$ be the random variable containing the output of this procedure.

Observe that $Z$ is the output of a binary symmetric channel $BSC(p_e)$ applied to the string $C(S)$, where the error probability $p_e$ is given by $$p_e := \sin^2(\pi/8) \approx 0.1464.$$ Recall that the channel $BSC(p_e)$ has capacity $1-h(p_e) \approx 0.3991$, where $h(p)$ is the binary entropy function, $$h(p) := -p\lg(p) - (1-p)\lg(1-p).$$ Also, note that the expected number of errors introduced by the channel is $np_e$.

This suggests that we should set the parameters $k$ and $r$ as follows: $$\label{eq-penguin}
k := n(1-h(p_e)-\theta),$$ $$r := n(p_e+\tau),$$ where $0<\theta \ll 1$ and $0<\tau \ll 1$ are small constants.

We prove the following statement, which is essentially Shannon’s noisy coding theorem for the binary symmetric channel, using an argument from [@welsh]. This shows that, when we choose $\theta$ and $\tau$ appropriately, then with high probability over the choice of the random code $C$, $\Pr[{\hat{S}}=S]$ is close to 1.

\[prop-sea-cucumber\] Fix any constants $\lambda \geq 1$, $0 < \tau \leq \tfrac{1}{2} - p_e \approx 0.3536$, and $\theta > \tau h'(p_e) \approx (2.5431) \tau$. Then for all sufficiently large $n$, the following statement holds: with probability $\geq 1-\tfrac{1}{\lambda}$ (over the choice of $C$), we have $$\Pr[{\hat{S}}=S] \geq 1 - \lambda \bigl[ e^{-2\tau^2 n} + 2^{-n (\theta - \tau h'(p_e))} \bigr]
\geq 1 - \lambda e^{-\Omega(n)}.$$

Proof: See Appendix \[app-noisy-coding\].

Security against 1-pass LOCC adversaries using 2-outcome measurements {#sec-stegosaurus-secure}
---------------------------------------------------------------------

In this section we will upper-bound the amount of information that can be extracted from our OTM devices by any 1-pass LOCC adversary using 2-outcome measurements. We use the collision entropy technique to analyze the first few steps taken by the adversary; then we use the entropy chaining technique to prove bounds on the adversary’s subsequent steps. To deal with the correlations among the states ${{\left| E(s,t) \right\rangle}}$, we will use large deviation bounds for sums of locally dependent random variables [@janson; @dubhashi].

\[thm-squid\] Let ${\mathbb{M}}$ be the set of all 1-pass LOCC strategies that use 2-outcome measurements. Then, with probability $\geq 1 - e^{-\Omega(n)}$ (over the choice of $C$ and $D$), the following statement holds: $$\forall {\mathcal{M}}\in {\mathbb{M}}, \; I(Z;S,T) \leq (1.9190)k + O(\sqrt{n} \log n),$$ where $Z$ denotes the output of the strategy ${\mathcal{M}}$. Equivalently, we can write: $$\forall {\mathcal{M}}\in {\mathbb{M}}, \; H(S,T|Z) \geq (0.081)k - O(\sqrt{n} \log n).$$

Proof: First, let $L$ be an ${\varepsilon}$-net for the set of single-qubit measurements with 2 outcomes where all POVM elements have rank 1, as described in Lemma \[lem-epsnet-2\]; and set ${\varepsilon}= 1/(200n)$. Let ${\mathbb{M}}'$ be the set of all strategies that use measurements chosen from the set $L$. By Lemmas \[lem-locc-rank1\] and \[lem-locc-epsnet\], any strategy in ${\mathbb{M}}$ can be approximated by one in ${\mathbb{M}}'$.

We will analyze the first $m$ steps of any strategy in ${\mathbb{M}}'$, where $$\label{eq-shrimp0}
m := \lfloor k/\lg(8/3) \rfloor \approx (0.7067)k.$$ We will show the following bound:

\[lem-cuttlefish\] With probability $\geq 1 - e^{-\Omega(n)}$ (over the choice of $C$ and $D$), $$\label{eq-cuttlefish}
\forall {\mathcal{M}}\in {\mathbb{M}}', \; \forall z_{1,\ldots,m}\in{{\lbrace{0,1}\rbrace}}^m, \;
H_2(S,T | Z_{1,\ldots,m}=z_{1,\ldots,m}) \geq 2k - m\lg(\tfrac{3}{2}) - \lg(O(n\lg n)),$$ where $Z_{1,\ldots,m}$ denotes the output of the first $m$ steps of the strategy ${\mathcal{M}}$, $H_2$ denotes the Renyi collision entropy, and $\lg(\tfrac{3}{2}) \approx 0.5850$.

Remark: Equation (\[eq-cuttlefish\]) is equivalent to the following statement:

> for all subsets of qubits $A \subset [n]$, of size ${{\lvert A \rvert}} = m$,\
> for all possible measurement outcomes $M_A$, that can be obtained by measuring the qubits in $A$ (using measurements chosen from the set $L$),\
> $H_2(S,T | M_A) \geq 2k - m\lg(\tfrac{3}{2}) - \lg(O(n\lg n))$.

Recall that a measurement outcome $M_A$ is uniquely represented by a rank-1 POVM element of the form $M_A = {\bigotimes}_{i\in A} M_i$, where each $M_i$ is a POVM element acting on qubit $i$, that corresponds to one possible outcome of some measurement in the set $L$.

Proof (of Lemma \[lem-cuttlefish\]): First, we will show that, for every $A$ and $M_A$, $\Pr[M_A]$ is approximately $\operatorname{tr}(M_A)/2^m$. Secondly, we will show that, for every $A$ and $M_A$, $\sum_u \Pr[M_A|S=s,T=t]^2$ is small. (To show these claims, we will use large-deviation bounds for every fixed choice of $A$ and $M_A$, followed by the union bound over all $A$ and $M_A$.) Finally, we will combine these two claims to get a lower-bound on $H_2(S,T|M_A)$.

First, fix some subset of qubits $A\subset [n]$, of size ${{\lvert A \rvert}} = m$, and fix some measurement outcome $M_A$. Let $\rho$ be the mixed state presented to the adversary, $\rho := 4^{-k} \sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} {{\left| E(s,t) \right\rangle}}{{\left\langle E(s,t) \right|}}$, and let $\rho_A$ be the reduced state on the subset $A$, $$\rho_A := \operatorname{tr}_{[n]\setminus A}(\rho) = 4^{-k} \sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} {{\left| E(s,t)_A \right\rangle}}{{\left\langle E(s,t)_A \right|}}, 
\text{ where } {{\left| E(s,t)_A \right\rangle}} := {\bigotimes}_{a\in A} {{\left| \alpha_{C(s)_a D(t)_a} \right\rangle}}.$$ Recall that $M_A$ is a tensor product of rank-1 operators acting on single qubits. Moreover, since the adversary uses single-qubit measurements with 2 outcomes, each measurement outcome is a rank-1 projector. So $\operatorname{tr}(M_A)=1$, and $M_A$ can be written in the form $$M_A = {{\left| \psi_A \right\rangle}}{{\left\langle \psi_A \right|}}, \quad 
\text{where } {{\left| \psi_A \right\rangle}} = {\bigotimes}_{a\in A} {{\left| \psi_a \right\rangle}}, \; {{\left| \psi_a \right\rangle}} \in {\mathbb{C}}^2, \; 
{{\left\langle \psi_a \middle| \psi_a \right\rangle}} = 1.$$

We will use Bernstein’s inequality for locally dependent random variables [@janson] to lower-bound the quantity $$\Pr[M_A] = \operatorname{tr}(M_A\rho_A) = 4^{-k} \sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} {{\lvert {{\left\langle \psi_A \middle| E(s,t)_A \right\rangle}} \rvert}}^2.$$ For convenience, let us define the random variables $$H := \sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} H_{st}, \quad H_{st} := {{\lvert {{\left\langle \psi_A \middle| E(s,t)_A \right\rangle}} \rvert}}^2.$$ We can calculate their expectation values: $$\operatorname{\mathbb{E}}_{CD} H_{st} = \prod_{a\in A} \operatorname{\mathbb{E}}_{CD}[ {{\lvert {{\left\langle \psi_a \middle| E(s,t)_a \right\rangle}} \rvert}}^2 ] = 2^{-m},$$ hence $\operatorname{\mathbb{E}}_{CD} H = 4^k 2^{-m}$. We can also bound their variances: $$\operatorname{Var}_{CD} H_{st} \leq \operatorname{\mathbb{E}}_{CD}[H_{st}^2] = \prod_{a\in A} \operatorname{\mathbb{E}}_{CD}[ {{\lvert {{\left\langle \psi_a \middle| E(s,t)_a \right\rangle}} \rvert}}^4 ]
\leq (\tfrac{3}{8})^m,$$ where in the last step we re-used the argument shown in equations (\[eq-hamster-a\])-(\[eq-hamster-z\]) in the proof of Lemma \[lem-flatfish\].

We claim that the dependency graph $\Gamma$ of the random variables $H_{st}$ ($s,t\in{{\lbrace{0,1}\rbrace}}^k$) has chromatic number $\chi(\Gamma) \leq 2^k$. To see this, note that two vertices $(s,t)$ and $(s',t')$ in $\Gamma$ are adjacent if and only if $s=s'$ or $t=t'$. We can color the vertices of $\Gamma$ as follows: assign each vertex $(s,t)$ the color specified by the string $s\oplus t \in {{\lbrace{0,1}\rbrace}}^k$ (where $\oplus$ denotes bitwise XOR). It is easy to check that this is a legal coloring, which uses $2^k$ colors.

Using Bernstein’s inequality for locally dependent random variables [@janson], we get that for all $\tau>0$, $$\begin{split}
\Pr_{CD}[H \leq \operatorname{\mathbb{E}}_{CD}H - \tau] 
&\leq \exp\biggl( -\frac{8\tau^2}{25\cdot 2^k (4^k (\tfrac{3}{8})^m + \tfrac{1}{3} \tau)} \biggr) \\
&\leq \exp\biggl( -\frac{8\tau^2}{25\cdot 2^k \max{{\lbrace{2\cdot (\tfrac{3}{2})^k (\tfrac{8}{3})^{k-m}, \tfrac{2}{3} \tau}\rbrace}}} \biggr) \\
&= \max\biggl\lbrace \exp\biggl( -\frac{4\tau^2}{25\cdot 3^k (\tfrac{8}{3})^{k-m}} \biggr), \; 
\exp\biggl( -\frac{12\tau^2}{25\cdot 2^k \tau} \biggr) \biggr\rbrace.
\end{split}$$ Now set $$\tau := 4^k 2^{-m} k^{-1} = 2^k 2^{k-m} k^{-1},$$ which implies $$\Pr_{CD}[H \leq 4^k 2^{-m} (1-k^{-1})] 
\leq \max\bigl\lbrace \exp(-\tfrac{4}{25} (\tfrac{4}{3})^k (\tfrac{3}{2})^{k-m} k^{-2}), \;
\exp(-\tfrac{12}{25} 2^{k-m} k^{-1}) \bigr\rbrace.$$

Now take the union bound over all subsets $A\subset[n]$ of size ${{\lvert A \rvert}}=m$, and all measurement outcomes $M_A$ that correspond to measurements chosen from the set $L$ and performed on the qubits in the set $A$. (There are $\binom{n}{m} < 2^n$ such sets, and $(2{{\lvert L \rvert}})^m \leq (O(1/{\varepsilon}^2))^m \leq (O(n^2))^m \leq 2^{O(n\lg n)}$ such measurement outcomes.) So, with probability $\geq 1 - 2^{O(n\lg n)} \cdot \max\bigl\lbrace \exp(-\tfrac{4}{25} (\tfrac{4}{3})^k (\tfrac{3}{2})^{k-m} k^{-2}), \;
\exp(-\tfrac{12}{25} 2^{k-m} k^{-1}) \bigr\rbrace$ (over the choice of $C$ and $D$), we have that: $$\label{eq-goldfish1}
\begin{split}
&\text{for all subsets $A$ of size $m$, and all measurement outcomes $M_A$, } \\
&\quad\quad H \geq 4^k 2^{-m} (1-k^{-1}), \text{ and hence, } \Pr[M_A] \geq 2^{-m} (1-k^{-1}).
\end{split}$$ Recall that $m \leq (0.7061)k$, and $k \approx (0.3991)n$; this implies that the failure probability is doubly-exponentially small in $n$.

Next, fix some subset of qubits $A\subset[n]$, ${{\lvert A \rvert}}=m$, and some measurement outcome $M_A = {{\left| \psi_A \right\rangle}}{{\left\langle \psi_A \right|}}$, as before. We will now upper-bound the quantity $$F := \sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} F_{st}, \quad 
\text{where } F_{st} := \Pr[M_A|S=s,T=t]^2 = {{\lvert {{\left\langle \psi_A \middle| E(s,t)_A \right\rangle}} \rvert}}^4.$$

First, note that $\operatorname{\mathbb{E}}_{CD} F_{st} \leq (\tfrac{3}{8})^m$ and $\operatorname{\mathbb{E}}_{CD} F \leq 4^k (\tfrac{3}{8})^m$, by the same argument shown in equations (\[eq-hamster-a\])-(\[eq-hamster-z\]) in the proof of Lemma \[lem-flatfish\]. In addition, since $0\leq F_{st}\leq 1$, we have that $\operatorname{Var}_{CD} F_{st} \leq \operatorname{\mathbb{E}}_{CD} (F_{st}^2) \leq \operatorname{\mathbb{E}}_{CD} F_{st} \leq (\tfrac{3}{8})^m$.

Now Bernstein’s inequality for locally dependent random variables [@janson] implies that, for all $\tau>0$, $$\Pr_{CD}[F > \operatorname{\mathbb{E}}_{CD} F + \tau] \leq \exp\biggl( -\frac{8\tau^2}{25\cdot 2^k (4^k (\tfrac{3}{8})^m + \tfrac{1}{3} \tau)} \biggr).$$ Recall that $m\leq k/\lg(\tfrac{8}{3})$, and note that this implies $2^k (\tfrac{3}{8})^m \geq 1$. Now set $$\tau = \tau_1 4^k (\tfrac{3}{8})^m, \text{ for any } \tau_1 \geq 1.$$ This implies $4^k (\tfrac{3}{8})^m + \tfrac{1}{3} \tau \leq (1+\tfrac{1}{3}) \tau_1 4^k (\tfrac{3}{8})^m = \tfrac{4}{3} \tau$. Substituting into the above equation, we get $$\Pr_E[F > 4^k (\tfrac{3}{8})^m (1+\tau_1)] \leq \exp(-\tfrac{6}{25} \tau_1 2^k (\tfrac{3}{8})^m)
\leq \exp(-\tfrac{6}{25} \tau_1).$$

Now take the union bound over all subsets $A\subset[n]$ of size ${{\lvert A \rvert}}=m$, and all measurement outcomes $M_A$ that correspond to measurements chosen from the set $L$ and performed on the qubits in the set $A$. Then, with probability $\geq 1 - 2^{O(n\lg n)} \exp(-\tfrac{6}{25}\tau_1)$, we have that: $$\label{eq-goldfish2}
\text{for all subsets $A$ of size $m$, and all measurement outcomes $M_A$, } 
F \leq 4^k (\tfrac{3}{8})^m (1+\tau_1).$$ By setting $\tau_1 := \Theta(n\lg n)$, we can make the failure probability exponentially small in $n$.

Finally, we will combine equations (\[eq-goldfish1\]) and (\[eq-goldfish2\]), to get a lower bound on $H_2(S,T|M_A)$. For any $A$ and $M_A$, we write $$\begin{split}
2^{-H_2(S,T|M_A)} &= \sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} \Pr[S=s,T=t|M_A]^2 \\
 &= \Pr[M_A]^{-2} 4^{-2k} \sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} \Pr[M_A|S=s,T=t]^2 \\
 &= \Pr[M_A]^{-2} 4^{-2k} F \\
 &\leq [2^{-m} (1-k^{-1})]^{-2} 4^{-2k} 4^k (\tfrac{3}{8})^m (1+\tau_1) \\
 &= 4^{-k} (\tfrac{3}{2})^m \tfrac{1+\tau_1}{(1-k^{-1})^2}.
\end{split}$$ This implies $$\begin{split}
H_2(S,T|M_A) &\geq 2k - m\lg(\tfrac{3}{2}) - \lg(1+\tau_1) + 2\lg(1-k^{-1}) \\
 &\geq 2k - m\lg(\tfrac{3}{2}) - \lg(O(n\lg n)).
\end{split}$$ This completes the proof of Lemma \[lem-cuttlefish\]. $\square$

We now return to the proof of Theorem \[thm-squid\]. Consider any measurement strategy ${\mathcal{M}}\in {\mathbb{M}}'$, and let $Z$ be its output. We will upper-bound the amount of information extracted during the first $m$ steps, using Lemma \[lem-cuttlefish\]: $$\label{eq-shrimp1}
\begin{split}
I(S,T; Z_{1,\ldots,m}) &= H(S,T) - H(S,T|Z_{1,\ldots,m}) \\
 &\leq H(S,T) - \sum_{z_{1,\ldots,m}} \Pr[Z_{1,\ldots,m}=z_{1,\ldots,m}] H_2(S,T|Z_{1,\ldots,m}=z_{1,\ldots,m}) \\
 &\leq 2k - [2k - m\lg(\tfrac{3}{2}) - \lg(O(n\lg n))] \\
 &= m\lg(\tfrac{3}{2}) + \lg(O(n\lg n)) \\
 &= k \tfrac{\lg(3/2)}{\lg(8/3)} + \lg(O(n\lg n)).
\end{split}$$

Next, we will analyze the subsequent steps of the adversary. First, let us fix some subset of qubits $A\subset[n]$, of size ${{\lvert A \rvert}}=m$, and some measurement outcome $M_A$; these represent past actions of the adversary during its first $m$ steps. We will then upper-bound the amount of information gained by the adversary in the next ${\tilde{m}}$ steps, conditioned on $M_A$. Finally, we will use the union bound to show that this result holds simultaneously for all choices of $A$ and $M_A$.

To simplify the notation, let us define $h := H_2(S,T|M_A)$, and $p_{st} := \Pr[S=s,T=t|M_A]$; so we have $$\sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} p_{st}^2 \leq 2^{-h}.$$ Note that $h$ and $p_{st}$ depend only on the qubits in the set $A$; so they only depend on those random variables $C(s)_a$ and $D(t)_a$ with $a\in A$. As shown above, with probability $\geq 1 - e^{-\Omega(n)}$ (over this subset of the random variables $C$ and $D$), $$h \geq 2k - m\lg(\tfrac{3}{2}) - \lg(O(n\lg n)).$$

We will look at the next ${\tilde{m}}$ steps of the adversary, and we set $$\label{eq-shrimp2}
{\tilde{m}}:= \lfloor h-k \rfloor \geq k - m\lg(\tfrac{3}{2}) - \lg(O(n\lg n)).$$ More precisely, we let ${\widetilde{\mathbb{M}}}$ be the set of all possible measurement strategies that an adversary in ${\mathbb{M}}'$ may follow for the next ${\tilde{m}}$ steps, after having received measurement outcome $M_A$ on the first $m$ steps. We let ${\tilde{Z}}:= (Z_{m+1},\ldots,Z_{m+{\tilde{m}}})$ be the output of the adversary on the next ${\tilde{m}}$ steps. Note that this depends only on the qubits outside the set $A$; so it only depends on those random variables $C(s)_a$ and $D(t)_a$ with $a\notin A$. We refer to this subset of random variables as ${\tilde{C}}$ and ${\tilde{D}}$. We show the following lemma:

Fix a particular subset of qubits $A$ and a particular measurement outcome $M_A$, as described above. Let $t_0>0$ and $u \geq 1$. With probability $\geq 1 - \exp(-2t_0^2) - 2\cdot 2^{-u^2}$ (over the choice of ${\tilde{C}}$ and ${\tilde{D}}$), the following statement holds: $$\forall {\mathcal{M}}\in {\widetilde{\mathbb{M}}}, \; I({\tilde{Z}};S,T|M_A) < \frac{{\tilde{m}}}{2} + \frac{t_0{\tilde{m}}}{2^{{\tilde{m}}/2}} + u\cdot O(\sqrt{\log n}).$$

Proof: We want to upper-bound the quantity $$I({\tilde{Z}};S,T|M_A) = H({\tilde{Z}}|M_A) - H({\tilde{Z}}|S,T,M_A).$$ We know that $H({\tilde{Z}}|M_A) \leq {\tilde{m}}$, since the adversary uses 2-outcome measurements. We now want to lower-bound $H({\tilde{Z}}|S,T,M_A)$. For any ${\mathcal{M}}\in {\widetilde{\mathbb{M}}}$, we define $$Q_{\mathcal{M}}:= H({\tilde{Z}}|S,T,M_A),$$ which is a random variable depending on ${\tilde{C}}$ and ${\tilde{D}}$. Note that we can write $$Q_{\mathcal{M}}= \sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} p_{st} H({\tilde{Z}}|S=s,T=t,M_A).$$ Let $\mu_{\mathcal{M}}:= \operatorname{\mathbb{E}}_{{\tilde{C}}{\tilde{D}}} Q_{\mathcal{M}}$; we will prove a lower bound for $\mu_{\mathcal{M}}$ below. We will then use entropy chaining (Lemma \[lem-dudley\]) to lower-bound the quantity $$\inf_{{\mathcal{M}}\in {\widetilde{\mathbb{M}}}} (Q_{\mathcal{M}}- \mu_{\mathcal{M}}).$$

First, we evaluate $\mu_{\mathcal{M}}$. Using the same argument as in the proof of Theorem \[thm-willow\], we get that $$\mu_{\mathcal{M}}\geq {\tilde{m}}/2.$$

We now show several technical facts which are needed in order to apply the entropy chaining argument (Lemma \[lem-dudley\]). First, fix some particular strategy ${\mathcal{M}}_0 \in {\widetilde{\mathbb{M}}}$. We will show that $Q_{{\mathcal{M}}_0}$ is tightly concentrated around its mean. Observe that $Q_{{\mathcal{M}}_0}$ is a sum of $4^k$ random variables, and recall that their dependency graph $\Gamma$ has chromatic number $\chi(\Gamma) \leq 2^k$. Using Hoeffding’s inequality for locally dependent random variables [@janson; @dubhashi], we get that

$$\Pr_{{\tilde{C}}{\tilde{D}}}[Q_{{\mathcal{M}}_0} < \mu_{{\mathcal{M}}_0} - t] \leq \exp\Bigl( -\frac{2t^2}{2^k \sum_{st} (p_{st}{\tilde{m}})^2} \Bigr)
= \exp\Bigl( -\frac{2t^2 \cdot 2^{{\tilde{m}}}}{{\tilde{m}}^2} \Bigr) \quad (\forall t>0),$$

or equivalently $$\Pr_{{\tilde{C}}{\tilde{D}}}\Bigl[Q_{{\mathcal{M}}_0} < \mu_{{\mathcal{M}}_0} - \frac{t_0 {\tilde{m}}}{2^{{\tilde{m}}/2}}\Bigr] \leq \exp(-2t_0^2), \quad (\forall t_0>0).$$

Next, we show that when two strategies ${\mathcal{M}}$ and ${\mathcal{M}}'$ are “similar,” the random variables $Q_{\mathcal{M}}$ and $Q_{{\mathcal{M}}'}$ are positively correlated. In particular, suppose that ${\mathcal{M}}$ and ${\mathcal{M}}'$ behave identically for the first $\ell$ steps. Let ${\tilde{Z}}_{1,\ldots,{\tilde{m}}}$ and ${\tilde{Z}}'_{1,\ldots,{\tilde{m}}}$ be the output of these two strategies; then $({\tilde{Z}}_{1,\ldots,\ell},U)$ and $({\tilde{Z}}'_{1,\ldots,\ell},U)$ have the same distribution. So we can write $$\begin{split}
Q_{\mathcal{M}}- Q_{{\mathcal{M}}'}
 &= H({\tilde{Z}}_{\ell+1,\ldots,{\tilde{m}}}|{\tilde{Z}}_{1,\ldots,\ell},S,T,M_A) - H({\tilde{Z}}'_{\ell+1,\ldots,{\tilde{m}}}|{\tilde{Z}}'_{1,\ldots,\ell},S,T,M_A) \\
 &= \sum_{s,t\in{{\lbrace{0,1}\rbrace}}^k} p_{st} [ H({\tilde{Z}}_{\ell+1,\ldots,{\tilde{m}}}|{\tilde{Z}}_{1,\ldots,\ell},S=s,T=t,M_A) - H({\tilde{Z}}'_{\ell+1,\ldots,{\tilde{m}}}|{\tilde{Z}}'_{1,\ldots,\ell},S=s,T=t,M_A) ], 
\end{split}$$ which again is a sum of $4^k$ locally-dependent random variables. By Hoeffding’s inequality (with local dependencies), $$\Pr_{{\tilde{C}}{\tilde{D}}}[Q_{\mathcal{M}}- Q_{{\mathcal{M}}'} - \mu_{\mathcal{M}}+ \mu_{{\mathcal{M}}'} \geq t]
 \leq \exp\Bigl( -\frac{2t^2}{2^k \sum_{st} (p_{st} \cdot 2({\tilde{m}}-\ell))^2} \Bigr)
 = \exp\Bigl( -\frac{t^2 \cdot 2^{{\tilde{m}}}}{2 ({\tilde{m}}-\ell)^2} \Bigr).$$ We can rewrite this bound in terms of a metric $d$ that measures the “distance” between strategies. We define $d$ as follows: [^8] $$d({\mathcal{M}},{\mathcal{M}}') := \sqrt{2} \cdot 2^{-{\tilde{m}}/2} ({\tilde{m}}-\ell({\mathcal{M}},{\mathcal{M}}')), \text{ where}$$ $$\ell({\mathcal{M}},{\mathcal{M}}') := \max {{\lbrace{\ell \;|\; \text{$0\leq\ell\leq{\tilde{m}}$, and ${\mathcal{M}}$ and ${\mathcal{M}}'$ behave identically on steps $1,2,\ldots,\ell$}}\rbrace}}.$$ We then have $$\Pr_{{\tilde{C}}{\tilde{D}}}[Q_{\mathcal{M}}- Q_{{\mathcal{M}}'} - \mu_{\mathcal{M}}+ \mu_{{\mathcal{M}}'} \geq t]
 \leq \exp\Bigl( -\frac{t^2}{d({\mathcal{M}},{\mathcal{M}}')^2} \Bigr).$$

Next, we bound the covering numbers of ${\widetilde{\mathbb{M}}}$ with respect to the metric $d$, and we bound the integral appearing in Lemma \[lem-dudley\] (“Dudley’s entropy integral”). Using the same argument as in the proof of Theorem \[thm-willow\], we get that $$S \leq O(\sqrt{\log n}).$$

Finally, using Lemma \[lem-dudley\], we have that: for all $t_0>0$ and $u \geq 1$, with probability $\geq 1 - \exp(-2t_0^2) - 2\cdot 2^{-u^2}$, the following holds: $$\forall {\mathcal{M}}\in {\widetilde{\mathbb{M}}}, \; Q_{{\mathcal{M}}} - \mu_{{\mathcal{M}}} > - \frac{t_0{\tilde{m}}}{2^{{\tilde{m}}/2}} - uS.$$ This implies $$\forall {\mathcal{M}}\in {\widetilde{\mathbb{M}}}, \; Q_{{\mathcal{M}}} > \frac{{\tilde{m}}}{2} - \frac{t_0{\tilde{m}}}{2^{{\tilde{m}}/2}} - u\cdot O(\sqrt{\log n}).$$ Hence $$\forall {\mathcal{M}}\in {\widetilde{\mathbb{M}}}, \; I({\tilde{Z}};S,T|M_A) < \frac{{\tilde{m}}}{2} + \frac{t_0{\tilde{m}}}{2^{{\tilde{m}}/2}} + u\cdot O(\sqrt{\log n}).$$ This proves the claim. $\square$

We now return to the proof of Theorem \[thm-squid\]. We take the union bound over all subsets $A\subset[n]$ of size ${{\lvert A \rvert}}=m$, and all measurement outcomes $M_A$ that correspond to measurements chosen from the set $L$ and performed on the qubits in the set $A$. Then, with probability $\geq 1 - 2^{O(n\lg n)} \cdot \exp(-2t_0^2) - 2^{O(n\lg n)} \cdot 2\cdot 2^{-u^2}$, we have that: $$\begin{split}
&\text{for all subsets $A$ of size $m$, and all measurement outcomes $M_A$, } \\
&\quad I({\tilde{Z}};S,T|M_A) < \frac{{\tilde{m}}}{2} + \frac{t_0{\tilde{m}}}{2^{{\tilde{m}}/2}} + u\cdot O(\sqrt{\log n}).
\end{split}$$ By setting $t_0 := \Theta(\sqrt{n\log n})$ and $u := \Theta(\sqrt{n\log n})$, we can make the failure probability exponentially small in $n$.

Hence, for any measurement strategy ${\mathcal{M}}\in {\mathbb{M}}'$, with output $Z$, and any sequence of measurement outcomes $z_{1,\ldots,m}$, we have $$I(Z_{m+1,\ldots,m+{\tilde{m}}}; S,T | Z_{1,\ldots,m}=z_{1,\ldots,m}) < \frac{{\tilde{m}}}{2} + O(\sqrt{n} \log n),$$ and hence $$\label{eq-shrimp3}
I(Z_{m+1,\ldots,m+{\tilde{m}}}; S,T | Z_{1,\ldots,m}) < \frac{{\tilde{m}}}{2} + O(\sqrt{n} \log n).$$

Finally, we consider the remaining steps of the adversary. Using Holevo’s inequality [@NC] (see the proof of Theorem \[thm-flounder\]), we get that $$\label{eq-shrimp4}
I(Z_{m+{\tilde{m}}+1,\ldots,n}; S,T | Z_{1,\ldots,m+{\tilde{m}}}) \leq n-m-{\tilde{m}}.$$

Combining equations (\[eq-shrimp1\]), (\[eq-shrimp3\]) and (\[eq-shrimp4\]), we get that $$\begin{split}
I(Z;S,T) &\leq m\lg(\tfrac{3}{2}) + \lg(O(n\lg n)) + \tfrac{1}{2}{\tilde{m}}+ O(\sqrt{n} \log n) + n-m-{\tilde{m}}\\
&= n - m\lg(\tfrac{4}{3}) - \tfrac{1}{2}{\tilde{m}}+ O(\sqrt{n} \log n).
\end{split}$$ From equations (\[eq-penguin\]), (\[eq-shrimp0\]) and (\[eq-shrimp2\]), we have that $$n \leq \tfrac{k}{1-h(p_e)} + O(\sqrt{n}) \approx (2.5056)k + O(\sqrt{n}),$$ $$m = \lfloor \tfrac{k}{\lg(8/3)} \rfloor \approx \lfloor (0.7067)k \rfloor,$$ $$\begin{split}
{\tilde{m}}&\geq k - m\lg(\tfrac{3}{2}) -\lg(O(n\lg n)) \\
 &\geq k - \tfrac{k\lg(3/2)}{\lg(8/3)} -\lg(O(n\lg n)) \\
 &\approx (0.5866)k -\lg(O(n\lg n)).
\end{split}$$ Combining these bounds, we get that $$I(Z;S,T) \leq (1.9190)k + O(\sqrt{n} \log n),$$ as desired. $\square$

Acknowledgements {#acknowledgements .unnumbered}
----------------

It is a pleasure to thank Anne Broadbent, Daniel Gottesman, Jonathan Katz, Dianne O’Leary, Rene Peralta, Christian Schaffner, Jake Taylor, and Stephanie Wehner, for helpful suggestions about this work. This work is a contribution of NIST, an agency of the US government, and is not subject to US copyright laws.

[99]{} S. Goldwasser, Y.T. Kalai and G.N. Rothblum, “One-Time Programs,” *CRYPTO 2008*, pp.39-56. V. Goyal, Y. Ishai, A. Sahai, R. Venkatesan and A. Wadia, “Founding Cryptography on Tamper-Proof Hardware Tokens,” *TCC 2010*, pp.308-326. M. Bellare, V. T. Hoang and P. Rogaway, “Adaptively Secure Garbling with Applications to One-Time Programs and Secure Outsourcing,” *ASIACRYPT 2012*, pp.134-153. A. Broadbent, G. Gutoski and D. Stebila, “Quantum one-time programs,” arXiv:1211.1080. H.-K. Lo and H.F. Chau, “Is quantum bit commitment really possible?” *Phys. Rev. Lett.* 78, 3410 (1997). H.-K. Lo, “Insecurity of quantum secure computations,” *Phys. Rev. A*, 56(2): 1154-1162 (1997). D. Mayers, “Unconditionally secure quantum bit commitment is impossible,” *Phys. Rev. Lett.*, 78:3414-3417 (1997). H. Buhrman, M. Christandl and C. Schaffner, “Complete Insecurity of Quantum Protocols for Classical Two-Party Computation,” *Phys. Rev. Lett.* 109, 160501 (2012). L. Salvail, “Quantum Bit Commitment from a Physical Assumption,” *CRYPTO 1998*, pp.338-353. I. Damgaard, S. Fehr, L. Salvail and C. Schaffner, “Cryptography In the Bounded Quantum-Storage Model,” *FOCS 2005*, pp.449-458. R. Koenig and B.M. Terhal, “The Bounded Storage Model in the Presence of a Quantum Adversary,” *IEEE Trans. Inf. Th.*, vol. 54, no. 2 (2008). I. Damgaard, S. Fehr, L. Salvail and C. Schaffner, “Secure Identification and QKD in the Bounded-Quantum-Storage Model,” *CRYPTO 2007*, pp.342-359. S. Wehner, C. Schaffner and B. Terhal, “Cryptography from Noisy Storage,” *Phys. Rev. Lett.* 100, 220502 (2008). I. Damgard, S. Fehr, R. Renner, L. Salvail and C. Schaffner, “A Tight High-Order Entropic Quantum Uncertainty Relation with Applications,” *CRYPTO 2007*, pp.360-378. N. J. Bouman, S. Fehr, C. Gonzalez-Guillen and C. Schaffner, “An All-But-One Entropic Uncertainty Relation, and Application to Password-Based Identification,” *TQC 2012*, pp.29-44. S. Wiesner, “Conjugate coding,” *ACM SIGACT News*, Volume 15, Issue 1, 1983, pp.78-88. C.H. Bennett, D.P. DiVincenzo, C.A. Fuchs, T. Mor, E. Rains, P.W. Shor, J.A. Smolin and W.K. Wootters, “Quantum nonlocality without entanglement,” *Phys. Rev. A* 59, pp.1070–1091 (1999). A.M. Childs, D. Leung, L. Mancinska and M. Ozols, “A framework for bounding nonlocality of state discrimination,” arXiv:1206.5822. D.P. DiVincenzo, D.W. Leung and B.M. Terhal, “Quantum Data Hiding,” *IEEE Trans. Inf. Theory*, Vol. 48, No. 3, pp.580-599 (2002). T. Eggeling and R. F. Werner, “Hiding Classical Data in Multipartite Quantum States,” *Phys. Rev. Lett.* 89, 097905 (2002). D.P. DiVincenzo, P. Hayden and B.M. Terhal, “Hiding Quantum Data,” *Found. Phys.* 33(11), pp.1629-1647, 2003. P. Hayden, D. Leung and G. Smith, “Multiparty data hiding of quantum information,” *Phys. Rev. A* 71, 062339 (2005). M. Talagrand, “Majorizing measures: the generic chaining,” *Ann. Probab.*, Vol. 24, No. 3 (1996), pp.1049-1103. F. Jelezko and J. Wrachtrup, “Single defect centres in diamond: A review,” *Physica Status Solidi (A)*, Volume 203, Issue 13, pp. 3207-3225, Oct. 2006. H. Bernien, B. Hensen, W. Pfaff, G. Koolstra, M. S. Blok, L. Robledo, T. H. Taminiau, M. Markham, D. J. Twitchen, L. Childress and R. Hanson, “Heralded entanglement between solid-state qubits separated by 3 meters,” *Nature* 497, pp.86-90 (2013). F. Pastawski, N. Y. Yao, L. Jiang, M. D. Lukin and J. I. Cirac, “Unforgeable Noise-Tolerant Quantum Tokens,” *Proc. Nat. Acad. Sci.* 109, 16079-16082 (2012). J. Walgate, A.J. Short, L. Hardy and V. Vedral, “Local Distinguishability of Multipartite Orthogonal Quantum States,” *Phys. Rev. Lett.* 85, 4972 (2000). P.-X. Chen and C.-Z. Li, “Orthogonality and distinguishability: Criterion for local distinguishability of arbitrary orthogonal states,” *Phys. Rev. A* 68, 062107 (2003). J. Walgate and A.J. Scott, “Generic local distinguishability and completely entangled subspaces,” *J. Phys. A* 41, 375305 (2008). A. Akavia, S. Goldwasser and V. Vaikuntanathan, “Simultaneous Hardcore Bits and Cryptography against Memory Attacks,” *TCC 2009*, pp.474-495. P. Hausladen and W. Wootters, “A ‘pretty good’ measurement for distinguishing quantum states,” *J. Mod. Opt.* 41, pp.2385 (1994). A. Montanaro, “On the distinguishability of random quantum states,” *Comm. Math. Phys.* 273(3), pp. 619-636, 2007. M.A. Nielsen and I.L. Chuang, *Quantum Computation and Quantum Information*, Cambridge University Press, 2000. H. Maassen and J. Uffink, *Phys. Rev. Lett.*, Vol. 60, pp.1103 (1988). S. Wehner and A. Winter, “Entropic uncertainty relations - A survey,” *New J. Phys.*, Vol. 12, 025009 (2010). J.A. Tropp, “User-Friendly Tools for Random Matrices: An Introduction,” manuscript, 2012, http://users.cms.caltech.edu/$\sim$jtropp/notes/Tro12-User-Friendly-Tools-NIPS.pdf. D.P. Dubhashi and A. Panconesi, *Concentration of Measure for the Analysis of Randomized Algorithms*, Cambridge University Press, 2009. A. Winter, “Coding theorem and strong converse for quantum channels,” *IEEE Trans. Inform. Theory* 45(7), pp.2481-2485 (1999). D. Welsh, *Codes and Cryptography*, Oxford University Press, 1988. S. Janson, “Large Deviations for Sums of Partly Dependent Random Variables,” *Random Struct. Alg.*, Vol. 24, pp.234-248, 2004.

Facts about LOCC measurement strategies {#app-locc-epsnet}
=======================================

(restatement of Lemma \[lem-locc-rank1\]) Let ${\mathcal{M}}$ be any 1-pass LOCC strategy in the isolated qubits model, which uses $q$-outcome measurements and returns output $Z$. Then there exists ${\mathcal{M}}'$, a 1-pass LOCC strategy in the isolated qubits model, which uses $q$-outcome measurements and returns output $Z'$, and has the following additional properties:

1.  $I(Z';U) \geq I(Z;U)$ (when playing the state discrimination game shown above).

2.  In every measurement performed by ${\mathcal{M}}'$, the POVM elements all have rank 1.

Proof: We will construct the strategy ${\mathcal{M}}'$ as follows. Consider what the strategy ${\mathcal{M}}$ does at step $a$, given some prior history $z_{<a}$. Any POVM element $M_a(z_{<a},\zeta)$ that has rank $>1$ can be written in the form $\alpha I + \beta {{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}}$, where $\alpha>0$, $\beta \geq 0$. We now construct a new POVM measurement, by replacing $M_a(z_{<a},\zeta)$ with two operators $\alpha I$ and $\beta {{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}}$. This new measurement can simulate the original measurement, by identifying the measurement outcomes $\alpha I$ and $\beta {{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}}$ with the original measurement outcome $\zeta$.

In this way, one can replace each measurement in ${\mathcal{M}}$ with a measurement that consists of at most $q$ POVM elements that have rank 1, and at most $q$ POVM elements that are multiples of $I$. This strategy is equivalent to a probabilistic mixture of strategies, where each strategy uses measurements with at most $q$ POVM elements, each of which has rank 1. By convexity of the mutual information $I(Z;U)$ (as a function of the conditional distribution $\Pr[Z=z|U=u]$, keeping the marginal distribution $\Pr[U=u]$ fixed), there must be a pure strategy ${\mathcal{M}}'$ that achieves $I(Z';U) \geq I(Z;U)$, and uses measurements with at most $q$ POVM elements, each of which has rank 1. $\square$

(restatement of Lemma \[lem-epsnet-2\]) Let $q = 2$. For any $0 < {\varepsilon}\leq 1$, there exists an ${\varepsilon}$-net $L$ for ${\mathcal{S}}$, with respect to the metric $t$, that has cardinality $|L| \leq C/{\varepsilon}^2$ (where $C$ is some numerical constant). Equivalently, we have $N({\mathcal{S}},t,{\varepsilon}) \leq C/{\varepsilon}^2$.

Proof: When $q = 2$, we can write the set ${\mathcal{S}}$ and the metric $t$ in a simpler form: $${\mathcal{S}}= {{\lbrace{({{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}}, I-{{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}}) \text{ s.t. } {{\left| \varphi \right\rangle}} \in {\mathbb{C}}^2, \; {{\left\langle \varphi \middle| \varphi \right\rangle}} = 1}\rbrace}},$$ $$t\bigl(({{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}}, I-{{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}}), ({{\left| \theta \right\rangle}}{{\left\langle \theta \right|}}, I-{{\left| \theta \right\rangle}}{{\left\langle \theta \right|}})\bigr) = {{\lVert {{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}} - {{\left| \theta \right\rangle}}{{\left\langle \theta \right|}} \rVert}}.$$ Let ${\mathcal{B}}:= {{\lbrace{{{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}} \text{ s.t. } {{\left| \varphi \right\rangle}} \in {\mathbb{C}}^2, \; {{\left\langle \varphi \middle| \varphi \right\rangle}} = 1}\rbrace}}$, and note that $$N({\mathcal{S}},t,{\varepsilon}) \leq N({\mathcal{B}},{{\lVert \cdot \rVert}},{\varepsilon}).$$ It follows from standard arguments [^9] that $N({\mathcal{B}}, {{\lVert \cdot \rVert}}, {\varepsilon}) \leq O(1/{\varepsilon}^2)$. $\square$

(restatement of Lemma \[lem-epsnet-q\]) Let $q \geq 2$. For any $0 < {\varepsilon}\leq 1$, there exists an ${\varepsilon}$-net $L$ for ${\mathcal{S}}$, with respect to the metric $t$, that has cardinality $|L| \leq (C/{\varepsilon})^{3q}$ (where $C$ is some numerical constant). Equivalently, we have $N({\mathcal{S}},t,{\varepsilon}) \leq (C/{\varepsilon})^{3q}$.

Proof: Observe that ${\mathcal{S}}\subset ({\mathcal{S}}'_1)^q$, where ${\mathcal{S}}'_1 := {{\lbrace{M \in {\mathbb{C}}^{2\times 2} \;|\; 0 \preceq M \preceq I, \; \operatorname{rank}(M) = 1}\rbrace}}$. This implies: [^10] $$N({\mathcal{S}},t,{\varepsilon}) \leq N({\mathcal{S}}'_1, {{\lVert \cdot \rVert}}, {\varepsilon}/2)^q.$$

Next, let ${\mathcal{B}}:= {{\lbrace{{{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}} \text{ s.t. } {{\left| \varphi \right\rangle}} \in {\mathbb{C}}^2, \; {{\left\langle \varphi \middle| \varphi \right\rangle}} = 1}\rbrace}}$. Note that we can write ${\mathcal{S}}'_1 = {{\lbrace{\lambda M \;|\; \lambda \in [0,1], \; M \in {\mathcal{B}}}\rbrace}}$. This implies: [^11] $$N({\mathcal{S}}'_1, {{\lVert \cdot \rVert}}, {\varepsilon}/2) \leq N([0,1], {{\lvert \cdot \rvert}}, {\varepsilon}/4) N({\mathcal{B}}, {{\lVert \cdot \rVert}}, {\varepsilon}/4).$$

It is easy to see that $N([0,1], {{\lvert \cdot \rvert}}, {\varepsilon}/4) \leq O(1/{\varepsilon})$, and it follows from standard arguments [^12] that $N({\mathcal{B}}, {{\lVert \cdot \rVert}}, {\varepsilon}/4) \leq O(1/{\varepsilon}^2)$. $\square$

Let ${\mathcal{M}}$ be any 1-pass LOCC strategy in the isolated qubits model, which uses $q$-outcome measurements, where all POVM elements have rank 1, and which has output $Z$. Fix some $0 < {\varepsilon}\leq 1/(qne)$, and let $L$ be the ${\varepsilon}$-net for ${\mathcal{S}}$ defined above. Let ${\mathcal{M}}'$ be the strategy that is obtained by duplicating the strategy ${\mathcal{M}}$, and replacing each measurement $M \in {\mathcal{S}}$ with the best approximating measurement $\tilde{M} \in L$. Let $Z'$ be the output of the strategy ${\mathcal{M}}'$. Then $${{\lvert I(Z';U) - I(Z;U) \rvert}} \leq 2qn^2{\varepsilon}+ 2\eta(qn{\varepsilon}),$$ where $\eta(x) := -x\lg x$.

Proof: For any $u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$, let $Z|_{U=u}$ be the random variable $Z$ conditioned on the event $U=u$; define $Z'|_{U=u}$ similarly. We will show that $Z|_{U=u}$ and $Z'|_{U=u}$ have nearly the same distribution, compared using total variation distance (denoted $\Delta(\cdot,\cdot)$). To see this, let us define a sequence of strategies that interpolate between ${\mathcal{M}}$ and ${\mathcal{M}}'$. For $a=0,1,2,\ldots,n$, we define a strategy ${\mathcal{M}}^{(a)}$ (whose output is denoted $Z^{(a)}$) that does the same measurements as ${\mathcal{M}}'$ for steps $1,2,\ldots,a$, and does the same measurements as ${\mathcal{M}}$ for steps $a+1,a+2,\ldots,n$. Note that ${\mathcal{M}}^{(0)} = {\mathcal{M}}$ and ${\mathcal{M}}^{(n)} = {\mathcal{M}}'$, and we have $$\Delta(Z|_{U=u}, Z'|_{U=u}) \leq \sum_{a=0}^{n-1} \Delta(Z^{(a)}|_{U=u}, Z^{(a+1)}|_{U=u}).$$

We now want to bound $$\Delta(Z^{(a)}|_{U=u}, Z^{(a+1)}|_{U=u}) = \sum_{z \in [q]^n} {{\lvert \Pr[Z^{(a)}=z|U=u] - \Pr[Z^{(a+1)}=z|U=u] \rvert}}.$$ The state of the $n$ qubits is given by ${{\left| E(u) \right\rangle}} = {\bigotimes}_{a=1}^n {{\left| \alpha_{E(u)_a} \right\rangle}}$; to simplify notation, let us call this state ${{\left| \psi \right\rangle}} = {\bigotimes}_{a=1}^n {{\left| \psi_a \right\rangle}}$. We will use the following notation: the strategy ${\mathcal{M}}$ is described by POVM elements $M_i(z_{\leq i})$, with the choice of which qubit to measure next being specified by $Q_i(z_{<i})$; the strategy ${\mathcal{M}}'$ is described by slightly different POVM elements $M'_i(z_{\leq i})$, and the same qubit choices $Q_i(z_{<i})$. Then we can write $$\Pr[Z^{(a)}=z|U=u] = \prod_{i=1}^a {{\left\langle \psi_{Q_i(z_{<i})} \right|}} M'_i(z_{\leq i}) {{\left| \psi_{Q_i(z_{<i})} \right\rangle}} \cdot 
\prod_{i=a+1}^n {{\left\langle \psi_{Q_i(z_{<i})} \right|}} M_i(z_{\leq i}) {{\left| \psi_{Q_i(z_{<i})} \right\rangle}}.$$ Hence $$\begin{split}
\Delta(Z^{(a)}|_{U=u}, Z^{(a+1)}|_{U=u})
 = \sum_{z \in [q]^n} 
&\prod_{i=1}^a {{\left\langle \psi_{Q_i(z_{<i})} \right|}} M'_i(z_{\leq i}) {{\left| \psi_{Q_i(z_{<i})} \right\rangle}} \cdot \\
&\Bigl\lvert {{\left\langle \psi_{Q_{a+1}(z_{<a+1})} \right|}} \bigl[ M_{a+1}(z_{\leq a+1}) - M'_{a+1}(z_{\leq a+1}) \bigr] {{\left| \psi_{Q_{a+1}(z_{<a+1})} \right\rangle}} \Bigr\rvert \cdot \\
&\prod_{i=a+2}^n {{\left\langle \psi_{Q_i(z_{<i})} \right|}} M_i(z_{\leq i}) {{\left| \psi_{Q_i(z_{<i})} \right\rangle}}
\end{split}$$ Now we can use the bound ${{\lVert M_{a+1}(z_{\leq a+1}) - M'_{a+1}(z_{\leq a+1}) \rVert}} \leq {\varepsilon}$, and we can evaluate the sum over $z$, using the fact that for any $z_{<i}$, $\sum_{z_i} M_i(z_{\leq i}) = I$ (and similarly for $M'_i(z_{\leq i})$). We get that $$\Delta(Z^{(a)}|_{U=u}, Z^{(a+1)}|_{U=u}) \leq q{\varepsilon},$$ and therefore $$\Delta(Z|_{U=u}, Z'|_{U=u}) \leq qn{\varepsilon},$$ which shows that $Z|_{U=u}$ and $Z'|_{U=u}$ have nearly identical distributions, as desired.

In the remainder of the proof, we will bound the difference between $I(Z;U)$ and $I(Z';U)$. First, using (the classical case of) Fannes’ inequality [@NC], and assuming $qn{\varepsilon}\leq 1/e$, we get that $${{\lvert H(Z|U=u) - H(Z'|U=u) \rvert}} \leq qn^2{\varepsilon}+ \eta(qn{\varepsilon}),$$ where $\eta(x) := -x\lg x$. This implies $${{\lvert H(Z|U) - H(Z'|U) \rvert}}
 = \bigl\lvert 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} (H(Z|U=u) - H(Z'|U=u)) \bigr\rvert
 \leq qn^2{\varepsilon}+ \eta(qn{\varepsilon}).$$ Next, we can bound the total variation distance between $Z$ and $Z'$ as follows: $$\begin{split}
\Delta(Z,Z')  &= \sum_{z\in[q]^n} \bigl\lvert 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} (\Pr[Z=z|U=u] - \Pr[Z'=z|U=u]) \bigr\rvert \\
 &\leq 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} \Delta(Z|_{U=u}, Z'|_{U=u}) \\
 &\leq qn{\varepsilon}.
\end{split}$$ Then, by Fannes’ inequality, $${{\lvert H(Z) - H(Z') \rvert}} \leq qn^2{\varepsilon}+ \eta(qn{\varepsilon}).$$ Combining these bounds, we get $${{\lvert I(Z;U) - I(Z';U) \rvert}} \leq 2qn^2{\varepsilon}+ 2\eta(qn{\varepsilon}),$$ as desired. $\square$

High success probability implies high mutual information {#app-ostrich}
========================================================

Suppose that $\Pr[Z=U] \geq 1-{\varepsilon}$, and ${\varepsilon}$ is sufficiently small that $2\sqrt{{\varepsilon}} + 2^{-{\tilde{n}}} \leq 1/e$. Then $I(Z;U) \geq (1-5\sqrt{{\varepsilon}}) {\tilde{n}}- \eta(2\sqrt{{\varepsilon}})$, where $\eta(x) := -x \lg x$.

Proof: First, we claim that, for most $u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$, $\Pr[Z=u|U=u]$ is close to 1. To see this, suppose $u$ is chosen uniformly at random in ${{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$, and define $\gamma(u) := 1-\Pr[Z=u|U=u]$. Note that $\gamma(u) \geq 0$ and $$\operatorname{\mathbb{E}}_u[\gamma(u)] = 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} (1-\Pr[Z=u|U=u]) = 1-\Pr[Z=U] \leq {\varepsilon}.$$ By Markov’s inequality, for any $C \geq 1$, $\Pr_u[\gamma(u) \geq C{\varepsilon}] \leq \tfrac{1}{C}$. Therefore, there exists a subset $S \subseteq {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$ of size ${{\lvert S \rvert}} \geq 2^{{\tilde{n}}} (1-\tfrac{1}{C})$, such that for all $u \in S$, $$\Pr[Z=u|U=u] > 1-C{\varepsilon}.$$ We need to choose $C$ such that both $\tfrac{1}{C}$ and $C{\varepsilon}$ are small. For concreteness, we set $C = \tfrac{1}{\sqrt{{\varepsilon}}}$, which implies that $\tfrac{1}{C} = \sqrt{{\varepsilon}} = C{\varepsilon}$.

We now show that $H(Z|U)$ is small. We write $H(Z|U) = 2^{-{\tilde{n}}} \sum_{u\in{{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} H(Z|U=u)$, and we upper-bound $H(Z|U=u)$. First, consider the case where $u \in S$. We bound the total-variation distance between the random variables $Z|_{U=u}$ and $U|_{U=u}$ as follows: (note that $U|_{U=u}$ equals $u$ with probability 1) $$\begin{split}
\Delta(Z|_{U=u},U|_{U=u}) &= {{\lvert \Pr[Z=u|U=u]-1 \rvert}} + \sum_{z\neq u} {{\lvert \Pr[Z=z|U=u]-0 \rvert}} \\
 &= 1 - \Pr[Z=u|U=u] + \Pr[Z\neq u|U=u] \\
 &= 2(1-\Pr[Z=u|U=u]) \\
 &< 2C{\varepsilon}= 2\sqrt{{\varepsilon}}.
\end{split}$$ Using Fannes’ inequality [@NC] (note that $2\sqrt{{\varepsilon}} \leq 1/e$), we get that $$H(Z|U=u) = {{\lvert H(Z|U=u) - H(U|U=u) \rvert}} \leq 2\sqrt{{\varepsilon}} \cdot {\tilde{n}}+ \eta(2\sqrt{{\varepsilon}}).$$ Next, consider the case where $u \notin S$. Here we use the trivial bound, $H(Z|U=u) \leq {\tilde{n}}$. We now bound $H(Z|U)$ as follows: $$H(Z|U) \leq 2^{-{\tilde{n}}} {{\lvert S \rvert}} (2\sqrt{{\varepsilon}} \cdot {\tilde{n}}+ \eta(2\sqrt{{\varepsilon}})) + 2^{-{\tilde{n}}} {{\lvert S^c \rvert}} {\tilde{n}}.$$ The right-hand side is largest when ${{\lvert S \rvert}} = 2^{{\tilde{n}}}(1-\sqrt{{\varepsilon}})$, so we get $$\label{eq-minnow-1}
\begin{split}
H(Z|U) &\leq (1-\sqrt{{\varepsilon}}) (2\sqrt{{\varepsilon}} \cdot {\tilde{n}}+ \eta(2\sqrt{{\varepsilon}})) + \sqrt{{\varepsilon}} \cdot {\tilde{n}}\\
 &< 3\sqrt{{\varepsilon}} \cdot {\tilde{n}}+ \eta(2\sqrt{{\varepsilon}}).
\end{split}$$

Next, we observe that, for most $z \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}$, $\Pr[Z=z]$ is not much smaller than $2^{-{\tilde{n}}}$. More precisely, for all $z \in S$, we have a lower bound: $$\Pr[Z=z] \geq 2^{-{\tilde{n}}} \Pr[Z=z|U=z] > 2^{-{\tilde{n}}} (1-\sqrt{{\varepsilon}}).$$ We also show a (loose) upper-bound on $\Pr[Z=z]$, when $z \in S$, as follows: $$\begin{split}
\Pr[Z=z] &= 2^{-{\tilde{n}}} \sum_{u \in {{\lbrace{0,1}\rbrace}}^{{\tilde{n}}}} \Pr[Z=z|U=u] \\
 &\leq 2^{-{\tilde{n}}} {{\lvert S\setminus{{\lbrace{z}\rbrace}} \rvert}} \sqrt{{\varepsilon}} + 2^{-{\tilde{n}}} + 2^{-{\tilde{n}}} {{\lvert S^c \rvert}}
\end{split}$$ The right-hand side is largest when ${{\lvert S \rvert}} = 2^{{\tilde{n}}}(1-\sqrt{{\varepsilon}})$, so we get $$\begin{split}
\Pr[Z=z] &< (1-\sqrt{{\varepsilon}}) \sqrt{{\varepsilon}} + 2^{-{\tilde{n}}} + \sqrt{{\varepsilon}} \\
 &< 2\sqrt{{\varepsilon}} + 2^{-{\tilde{n}}}.
\end{split}$$

Finally, we will show that $H(Z)$ is large. First, we write $$H(Z) \geq \sum_{z\in S} \eta(\Pr[Z=z]).$$ Note that $\eta(x) := -x \lg x$ is increasing on the interval $[0,1/e]$. From the previous paragraph, we know that for all $z \in S$, we have $2^{-{\tilde{n}}} (1-\sqrt{{\varepsilon}}) < \Pr[Z=z] < 2\sqrt{{\varepsilon}} + 2^{-{\tilde{n}}} < 1/e$. So we can write $$\label{eq-minnow-2}
\begin{split}
H(Z) &\geq \sum_{z\in S} \eta(2^{-{\tilde{n}}} (1-\sqrt{{\varepsilon}})) \\
 &= {{\lvert S \rvert}} 2^{-{\tilde{n}}} (1-\sqrt{{\varepsilon}}) (-1) \lg(2^{-{\tilde{n}}} (1-\sqrt{{\varepsilon}})) \\
 &\geq (1-\sqrt{{\varepsilon}})^2 ({\tilde{n}}- \lg(1-\sqrt{{\varepsilon}})) \\
 &> (1-2\sqrt{{\varepsilon}}) {\tilde{n}}.
\end{split}$$

Finally, we combine equations (\[eq-minnow-1\]) and (\[eq-minnow-2\]) to get the desired lower bound on $I(Z;U) = H(Z) - H(Z|U)$. $\square$

Entropy chaining {#app-entropy-chaining}
================

We prove a variant of Dudley’s inequality, for bounding the expected supremum of a family of correlated random variables, $\operatorname{\mathbb{E}}\sup_t X_t$, using entropy chaining. Our claim is a slight generalization of the usual statement of Dudley’s inequality, in that it allows the random variables $X_t$ to have different means; also, we state our result as a tail bound on $\sup_t X_t$, which is stronger than the usual form of Dudley’s inequality. Nonetheless, the proof is more or less the same as the usual one; see, e.g., [@talagrand].

\[lem-dudley\] Let ${{\lbrace{X_t \;|\; t\in T}\rbrace}}$ be a family of random variables taking values in ${\mathbb{R}}$. Define $\mu_t := \operatorname{\mathbb{E}}X_t$.

Let $d(\cdot,\cdot)$ be a metric on the set $T$, such that the following “increment condition” holds: $$\label{dudley-increment}
\Pr[X_s - X_t - \mu_s + \mu_t > u] \leq \exp(-u^2 / d(s,t)^2), \quad \forall s,t\in T, \quad \forall u>0.$$ (Note that, by exchanging $s$ and $t$, this also implies a similar bound on the lower tail of $X_s - X_t$.) Also, suppose that, for any sequence $s_1,s_2,s_3,\ldots \in T$, and any $t \in T$, if $\lim_{j\rightarrow\infty} d(s_j,t) = 0$, then $\lim_{j\rightarrow\infty} \mu_{s_j} = \mu_t$.

Suppose there exist $t_0 \in T$ and $\delta,{\varepsilon}> 0$, such that $Pr[X_{t_0} - \mu_{t_0} > \delta] \leq {\varepsilon}$. Then we have the following bound: $$\label{dudley-upper-tail}
\Pr[\sup_t (X_t - \mu_t) > \delta + uS] \leq {\varepsilon}+ 2\cdot 2^{-u^2}, \quad \forall u\geq 1,$$ where $$\label{dudley-S}
S \leq C_0 \int_0^\infty \sqrt{\log N(T,d,{\varepsilon})} d{\varepsilon},$$ $C_0$ is a numerical constant, and $N(T,d,{\varepsilon})$ is the covering number, i.e., the minimum cardinality of an ${\varepsilon}$-net for the set $T$ with respect to the metric $d(\cdot,\cdot)$.

By applying the same argument to the random variables ${{\lbrace{-X_t \;|\; t\in T}\rbrace}}$, we also have a lower bound. Suppose there exist $t_0 \in T$ and $\delta,{\varepsilon}> 0$, such that $Pr[X_{t_0} - \mu_{t_0} < -\delta] \leq {\varepsilon}$. Then: $$\label{dudley-lower-tail}
\Pr[\inf_t (X_t - \mu_t) < -\delta - uS] \leq {\varepsilon}+ 2\cdot 2^{-u^2}, \quad \forall u\geq 1.$$

Proof: We use a standard entropy chaining argument [@talagrand]. Fix some $r \geq 2$, and choose some integer $j_0$ such that $r^{-(j_0+1)} < \text{diam}(T) \leq r^{-j_0}$. For all $j \geq j_0$, we will construct sets $\Pi_j \subset T$ and maps $\pi_j:\; T \rightarrow \Pi_j$ that have the following properties: $$\label{dudley-ppty1}
\pi_{j_0}(t) = t_0, \quad \forall t\in T,$$ $$\label{dudley-ppty2}
\lim_{j\rightarrow\infty} d(\pi_j(t), t) = 0, \quad \forall t\in T,$$ $$\label{dudley-ppty3}
d(\pi_j(t), \pi_{j-1}(t)) \leq 2r^{-(j-1)}, \quad \forall t\in T, \quad \forall j\geq j_0+1.$$ (Intuitively, for each $t\in T$, the sequence of points ${{\lbrace{\pi_j(t) \;|\; j=j_0, j_0+1, j_0+2, \ldots}\rbrace}}$ starts at $t_0$ and quickly converges to $t$.) Also note that equation (\[dudley-ppty2\]) implies that $$\label{dudley-ppty4}
\lim_{j\rightarrow\infty} \mu_{\pi_j(t)} = \mu_t, \quad \forall t\in T,$$

We will construct the sets $\Pi_j$ and maps $\pi_j$ later. In the mean time, note that $$X_t - X_{t_0} = \sum_{j\geq j_0+1} X_{\pi_j(t)} - X_{\pi_{j-1}(t)},$$ $$\mu_t - \mu_{t_0} = \sum_{j\geq j_0+1} \mu_{\pi_j(t)} - \mu_{\pi_{j-1}(t)}.$$ Fix any real numbers $a_j > 0$ (for all $j\geq j_0+1$). (We will choose values for the $a_j$ later.) Define $S := \sum_{j\geq j_0+1} a_j$, and fix any $u>0$. Note that, for any $t\in T$, if $$X_{\pi_j(t)} - X_{\pi_{j-1}(t)} \leq \mu_{\pi_j(t)} - \mu_{\pi_{j-1}(t)} + ua_j, \quad \forall j\geq j_0+1,$$ then $X_t - X_{t_0} \leq \mu_t - \mu_{t_0} + uS$. Moreover, using the increment condition (\[dudley-increment\]), we have that $$\Pr[X_{\pi_j(t)} - X_{\pi_{j-1}(t)} > \mu_{\pi_j(t)} - \mu_{\pi_{j-1}(t)} + ua_j]
\leq \exp(-u^2 a_j^2 / (2r^{-(j-1)})^2).$$ Hence, using the union bound, we get that $$\begin{split}
\Pr[\exists t\in T &\text{ s.t. } X_t - X_{t_0} > \mu_t - \mu_{t_0} + uS] \\
&\leq \Pr[\exists t\in T, \; \exists j\geq j_0+1, \text{ s.t. } X_{\pi_j(t)} - X_{\pi_{j-1}(t)} > \mu_{\pi_j(t)} - \mu_{\pi_{j-1}(t)} + ua_j] \\
&\leq \sum_{j\geq j_0+1} |\Pi_j| |\Pi_{j-1}| \exp(-u^2 a_j^2 / (2r^{-(j-1)})^2).
\end{split}$$

Now set $a_j := 2r^{-(j-1)} \sqrt{\log(2^{j-j_0} |\Pi_j| |\Pi_{j-1}|)}$, and assume that $u^2 \geq 1$. Then we have $$\begin{split}
\Pr[\exists t\in T &\text{ s.t. } X_t - X_{t_0} > \mu_t - \mu_{t_0} + uS] \\
&\leq \sum_{j\geq j_0+1} |\Pi_j| |\Pi_{j-1}| (2^{j-j_0} |\Pi_j| |\Pi_{j-1}|)^{-u^2} \\
&\leq \sum_{j\geq j_0+1} 2^{-(j-j_0) u^2} = 2^{-u^2} \sum_{a=0}^\infty 2^{-au^2} \\
&\leq 2^{-u^2} \sum_{a=0}^\infty 2^{-a} < 2\cdot 2^{-u^2}.
\end{split}$$ We can rewrite this as $\Pr[\sup_{t\in T} (X_t - \mu_t) > X_{t_0} - \mu_{t_0} + uS] < 2\cdot 2^{-u^2}$. This now implies the claimed bound (\[dudley-upper-tail\]); and by applying the same argument to the random variables ${{\lbrace{-X_t \;|\; t\in T}\rbrace}}$, we also get the bound (\[dudley-lower-tail\]).

It remains to construct the sets $\Pi_j$ and maps $\pi_j$, and prove the upper bound on $S$ shown in (\[dudley-S\]). For each $j\geq j_0$, we choose the set $\Pi_j$ to be an ${\varepsilon}$-net for the set $T$, with ${\varepsilon}= r^{-j}$, and with respect to the metric $d(\cdot,\cdot)$. In particular, we choose $\Pi_j$ to be an ${\varepsilon}$-net of minimum cardinality, so that $|\Pi_j| = N(T,d,r^{-j})$. For notational convenience, we define $N_j := |\Pi_j|$. In the case of $j=j_0$, we let $\Pi_{j_0} = {{\lbrace{t_0}\rbrace}}$, recalling that $\text{diam}(T) \leq r^{-j_0}$. We define $\pi_j$ to be the map that, given any point $t\in T$, returns the nearest point in $\Pi_j$; hence, $d(\pi_j(t), t) \leq r^{-j}$. Note that equations (\[dudley-ppty1\]) and (\[dudley-ppty2\]) are satisfied, and (\[dudley-ppty3\]) follows from the triangle inequality.

We upper-bound $S$ as follows: $$\begin{split}
S &= \sum_{j\geq j_0+1} a_j = \sum_{j\geq j_0+1} 2r^{-(j-1)} \sqrt{\log(2^{j-j_0} N_j N_{j-1})} \\
&\leq \sum_{j\geq j_0+1} 2r^{-(j-1)} \Bigl( \sqrt{(j-j_0)\log2} + \sqrt{\log N_j} + \sqrt{\log N_{j-1}} \Bigr) \\
&\leq r^{-j_0} \sum_{j=1}^\infty 2r^{-(j-1)} \sqrt{j\log2} + (r+1) \sum_{j\geq j_0} 2r^{-j} \sqrt{\log N_j} \\
&= r^{-j_0} K(r) + (r+1) \sum_{j\geq j_0} 2r^{-j} \sqrt{\log N_j}, 
\end{split}$$ where we used the fact that $\sqrt{a+b} \leq \sqrt{a} + \sqrt{b}$ (for all $a,b \geq 0$), and we defined $K(r) := \sum_{j=1}^\infty 2r^{-(j-1)} \sqrt{j\log2}$. Next, recall that $\text{diam}(T) > r^{-(j_0+1)} \geq 2r^{-(j_0+2)}$, and hence $N_{j_0+2} \geq 2$. So we can write $$S \leq \biggl( \frac{r^2 K(r)}{2\sqrt{\log2}} + r+1 \biggr) \sum_{j\geq j_0} 2r^{-j} \sqrt{\log N_j}.$$ We will now replace the sum on the right hand side by an integral. Note that, for any ${\varepsilon}\leq r^{-j}$, we have $N(T,d,{\varepsilon}) \geq N_j$. So we can write $$\int_{r^{-(j+1)}}^{r^{-j}} \sqrt{\log N(T,d,{\varepsilon})} d{\varepsilon}\geq (1-\tfrac{1}{r}) r^{-j} \sqrt{\log N_j},$$ and hence $$S \leq \biggl( \frac{r^2 K(r)}{2\sqrt{\log2}} + r+1 \biggr) \cdot 2 (1-\tfrac{1}{r})^{-1} 
\int_0^{r^{-j_0}} \sqrt{\log N(T,d,{\varepsilon})} d{\varepsilon}.$$ Note that we can extend the integral over the interval $[0,\infty)$ without weakening the bound; for when ${\varepsilon}\geq r^{-j_0}$, we have $N(T,d,{\varepsilon}) = 1$, hence $\sqrt{\log N(T,d,{\varepsilon})} = 0$. Now set $r\geq 2$ to be some numerical constant. This proves equation (\[dudley-S\]). $\square$

Shannon’s noisy coding theorem {#app-noisy-coding}
==============================

(restatement of Prop. \[prop-sea-cucumber\]) Fix any constants $\lambda \geq 1$, $0 < \tau \leq \tfrac{1}{2} - p_e \approx 0.3536$, and $\theta > \tau h'(p_e) \approx (2.5431) \tau$. Then for all sufficiently large $n$, the following statement holds: with probability $\geq 1-\tfrac{1}{\lambda}$ (over the choice of $C$), we have $$\Pr[{\hat{S}}=S] \geq 1 - \lambda \bigl[ e^{-2\tau^2 n} + 2^{-n (\theta - \tau h'(p_e))} \bigr]
\geq 1 - \lambda e^{-\Omega(n)}.$$

Proof: We can view $\Pr[{\hat{S}}\neq S]$ as a random variable depending on the choice of the random code $C$. We then calculate $\operatorname{\mathbb{E}}_C \Pr[{\hat{S}}\neq S]$.

We can upper-bound $\Pr[{\hat{S}}\neq S]$ as follows: $$\Pr[{\hat{S}}\neq S]
\leq \Pr[d_H(C(S),Z) > r] + \Pr[d_H(C(S),Z) \leq r \text{ and } \exists t\in {{\lbrace{0,1}\rbrace}}^k \text{ s.t. } t\neq S, \; d_H(C(t),Z) \leq r].$$ Let $N_e$ be the number of errors introduced by the channel $BSC(p_e)$, acting independently on the $n$ bits of the string $C(S)$. Then $N_e = d_H(C(S),Z)$, $\operatorname{\mathbb{E}}N_e = np_e$, and by Hoeffding’s inequality, $\Pr[N_e > r] \leq e^{-2\tau^2 n}$. So we have $$\label{eq-bat}
\begin{split}
\Pr[{\hat{S}}\neq S]
&\leq e^{-2\tau^2 n} + \Pr[\exists t\in {{\lbrace{0,1}\rbrace}}^k \text{ s.t. } t\neq S, \; d_H(C(t),Z) \leq r] \\
&= e^{-2\tau^2 n} + 2^{-k} \sum_{s\in{{\lbrace{0,1}\rbrace}}^k} \Pr[\exists t\in {{\lbrace{0,1}\rbrace}}^k \text{ s.t. } t\neq S, \; d_H(C(t),Z) \leq r | S=s] \\
&\leq e^{-2\tau^2 n} + 2^{-k} \sum_{s\in{{\lbrace{0,1}\rbrace}}^k} \sum_{t\in {{\lbrace{0,1}\rbrace}}^k \setminus {{\lbrace{s}\rbrace}}} \Pr[d_H(C(t),Z) \leq r | S=s] \\
&= e^{-2\tau^2 n} + 2^{-k} \sum_{s\in{{\lbrace{0,1}\rbrace}}^k} \sum_{t\in {{\lbrace{0,1}\rbrace}}^k \setminus {{\lbrace{s}\rbrace}}} \sum_{z\in{{\lbrace{0,1}\rbrace}}^n} 1[d_H(C(t),z) \leq r] \Pr[Z=z | S=s]. \\
\end{split}$$

We now bound $\operatorname{\mathbb{E}}_C \Pr[{\hat{S}}\neq S]$, taking the expectation over the choice of the random code $C$. Note that $$\operatorname{\mathbb{E}}_C \bigl[ 1[d_H(C(t),z) \leq r] \Pr[Z=z | S=s] \bigr]
= \operatorname{\mathbb{E}}_C \bigl[ 1[d_H(C(t),z) \leq r] \bigr] \operatorname{\mathbb{E}}_C\bigl[ \Pr[Z=z | S=s] \bigr],$$ since $C(s)$ and $C(t)$ are independent random variables (since $s\neq t$). We have the following bound: $$\operatorname{\mathbb{E}}_C[ 1[d_H(C(t),z) \leq r] ] = \Pr_C[d_H(C(t),z) \leq r]
= 2^{-n} \sum_{a=0}^{\lfloor r \rfloor} \tbinom{n}{a}
\leq 2^{-n} 2^{nh(r/n)},$$ where we used a tail inequality from [@welsh p.39] (note that $r \leq n/2$, since $\tau \leq \tfrac{1}{2} - p_e$). Hence, plugging into (\[eq-bat\]), we get that $$\operatorname{\mathbb{E}}_C \Pr[{\hat{S}}\neq S] \leq e^{-2\tau^2 n} + 2^k 2^{-n(1-h(r/n))}.$$

Note that $h$ is a concave function, so it satisfies the linear upper-bound $h(r/n) = h(p_e + \tau) \leq h(p_e) + \tau h'(p_e)$, where $h'(p_e) \approx 2.5431$. Plugging this in, and using equation (\[eq-penguin\]), we get that $$\begin{split}
\operatorname{\mathbb{E}}_C \Pr[{\hat{S}}\neq S] &\leq e^{-2\tau^2 n} + 2^k 2^{-n(1-h(p_e)-\tau h'(p_e))} \\
 &= e^{-2\tau^2 n} + 2^{-n\theta} 2^{n\tau h'(p_e)} \\
 &\leq e^{-\Omega(n)}.
\end{split}$$ We then use Markov’s inequality to get the desired result. $\square$

[^1]: A one-time program is a package of hardware and software that is prepared by Alice and given to Bob. It can compute a function $f$ (chosen by Alice when she prepares the package) on a single input $x$ provided by Bob (when he runs the package). During its execution, the one-time program behaves like a black box, i.e., Bob learns nothing about its internal functioning. After running once, the one-time program “self-destructs,” i.e., it stops functioning, and no more information can be extracted from it.

[^2]: More precisely, the difference is that OTM’s are asynchronous, in the sense that there is only one message from Alice to Bob. In contrast, most other protocols (even those that only require one-way communication rather than two-way interaction [@tight-eur]) still use a sequence of two messages from Alice to Bob, in such a way that any dishonest action occurs before the second message, so that the second message can be used to perform privacy amplification. A notable exception is the recent work [@all-but-one], which considers a situation that is fully asynchronous, with a non-adaptive adversary.

[^3]: Formally, we upper-bound the Shannon mutual information.

[^4]: Let ${{\left| \alpha_{C(s)_i D(t)_i} \right\rangle}}$ be the state used to encode $C(s)_i$ and $D(t)_i$ into qubit $i$ (see Section 3 for the precise definition). It turns out that ${{\left| \alpha_{00} \right\rangle}}$ and ${{\left| \alpha_{11} \right\rangle}}$ are orthogonal, and likewise, ${{\left| \alpha_{01} \right\rangle}}$ and ${{\left| \alpha_{10} \right\rangle}}$ are orthogonal. So, a one-pass LOCC strategy that measures each qubit in the basis ${{\lbrace{{{\left| \alpha_{00} \right\rangle}}, {{\left| \alpha_{11} \right\rangle}}}\rbrace}}$ can extract $n/2 \approx (1.2528)k$ bits of information.

[^5]: Any measurement can be described by a set of measurement operators $K_1,K_2,\ldots$ which satisfy $\sum_j K_j^\dagger K_j = I$. For a given state $\rho$, the measurement returns outcome $j$ with probability $\operatorname{tr}(K_j\rho K_j^\dagger)$, and the post-measurement state (conditioned on observing $j$) is $K_j\rho K_j^\dagger / \operatorname{tr}(K_j\rho K_j^\dagger)$. Note that the measurement can also be described by a set of POVM elements $M_j = K_j^\dagger K_j$; the probability of observing outcome $j$ can then be written as $\operatorname{tr}(M_j\rho)$.

[^6]: Note that $d$ is indeed a metric: It is easy to see that $d({\mathcal{M}},{\mathcal{M}}') \geq 0$, with equality iff ${\mathcal{M}}= {\mathcal{M}}'$. Also, clearly $d({\mathcal{M}},{\mathcal{M}}') = d({\mathcal{M}}',{\mathcal{M}})$. It remains to show that $d({\mathcal{M}},{\mathcal{M}}'') \leq d({\mathcal{M}},{\mathcal{M}}') + d({\mathcal{M}}',{\mathcal{M}}'')$. We consider two cases. On one hand, if ${\mathcal{M}}'$ satisfies $\ell({\mathcal{M}},{\mathcal{M}}') \leq \ell({\mathcal{M}},{\mathcal{M}}'')$ or $\ell({\mathcal{M}}',{\mathcal{M}}'') \leq \ell({\mathcal{M}},{\mathcal{M}}'')$, then the claim follows immediately. On the other hand, if ${\mathcal{M}}'$ satisfies $\ell({\mathcal{M}},{\mathcal{M}}') > \ell({\mathcal{M}},{\mathcal{M}}'')$ and $\ell({\mathcal{M}}',{\mathcal{M}}'') > \ell({\mathcal{M}},{\mathcal{M}}'')$, then this is impossible, since ${\mathcal{M}}$ and ${\mathcal{M}}''$ do not agree at step $\ell({\mathcal{M}},{\mathcal{M}}'')+1$; hence this case cannot occur.

[^7]: In particular, for any $\theta \geq 0$, if we set ${\varepsilon}= 2^{-\theta}$, then $H_\infty^{\varepsilon}(X) \geq H_2(X) - \theta$; this follows from Markov’s inequality.

[^8]: Note that $d$ is indeed a metric: It is easy to see that $d({\mathcal{M}},{\mathcal{M}}') \geq 0$, with equality iff ${\mathcal{M}}= {\mathcal{M}}'$. Also, clearly $d({\mathcal{M}},{\mathcal{M}}') = d({\mathcal{M}}',{\mathcal{M}})$. It remains to show that $d({\mathcal{M}},{\mathcal{M}}'') \leq d({\mathcal{M}},{\mathcal{M}}') + d({\mathcal{M}}',{\mathcal{M}}'')$. We consider two cases. On one hand, if ${\mathcal{M}}'$ satisfies $\ell({\mathcal{M}},{\mathcal{M}}') \leq \ell({\mathcal{M}},{\mathcal{M}}'')$ or $\ell({\mathcal{M}}',{\mathcal{M}}'') \leq \ell({\mathcal{M}},{\mathcal{M}}'')$, then the claim follows immediately. On the other hand, if ${\mathcal{M}}'$ satisfies $\ell({\mathcal{M}},{\mathcal{M}}') > \ell({\mathcal{M}},{\mathcal{M}}'')$ and $\ell({\mathcal{M}}',{\mathcal{M}}'') > \ell({\mathcal{M}},{\mathcal{M}}'')$, then this is impossible, since ${\mathcal{M}}$ and ${\mathcal{M}}''$ do not agree at step $\ell({\mathcal{M}},{\mathcal{M}}'')+1$; hence this case cannot occur.

[^9]: Let ${\mathcal{B}}_2 = {{\lbrace{{{\left| \varphi \right\rangle}} \in {\mathbb{C}}^2, \; {{\left\langle \varphi \middle| \varphi \right\rangle}} = 1}\rbrace}}$. We claim that, for all ${\varepsilon}\leq 1$, $N({\mathcal{B}}, {{\lVert \cdot \rVert}}, {\varepsilon}) \leq N({\mathcal{B}}_2, {{\lVert \cdot \rVert}}_2, {\varepsilon}/3)$. This follows because, for any ${{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}}, {{\left| \varphi' \right\rangle}}{{\left\langle \varphi' \right|}} \in {\mathcal{B}}$, such that ${{\left| u \right\rangle}} := {{\left| \varphi' \right\rangle}} - {{\left| \varphi \right\rangle}}$ satisfies ${{\lVert u \rVert}}_2 \leq 1$, we can write ${{\lVert {{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}} - {{\left| \varphi' \right\rangle}}{{\left\langle \varphi' \right|}} \rVert}} = {{\lVert  -{{\left| u \right\rangle}}{{\left\langle \varphi \right|}} - {{\left| \varphi \right\rangle}}{{\left\langle u \right|}} - {{\left| u \right\rangle}}{{\left\langle u \right|}} \rVert}} \leq 2{{\lVert u \rVert}}_2 + {{\lVert u \rVert}}_2^2 \leq 3{{\lVert u \rVert}}_2$. Finally, it is easy to see that $N({\mathcal{B}}_2, {{\lVert \cdot \rVert}}_2, {\varepsilon}/3) \leq O(1/{\varepsilon}^2)$.

[^10]: This follows because, given an $({\varepsilon}/2)$-net for ${\mathcal{S}}'_1$, we can take its $q$-fold Cartesian product, “round” each point to the nearest point in ${\mathcal{S}}$, and get an ${\varepsilon}$-net for ${\mathcal{S}}$.

[^11]: To see this, let $E_1$ be any $({\varepsilon}/4)$-net for $[0,1]$, and let $E_2$ be any $({\varepsilon}/4)$-net for ${\mathcal{B}}$. We claim that $F := {{\lbrace{\tilde{\lambda} \tilde{M} \;|\; \tilde{\lambda} \in E_1, \; \tilde{M} \in E_2}\rbrace}}$ is an $({\varepsilon}/2)$-net for ${\mathcal{S}}'_1$. To see this, let $\lambda M$ be any element of ${\mathcal{S}}'_1$. Then there exists some $\tilde{\lambda} \tilde{M} \in F$, such that ${{\lVert \lambda M - \tilde{\lambda} \tilde{M} \rVert}} \leq {{\lVert \lambda M - \tilde{\lambda} M \rVert}} + {{\lVert \tilde{\lambda} M - \tilde{\lambda} \tilde{M} \rVert}} \leq {{\lvert \lambda-\tilde{\lambda} \rvert}} + {{\lVert M-\tilde{M} \rVert}} \leq {\varepsilon}/4 + {\varepsilon}/4 = {\varepsilon}/2$.

[^12]: Let ${\mathcal{B}}_2 = {{\lbrace{{{\left| \varphi \right\rangle}} \in {\mathbb{C}}^2, \; {{\left\langle \varphi \middle| \varphi \right\rangle}} = 1}\rbrace}}$. We claim that, for all ${\varepsilon}\leq 1$, $N({\mathcal{B}}, {{\lVert \cdot \rVert}}, {\varepsilon}/4) \leq N({\mathcal{B}}_2, {{\lVert \cdot \rVert}}_2, {\varepsilon}/12)$. This follows because, for any ${{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}}, {{\left| \varphi' \right\rangle}}{{\left\langle \varphi' \right|}} \in {\mathcal{B}}$, such that ${{\left| u \right\rangle}} := {{\left| \varphi' \right\rangle}} - {{\left| \varphi \right\rangle}}$ satisfies ${{\lVert u \rVert}}_2 \leq 1$, we can write ${{\lVert {{\left| \varphi \right\rangle}}{{\left\langle \varphi \right|}} - {{\left| \varphi' \right\rangle}}{{\left\langle \varphi' \right|}} \rVert}} = {{\lVert  -{{\left| u \right\rangle}}{{\left\langle \varphi \right|}} - {{\left| \varphi \right\rangle}}{{\left\langle u \right|}} - {{\left| u \right\rangle}}{{\left\langle u \right|}} \rVert}} \leq 2{{\lVert u \rVert}}_2 + {{\lVert u \rVert}}_2^2 \leq 3{{\lVert u \rVert}}_2$. Finally, it is easy to see that $N({\mathcal{B}}_2, {{\lVert \cdot \rVert}}_2, {\varepsilon}/12) \leq O(1/{\varepsilon}^2)$.
