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 (36)

• Predicting Many Properties of a Quantum System from Very Few Measurements
• Randomized Benchmarking of Quantum Gates
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Scalable Noise Estimation with Random Unitary Operators
• Chaos and complexity by design
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• The Second Law of Quantum Complexity
• Quantum communication complexity of symmetric predicates
• Multiqubit Clifford groups are unitary 3-designs
• A decoupling approach to the quantum capacity
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Decoupling with unitary approximate two-designs
• The ghost in the radiation: Robust encodings of the black hole interior
• Unitary designs from statistical mechanics in random quantum circuits
• The Clifford group fails gracefully to be a unitary 4-design
• Mixing properties of stochastic quantum Hamiltonians
• 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
• Non-malleable encryption of quantum information
• Phase Retrieval Using Unitary 2-Designs
• On the explicit constructions of certain unitary $t$-designs
• 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