We show how to efficiently generate pseudorandom states suitable for quantum information processing via cluster-state quantum computation. By reformulating pseudorandom algorithms in the cluster-state picture, we identify a strategy for optimizing pseudorandom circuits by properly choosing single-qubit rotations. A Markov chain analysis provides the tool for analyzing convergence rates to the Haar measure and finding the optimal single-qubit gate distribution. Our results may be viewed as an alternative construction of approximate unitary
2-designs.
Efficient methods for generating pseudorandomly 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 pseudorandom 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, though the rate for uniform convergence must decrease exponentially with the number of qubits. We describe how the rate of convergence for test functions associated with specific randomization tasks leads to weaker convergence conditions that may allow efficient random circuit constructions.
We consider quantum circuit models where the gates are drawn from arbitrary gate ensembles given by probabilistic distributions over certain gate sets and circuit architectures, which we call stochastic quantum circuits. Of main interest in this work is the speed of convergence of stochastic circuits with different gate ensembles and circuit architectures to unitary t-designs. A key motivation for this theory is the varying preference for different gates and circuit architectures in different practical scenarios. In particular, it provides a versatile framework for devising efficient circuits for implementing
t-designs and relevant applications including random circuit and scrambling experiments, as well as benchmarking the performance of gates and circuit architectures. We examine various important settings in depth. A key aspect of our study is an "ironed gadget" model, which allows us to systematically evaluate and compare the convergence efficiency of entangling gates and circuit architectures. Particularly notable results include i) gadgets of two-qubit gates with KAK coefficients
(4π−81arccos(51),8π,81arccos(51)) (which we call
χ gates) directly form exact 2- and 3-designs; ii) the iSWAP gate family achieves the best efficiency for convergence to 2-designs under mild conjectures with numerical evidence, even outperforming the Haar-random gate, for generic many-body circuits; iii) iSWAP + complete graph achieve the best efficiency for convergence to 2-designs among all graph circuits. A variety of numerical results are provided to complement our analysis. We also derive robustness guarantees for our analysis against gate perturbations. Additionally, we provide cursory analysis on gates with higher locality and found that the Margolus gate outperforms various other well-known gates.
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.
The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary t -designs. Unitary t -designs are probability distributions that mimic Haar randomness up to t th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth O(nt10.5) are approximate unitary t -designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by Ω(n−1t−9.5) . We improve this lower bound to Ω(n−1t−4−o(1)) , where the o(1) term goes to 0 as t→∞ . A direct consequence of this scaling is that random quantum circuits generate approximate unitary t -designs in depth O(nt5+o(1)) . Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.
Random many-body states and matrices are both a useful tool to model certain physical systems and an important asset for quantum computation. Realizing them, however, generally requires an exponential (in system size) amount of resources. Recent research has presented a way out by showing that one can generate random states and matrices, or more precisely a controlled approximation of them, by applying a quantum circuit built in terms of few-body unitary gates. Most of this research has been focussed on the case of quantum circuits composed by fully random unitary gates. Here we consider what happens for circuits that, instead, involve a minimal degree of randomness. Specifically, we concentrate on two different settings: (a) brickwork quantum circuits with a single one-qudit random matrix at a boundary; (b) brickwork quantum circuits with fixed interactions but random one-qudit gates everywhere. We show that, for any given initial state, (a) and (b) produce a distribution of states approaching the Haar distribution in the limit of large circuit depth. More precisely, we show that the moments of the distribution produced by our circuits can approximate the ones of the Haar distribution in a depth proportional to the system size. Interestingly we find that in both Cases (a) and (b) the relaxation to the Haar distribution occurs in two steps—this is in contrast with what happens in fully random circuits. Moreover, we show that choosing appropriately the fixed interactions, for example taking the local gate to be a dual-unitary gate with high enough entangling power, minimally random circuits produce a Haar random distribution more rapidly than fully random circuits. In particular, dual-unitary circuits with maximal entangling power—i.e. perfect tensors—appear to provide the optimal quantum state design preparation for any design number. Our results also suggest that the minimally random settings (a) and (b) give an optimal framework to prepare unitary designs, i.e., random unitary matrices.