Efficient unitary designs and pseudorandom unitaries from permutations

Abstract

In this work we give an efficient construction of unitary $k$-designs using $\tilde{O}(k\cdot poly(n))$ quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over $S(N)$ to random unitaries over $U(N)$ for $N=2^n$. In particular, we show that products of exponentiated sums of $S(N)$ permutations with random phases approximately match the first $2^{\Omega (n)}$ moments of the Haar measure. By substituting either $\tilde{O}(k)$-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-$N$ by interpolating from the much simpler large-$N$ limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-$N$ expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension $N$.

70 pages, 11 figures. v2: minor edits

References in corpus (35)

• 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
• 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
• Clifford Group and Unitary Designs under Symmetry
• On the explicit constructions of certain unitary $t$-designs
• 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