Cloning Games, Black Holes and Cryptography

Our first contribution is to expose several important gaps in our understanding of cloning games; more importantly, we also show that existing techniques for analyzing cloning games appear fundamentally insufficient at addressing them. We list some of these gaps below:

1. 1.

   Optimal games: Prior work on cloning games over $𝒳={\{0,1\}}^n$ has shown the upper bounds of ${\cos }^2{\left(\frac{\pi }{8}\right)}^n$ and $2^{-n/4}$ in the case of BB84 states [56] and subspace coset states [27, 52], respectively. In contrast, a trivial strategy always succeeds with probability $2^{-n}$, and this holds for any cloning game. Are there especially hard cloning games which admit no non-trivial strategies and have asymptotically optimal bounds of the form $O(2^{-n})$? Closing this gap is not merely an intellectual and aesthetic curiosity; it has important consequences for an application of cloning games to black hole physics which we introduce and study in our work. We outline this application in Section 1.3 of the full version.

   Not only are all known cloning games far from optimal, we prove that existing techniques can at best only produce upper bounds of the form $2^{-n/2}$. We discuss this limitation in detail in Section 2.1.

2. 2.

   Unclonable encryption in MicroCrypt: A number of recent works [41, 10, 3, 17] showed how to build quantum cryptography from pseudorandom states and unitaries, which exist in “MicroCrypt” and are potentially even weaker than one-way functions [41]. To this day, however, the worlds of unclonable cryptography and MicroCrypt have been somewhat disconnected³³3This is with the notable exception of private-key quantum money, which is implied by pseudorandom states [38]., as was recently observed in [46, 8]. Do pseudorandom unitaries, which have so far eluded major cryptographic application, give rise to interesting unclonable cryptography?

   The analysis of Haar cloning games, where $U_{\theta }$ is a Haar unitary (or, a unitary sampled from a unitary design), seems far beyond the scope of existing techniques, as we explain in Sections 2.1 and 2.2.

3. 3.

   Multi-copy games: Can we extend $1\mapsto 2$ cloning games to $t\mapsto t+1$ cloning games, where the cloner $\mathrm{\Phi }$ receives $t$ many copies ${(U_{\theta }|x⟩)}^{\otimes t}$ and where $t+1$ players ${𝒫}_1,\mathrm{\dots },{𝒫}_{t+1}$ simultaneously seek to recover $x$? Although multi-copy variants of no-cloning have been studied before [57], these are far from sufficient to understand multi-copy cloning games, as we previously noted in Remark 1. The natural notion of multi-copy games was raised as an open problem in [46, 8], where the latter initiated the study of multi-copy security in the context of revocable cryptography.

   Not only is prior work limited to $1\mapsto 2$ cloning games, all existing unclonable cryptography is based on highly learnable classes of states and becomes completely insecure if $t$ is allowed to grow polynomially in the number of qubits; this is in stark contrast with most quantum states which require exponentially many copies to be learned, as the literature on quantum tomography suggests [11]. We discuss the limitations of current approaches in Section 2.1 and provide strong evidence that existing techniques seem fundamentally insufficient for analyzing multi-copy games more generally.

   We remark that prior works [43, 21] studied a variant of multi-copy security in the context of quantum copy-protection and unclonable decryption, where each “copy” of the program or key is an i.i.d. mixed state, and thus effectively an independent sample rather than an identical copy of a pure state. While this setting allows one to generically reduce notions of multi-copy security to $1\mapsto 2$ security (using a “quantum pigeonhole argument”), it fails to capture the natural – and significantly more quantum – notion of identical pure state copies; in particular, the same techniques do not carry over in this setting. The pure state notion of unclonability is clearly more desirable in practice; not only does it allow one to send copies of the same exact state to multiple recipients without compromising security, many identical copies also allow the recipients to approximately reflect around the state [54], thereby offering an additional “public verification feature” which is unavailable for mixed states, and which has found many use-cases in unclonable cryptography [12, 8].

4. 4.

   Applications beyond cryptography: While cloning games appear quite fundamental, their use case has so far been limited to cryptography. Can cloning games offer new insights in other scenarios where no-cloning and monogamy of entanglement play an important role, such as in black hole physics? Recent works studied idealized models of black holes which rely on Haar random or pseudorandom unitary dynamics [37, 40, 30], which raises the question: can cloning games with Haar random unitaries help us understand how information gets scrambled inside of a black hole?

   An application to black hole physics once again seems to require new insights into Haar cloning games which, as mentioned before, are currently out of reach. We refer to Sections 2.1 and 2.2.

Given these inherent limitations on cloning games, it seems that fundamentally new techniques are needed in order to advance the field. This is where our next contribution comes in.

