Quantum t-designs: t-wise independence in the quantum world
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states, w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t. We then show that an approximate 4-design provides a derandomization of the state-distinction problem considered by Sen (quant-ph/0512085), which is relevant to solving certain instances of the hidden subgroup problem.
19 pages, v2 two references added, to appear in Complexity'06
19 pages, v2 two references added, to appear in Complexity'06