Quantum t-designs: T-wise independence in the quantum world

Andris Ambainis; Joseph Emerson

doi:10.1109/CCC.2007.26

Quantum t-designs: T-wise independence in the quantum world

Andris Ambainis^*
, Joseph Emerson

^*Corresponding author for this work

University of Waterloo

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

149 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007
Pages	129-140
Number of pages	12
DOIs	https://doi.org/10.1109/CCC.2007.26
Publication status	Published - 2007
Externally published	Yes
Event	22nd Annual IEEE Conference on Computational Complexity, CCC 2007 - San Diego, CA, United States Duration: 13 Jun 2007 → 16 Jun 2007

Publication series

Name	Proceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)	1093-0159

Conference

Conference	22nd Annual IEEE Conference on Computational Complexity, CCC 2007
Country/Territory	United States
City	San Diego, CA
Period	13/06/07 → 16/06/07

Access to Document

10.1109/CCC.2007.26

Cite this

@inproceedings{b4d9d537a5084a30ad2e3462ea3388c3,

title = "Quantum t-designs: T-wise independence in the quantum world",

abstract = "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.",

author = "Andris Ambainis and Joseph Emerson",

year = "2007",

doi = "10.1109/CCC.2007.26",

language = "English",

isbn = "0769527809",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

pages = "129--140",

booktitle = "Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007",

note = "22nd Annual IEEE Conference on Computational Complexity, CCC 2007 ; Conference date: 13-06-2007 Through 16-06-2007",

}

Ambainis, A & Emerson, J 2007, Quantum t-designs: T-wise independence in the quantum world. in Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007., 4262758, Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 129-140, 22nd Annual IEEE Conference on Computational Complexity, CCC 2007, San Diego, CA, United States, 13/06/07. https://doi.org/10.1109/CCC.2007.26

Quantum t-designs: T-wise independence in the quantum world. / Ambainis, Andris; Emerson, Joseph.
Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007. 2007. p. 129-140 4262758 (Proceedings of the Annual IEEE Conference on Computational Complexity).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - Quantum t-designs

T2 - 22nd Annual IEEE Conference on Computational Complexity, CCC 2007

AU - Ambainis, Andris

AU - Emerson, Joseph

PY - 2007

Y1 - 2007

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

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

UR - https://www.scopus.com/pages/publications/34748892553

U2 - 10.1109/CCC.2007.26

DO - 10.1109/CCC.2007.26

M3 - Conference paper

AN - SCOPUS:34748892553

SN - 0769527809

SN - 9780769527802

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 129

EP - 140

BT - Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007

Y2 - 13 June 2007 through 16 June 2007

ER -

Quantum t-designs: T-wise independence in the quantum world

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this