We develop the concept of a unitary
t-design as a means of expressing operationally useful subsets of the stochastic properties of the uniform (Haar) measure on the unitary group
U(2n) on
n qubits. In particular, sets of unitaries forming 2-designs have wide applicability to quantum information protocols. We devise an
O(n)-size in-place circuit construction for an approximate unitary 2-design. We then show that this can be used to construct an efficient protocol for experimentally characterizing the fidelity of a quantum process on
n qubits with quantum circuits of size
O(n) without requiring any ancilla qubits, thereby improving upon previous approaches.
Shadow estimation is a powerful framework for predicting quantum properties from randomized measurements. While
3-design protocols achieve optimal worst-case performance, the minimal number of measurement bases required for such optimality has remained open. Here we prove that
Θ(d2) measurement bases are both necessary and sufficient for worst-case optimal shadow estimation and construct an explicit basis family. In stark contrast, any state
2-design already suffices for average-case optimality: the mean squared shadow norm of normalized observables is bounded by a universal constant, and we prove strong concentration for Haar-random states, yielding constant sample complexity for generic pure-state fidelity estimation. Easily implementable
2-designs -- from mutually unbiased bases, cyclic measurements, or shallow
O(logn)-depth circuits -- enable optimal average-case protocols with remarkably simple measurement strategies. Our results establish a fundamental complexity separation: worst-case estimation requires
Θ(d2) bases, whereas average-case performance requires only
Θ(d) bases, with broad implications for quantum information theory and near-term experiments.
Efficient methods for generating pseudo-randomly distributed unitary operators are needed for the practical application of Haar distributed random operators in quantum communication and noise estimation protocols. We develop a theoretical framework for analyzing pseudo-random ensembles generated through a random circuit composition. We prove that the measure over random circuits converges exponentially (with increasing circuit length) to the uniform (Haar) measure on the unitary group and describe how the rate of convergence may be calculated for specific applications.
Approximate unitary designs reproduce the statistics of Haar-random unitaries to a given order and accuracy. Recent constructions realize such designs with logarithmic-depth circuits, enabling shallow measurement protocols for various quantum state-learning tasks while preserving performance. These results raise the question of whether approximate designs can replace exact designs more generally. We show that even exponentially small design error need not preserve the learning guarantees of exact designs. This motivates deriving learning guarantees directly from the measurement circuit structure. For observable estimation with classical shadows, we prove that logarithmic-depth two-layer Clifford circuits yield an unbiased estimator matching the global Clifford variance scaling for every state and Hermitian observable. Beyond observable estimation, this bound allows shallow measurements to retain global Clifford guarantees for other tasks, including setting-efficient tomography, mixed-state metrology, and stabilizer structure learning. We complement these statistical guarantees with a compact, exact tensor-network representation of the inverse shadow channel. When measurement bases are reused, approximate unitary designs of arbitrarily high order need not uniformly match the Haar variance in the many-shot limit. For the all-to-all random two-local circuits considered, doing so requires nearly linear depth. Together, our results reveal the capabilities and limitations of shallow quantum state learning, highlighting the distinction between approximating Haar randomness and reproducing its learning guarantees.
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong
ε-approximate unitary
k-design on
n qubits, the distribution of each output probability is within
O(k−1/2(1+k/2n)−1/2+ε) in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters
1 and
2n−1. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance
O(k−1/2+ε). Every strong
ε-approximate unitary
k-design invariant on
logk+O(1) qubits achieves error
2−Ω(k)+O(ε) in Kolmogorov distance and
2−Ω(k)+O(εlog(2/ε)) in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong
ε-approximate
k-design is concentrated around its Haar value
n−Θ(1): its mean differs from the Haar mean by
O(k−1/4+ε1/2) and its standard deviation is
O(2−n/2+k−1/8+ε1/4). Consequently, a trusted device sampling such circuits generates
n−O(1) bits of entropy per sample, which makes them useful for random number generation.
We extend the recent bounds of Sason and Verd\'u relating R\'enyi entropy and Bayesian hypothesis testing (arXiv:1701.01974.) to the quantum domain and show that they have a number of different applications. First, we obtain a sharper bound relating the optimal probability of correctly distinguishing elements of an ensemble of states to that of the pretty good measurement, and an analogous bound for optimal and pretty good entanglement recovery. Second, we obtain bounds relating optimal guessing and entanglement recovery to the fidelity of the state with a product state, which then leads to tight tripartite uncertainty and monogamy relations.