Classical Outputs from One Haar-Random State Look Like Outputs from Many
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
Hand an algorithm one copy of a random quantum state and let it print a classical string. Do this \(t\) times. There are two ways to supply the states: draw \(t\) independent Haar-random states, or draw one Haar-random state and hand out \(t\) copies of it. In the second the printed strings are correlated — they all come from the same underlying state. The conjecture is that no one can tell: for any algorithm and any polynomial \(t\), the two joint distributions of classical strings are within negligible total variation distance. It is entirely information-theoretic, with no computational assumption anywhere, and the source could neither prove it nor find it in the literature.
View PDF · LaTeX source · Formal statement — not yet formalized
The setting. Let \(\mathcal{H}_n\) be the state space of \(n\) qubits, of dimension \(N = 2^n\), and \(\mu_{\mathcal{H}_n}\) the Haar measure on its pure states. Let \(\mathcal{A}\) be any algorithm taking a single \(n\)-qubit state and outputting a classical string. It may be an arbitrary quantum channel followed by a measurement, may use ancillae, and is not required to be efficient.
Two distributions over \(t\)-tuples of classical strings:
- the product distribution, from \(t\) independent \(|\phi_1\rangle,\dots,|\phi_t\rangle \sim \mu_{\mathcal{H}_n}\), outputting \(\mathcal{A}(|\phi_1\rangle) \otimes \cdots \otimes \mathcal{A}(|\phi_t\rangle)\);
- the correlated distribution, from a single \(|\phi\rangle \sim \mu_{\mathcal{H}_n}\), outputting \(\mathcal{A}(|\phi\rangle) \otimes \cdots \otimes \mathcal{A}(|\phi\rangle)\) with \(t\) independent invocations each receiving one copy of the same state.
Conjecture (the source’s own sentence). For any algorithm \(\mathcal{A}\) that outputs a classical string, and any polynomial \(t = t(n)\), the total variation distance between the product and correlated distributions above is negligible in \(n\). Verbatim, page 10: “For any algorithm \(\mathcal{A}\) that outputs a classical string, and any polynomial \(t = t(n)\), the total variation distance between \(\mathcal{A}(|\phi_1\rangle) \otimes \cdots \otimes \mathcal{A}(|\phi_t\rangle)\), where \(|\phi_1\rangle,\dots,|\phi_t\rangle \sim \mu_{\mathcal{H}_n}\) and \(\mathcal{A}(|\phi\rangle) \otimes \cdots \otimes \mathcal{A}(|\phi\rangle)\), where the same state \(|\phi\rangle \sim \mu_{\mathcal{H}_n}\) is used in all the algorithms, is negligible in \(n\).” Only the names are this page’s; the mathematics is unchanged.
Why the two might differ. If \(\mathcal{A}\) measures in the computational basis, the correlated experiment draws \(t\) samples from one Porter-Thomas distribution while the product experiment draws each from a different one. Second moments already separate the two families — the collision probability of two outcomes is of order \(2/N\) in the correlated case and \(1/N\) in the product case. The question is whether such discrepancies stay below negligible in total variation once summed over all pairs and beyond, at polynomial \(t\).
Status. Verbatim, page 10: “We could not prove nor find any previous work in the literature that proves or even formalizes this conjecture.” And on why it is worth having: “We think this is an interesting open question on its own, and if proven, this result can be a useful tool for quantum cryptography.”
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open, with a strictly weaker statement proved and the gap stated by the source.
What is proved (the source’s Lemma 2). For \(\mathcal{A}\) outputting \(c\)-bit strings, every \(t \in \mathrm{poly}(\lambda)\) and all \(a_1,\dots,a_t\), \[\Pr\nolimits_{\mathrm{corr}}[(f_1,\dots,f_t) = (a_1,\dots,a_t)] \le \frac{N^{t}}{\binom{N+t-1}{t}} \cdot \Pr\nolimits_{\mathrm{prod}}[(f_1,\dots,f_t) = (a_1,\dots,a_t)].\]
Why that is much weaker. For \(t \ll N\) the factor \(N^t/\binom{N+t-1}{t}\) is about \(t\) factorial. The lemma therefore says only that the correlated distribution never exceeds the product distribution by more than a factorial factor, pointwise. That transfers a bound “this bad event has probability \(\eta\) under the product distribution” into “at most \(t\) factorial times \(\eta\) under the correlated one”, which is what the source’s unforgeability and collision-freeness arguments need. It says nothing about total variation, which the factorial swamps.
The source says so itself, in a footnote on page 18: “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 lemma is a weaker version of this statement, but it suffices for our purposes.”
Why the existing proof cannot be pushed further. In the special case where \(\mathcal{A}\) is a computational-basis measurement, Lemma 2 is two lines of symmetric-subspace counting: for each outcome tuple exactly one symmetric type contributes, giving probability at most \(1/\binom{N+t-1}{t}\) in the correlated case and exactly \(N^{-t}\) in the product case. Being pointwise, that argument cannot give more than a ratio.
Three sources of difficulty. The algorithm is arbitrary and may use ancillae, so the map on the input register is not unitary — the source flags exactly this elsewhere, “the destruct algorithms may use ancillae qubits, and therefore the overall process becomes non-unitary, even before the measurement” — and non-unitary processing does not preserve Haar-randomness of a residual state, so a reduction to the projective case is not immediate. The output may be long, so higher-order discrepancies must all be controlled, not just the first. And the bound must be uniform over all algorithms with no efficiency restriction, making this a statement about the \(t\)-copy Haar ensemble rather than about what a bounded observer can extract.
Checked against the literature, 2026-08-28. No proof or refutation found. The check was targeted at the pseudorandom-states line, where a statement of this shape would most plausibly already exist, rather than exhaustive over quantum information theory — which is the first place a would-be prover should look harder than this page did.
Why a clean version would get used. This is the kind of statement that gets reproved ad hoc, in a weaker form each time, wherever a security proof needs to move between one shared Haar-random state and many independent ones. A version with an explicit bound in \(t\) and \(n\) would replace those. The source’s own Lemma 2 is one such ad hoc weaker form.
The refutation is at least as interesting. It would exhibit an algorithm whose classical output distinguishes “one state, \(t\) copies” from “\(t\) states” at polynomial \(t\) — a statement about the \(t\)-copy Haar ensemble nobody currently expects.
Neighbours in the same list, not published here. The source’s Open Problems section also asks whether PRSPD implies short-input PRFSPD, whether separations from one-way functions extend to the proof-of-destruction variants, and whether its construction satisfies quantum adaptive pseudorandomness. Those are separate questions about cryptographic primitives; this one is a statement about the Haar measure and stands alone.
What a reviewer should be suspicious of, in order. First, which distribution is which — the correlated one is a single state handed out \(t\) times, and the source’s Definition 3 introduces the two in the reverse order from the conjecture’s sentence. Second, the quantifier on \(\mathcal{A}\): every algorithm, not every efficient one. Third, whether a claimed proof covers algorithms with ancillae, since restricting to projective measurements on the input register leaves out the case the source names as the difficulty.