Acorn tricks turn weak quantum resources into stronger "randomized" ones. A recent example is the random purification channel, which turns $t$ copies of a mixed state into $t$ copies of a random purification. We ask whether analogous techniques can turn queries to an isometry into queries to a random unitary completion, or queries to a quantum channel into queries to a random isometry dilation.
For an isometry from dimension $N$ to dimension $M$, we give an efficient, stateful simulator for $T$ sequential, forward queries to a fixed Haar random unitary completion. It uses at most one forward isometry query per simulated call, with total trace-distance error $O(T\sqrt{N/(M-T)})$. This lifts isometry query lower bounds to arbitrary unitary completions, and copy complexity lower bounds to forward access to state preparation unitaries, with dimension-dependent loss that can be made arbitrarily small for most applications.
Conversely, we construct two distributions on quantum channels distinguishable exactly with two queries to an arbitrary dilation, but requiring exponentially many channel queries for nonnegligible advantage. This rules out efficient simulation of random channel dilations. Our technique also shows that approximating the quantum switch to any constant error below $1/2$ requires exponentially many channel queries, even for identical channels, giving an exponential query advantage for indefinite causal order and improving on Bavaresco et al. (2025).
Finally, we show how to "decontrol" controlled forward access to an isometry: any algorithm making controlled queries to $φV$ for a random phase $φ$ can be transformed into one using the same number of uncontrolled forward queries to $V$, generalizing the analogous result for unitaries.
AI Summary
The paper asks whether forward queries to an isometry or quantum channel can simulate queries to a randomly chosen unitary completion or Stinespring dilation, respectively. It gives an approximate positive result for isometries and an exponential query separation for channels.
For an isometry from dimension $N$ to $M$, an efficient stateful simulator reproduces any $T$ sequential forward queries to a fixed Haar-random unitary completion with trace-distance error $O(T\sqrt{N/(M-T)})$, using at most one isometry query per simulated call. The construction compares exact path-recording oracles on the full output space and the unknown complementary subspace. A supporting result removes controlled isometry queries exactly after averaging over one shared random global phase. Applications lift copy-complexity lower bounds to forward state-preparation queries, yielding $\Omega(\min\{L,\sqrt{ND}\})$ queries from an $\Omega(L)$ copy lower bound, with purification dimension $D$.
Conversely, two channel ensembles are perfectly distinguishable using two adaptive queries to any fixed dilation, while $q$ ordinary channel queries give advantage at most $O(q^{3/2}/\sqrt D)$ in channel dimension $D$. The construction encodes the distinction in symmetric versus antisymmetric environment correlations; a hybrid argument bounds information obtainable without environment access. The same test implies that approximating the quantum switch to any fixed error below $1/2$ requires $\Omega(2^{n/3})$ channel queries, even for identical $n$-qubit channels.
The positive simulation is approximate, dimension-dependent, and restricted to forward access. The switch bound leaves a cubic-in-dimension gap from the stated $\Omega(2^n)$ conjecture; error $1/2$ is achievable with one query to each channel.
Likely largely AI-generatedAI use disclosed
AI assisted with drafting technical details for all proofs, with the final results being both independently verified and substantially rewritten.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Acorn tricks turn weak quantum resources into stronger "randomized" ones. A recent example is the random purification channel, which turns t copies of a mixed state into t copies of a random purification. We ask whether analogous techniques can turn queries to an isometry into queries to a random unitary completion, or queries to a quantum channel into queries to a random isometry dilation.
For an isometry from dimension N to dimension M, we give an efficient, stateful simulator for T sequential, forward queries to a fixed Haar random unitary completion. It uses at most one forward isometry query per simulated call, with total trace-distance error O(TN/(M−T)). This lifts isometry query lower bounds to arbitrary unitary completions, and copy complexity lower bounds to forward access to state preparation unitaries, with dimension-dependent loss that can be made arbitrarily small for most applications.
Conversely, we construct two distributions on quantum channels distinguishable exactly with two queries to an arbitrary dilation, but requiring exponentially many channel queries for nonnegligible advantage. This rules out efficient simulation of random channel dilations. Our technique also shows that approximating the quantum switch to any constant error below 1/2 requires exponentially many channel queries, even for identical channels, giving an exponential query advantage for indefinite causal order and improving on Bavaresco et al. (2025).
Finally, we show how to "decontrol" controlled forward access to an isometry: any algorithm making controlled queries to φV for a random phase φ can be transformed into one using the same number of uncontrolled forward queries to V, generalizing the analogous result for unitaries.
The paper asks whether forward queries to an isometry or quantum channel can simulate queries to a randomly chosen unitary completion or Stinespring dilation, respectively. It gives an approximate positive result for isometries and an exponential query separation for channels.
For an isometry from dimension N to M, an efficient stateful simulator reproduces any T sequential forward queries to a fixed Haar-random unitary completion with trace-distance error O(TN/(M−T)), using at most one isometry query per simulated call. The construction compares exact path-recording oracles on the full output space and the unknown complementary subspace. A supporting result removes controlled isometry queries exactly after averaging over one shared random global phase. Applications lift copy-complexity lower bounds to forward state-preparation queries, yielding Ω(min{L,ND}) queries from an Ω(L) copy lower bound, with purification dimension D.
Conversely, two channel ensembles are perfectly distinguishable using two adaptive queries to any fixed dilation, while q ordinary channel queries give advantage at most O(q3/2/D) in channel dimension D. The construction encodes the distinction in symmetric versus antisymmetric environment correlations; a hybrid argument bounds information obtainable without environment access. The same test implies that approximating the quantum switch to any fixed error below 1/2 requires Ω(2n/3) channel queries, even for identical n-qubit channels.
The positive simulation is approximate, dimension-dependent, and restricted to forward access. The switch bound leaves a cubic-in-dimension gap from the stated Ω(2n) conjecture; error 1/2 is achievable with one query to each channel.
We present a quantum circuit that implements the random dilation superchannel, transforming parallel queries of an unknown quantum channel into the same number of parallel queries of a randomly chosen dilation isometry of the input channel. This is a natural generalization of the random purification channel, that transforms copies of an unknown mixed state to copies of a randomly chosen purification state. The circuit complexity of our construction is O(poly(n,logdI,logdO)), where n is the number of queries and dI and dO are the input and output dimensions of the input channel, respectively. This random dilation superchannel is extended to the sequential queries approximately, by transforming the parallel random dilation isometry into sequential random dilation unitaries with O(poly(dI)) overhead in the number of queries. We also show that our results can be further extended to the case of quantum superchannels. On the other hand, we show a no-go theorem on the exact random dilation of sequential queries with o(poly(min{dI,dO})) query overhead, showcasing a fundamental difference between the parallel and sequential cases. As an application, we show an efficient storage-and-retrieval of an unknown quantum channel, which improves the program cost exponentially in the retrieval error ε. For the case where the Kraus rank r is the least possible (i.e., r=dI/dO), we show quantum circuits that transform n parallel queries of an unknown quantum channel Λ to Θ(nα) parallel queries of Λ for any α<2 approximately, and implement its Petz recovery map for the maximally mixed reference state probabilistically and exactly.
The recently introduced random purification channel, which converts n copies of an arbitrary mixed quantum state into n copies of the same uniformly random purification, has emerged as a powerful tool in quantum information theory. Motivated by this development, we introduce a channel-level analogue, which we call the random Stinespring superchannel. This consists in a procedure to transform n parallel queries of an arbitrary quantum channel into n parallel queries of the same uniformly random Stinespring isometry, via universal encoding and decoding operations that are efficiently implementable. When the channel is promised to have Choi rank at most r, the procedure can be tailored to yield a Stinespring environment of dimension r. We present two applications of the random Stinespring superchannel, one in quantum Shannon theory and one in quantum learning theory. In quantum Shannon theory, we prove a channel-level analogue of Uhlmann's theorem for quantum divergences. In quantum learning theory, our construction shows that tomography of quantum channels reduces to tomography of isometries. This yields a simple channel learning algorithm, based on existing isometry learning protocols, that matches the performance of the two recently proposed channel tomography algorithms. Complementarily, whereas the optimality of these algorithms had previously been established only up to a logarithmic factor in the dimension, we close this gap by removing this logarithmic factor from the lower bound. Taken together, our results fully establish the optimality of these recently introduced channel learning algorithms, showing that the optimal query complexity of learning a quantum channel with input dimension dA, output dimension dB, and Choi rank r is Θ(dAdBr).
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every n-qubit unitary U is computable by efficient quantum circuits relative to some classical oracle f=fU depending on U. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly(n) parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries P∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries ∣x⟩↦αx∣x⟩, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.
We study the estimation of an unknown quantum channel E with input dimension d1, output dimension d2 and Kraus rank at most r. We establish a connection between the query complexities in two models: (i) access to E, and (ii) access to a random dilation of E. Specifically, we show that for parallel (possibly coherent) testers, access to dilations does not help. This is proved by constructing a local tester that uses n queries to E yet faithfully simulates the tester with n queries to a random dilation. As application, we show that:
- O(rd1d2/ε2) queries to E suffice for channel tomography to within diamond norm error ε.
Moreover, when rd2=d1, we show that the Heisenberg scaling O(1/ε) can be achieved, even if E is not a unitary channel:
- O(min{d12.5/ε,d12/ε2}) queries to E suffice for channel tomography to within diamond norm error ε, and O(d12/ε) queries suffice for the case of Choi state trace norm error ε.
- O(min{d11.5/ε,d1/ε2}) queries to E suffice for tomography of the mixed state E(∣0⟩⟨0∣) to within trace norm error ε.
The random purification channel maps n copies of any mixed quantum state to n copies of a random purification of the state. We generalize this construction to arbitrary symmetries: for any group G of unitaries, we construct a quantum channel that maps states contained in the algebra generated by G to random purifications obtained by twirling over G. In addition to giving a surprisingly concise proof of the original random purification theorem, our result implies the existence of fermionic and bosonic Gaussian purification channels. As applications, we obtain the first tomography protocol for fermionic Gaussian states that scales optimally with the number of modes and the error, as well as an improved property test for this class of states.
We give a natural problem over input quantum oracles U which cannot be solved with exponentially many black-box queries to U and U†, but which can be solved with constant many queries to U and U∗, or U and UT. We also demonstrate a quantum commitment scheme that is secure against adversaries that query only U and U†, but is insecure if the adversary can query U∗. These results show that conjugate and transpose queries do give more power to quantum algorithms, lending credence to the idea put forth by Zhandry that cryptographic primitives should prove security against these forms of queries. Our key lemma is that any circuit using q forward and inverse queries to a state preparation unitary for a state σ can be simulated to ε error with n=O(q2/ε) copies of σ. Consequently, for decision tasks, algorithms using (forward and inverse) state preparation queries only ever perform quadratically better than sample access. We also identify a motif, which we call the "acorn trick", where generically strengthening a quantum resource can be possible if the output is allowed to be random, bypassing no-go theorems for deterministic algorithms. We demonstrate this idea for several settings, including controlization and purification.