Our approach towards overcoming both limitations 1 and 3 is to focus on entirely new cloning games altogether. Inspired by the recent literature on pseudorandom quantum states [38, 18, 23], we study a cloning game based on binary phase states. The pseudorandomness of these states makes them excellent candidates for multi-copy unclonability [57], in the sense of a traditional no-cloning theorem. In order to extend this to a stronger cloning game bound as discussed in Remark 1, we take the existing formalism of binary types [3] and extend it to a new notion of binary subtypes, proving new standalone spectral bounds along the way. For technical reasons, our results only apply to a restricted model: rather than receiving the string $\theta$ in the clear, each player receives oracle access and is allowed to make a single query to either $U_{\theta }$ or $U_{\theta }^{†}$. While this constitutes a weaker model, it already implies something much stronger than a conventional $t\mapsto t+1$ no-cloning bound.⁴⁴4As we explain in Remark 1 and Remark 7 of the full version, approximate $t\mapsto t+1$ no-cloning emerges as a special case of our one-query cloning game, whereby each player makes a single query to $U_{\theta }^{†}$ and immediately measures in the computational basis (with no post-processing whatsoever). In this case, the value of the cloning game is precisely equal to the maximum average cloning fidelity for $t\mapsto t+1$.

Ultimately, we prove the following theorem (see Section 2.3 for more details):

For constant $t$, this is asymptotically optimal and thus overcomes limitation 1. For $t=o(n/\log n)$, this is still negligible in $n$ and thus makes significant progress towards overcoming limitation 3. However, we believe that this construction is plausibly secure when $t$ is any polynomial in $n$ (unlike previous constructions based on BB84 [56, 19] and coset states [24, 27, 52]), and view our results as providing evidence towards this conjecture. Our justification for the plausible security of this construction is the fact that binary phase states are pseudorandom [38, 18] and hence multi-copy unclonable [57]. We discuss our binary phase state construction more in Section 2.3.

Secondly, we study the new and natural notion of a Haar cloning game. Here, the unitary $U_{\theta }$ is sampled according to the Haar measure and the players receive oracle access to $U_{\theta }$ and $U_{\theta }^{†}$. We show that the Haar cloning game is the hardest cloning game by exhibiting a worst-case to average-case reduction; this allows us to use an upper bound on the value of any cloning game, including our binary phase state game, in order to bound the value of the Haar cloning game. As a consequence, we additionally obtain the following:

We will see next that Haar cloning games are central to the applications previously listed in items 2 and 4. We will discuss Haar cloning games and our worst-case to average-case reduction more in Section 2.2.

To demonstrate the full potential of our new insights into cloning games, we give two applications of our techniques which help resolve fundamental open questions in the field. We will see that these applications crucially require us to overcome the aforementioned limitations 1 and 3 in the existing constructions and analyses of cloning games.

• $\mathrm{■}$

  Black Hole Cloning Games. In Section 8 of the full version, we analyze a new three-player game which is designed to capture cloning and entanglement monogamy in the context of evaporating black holes. Our results offer new quantitative insights into the black hole information paradox [36, 48, 37] and suggest that, in an idealized model of a black hole which features Haar random (or pseudorandom) scrambling dynamics, the information from infalling qubits can only be recovered from either the interior or the exterior of the black hole, but never from both places at once – even in the presence of powerful observers which can make a single query to the scrambling unitary or its inverse.

  At a technical level, this requires us to essentially show a bound of $O(2^{-n})$ for the $1\mapsto 2$ Haar cloning game; even an exponentially small bound of $O\mathbf{(}{\mathrm{𝟐}}^{\mathbf{-}cn}\mathbf{)}$ for will not suffice. We thus crucially need to overcome the aforementioned limitation 1, and we also need to make use of the aforementioned worst-case to average-case reduction. We discuss this application at a high level in Section 1.3 of the full version, taking care to provide context on relevant prior work in black hole physics.

• $\mathrm{■}$

  Unclonable Encryption: “MicroCrypt” and the Multi-Copy Setting. In Section 9 of the full version, we give an affirmative answer to an open question which was recently posed in [46]; namely: do interesting unclonable cryptographic primitives – other than private-key quantum money which is implied by pseudorandom states [38] – exist, even in a world in which $𝖯=\mathrm{𝖭𝖯}$? We construct succinct unclonable encryption schemes from the existence of pseudorandom unitaries; thereby continuing to close the gap between the worlds of MicroCrypt and unclonable cryptography. A crucial ingredient for this result is the aforementioned worst-case to average-case reduction.

  Secondly, we propose a candidate multi-copy unclonable encryption scheme based on the aforementioned binary phase cloning game. We view Theorem 2 as evidence and a first step towards proving its security in the stronger setting where $t$ can be an a priori unbounded polynomial in $n$ and the players are free to make polynomially many queries to the encryption and decryption functionality (or even more strongly, are given the secret key $\theta$ in the clear). Considering the pseudorandomness of the binary phase states that we use as ciphertexts, we believe this stronger security guarantee to be plausible. Obtaining multi-copy security clearly requires us to overcome limitation 3.

  We discuss these applications to unclonable cryptography in some more detail in Section 1.4 of the full version.

We now turn to a detailed overview of our techniques.

