Quantum information · Theory
On Random Purifications of Isometries and Channels
arXiv:2611.04573v1 ↗PDF ↗Submitted 3 November 2026
- Question
- The random purification channel turns copies of a mixed state into copies of a random purification, and has driven recent results in learning and cryptography. Tang, Wright and Zhandry asked whether the same trick lifts queries one level up the hierarchy of maps: can queries to an isometry simulate queries to a random unitary completion, and can queries to a channel simulate queries to a random isometry dilation?
- Result
- The first holds approximately and the second fails badly. An efficient, stateful simulator makes one forward query to an isometry \(V:N\to M\) per call and emulates \(T\) queries to a Haar-random completion with trace-distance error \(O(T\sqrt{N/(M-T)})\). In contrast, two channel ensembles on dimension \(D\) can be told apart perfectly with two queries to any dilation, or with one quantum switch, while \(q\) channel queries give advantage only \(O(q^{3/2}/\sqrt D)\).
The paper in detail
A completion of an isometry \(V:\mathbf A\to\mathbf A\otimes\mathbf B\) is a unitary \(D\) with \(D(|x\rangle|0\rangle)=V|x\rangle\). A random completion fixes \(D\) on the image of \(\Pi_0\), the inputs of the form \(|x\rangle|0\rangle\), and maps the complement \(\Pi_0^\perp\) onto \(\Pi_V^\perp\) by a Haar-random unitary. Exact simulation is impossible: complex conjugation of an unknown unitary takes \(M-1\) queries, but for an isometry it cannot be done with any finite number. So the question is whether approximate simulation is possible, and at what error.
The simulator measures \(\{\Pi_0,\Pi_0^\perp\}\) coherently. On \(\Pi_0\) it applies \(V\). On the complement it applies a path-recording oracle, a stateful simulation of a Haar unitary on the whole space, and then uncomputes the flag by checking whether the state was produced by that oracle. The Haar output lands in \(\Pi_V^\perp\) except for a fraction \(N/M\) (\(2^{-m}\) for \(m\) ancilla qubits), so the error per query is about \(\sqrt{N/M}\). A second result removes the control: \(T\) controlled queries to \(e^{i\theta}V\), averaged over \(\theta\), can be simulated with \(T\) forward queries to \(V\), extending a theorem of Tang and Wright from unitaries.
Applications include lower bounds of \(\Omega(\sqrt{M/N})\) for isometry tomography, and \(\Omega(\min\{L,\sqrt{ND}\})\) for state-preparation unitaries whenever \(L\) copies are needed. The second bound covers PAC learning, state distinguishing, rank-\(r\) tomography and mixedness testing.
For channels, two dilation queries can reveal whether the two environment registers are in the symmetric or the antisymmetric subspace, which channel queries cannot. The construction uses hidden orthonormal pairs \(|\phi_{x,0}\rangle,|\phi_{x,1}\rangle\) for \(x\in[L]\). SAME and DIFF differ only by a sign \((-1)^b\), which shows up in the environment only after the second query. Theorem 7.9 bounds the channel-query advantage by \(8q^{3/2}/\sqrt L\), and a search version shows that even simulation error close to 1 needs exponentially many queries.
Transferable methods
Symmetric versus antisymmetric environments
Any two dilations of a channel differ by a unitary on the environment, so a single environment state carries no usable information. Correlations between the environments of two queries do, and a swap test detects them.
Take \(V|s\rangle=\frac1{\sqrt{2L}}\sum_{x,b}|x,\phi_{x,b}\rangle|x,b\rangle_E\) and \(V|x,\phi_{x,b}\rangle=\sigma^b|s\rangle|x,b\oplus1\rangle_E\), with \(\sigma=+1\) for SAME and \(-1\) for DIFF. Applying \(V\) twice to \(|s\rangle\) gives \[|s\rangle\otimes\frac1{\sqrt{2L}}\sum_x\big(|x,0\rangle_{E_1}|x,1\rangle_{E_2}+\sigma|x,1\rangle_{E_1}|x,0\rangle_{E_2}\big),\] which is symmetric under swapping \(E_1\) and \(E_2\) for SAME and antisymmetric for DIFF. A swap of the environments controlled by \(|+\rangle\) then sends the control to \(|+\rangle\) or \(|-\rangle\) with certainty. A different dilation \((I\otimes U)V\) acts as \(U\otimes U\) on the pair, which commutes with the swap, so the result holds for every dilation.
A channel query on \(|s\rangle\) returns a random \(|x,\phi_{x,b}\rangle\), and the sign appears only in the discarded environment. To see it, an algorithm would have to send the same hidden pair back coherently with a reference, but it does not know \(\phi_{x,b}\) and rarely gets the same \(x\) twice. This is why the advantage falls as \(L^{-1/2}\). The quantum switch \(\mathrm{Sw}[\Phi,\Phi]\) applied to \(|+\rangle|s\rangle\) performs exactly this controlled swap of environments, which gives the switch lower bound.
Editorial check: we built \(V_{\mathrm{SAME}}\) and \(V_{\mathrm{DIFF}}\) explicitly for \((L,d)=(2,3)\) and \((3,4)\), with Haar-random hidden pairs. Both are exact isometries, two queries return \(|s\rangle\) on the input register, and the joint environment state is exactly symmetric for SAME and exactly antisymmetric for DIFF.
How to reuse it
To separate access to a purification from access to the channel, look for properties of several environments jointly that are invariant under \(U^{\otimes k}\), such as irreducible representations of the symmetric group. A permutation test then detects them, and any process that coherently permutes the uses of the channel can implement that test.
Completing an isometry with a Haar oracle on the whole space
An exact random completion needs a Haar unitary onto \(\Pi_V^\perp\), which cannot be implemented without knowing \(V\)'s image. Replacing it by a Haar unitary on the whole space costs only the small overlap of a random state with the image.
The target is \(D^V_{\tilde U}=D^V\Pi_0+\tilde U\Pi_0^\perp\), with \(\tilde U\) Haar from \(\mathrm{Im}\,\Pi_0^\perp\) onto \(\mathrm{Im}\,\Pi_V^\perp\). Theorem 5.4 uses the contraction \(\widetilde W=PR\,\Pi_{M_1}+e^{i\theta}(I-PR\,PR^\dagger)D^V\Pi_{M_0}\), where \(PR\) is exact path recording on the whole \(M\)-dimensional space and \(\theta\) is a random global phase. The phase is then removed by the decontrol theorem. Each call uses at most one query to \(V\).
Both subspaces have rank \(M-N\). A Haar-random vector in dimension \(M\) has expected weight \(N/M\) on \(\mathrm{Im}\,\Pi_V\), so the whole-space oracle leaks an amplitude of order \(\sqrt{N/M}\) per call. After \(T\) calls, \(T\) dimensions are recorded, which gives the \(M-T\) in \(O(T\sqrt{N/(M-T)})\). For \(m\) ancilla qubits the per-query scale is \(2^{-m/2}\), for example \(0.03\) at \(m=10\). Editorial remark: this heuristic only explains the scaling. The proof uses an invariant subspace and the exact path-recording framework, which we did not check.
Editorial example: padding \(V\) to \(V\otimes|0^m\rangle\) is also an isometry and is equally useful to an algorithm. With \(m=40\), even \(T=10^6\) queries give an error bound of order \(10^6\cdot2^{-20}\approx1\). So the dimension needed grows as \(T^2\), and the error is small only when \(M\gg T^2N\).
How to reuse it
When a random object is needed only on an unknown subspace, sample it on the whole space and pay for the overlap with the known complement. Dimension padding makes that overlap as small as needed, at the price of ancillas.
Context & limitations
Why it matters. Isometry lower bounds now extend to algorithms that query arbitrary unitary completions, and copy-complexity lower bounds extend to forward access to state-preparation unitaries. The negative result settles a conjecture. Because the quantum switch reveals the same symmetry as two dilation queries, it also gives an \(\Omega(2^{n/3})\) query lower bound for simulating the switch to any error below ½, which is an exponential advantage for indefinite causal order.
Limitations. The completion simulator is useful only when \(M\gg N\), that is, for strongly expanding isometries or after padding with ancillas, and its error grows linearly in \(T\). The switch lower bound loses a cube in the dimension relative to the conjectured \(\Omega(2^n)\), and the channel construction is designed for the purpose. The author states that ChatGPT 5.6 Sol, 6 Astra and 6.1 Sol helped draft all proofs and developed the original proofs of Section 5.2. The model also turned a human sketch with advantage ¼ into the perfect two-query separation, and extended it to the switch.