Large deviation bounds for k-designs

DOI10.1098/RSPA.2009.0232MaRDI QIDQ3561997zbMATH OpenOpenAlexFDO

Authors 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)

Full work available at URL https://arxiv.org/abs/0903.5236, http://rspa.royalsocietypublishing.org/content/vol465/issue2111/

zbMATH Keywords

de-randomizationdesignslarge deviation boundsmeasure concentration

Mathematics Subject Classification ID

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

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.

Recommendations

• Evenly distributed unitaries: On the structure of unitary designs
• Random quantum circuits are approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Implementing unitary 2-designs using random diagonal-unitary matrices

Cites work

• Randomizing quantum states: constructions and applications

Cited in

(14)

• Holographic duality between local Hamiltonians from random tensor networks
• A partial derandomization of phaselift using spherical designs
• An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs
• Low rank matrix recovery from rank one measurements
• Representations of the multi-qubit Clifford group
• Thermalization and canonical typicality in translation-invariant quantum lattice systems
• Local random quantum circuits are approximate polynomial-designs
• Approximate Unitary n^2/3-Designs Give Rise to Quantum Channels with Super Additive Classical Holevo Capacity
• Generating a state t-design by diagonal quantum circuits
• Diagonal-unitary 2-design and their implementations by quantum circuits
• Exact exponent for atypicality of random quantum states
• Approximate unitary k-designs from shallow, low-communication circuits
• Quantum pseudoentanglement
• On the complexity of quantum states and circuits from the orthogonal and symplectic groups

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)