A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space

Oded Regev

A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-polynomial. We describe a modified algorithm whose running time is still subexponential and whose space requirement is only polynomial.

Original language	Undefined
Article number	quant-ph/0406151
Journal	arXiv
State	Published - Jun 21 2004

Keywords

quant-ph

Cite this

@article{b879f614327a4ba2b6abae1ceee65749,

title = "A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space",

abstract = "In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-polynomial. We describe a modified algorithm whose running time is still subexponential and whose space requirement is only polynomial.",

keywords = "quant-ph",

author = "Oded Regev",

note = "7 pages, 1 figure",

year = "2004",

month = jun,

day = "21",

language = "Undefined",

journal = "arXiv",

}

TY - JOUR

T1 - A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space

AU - Regev, Oded

N1 - 7 pages, 1 figure

PY - 2004/6/21

Y1 - 2004/6/21

N2 - In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-polynomial. We describe a modified algorithm whose running time is still subexponential and whose space requirement is only polynomial.

AB - In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-polynomial. We describe a modified algorithm whose running time is still subexponential and whose space requirement is only polynomial.

KW - quant-ph

M3 - Article

JO - arXiv

JF - arXiv

M1 - quant-ph/0406151

ER -