Large deviation bounds for k -designs

DOI10.1098/RSPA.2009.0232zbMATH Open1186.82034arXiv0903.5236OpenAlexW3099659101MaRDI QIDQ3561997FDOQ3561997

Richard A. Low

Publication date: 19 May 2010

Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0903.5236

zbMATH Keywords

designsmeasure concentrationde-randomizationlarge deviation bounds

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Quantum computation (81P68) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Renormalization group methods in equilibrium statistical mechanics (82B28)

Cites Work

• Randomizing quantum states: constructions and applications

Cited In (11)

• Representations of the multi-qubit Clifford group
• Approximate Unitary n^2/3-Designs Give Rise to Quantum Channels with Super Additive Classical Holevo Capacity
• A partial derandomization of phaselift using spherical designs
• Exact exponent for atypicality of random quantum states
• DIAGONAL-UNITARY 2-DESIGN AND THEIR IMPLEMENTATIONS BY QUANTUM CIRCUITS
• Generating a statet-design by diagonal quantum circuits
• Low rank matrix recovery from rank one measurements
• An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs
• Thermalization and canonical typicality in translation-invariant quantum lattice systems
• Local random quantum circuits are approximate polynomial-designs
• Holographic duality between local Hamiltonians from random tensor networks

This page was built for publication: Large deviation bounds for k -designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3561997)