The quantum query complexity of the hidden subgroup problem is polynomial
pith:ZAIXIK4E Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{ZAIXIK4E}
Prints a linked pith:ZAIXIK4E badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
We present a quantum algorithm which identifies with certainty a hidden subgroup of an arbitrary finite group G in only a polynomial (in log |G|) number of calls to the oracle. This is exponentially better than the best classical algorithm. However our quantum algorithm requires exponential time, as in the classical case. Our algorithm utilizes a new technique for constructing error-free algorithms for non-decision problems on quantum computers.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Lower overhead fault-tolerant building blocks for noisy quantum computers
New combinatorial proofs and circuit designs for quantum error correction reduce physical qubit overhead by up to 10x and time overhead by 2-6x for codes including Steane, Golay, and surface codes.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.