Efficient Quantum Tensor Product Expanders and k-designs

Abstract

Quantum expanders are a quantum analogue of expanders, and k-tensor product expanders are a generalisation to graphs that randomise k correlated walkers. Here we give an efficient construction of constant-degree, constant-gap quantum k-tensor product expanders. The key ingredients are an efficient classical tensor product expander and the quantum Fourier transform. Our construction works whenever k=O(n/log n), where n is the number of qubits. An immediate corollary of this result is an efficient construction of an approximate unitary k-design, which is a quantum analogue of an approximate k-wise independent function, on n qubits for any k=O(n/log n). Previously, no efficient constructions were known for k>2, while state designs, of which unitary designs are a generalisation, were constructed efficiently in [Ambainis, Emerson 2007].

16 pages, typo in references fixed

References in corpus (6)

• Randomizing quantum states: Constructions and applications
• Random Quantum Circuits are Approximate 2-designs
• Efficient Quantum Tensor Product Expanders and k-designs
• Quantum expanders and the quantum entropy difference problem
• Symmetric Groups and Expanders
• Simple Permutations Mix Even Better

Cited by in corpus (21)

• Onset of Random Matrix Behavior in Scrambling Systems
• Universal behavior beyond multifractality of wave-functions at measurement--induced phase transitions
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Models of quantum complexity growth
• Unitary designs and codes
• Driven quantum dynamics: will it blend?
• Large Deviation Bounds for k-designs
• Efficient Quantum Pseudorandomness
• Unitary $2$-designs from random $X$- and $Z$-diagonal unitaries
• Efficient Quantum Tensor Product Expanders and k-designs
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Black holes as clouded mirrors: the Hayden-Preskill protocol with symmetry
• The curious nonexistence of Gaussian 2-designs
• Efficient Unitary T-designs from Random Sums
• Efficient unitary designs and pseudorandom unitaries from permutations
• Pseudo-randomness and Learning in Quantum Computation
• Variations on Classical and Quantum Extractors
• A symmetrization technique for continuous-variable quantum key distribution
• On Computational Complexity of Unitary and State Design Properties
• A note on quantum expanders
• High-expressibility Quantum Neural Networks using only classical resources