One can extend cloning games as defined in Figure 1 to multi-copy cloning games: in this variant, the cloner $\mathrm{\Phi }$ receives $t$ copies i.e. the state ${(U_{\theta }|x⟩)}^{\otimes t}$. In the place of Bob and Charlie, there are now $t+1$ players ${𝒫}_1,\mathrm{\dots },{𝒫}_{t+1}$ who wish to all simultaneously guess $x$. It is easy to see that this game becomes provably easier for the adversaries as $t$ increases.

In the case of BB84 states, where $U_{\theta }|x⟩={𝖧}^{\theta }|x⟩$, we claim that the adversaries can win with probability 1 for any $t\ge 2$. The attack is simple: $\mathrm{\Phi }$ will measure one copy in the standard basis and one copy in the Hadamard basis, and forward these results to all players. Upon receiving $\theta$, the players can mix-and-match these results to recover $x$. The intuitive issue here is that the measurement basis is entirely disentangled across qubits; in fact, [4] describes a generic attack on cloning games with this disentangled structure.

The case of coset states [24, 27, 52] is similar, albeit only after $t$ becomes larger than $n$. Here, we will interpret the basis $\theta$ as a subspace $A\subseteq {𝔽}_2^n$ of dimension $n/2$, and the input $x\in {\{0,1\}}^n$ as a pair of cosets $s+A,s^{\prime }+A^{⟂}$. Then the cloner will receive copies of the state

The cloner can measure half the copies in the standard basis and half the copies in the Hadamard basis, and forward these results to all players. Upon receiving $A$, they can all identify the cosets $s+A$ and $s^{\prime }+A^{⟂}$ with high probability.

As stated, the above attacks only apply in the strong cloning setting. However, the situation is more grim for a very simple reason: these families of states are both learnable given $\mathrm{𝗉𝗈𝗅𝗒}(n)$ copies, whereas most states require exponentially many copies to become learnable, as the state of the art in quantum tomography [11] suggests. Hence, the cloner $\mathrm{\Phi }$ can simply learn a classical description of the state and subsequently forward both the basis $\theta$ and the message $x$ to the $t+1$ players; the players do not even require the challenger to send them $\theta$. In other words, these attacks even hold in the bounded-query-oracular model with $q=0$ or $q=1$. Nevertheless, our technical starting point, which we discuss next, is the toolkit used by previous works to analyze cloning games in the single copy ($t=1$) case. We will pin down where exactly it fails to work in the multi-copy case and remedy these problems. To provide the necessary background, we begin by introducing the notion of a monogamy of entanglement game.

We now take a brief detour and discuss the concept of monogamy of entanglement games; we will see shortly that they are closely related to cloning games. Monogamy of entanglement games were introduced by Tomamichel, Fehr, Kaniewski and Wehner [56] in order to characterize entanglement monogamy [55] using the language of non-local games. Informally, quantum correlations are “monogamous”, and thus cannot be shared freely among multiple parties.

A monogamy of entanglement (MOE) game $𝖦$ with respect to the question set $\mathrm{\Theta }$, answer set $𝒳$ and measurement set ${\{{𝐀}_x^{\theta }\}}_{\theta \in \mathrm{\Theta },x\in 𝒳}$ is an interactive game played by three players: a trusted referee called Alice, as well as two colluding and adversarial parties called Bob and Charlie.

1. 1.

   (Setup phase) Bob and Charlie prepare a tripartite quantum state $\rho \in 𝒟({\mathscr{H}}_{𝖠}\otimes {\mathscr{H}}_{𝖡}\otimes {\mathscr{H}}_{𝖢})$. They send register $𝖠$ to Alice, and hold onto registers $𝖡$ and $𝖢$, respectively. Afterwards, they are no longer allowed to communicate for the remainder of the game.

2. 2.

   (Question phase) Alice samples a random question $\theta \sim \mathrm{\Theta }$, and then applies the corresponding measurement ${\{{𝐀}_x^{\theta }\}}_{x\in 𝒳}$ to her register $𝖠$. Afterwards, Alice announces the question $\theta$ to both Bob and Charlie, and keeps the measurement outcome in $𝒳$ to herself.

3. 3.

   (Answer phase) Bob and Charlie independently output a guess for Alice’s outcome by applying the measurements ${\{{𝐁}_x^{\theta }\}}_{x\in 𝒳}$ and ${\{{𝐂}_x^{\theta }\}}_{x\in 𝒳}$ to their registers $𝖡$ and $𝖢$, respectively.

4. 4.

   (Outcome phase) Bob and Charlie win if they both guess Alice’s outcome correctly.

Here, we associate a particular strategy $𝖲$ employed by Bob and Charlie with the tuple consisting of the initial shared state $\rho$ and the positive operator-valued measurements ${\{{𝐁}_x^{\theta }\}}_{\theta \in \mathrm{\Theta },x\in 𝒳}$ and ${\{{𝐂}_x^{\theta }\}}_{\theta \in \mathrm{\Theta },x\in 𝒳}$. The value of a particular strategy $𝖲$ for the monogamy game $𝖦$ is defined as the average winning probability

