Technical Summary: More is Less: Optimal Security for Haar Quantum Money and More

1. Problem Statement

The paper addresses a fundamental security gap in quantum money and copy-protection schemes: the potential for an adversary's existing holdings to facilitate counterfeiting. In classical cryptography, possessing more resources (e.g., more banknotes) typically does not lower the computational cost of breaking the system. However, in quantum settings, possessing multiple copies of a quantum state can sometimes aid in state estimation or cloning.

Specifically, the authors investigate the $k \to k+r$ cloning problem: given $k$ copies of an unknown quantum state $|\psi\rangle$ and access to a reflection oracle $C|\psi\rangle Z$, what is the query complexity required to produce $k+r$ valid copies?

Existing bounds, such as those by Aaronson and Christiano [AC12], suggest that the query complexity for cloning degrades as $k$ increases (e.g., $\Omega(\sqrt{N/k})$). This implies that "the rich get richer" in a cryptographic sense: possessing more banknotes makes counterfeiting easier. The paper seeks to determine if this degradation is inherent or if there exist constructions where the cost of producing additional copies remains independent of $k$, provided $k$ is below the threshold required for full state tomography ($k \ll N$, where $N=2^n$).

2. Methodology

2.1 Lower Bound Framework: Compressed Oracle for Quantum Tasks

The core technical contribution is a novel adaptation of Zhandry's compressed oracle technique [Zha19] to the inherently quantum task of cloning.

• Oracle Purification and Discretization: The authors first reduce the continuous Haar-random distribution to a discrete distribution of phase states defined by random functions $f: [N] \to [M]$. This allows for the purification of the oracle into a quantum register.
• Fourier Basis and Multisets: By viewing the oracle register in the Fourier basis, the state of the oracle is represented as a "multiplicity-recording table" (a multiset of signed integers).
  • Balance: The sum of entries in the multiset (invariant under reflection queries).
  • Negative-size: The number of negative entries in the multiset.
• Progress Measures: The authors define a set of projectors $\Gamma_\ell$ that project onto states where the multiset has exactly $\ell$ negative elements.
  • The initial state (with $k$ copies) has negative-size 0.
  • The winning state (with $k+r$ copies) requires the state to be supported on subspaces with negative-size at least $r$.
  • A single reflection query can increase the negative-size by at most 1.
• Bounding Increments: The proof bounds the probability amplitude of moving from a subspace with $\ell-1$ negative elements to $\ell$ negative elements. Crucially, the authors show that this transition incurs a penalty factor related to $1/\sqrt{N}$, and that accumulating $r$ such steps results in an exponential decay in success probability unless the number of queries $T$ is sufficiently large.

2.2 Upper Bound: Doubling Algorithm

To demonstrate tightness, the authors construct an algorithm that matches the lower bound:

• State Estimation: The algorithm uses an optimal POVM (Symmetric Pure-State POVM) to estimate the unknown state $|\psi\rangle$ from $k$ copies, producing a classical description of a state $|g\rangle$.
• Amplitude Amplification: Using the estimated state $|g\rangle$, the algorithm applies fixed-point amplitude amplification to generate a new copy of $|\psi\rangle$.
• Doubling Strategy: The algorithm employs a "doubling" strategy. Starting with $k$ copies, it generates $2k$ copies, then $4k$, and so on. The expected query complexity for generating $r$ additional copies is shown to be $O(\sqrt{rN})$, independent of the initial $k$ (as long as $k+r = o(N)$).

2.3 Cryptographic Reductions

The cloning bounds are applied to two cryptographic primitives:

1. Public-Key Quantum Money: The authors show that for Haar-random state money schemes with reflection-oracle verification, the security against counterfeiting $r$ additional notes depends only on $r$ and $N$, not on the number of notes $k$ already held by the counterfeiter.
2. Quantum Copy Protection: Adapting the framework of [ALL+21], the authors construct a copy-protection scheme for unlearnable functions. They prove a security dichotomy: an adversary either learns the function (breaking the unlearnability assumption) or successfully clones the Haar-random program state. The cloning barrier remains high regardless of the number of copies the pirate possesses.

3. Key Results

3.1 Tight Cloning Bounds

The paper establishes tight bounds for the query complexity of cloning. Let $N=2^n$.

• Theorem 1.1 ($k \to k+1$): For a Haar-random state $|\psi\rangle$, any algorithm making $T$ queries to $C|\psi\rangle Z$ and outputting $k+1$ registers satisfies:
  $$\mathbb{E}_{|\psi\rangle} \text{Tr}[(|\psi\rangle\langle\psi|)^{\otimes(k+1)} \rho_\psi] \leq O\left(\frac{T^2}{N} + \frac{k+1}{N}\right)$$
  Consequently, to achieve constant success probability, $T = \Theta(\sqrt{N})$ is required, provided $k = o(N)$. The presence of $k$ copies does not asymptotically reduce the query cost.

• Theorem 1.3 ($k \to k+r$): For generating $r$ additional copies:
  $$\mathbb{E}_{|\psi\rangle} \text{Tr}[(|\psi\rangle\langle\psi|)^{\otimes(k+r)} \rho_\psi] \leq \left( O\left(\frac{T^2}{rN} + \frac{k+r}{N}\right) \right)^r$$
  The optimal query complexity is $\Theta(\sqrt{rN})$. Notably, the cost per new copy decreases as $r$ increases (batch generation is more efficient), but possessing more initial copies ($k$) provides no advantage.

3.2 Cryptographic Implications

• Quantum Money (Theorem 1.5): The construction based on Haar-random states and reflection oracles achieves optimal query security. Counterfeiting one additional banknote requires $\Theta(2^{n/2})$ queries, regardless of whether the adversary holds 1 or $o(2^n)$ banknotes. This resolves the "More is Less" paradox: greater wealth (more banknotes) does not grant greater counterfeiting power.
• Copy Protection (Theorem 1.6): The security of the proposed copy-protection scheme is bounded by the sum of the learning advantage and the cloning advantage. The cloning term $HClone_{N,k}(T^*)$ scales as $T^2/N$ without multiplicative loss depending on $k$. Thus, possessing multiple copies of a protected program does not lower the barrier to piracy.

4. Significance and Claims

The paper claims to resolve an open problem posed by Aaronson [Aar09] regarding the parameters of the complexity-theoretic no-cloning theorem.

• Optimality: The authors demonstrate that the "More is Less" property (where more copies do not help) is achievable and optimal for Haar-random states. The security of such systems does not deteriorate as the adversary accumulates more copies, up to the point where full state tomography becomes feasible ($k \approx N$).
• Technical Novelty: The work provides one of the first applications of the compressed oracle technique to a purely quantum task (cloning) rather than classical problems (like collision finding). The development of a multi-stage progress measure (tracking negative elements in the multiset) allows for tight bounds on the $k \to k+r$ transition.
• Cryptographic Robustness: By proving that the cloning barrier is independent of $k$, the paper strengthens the theoretical foundation for quantum money and copy protection, ensuring that these systems remain secure even against adversaries with significant initial holdings.

The authors explicitly state that their lower-bound proofs were developed without AI assistance, while the upper bound for the general $k \to k+r$ case utilized AI for initial proof sketching, which was subsequently verified and rewritten by the authors. The results extend to phase states in the Quantum Random Oracle Model (QROM), suggesting potential routes for efficient plain-model constructions, though the paper notes that establishing security for such instantiations remains an open direction.