Random Quantum Circuits are Approximate 2-designs

By Aram Wettroth Harrow, Richard Andrew Low. 2008

383 citations recorded by the source corpus.

Given a universal gate set on two qubits, it is well known that applying random gates from the set to random pairs of qubits will eventually yield an approximately Haar-distributed unitary. However, this requires exponential time. We show that random circuits of only polynomial length will approximate the first and second moments of the Haar distribution, thus forming approximate 1- and 2-designs. Previous constructions required longer circuits and worked only for specific gate sets. As a corollary of our main result, we also improve previous bounds on the convergence rate of random walks on the Clifford group.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/7bb088b05322415881f92a538587ebcad95fcc40

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Diagnosing Barren Plateaus with Tools from Quantum Optimal Control (2021, background): “[84] Aram W Harrow and Richard A Low, “Random quantum circuits are approximate 2-designs,” Communications in Mathematical Physics 291, 257–302 (2009).”
Fast Scram blers (2008, background): “See [8] for the study of more general cases and for subtleties of the definition of scrambling.”
Towards the fast scrambling conjecture (2011, background): “Other researchers have studied random quantum circuits, establishing that they are scramblers, but the question of whether they scramble in time O(log n) remains open [21–25].”
Barren plateaus in quantum neural network training landscapes (2018, background): “This motivates the concept of unitary t -designs [42–44], which satisfy the above properties for restricted classes of f ( U ), often requiring only modest polynomial resources.”
Variational quantum algorithms (2020, background): “The proof of this result relies on the fact that these unstructured ansatze become 2-designs when their depth grows polynomially with the number of qubits n [166, 167].”
Unitary designs from statistical mechanics in random quantum circuits. (2019, methodology): “From a quantum information perspective, random quantum circuits are low-depth constructions of unitary k -designs [1, 2], rapid information scramblers [3, 4], and essentially optimal decouplers [5].”
Connecting ansatz expressibility to gradient magnitudes and barren plateaus (2021, methodology): “We use the diamond norm here in line with the literature on εapproximate unitary designs [59]; however, alternative norms can be used (for a discussion, see [57]).”
Random Quantum Circuits (2022, background): “The transfer matrix TSS′(t) defines a Markov process on the space of basis operators, with local updates of the strings and string probabilities a(2)S (110, 129, 111, 130, 49, 50):”
Emergent Quantum State Designs from Individual Many-Body Wave Functions (2021, background): “A canonical example is that of random unitary circuits [14,36,38], where a set of random two-qubit unitary gates in a certain geometric arrangement are sequentially applied to simple initial states [for an example, see Fig.”
A semiclassical ramp in SYK and in gravity (2018, neutral): “” See for example [34, 35].”
Entanglement Membrane in Chaotic Many-Body Systems (2019, background): “The approach could also be used to study questions motivated by quantum information such as the emergence of the “design” property in random circuits with non-Haar–distributed gates [5, 17, 80–82].”