We let $\omega (𝖦)$ denote the maximal value of the game, i.e., the optimal winning probability over all strategies. An upper bound on the value of a monogamy game therefore limits the extent to which Bob and Charlie can simultaneously maintain a quantum correlation with Alice who holds a register outside of their view. We emphasize that, in general monogamy of entanglement games, the shared state $\rho$ is completely arbitrary and adversarially chosen by Bob and Charlie; as we will see, this is the main way in which cloning games deviate from the monogamy of entanglement setting.

The standard tool for analyzing cloning games is to recast them as a special type of monogamy game. Together with the techniques laid out by [56] for analyzing monogamy games, this has found numerous applications in unclonable cryptography, including unclonable encryption [19], quantum copy-protection [1, 25, 24, 5], unclonable decryption keys [31], and unclonable proofs [32].

We now explain this connection between cloning and MOE games. In a cloning game, Alice sends the cloner $\mathrm{\Phi }$ the state $U_{\theta }|x⟩$. Instead, we could imagine that Alice and $\mathrm{\Phi }$ share several EPR pairs, and later on in the game (even after the cloning phase) Alice can apply a measurement ${\left\{{𝐀}_x^{\theta }:={\overline{U}}_{\theta }|x⟩⟨x|{\overline{U}}_{\theta }^{†}\right\}}_{x\in {\{0,1\}}^n}$ on her side to induce the state $U_{\theta }|x⟩$ on the cloner’s side, where $\overline{U}$ denotes the complex conjugate of $U$. This yields a monogamy of entanglement game with the following two restrictions:

• $\mathrm{■}$

  As already mentioned, Alice’s measurements ${𝐀}_x^{\theta }$ must take the form ${\overline{U}}_{\theta }|x⟩⟨x|{\overline{U}}_{\theta }^{†}$.

• $\mathrm{■}$

  The tripartite state $\rho$ shared by Alice, Bob, and Charlie is the Choi state of the cloning channel $\mathrm{\Phi }$. Concretely, we must have the special form

  $${\rho }_{\mathrm{𝖠𝖡𝖢}}=({𝕀}_{𝖠}\otimes {\mathrm{\Phi }}_{{𝖠}^{\prime }\to \mathrm{𝖡𝖢}})(|\mathrm{𝖤𝖯𝖱}⟩{⟨\mathrm{𝖤𝖯𝖱}|}_{{\mathrm{𝖠𝖠}}^{\prime }}).$$

  (1)

  In words, $\rho$ can be adversarially chosen subject to the constraint that its marginal state on Alice’s system is maximally mixed.

This equivalence, which we formally show in Lemma A.1 of the full version, was first observed in the context of BB84 states by Broadbent and Lord [19]. On a high level, the statement is a consequence of the ricochet property of EPR pairs, which we formally state in Section 2.1 of the full version. The technical benefit of doing this is that it enables us to get a handle on the cloning channel $\mathrm{\Phi }$ by absorbing it into the state shared by the players in the equivalent monogamy game. Now we can focus on Bob and Charlie’s measurements which, as we will see, can be handled using spectral bounds as first observed by [56].

Although the equivalence observed by [19] is in the single-copy setting, it turns out that this idea readily generalizes to the multi-copy setting, as we show in Lemma A.2 of the full version. The differences are as follows:

• $\mathrm{■}$

  In the cloning game, Alice and the cloner $\mathrm{\Phi }$ now share $nt$ EPR pairs, and Alice will measure each of the $t$ copies in the basis specified by ${\left\{{\overline{U}}_{\theta }|x⟩⟨x|{\overline{U}}_{\theta }^{†}\right\}}_{x\in {\{0,1\}}^n}$.

• $\mathrm{■}$

  In the equivalent monogamy-like⁵⁵5We say “monogamy-like” because monogamy-of-entanglement games traditionally involve just three parties [56]. game, we only say that the adversaries win if Alice’s $t$ measurements and the $t+1$ players’ outputs are all equal to the same string $x$. In other words, we need to essentially post-select on Alice’s measured string $x\in {\{0,1\}}^n$ being the same for each of the $t$ copies, which means the value of this monogamy-like game is immediately upper bounded by $2^{-n(t-1)}$.

Because of this post-selection, what we end up with is an equality of the following form:

Note that when $t=1$, the $2^{n(t-1)}$ term is 1 and we recover the equivalence used by [19]. Our goal is hence to upper bound the value of ${𝖦}_{\mathrm{monogamy}-\mathrm{like}}$ by $2^{-n(t-1)}\cdot \mathrm{𝗇𝖾𝗀𝗅}(n)$, ideally even $O(2^{-nt})$.

The work by Tomamichel, Fehr, Kaniewski and Wehner [56] analyzes MOE games and later focuses on the BB84 case (i.e. $U_{\theta }={𝖧}^{\theta }$) and uses two beautiful ideas, which for simplicity we state in the single-copy setting:

