Efficient Unitary T-designs from Random Sums

Abstract

Unitary $T$-designs play an important role in quantum information, with diverse applications in quantum algorithms, benchmarking, tomography, and communication. Until now, the most efficient construction of unitary $T$-designs for $n$-qudit systems has been via random local quantum circuits, which have been shown to converge to approximate $T$-designs in the diamond norm using $O(T^{5+o(1)}{n}^2)$ quantum gates. In this work, we provide a new construction of $T$-designs via random matrix theory using $\tilde{O}(T^2{n}^2)$ quantum gates. Our construction leverages two key ideas. First, in the spirit of central limit theorems, we approximate the Gaussian Unitary Ensemble (GUE) by an i.i.d. sum of random Hermitian matrices. Second, we show that the product of just two exponentiated GUE matrices is already approximately Haar random. Thus, multiplying two exponentiated sums over rather simple random matrices yields a unitary $T$-design, via Hamiltonian simulation. A central feature of our proof is a new connection between the polynomial method in quantum query complexity and the large-dimension ($N$) expansion in random matrix theory. In particular, we show that the polynomial method provides exponentially improved bounds on the high moments of certain random matrix ensembles, without requiring intricate Weingarten calculations. In doing so, we define and solve a new type of moment problem on the unit circle, asking whether a finite number of equally weighted points, corresponding to eigenvalues of unitary matrices, can reproduce a given set of moments.

112 pages, 4 figures

References in corpus (16)

• Randomized Benchmarking of Quantum Gates
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Unitary designs from statistical mechanics in random quantum circuits
• The Clifford group fails gracefully to be a unitary 4-design
• Quantum Cryptography in Algorithmica
• Quantum circuits for exact unitary $t$-designs and applications to higher-order randomized benchmarking
• Efficient Quantum Tensor Product Expanders and k-designs
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Clifford Group and Unitary Designs under Symmetry
• Sparse random Hamiltonians are quantumly easy
• Incompressibility and spectral gaps of random circuits
• Pseudorandom and Pseudoentangled States from Subset States
• Pseudorandomness from Subset States
• A new approach to strong convergence
• The Complexity of Learning (Pseudo)random Dynamics of Black Holes and Other Chaotic Systems

Cited by in corpus (10)

• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Computing exact moments of local random quantum circuits via tensor networks
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Designs from magic-augmented Clifford circuits
• Quantum-Computable One-Way Functions without One-Way Functions
• Efficient approximate unitary designs from random Pauli rotations
• Random Circuits in the Black Hole Interior
• On Computational Complexity of Unitary and State Design Properties
• Bridging Classical and Quantum Information Scrambling with the Operator Entanglement Spectrum
• Moments of Quantum Channel Ensembles