One Haar-random state handed out many times
Whether the correlation between copies of a single random state is visible in the classical outputs, at polynomial copy count
Motivation
Quantum security proofs constantly need to move between two ways of supplying random states to a collection of algorithms: draw a fresh Haar-random state for each, or draw one and hand out copies. The first makes the algorithms’ outputs independent; the second correlates them, since they all descend from the same underlying state. If the two are statistically indistinguishable at polynomial copy count, a proof written in the easy model transfers to the hard one for free.
Nobody appears to have written down the general statement. What gets written down instead, repeatedly, is whatever weaker version the proof at hand needs — a pointwise domination bound here, a collision bound there — each proved from scratch. A clean version with an explicit bound in the copy count and the number of qubits would replace them.
The statement is entirely information-theoretic. There is no computational assumption, no efficiency restriction on the algorithm, and no cryptographic primitive in it: it is a fact about the \(t\)-copy Haar ensemble, or it is false.
Provenance and history
Amit Behera, Zvika Brakerski, Or Sattath and Omri Shmueli, Pseudorandomness with Proof of Destruction and Applications (IACR ePrint 2023/543, TCC 2023), state the conjecture in their Open Problems section, together with an unusually clear account of its status: “We could not prove nor find any previous work in the literature that proves or even formalizes this conjecture.”
What they prove instead is their Lemma 2, a pointwise domination bound: the correlated distribution never exceeds the product distribution by more than a factor \(N^{t}/\binom{N+t-1}{t}\), which for \(t\) small against \(N = 2^n\) is about \(t\) factorial. In the special case where the algorithm measures in the computational basis the proof is two lines of symmetric-subspace counting — for each outcome tuple exactly one symmetric type contributes — and being pointwise it cannot produce a total variation bound at all. The lemma is enough for the paper’s unforgeability and collision-freeness arguments, which need to carry a small-probability bad event from one experiment to the other, and the authors say plainly that it is a stand-in: “We believe that the distributions are in fact, statistically close due to the strong concentration of the Haar measure, but we have not been able to prove it.”
The surrounding literature has statements of a similar flavour but not this one. Ji, Liu and Song’s conjecture that a uniform superposition with random binary phase is statistically indistinguishable from a Haar-random state, proved by Brakerski and Shmueli, compares an efficiently generated family against the Haar ensemble. This one compares the Haar ensemble against itself, in two different couplings.
Parameter lattice
What is known about the correlated-versus-product comparison.
| Regime | Result | Status |
|---|---|---|
| Pointwise ratio, any algorithm, any polynomial \(t\) | \(\le N^{t}/\binom{N+t-1}{t}\) | proved (Lemma 2) |
| Total variation, single-bit output | negligible | follows from concentration |
| Total variation, any classical output, polynomial \(t\) | negligible | c/0104 — open |
| Total variation, superpolynomial \(t\) | — | false for \(t\) comparable to \(N\) |
| Algorithms restricted to projective measurement on the input | — | unstated — the source flags ancillae as the difficulty |