1. 1.

   The value of a particular monogamy game can be bounded independently of the state ${\rho }_{\mathrm{𝖠𝖡𝖢}}$ shared by the 3 players, noting that ${\rho }_{\mathrm{𝖠𝖡𝖢}}$ is PSD and has trace 1. Concretely, one can show that

   $\underset{\theta \sim \mathrm{\Theta }}{𝔼}{\displaystyle \sum _{x\in 𝒳}}\mathrm{Tr}\left[({𝐀}_x^{\theta }\otimes {𝐁}_x^{\theta }\otimes {𝐂}_x^{\theta }){\rho }_{\mathrm{𝖠𝖡𝖢}}\right]$

   $\le {\Vert \underset{\theta \sim \mathrm{\Theta }}{𝔼}{\displaystyle \sum _{x\in 𝒳}}{𝐀}_x^{\theta }\otimes {𝐁}_x^{\theta }\otimes {𝐂}_x^{\theta }\Vert }_{\mathrm{\infty }}.$

   This reduces the task of bounding the value of a monogamy game to bounding an operator norm. In general monogamy games as formulated by [56], the shared state ${\rho }_{𝖠BC}$ is adversarially chosen so this step is tight. However, we will see soon that this step is too lossy when restricting attention to the special monogamy-like games that are equivalent to cloning games.

2. 2.

   This operator norm can in turn be bounded just in terms of pairwise overlaps between the ${𝐀}_x^{\theta }$’s, which the designer of the game is free to choose. As we restate in Theorem 6.1 of the full version, the authors of [56] show that

   $${\Vert \underset{\theta \sim \mathrm{\Theta }}{𝔼}\sum _{x\in 𝒳}{𝐀}_x^{\theta }\otimes {𝐁}_x^{\theta }\otimes {𝐂}_x^{\theta }\Vert }_{\mathrm{\infty }}\le \frac{1}{|\mathrm{\Theta }|}+\frac{|\mathrm{\Theta }|-1}{|\mathrm{\Theta }|}\cdot \underset{\begin{array}{c}\theta ,{\theta }^{\prime }\in \mathrm{\Theta }\\ \theta \ne {\theta }^{\prime }\end{array}}{\max }\underset{x,x^{\prime }\in 𝒳}{\max }{\Vert {𝐀}_x^{\theta }{𝐀}_{x^{\prime }}^{{\theta }^{\prime }}\Vert }_{\mathrm{\infty }}.$$

   We refer the reader to Theorem 6.1 of the full version for a formal statement.

In the BB84 monogamy game where $\mathrm{\Theta }=𝒳=\{0,1\}$ and ${𝐀}_x^{\theta }={𝖧}^{\theta }|x⟩⟨x|{𝖧}^{\theta }$, it is straightforward to see that ${\Vert {𝐀}_x^{\theta }{𝐀}_{x^{\prime }}^{{\theta }^{\prime }}\Vert }_{\mathrm{\infty }}=\frac{1}{\sqrt{2}}$, and hence $\omega ({𝖦}_{\text{BB84}})\le \frac{1}{2}+\frac{1}{2\sqrt{2}}$. The work by [56] also extends this to “parallel-repeated” BB84 games with $|\mathrm{\Theta }|=|𝒳|={\{0,1\}}^n$ (see Theorem 3.4 of the full version for a formal definition), and show that

Hence the BB84 monogamy game has value $\le 2^{-0.228n}$, and in fact this is tight; [56] exhibits a simple strategy achieving this bound. Similar techniques were used by [27] and improved upon by [52] to analyze subspace coset states, ultimately proving an upper bound of $O(2^{-n/4})$; it is not known whether or not this is tight.⁶⁶6Previous work [53] proved an upper bound of $O(2^{-n/2})$ in a setting where the cloner $\mathrm{\Phi }$ is restricted to splitting the state as is into two equal-sized halves, sending one to Bob and the other to Charlie. We cite $O(2^{-n/4})$ as the state of the art, as we are interested in games where the cloner $\mathrm{\Phi }$ is unrestricted. However, the techniques laid out by [56] provably do not suffice for our applications:

