Are clonable quantum proofs more powerful than classical proofs?

Clonability is not what makes quantum proofs stronger

Recent classical-oracle separations between QMA and QCMA highlighted the unclonability of their quantum witnesses as a key mechanism: a classical witness can be copied and reused across many executions, eventually leaking too much information about the oracle. That raised the question of whether unclonability is actually necessary for quantum proofs to beat classical ones.

This paper answers no. It constructs a classical oracle O such that QCMA^O is strictly contained in ClonableQMA^O. The honest witnesses in the construction admit polynomial-time cloning with fidelity 1 - negl(lambda), so the quantum advantage survives even when the proof state can be copied. The result strengthens the earlier quantum-oracle separation of Nehoran and Zhandry to a purely classical oracle, resolving their open question.

Where ClonableQMA sits between QCMA and QMA

ClonableQMA was introduced by Nehoran and Zhandry as the complexity-theoretic notion for quantum proofs that are efficiently clonable under computational constraints. It sits in the hierarchy QCMA subseteq ClonableQMA subseteq QMA, placing clonable quantum proofs between classical proofs and unrestricted quantum proofs.

The two endpoints of this hierarchy, QCMA and QMA, had been the subject of a long-standing question first posed by Aharonov and Naveh: whether quantum proofs are more powerful than classical ones. Recent breakthroughs by Bostanci, Haferkamp, Nirkhe, and Zhandry, and subsequently by Bostanci, Huang, and Vaikuntanathan, established unconditional separations between QMA and QCMA relative to a classical oracle. This paper instead targets the intermediate class, showing that ClonableQMA itself is strictly stronger than QCMA relative to a classical oracle.

The advice state built from code intersection

The construction builds on the Yamakawa-Zhandry code-intersection problem. Given a linear code C over Sigma^n, hash functions H_i mapping Sigma to {0,1}, and a target b in {0,1}^n, the task is to find a codeword c in C such that the concatenated hash H(c) equals b. For suitable codes, the Yamakawa-Zhandry quantum algorithm solves this efficiently while polynomial-query classical algorithms fail. The paper uses the biased variant of Bostanci, Huang, and Vaikuntanathan, with targets b = z concatenated with 0^(n-l) and hash functions strongly biased toward zero.

The central quantum state is |adv_H>, a tensor product of uniform superpositions over hash preimages |H_i^{-1}(0)> and |H_i^{-1}(1)> for each coordinate, together with |phi_2>, the uniform superposition over codewords in C. The same state serves three roles under different oracle interfaces: a clonable quantum proof in ClonableQMA, a clonable quantum advice in BQP/clonableqpoly, and a flame state in quantum fire. Because it originates from the Yamakawa-Zhandry search algorithm, the authors consistently call it the advice state.

Locked hash access lets the state reproduce itself

The key technical device is the oracle M[H, E], which extends the verification oracle of Bostanci, Huang, and Vaikuntanathan with locked access to hash values. On input (i, x, c), it returns H_i(x) when c is a codeword in C whose hash equals BinEnc(i, x) concatenated with 0^(n-l) and (BinEnc(i, x), c) belongs to E, and returns the bottom symbol otherwise. When E is full, the advice state can unlock this access and thereby reproduce itself.

Cloning works because solving the code-intersection problem coherently lets the algorithm extract hash values while approximately preserving the advice. Fixing a coordinate i and preparing a uniform superposition over x in Sigma, the algorithm runs a purification of the biased Yamakawa-Zhandry algorithm on challenge BinEnc(i, x), queries M[H] with the resulting codeword, and uncomputes. On a successful output the oracle answer is always H_i(x) regardless of which valid codeword was produced, so the answer can be copied to a separate register. Repeating this polynomially many times with the same seed advice, and bounding accumulated disturbance by a hybrid argument, yields both preimage states for every coordinate with overwhelming probability. Assembling the registers gives a fresh advice state while preserving the original one, with fidelity 1 - negl(lambda).

Why classical witnesses still cannot match it

The lower bound follows the query-extraction approach behind the earlier QMA versus QCMA separations. Suppose a polynomial-query verifier with a classical witness distinguishes the full oracle M[H] from all allowed restricted oracles M[H, E]. A hybrid lemma forces its queries to place noticeable weight on valid pairs omitted from E, so measuring a uniformly selected query extracts a new valid pair with inverse-polynomial probability.

The crucial step is making extraction repeatable without oracle access. After extracting a pair, the argument inserts it into the simulated set E and restarts the verifier with the same classical witness. To keep this working, the simulator must reproduce the complete oracle answers on all previously inserted pairs, and unlike the earlier verification oracle, M also returns a hash bit. This is why the challenge encodes both the coordinate i and the symbol x as z = BinEnc(i, x): each stored valid pair then unlocks only one hash value H_i(x), which the no-query simulator guesses and records at a cost of only a factor of 1/2 per round. If the challenge encoded only x, the same stored codeword could unlock H_j(x) for every j, and simulating later executions could require guessing an entire n-bit hash column, a per-round loss too large for the argument.

Combining the witness-guessing cost with L extraction rounds gives a no-query guesser succeeding with probability at least 2^{-t(lambda)} times (1/poly(lambda))^L. On the other side, near-optimal list recovery of the code forces L distinct valid pairs to prescribe hash values at Omega(nL) distinct coordinate-symbol locations, and under the biased hash distribution any no-query guesser succeeds with probability at most (1 - lambda^{-4})^{Omega(nL)} = exp(-Omega(lambda L)). Choosing L large enough to absorb the witness-guessing cost makes the two bounds incompatible, so locked hash access enables efficient quantum cloning while preserving the classical-witness lower bound.

The same technique separates clonable advice and yields quantum fire

The technique extends from quantum proofs to quantum advice. The paper shows a classical-oracle separation between BQP/clonableqpoly and BQP/poly: relative to a classical oracle, polynomial-size advice that can be efficiently cloned is strictly more useful than polynomial-size classical advice. In both the proof and advice settings, efficient clonability does not eliminate the advantage of quantum information.

The construction also has cryptographic applications. Building on the Yamakawa-Zhandry algorithm and the good-code framework, the authors obtain a quantum fire scheme relative to a classical oracle satisfying strong clonability and untelegraphable security. This gives a direct proof of the classical-oracle quantum-fire existence result of Cakan, Goyal, and Shmueli, without claiming their stronger key-fire or interactive-security guarantees. The quantum fire mini-scheme uses the advice state as its flame: Spark samples a serial number and prepares |adv_H>, Clone applies the cloning algorithm, and Ver runs an amplified verifier that samples (i, a) uniformly, runs the biased Yamakawa-Zhandry algorithm on the flame, and accepts precisely when the oracle response differs from the bottom symbol.

What the separation does and does not establish

The separation is relativized: it holds relative to a constructed classical oracle O, not unconditionally. The paper's own framing places the result inside the relativized setting, strengthening the quantum-oracle separation of Nehoran and Zhandry to a classical oracle. The authors also conjecture that the code-intersection subset size problem of Bostanci, Huang, and Vaikuntanathan separates QMA from ClonableQMA relative to a classical oracle, but this is stated as a conjecture, not a proved result.

The quantum fire result is a mini-scheme with noninteractive untelegraphability; the stronger key-fire and interactive-security guarantees of the earlier construction are explicitly not asserted. The untelegraphability bound in Theorem 7 is stated for a uniform query-bounded adversary with no shared quantum state between stages, whose classical transcript has at most t bits, and it depends on parameters including the number of queries to H, P, and the target locked oracle. These conditions define the scope within which the cryptographic claim applies.

Sources used in this answer