Approximate orthogonality of permutation operators, with application to quantum information

Abstract

Consider the $n!$ different unitary matrices that permute $n$ $d$-dimensional quantum systems. If $d\ge n$ then they are linearly independent. This paper discusses a sense in which they are approximately orthogonal (with respect to the Hilbert-Schmidt inner product) if $d\gg n^2$, or, in a different sense, if $d\gg n$. Previous work had shown pairwise approximate orthogonality of these matrices, but here we show a more collective statement, quantified in terms of the operator norm distance of the Gram matrix to the identity matrix. This simple point has several applications in quantum information and random matrix theory: (1) showing that random maximally entangled states resemble fully random states, (2) showing that Boson sampling output probabilities resemble those from Gaussian matrices, (3) improving the Eggeling-Werner scheme for multipartite data hiding, (4) proving that the product test of Harrow-Montanaro cannot be performed using LOCC without a large number of copies of the state to be tested, (5) proving that the purity of a quantum state also cannot be efficiently tested using LOCC, and (6, published separately) helping prove that poly-size random quantum circuits are poly-designs.

arXiv comment23 pages

References in corpus (16)

• Separability Criterion for Density Matrices
• Separability of Mixed States: Necessary and Sufficient Conditions
• Quantum computational advantage using photons
• Average Entropy of a Subsystem
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask)
• Aspects of generic entanglement
• Local random quantum circuits are approximate polynomial-designs
• Concurrence of mixed multi-partite quantum states
• Faithful Squashed Entanglement
• Hiding classical data in multi-partite quantum states
• Convergence to equilibrium under a random Hamiltonian
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Jucys-Murphy elements and Weingarten matrices
• Moments of a single entry of circular orthogonal ensembles and Weingarten calculus
• Moment Methods on compact groups: Weingarten calculus and its applications

Cited by in corpus (4)

• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Single-copy stabilizer testing
• Architectures and random properties of symplectic quantum circuits
• Moments of Quantum Channel Ensembles