• $\mathrm{■}$

  In the multi-copy case, recall from Equation (2) that we need to prove a bound on ${𝖦}_{\mathrm{monogamy}-\mathrm{like}}$ of $\ll 2^{-n(t-1)}$. Item 1 of the [56] methodology proposes to ignore the structure of the state shared by Alice and ${𝒫}_1,\mathrm{\dots },{𝒫}_{t+1}$, in order to reduce our task to bounding an operator norm.

  This is likely too lossy in our setting, as evidenced by the following simple counterexample (assume $t>1$ is even for simplicity) that holds against any cloning game where the unitaries $U_{\theta }$ have real entries. Alice will hold $tn/2$ EPR pairs (which are unentangled from the states held by ${𝒫}_1,\mathrm{\dots },{𝒫}_{t+1}$). The $t+1$ players will each deterministically output $0^n$ as their guess (note that once again this strategy does not depend at all on $\theta$). The winning probability is now just the probability that Alice measures $0$ on each of her $tn/2$ EPR pairs (in whatever basis she samples), which is $2^{-nt/2}\ge 2^{-n(t-1)}$. We formalize this counterexample in Section 6.1 of the full version.

  We note that this does not rule out the possibility of the [56] technique being adaptable to the multi-copy setting for a construction that uses unitaries with complex entries. However, the pre-existing constructions based on BB84 states or coset states – as well as our main construction based on binary phase states (which we sketch in Section 2.3) – only use unitaries with real entries. Thus we still view our result as a bound against the adaptability of existing construction and techniques to the multi-copy setting.

• $\mathrm{■}$

  Even in the single-copy case, there is another inherent limitation that arises from using Item 2 of the [56] methodology: the maximal pairwise overlap ${\max }_{\theta \ne {\theta }^{\prime }}{\Vert {𝐀}_x^{\theta }{𝐀}_{x^{\prime }}^{{\theta }^{\prime }}\Vert }_{\mathrm{\infty }}$ is provably at least $2^{-n/2}$ for any monogamy game, as we show in Section 6.2 of the full version. For completeness, we also show in Section 6.3 of the full version that our binary phase state construction (which we will discuss more in Section 2.3) essentially attains this maximum pairwise overlap.

  Howeover, we would ideally like to prove a tight bound (up to constant factors) of $O(2^{-n})$. This is not just a matter of aesthetic taste; this is actually crucial for our application to black hole physics, as we explain in Section 1.3 of the full version.

We next turn our attention to our construction and our new techniques for analyzing it, which make progress towards overcoming both of these barriers.

We begin from a simple starting point: in Section 2.2, we suggested having Alice send a Haar random state $U_{\theta }|x⟩$ to the cloner. Instead, what if Alice were to send a pseudorandom state [38, 18]? These are also multi-copy unclonable by a trivial hybrid argument combined with Werner’s result [57] in the Haar case. The advantage of working with binary phase states is that we have much simpler constructions that, as we will see, are easier to analyze.

It was shown by [38, 18] that if $𝔉$ is a family of post-quantum pseudorandom functions [61] $f:{\{0,1\}}^n\to \{0,1\}$, then the binary phase state

is pseudorandom. To use this in a cloning game, we follow the approach in [23] in order to encode $x\in {\{0,1\}}^n$ into this state, which we do by taking:

is a phase oracle for $f$. In other words, we are proposing to define a cloning game with $\mathrm{\Theta }=𝔉$ and $U_{\theta }={𝖴}_f{𝖧}^{\otimes n}$. Thus in the equivalent monogamy game, Alice’s projectors will be defined by

The question is now how one should go about analyzing this game. As mentioned in Section 2.1, the usual [56] methodology for analyzing cloning games is firstly limited to the single-copy setting, and secondly even in this setting can only prove a bound of $2^{-n/2}$. For completeness, we show in Section 6.3 of the full version that plugging our binary phase construction into [56] “saturates” this technique and yields a single-copy cloning bound of $\tilde{O}(2^{-n/2})$, which is stronger than the previous results on BB84 [56, 19] and coset [24, 27, 52] states.

The techniques discussed up to this point draw on the machinery of [56] and thus suffice to establish cloning bounds even in the setting where a classical description of the measurement basis $\theta$ (in the binary phase case, the function $f$) is sent to all players ${𝒫}_1,\mathrm{\dots },{𝒫}_{t+1}$ in the clear. To our knowledge, the only other technique that works in this strong regime is the decoupling technique by [16]. However, as we explained in Sections 2.1 and 2.2, both of these techniques run into limitations with respect to the multi-copy setting and/or attaining an optimal bound of $O(2^{-n})$.

We hence propose to migrate to the oracular setting, where each player can make oracle queries to ${𝖴}_f$, but is not given a description of $f$ in the clear. Note that this still suffices to recover $x$ from ${𝖴}_f{𝖧}^{\otimes n}|x⟩$. In fact, we only need one query: a single query to ${𝖴}_f$ would leave us with ${𝖧}^{\otimes n}|x⟩$, and now measuring in the Hadamard basis yields $x$. We explain this in the case of general cloning games in Remark 7 of the full version.

We now want to reason about algorithms that make oracle queries to ${𝖴}_f$ for a random (or pseudorandom) function $f$. The natural candidate technique for such a task is Zhandry’s compressed oracle technique [60]. The crucial idea is to purify the cloning game by adding a register that stores the function $f$. One can then argue that queries to ${𝖴}_f$ for a random $f:{\{0,1\}}^n\to \{0,1\}$ can be simulated as follows:

• $\mathrm{■}$

  We will add a purifying “database” register to the system that we initialize to $|\mathrm{\varnothing }⟩$. In general, it will store some subset $S\subseteq {\{0,1\}}^n$.

