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).
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form
Lφ(ρ)=tr(φ(dρ))/d, where
ρ is an unknown
d-dimensional quantum state and
φ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating
Lφ(ρ) from properties of
φ, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting.
The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is
Θ(εlog2(d)max{1,εlog2(d)}d2+ε2log2(d)), and the sample complexity of spectrum estimation is
Θ(ε2log2(d)max{1,ε2log2(d)}d2). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
We implement a procedure-based on the Wishart-Laguerre distribution-recently outlined by {Ż}yczkowski and Khvedelidze, Rogojin and Abgaryan, for the generation of random (complex or real)
N×N density matrices of rank
k≤N with respect to Hilbert-Schmidt (HS) measure. In the complex case, one commences with a Ginibre matrix
A of dimensions
k×k+2(N−k), while for a real scenario, one employs a Ginibre matrix
B of dimensions
k×k+1+2(N−k). Then, the
k×k product
AA† or
BBT is diagonalized-padded with zeros to size
N×N-and rotated, obtaining a random density matrix. Implementing the procedure for rank-4 rebit-retrit states, for 800 million Ginibre-matrix realizations, 6,192,047 were found separable, for a sample probability of .00774006-suggestive of an exact value
5000387=23⋅5432⋅43=.0774. A conjecture for the HS separability probability of rebit-retrit systems of full rank is
6561860=3822⋅5⋅43≈0.1310775 (the two-rebit counterpart has been proven to be
6429=2629). Subject to these conjectures, the ratio of the rank-4 to rank-6 probabilities would be
100000059049=26⋅56310≈0.059049, with the common factor 43 cancelling. As to the intermediate rank-5 probability, a 2006 theorem of Szarek, Bengtsson and {Ż}ycskowski informs us that it must be one-half the rank-6 probability-itself conjectured to be
100027=23⋅5333, while for rank 3 or less, the associated probabilities must be 0 by a 2009 result of Ruskai and Werner. We are led to re-examine a 2005 qubit-qutrit analysis of ours, in these regards, and now find evidence for a
267370=35⋅112⋅5⋅7≈0.0261878 rank-4 to rank-6 probability ratio.