Large Deviation Bounds for k-designs

Abstract

We present a technique for derandomising large deviation bounds of functions on the unitary group. We replace the Haar distribution with a pseudo-random distribution, a k-design. k-designs have the first k moments equal to those of the Haar distribution. The advantage of this is that (approximate) k-designs can be implemented efficiently, whereas Haar random unitaries cannot. We find large deviation bounds for unitaries chosen from a k-design and then illustrate this general technique with three applications. We first show that the von Neumann entropy of a pseudo-random state is almost maximal. Then we show that, if the dynamics of the universe produces a k-design, then suitably sized subsystems will be in the canonical state, as predicted by statistical mechanics. Finally we show that pseudo-random states are useless for measurement based quantum computation.

20 pages

References in corpus (9)

• Aspects of generic entanglement
• Randomizing quantum states: Constructions and applications
• Random Quantum Circuits are Approximate 2-designs
• Most quantum states are too entangled to be useful as computational resources
• Superdense coding of quantum states
• Are random pure states useful for quantum computation?
• Distribution of bipartite entanglement for random pure states
• On almost randomizing channels with a short Kraus decomposition
• Efficient Quantum Tensor Product Expanders and k-designs

Cited by in corpus (35)

• Local random quantum circuits are approximate polynomial-designs
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• A Partial Derandomization of PhaseLift using Spherical Designs
• Thermalization and canonical typicality in translation-invariant quantum lattice systems
• Random bosonic states for robust quantum metrology
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Typicality in random matrix product states
• Efficient Quantum Pseudorandomness
• Statistical properties of random matrix product states
• Quantum circuits for exact unitary $t$-designs and applications to higher-order randomized benchmarking
• Almost Markovian processes from closed dynamics
• Generating a state $t$-design by diagonal quantum circuits
• Random Matrix Theory of the Isospectral twirling
• Diagonal quantum circuits: their computational power and applications
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Shadow tomography from emergent state designs in analog quantum simulators
• Markovianization with approximate unitary designs
• Operational Metric for Quantum Chaos and the Corresponding Spatiotemporal Entanglement Structure
• Local random quantum circuits are approximate polynomial-designs - numerical results
• Representations of the multi-qubit Clifford group
• Diagonal-unitary 2-designs and their implementations by quantum circuits
• Simulation of quantum optics by coherent state decomposition
• Fluctuations of subsystem entropies at late times
• Holographic duality between local Hamiltonians from random tensor networks
• Phase Retrieval Using Unitary 2-Designs
• On the generic increase of observational entropy in isolated systems
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Saturation and recurrence of quantum complexity in random local quantum dynamics
• Efficient quantum tensor product expanders and unitary t-designs via the zigzag product
• Thermal states of random quantum many-body systems
• A quantum Johnson-Lindenstrauss lemma via unitary t-designs
• Discord in relation to resource states for measurement-based quantum computation
• Approximate unitary $n^{2/3}$-designs give rise to quantum channels with super additive classical Holevo capacity
• More global randomness from less-random local gates