• $\mathrm{■}$

  If the algorithm wishes to query the string $y\in {\{0,1\}}^n$, simply update $|S⟩\leftarrow |S\oplus \left\{y\right\}⟩$ (note that if $y$ is in $S$ before the query, this will remove $y$ from $S$.)

Let us see how this technique would play out in our setting. Alice and ${𝒫}_1,\mathrm{\dots },{𝒫}_{t+1}$ all share some global state, and act as follows:

• $\mathrm{■}$

  Alice queries each of her $t$ $n$-qubit states, then applies a Hadamard to each copy. Her local transformation can be written as ${⨂}_{i=1}^t\left({\sum }_{y_i\in {\{0,1\}}^n}{𝖧}^{\otimes n}|y_i⟩⟨y_i|\right)$, and she will XOR $\left\{y_1\right\}\oplus \mathrm{\dots }\oplus \left\{y_t\right\}$ into the database register.

• $\mathrm{■}$

  For each $i\in [t+1]$, let the adversary ${𝒫}_i$ make $q$ adaptive queries represented by unitaries $V_{i,1},\mathrm{\dots },V_{i,q}$. Their local transformation can be written as a sum of terms of the form

  $$V_{i,q}|z_{i,q}⟩⟨z_{i,q}|V_{i,q-1}|z_{i,q-1}⟩⟨z_{i,q-1}|\mathrm{\dots }{V}_{i,1}|z_{i,1}⟩⟨z_{i,1}|,$$

  and they will XOR $\left\{z_{i,1}\right\}\oplus \mathrm{\dots }\oplus \left\{z_{i,q}\right\}$ into the database register.

In summary, the database register will contain the set:

At this point, it is unclear how to proceed, for the following simple conceptual reason: the utility of Zhandry’s compressed oracle technique [60] lies in the fact that it connects an algorithm’s success probability with the contents of the database register in some way. For example, when reproving the [14] lower bound showing the optimality of Grover search, Zhandry shows that the success probability of the algorithm is essentially upper bounded by the probability of a solution $x$ to the search problem appearing in the database register. However, there is no analogous notion in our setting, because we are considering a problem with inherently quantum inputs; a successful adversary likely needs to query ${𝖴}_f$ on every input in superposition.

Instead, we will deviate from Zhandry’s compressed oracle formalism by simply tracing out (or equivalently, measuring) the database register. This effectively conditions our superposition on the collection of strings that are listed an odd number of times in Equation (4). This is exactly the notion of binary types introduced by [3]. In order to get a better handle on the binary type’s combinatorial structure, we will restrict each of the $t+1$ players to only make one oracle query to ${𝖴}_f$; as explained in Remark 7 of the full version, this is still sufficiently expressive to admit a trivial strategy attaining value $2^{-n}$.

In this case, a binary type $𝝀$ is specified by a subset $T_{𝝀}\subseteq [2^n]$ with $|T_{𝝀}|\le 2t+1$. For $𝐱\in {[2^n]}^{2t+1}$, we say that $\mathrm{𝖡𝗂𝗇𝖳𝗒𝗉𝖾}(𝐱)=𝝀$, or equivalently that $𝐱$ matches $𝝀$, if every string in $T_{𝝀}$ appears an odd number of times in $𝐱$, while every string outside $T_{𝝀}$ appears an even number of times in $𝐱$. Thus, if Alice and the players jointly hold a standard basis state $|𝐱⟩$, a simultaneous query to ${𝖴}_f$ by all parties will write $\mathrm{𝖡𝗂𝗇𝖳𝗒𝗉𝖾}(𝐱)$ into the database register. Finally, we let ${\mathrm{\Pi }}_{𝝀}$ denote the projector onto standard basis vectors $𝐱$ that match $𝝀$. We provide more precise definitions and properties of binary types in Section 4.2 of the full version. We now model each player’s projector as follows:

for unitaries $Q_i$.⁸⁸8In reality, we later also allow these players additional ancillary workspace qubits; we define this generalization in Definition 3.8 of the full version. Moreover, we assume without loss of generality that the players do not perform any preprocessing before making their query to ${𝖴}_f$, by absorbing this preprocessing into the cloning channel $\mathrm{\Phi }$ that constructs their initial states. This simplification together with the aforementioned binary type formalism allows us to succinctly characterize the value of the cloning game: if we define

where $\rho$ is the shared state from the monogamy-like game that we introduced in Section 2.1. We face two challenges in bounding expressions of this form. We state them below and then describe how we address these challenges:

1. 1.

   The [56] paradigm of discarding the tripartite state $\rho$ and simply bounding this expression by ${\max }_{𝝀}{\Vert {\mathrm{\Pi }}_{𝝀}\mathrm{\Xi }{\mathrm{\Pi }}_{𝝀}\Vert }_{\mathrm{\infty }}$⁹⁹9This bound holds by noting that the projectors ${\mathrm{\Pi }}_{𝝀}\mathrm{\Xi }{\mathrm{\Pi }}_{𝝀}$ are mutually orthogonal. is provably too lossy, as we explained in Section 2.1.

