Efficient Quantum Tensor Product Expanders and k-Designs

DOI10.1007/978-3-642-03685-9_41MaRDI QIDQ3638902zbMATH OpenOpenAlexFDO

Authors Aram W. Harrow, Richard A. Low

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph designs and isomorphic decomposition (05C51) Quantum computation (81P68)

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].

Recommendations

• Classical and quantum tensor product expanders
• Quantum combinatorial designs and \(k\)-uniform states
• Mapping qubit algebras to combinatorial designs
• Tensor products of quantum structures and their applications in quantum measurements
• Efficient quantum circuits for Schur and Clebsch-Gordan transforms
• An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs
• Efficient quantum circuits for Toeplitz and Hankel matrices
• QUANTUM COMPUTATIONAL SCHEMES GENERATED BY k-BOSON ALGEBRAS
• New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√ n log ^k n ) distance
• Computations in quantum tensor networks

Cited in

(15)

• Unitary designs and codes
• Explicit construction of exact unitary designs
• The curious nonexistence of Gaussian 2-designs
• scientific article; zbMATH DE number 5899289 (Why is no real title available?)
• Quantum expanders from any classical Cayley graph expander
• Quantum Margulis expanders
• Classical and quantum tensor product expanders
• Local random quantum circuits are approximate polynomial-designs
• Generating a state t-design by diagonal quantum circuits
• Unitary 2-designs from random X- and Z-diagonal unitaries
• A note on quantum expanders
• Optimal quantum (tensor product) expanders from unitary designs
• Quantum pseudorandom scramblers
• The high-dimension limit of characters of compact reductive Lie groups and restrictions on the production of quantum randomness
• Quantum pseudorandom scramblers

This page was built for publication: Efficient Quantum Tensor Product Expanders and k-Designs

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