2. 2.

   Even if it were somehow sufficient to bound ${\Vert {\mathrm{\Pi }}_{𝝀}\mathrm{\Xi }{\mathrm{\Pi }}_{𝝀}\Vert }_{\mathrm{\infty }}$ for each $𝝀$, to the best of our knowledge, it appears difficult to directly establish such a bound. Informally, the reason is that the combinatorial structure arising from a type $𝝀$ entangles registers together; if we consider the $t=1$ case and the type defined by $T_{𝝀}=\left\{x^{\ast }\right\}$ for some string $x^{\ast }$, then strings of the form $(x^{\ast },y,y),(y,x^{\ast },y),$ or $(x^{\ast },y,y)$ would all match $𝝀$. It would be much cleaner if we could just analyze strings from one of these categories at a time.

To address Item 1, we take a closer look at the structure of the shared state $\rho$. It is the result of applying some (adversarially chosen) channel to the right half of $tn$ $\mathrm{𝖤𝖯𝖱}$ pairs. This can be seen from Equation (1) (appropriately generalized to the multi-copy setting). In other words, if we apply a partial trace to remove the ${𝖯}_{\mathrm{𝟣}\to 𝗍+\mathrm{𝟣}}$ registers of the $t+1$ players, the residual state on Alice’s register $𝖠$ will always be proportional to ${𝕀}_{2^n\times 2^n}$.

This structure may seem mild, but it turns out to be enough to complete our analysis; we present this in Sections 5.4 and 5.5 of the full version. This is perhaps not surprising; in the counterexample we presented in Section 2.1 showing that just bounding the operator norm would be insufficient, Alice’s local state was very far from maximally mixed. In fact, it was a pure state consisting of $t/2$ EPR qudit pairs.

At a high level, our analysis to use this structure of $\rho$ proceeds by showing that for any type $𝝀$ such that ${\mathrm{\Pi }}_{𝝀}\mathrm{\Xi }{\mathrm{\Pi }}_{𝝀}$ has high operator norm, the shared state $\rho$ must place low weight on the image of ${\mathrm{\Pi }}_{\lambda }$. These effects roughly cancel each other out.

We now turn to the issue stated in Item 2. Continuing with the $t=1$ example, reasoning about $𝝀$ directly requires simultaneously handling three categories of strings: $(x^{\ast },y,y),(y,x^{\ast },y),$ or $(x^{\ast },y,y)$. Instead, we simplify matters by focusing on just one of these categories at a time – we call such a category a subtype, a novel notion we define formally in Section 4.3 of the full version. We denote subtypes by $𝝁$ and their corresponding subtype projectors by ${\mathrm{\Pi }}_{𝝁}$. In Section 4.3.2 of the full version, we show that instead of bounding ${\Vert {\mathrm{\Pi }}_{𝝀}\mathrm{\Xi }{\mathrm{\Pi }}_{𝝀}\Vert }_{\mathrm{\infty }}$ for a type $𝝀$, it suffices to bound ${\Vert {\mathrm{\Pi }}_{𝝁}\mathrm{\Xi }{\mathrm{\Pi }}_{𝝁}\Vert }_{\mathrm{\infty }}$ for a subtype $𝝁$. This added structure allows us to prove better spectral bounds, which we present in Section 5.3 of the full version.

It turns out that this technique allows us to prove the desired bound of $O(2^{-n})$ for $1\mapsto 2$ cloning games, albeit with the restriction that Bob and Charlie can only make one query each to ${𝖴}_f$. At a very high level, the “product structure” of subtypes enables us to leverage a simple but novel spectral bound on the column-wise tensor product of several matrices, which we present in Lemma 2.18 of the full version.

In order to prove spectral bounds on the norm of ${\mathrm{\Pi }}_{𝝁}\mathrm{\Xi }{\mathrm{\Pi }}_{𝝁}$ for any subtype $𝝁$, and accommodate the possibility of the $t+1$ players using ancilla qubits, we require a novel bound on the norm of a blockwise tensor product of $d\times d$ block matrices. As a simple example, the $d=2$ case is the following: we need to show that

provided that are unitary and $|c_{i,j}|\le 1$ for all $i,j$. Proving this turns out to be rather technically challenging; we present this result and its proof in Theorem 2.15 of the full version. We also discuss at the end of Section 2.4.1 of the full version why existing techniques fail to prove the general result we need. Given that this theorem is a purely linear algebraic statement unrelated to monogamy games, we are hopeful that it might be useful elsewhere in quantum information and even in other areas.

Putting these ideas together, we manage to prove a multi-copy cloning bound of $O_t(2^{-n})$, overcoming the limitations of previous techniques explained in 2.1 with a complete overhaul of the technical framework laid out by [56], albeit at the expense of restricting the $t+1$ players to make a single oracle query to ${𝖴}_f$.