|
related topics |
{algorithm, log, probability} |
{let, theorem, proof} |
{qubit, qubits, gate} |
{group, space, representation} |
{equation, function, exp} |
{error, code, errors} |
|
The Quantum Fourier Transform and Extensions of the Abelian Hidden
Subgroup Problem
Lisa R. Hales
abstract: The quantum Fourier transform (QFT) has emerged as the primary tool in
quantum algorithms which achieve exponential advantage over classical
computation and lies at the heart of the solution to the abelian hidden
subgroup problem, of which Shor's celebrated factoring and discrete log
algorithms are a special case. We begin by addressing various computational
issues surrounding the QFT and give improved parallel circuits for both the QFT
over a power of 2 and the QFT over an arbitrary cyclic group. These circuits
are based on new insight into the relationship between the discrete Fourier
transform over different cyclic groups. We then exploit this insight to extend
the class of hidden subgroup problems with efficient quantum solutions. First
we relax the condition that the underlying hidden subgroup function be distinct
on distinct cosets of the subgroup in question and show that this relaxation
can be solved whenever G is a finitely-generated abelian group. We then extend
this reasoning to the hidden cyclic subgroup problem over the reals, showing
how to efficiently generate the bits of the period of any sufficiently
piecewise-continuous function on R. Finally, we show that this problem of
period-finding over R, viewed as an oracle promise problem, is strictly harder
than its integral counterpart. In particular, period-finding over R lies
outside the complexity class MA, a class which contains period-finding over the
integers.
- oai_identifier:
- oai:arXiv.org:quant-ph/0212002
- categories:
- quant-ph
- comments:
- PhD Thesis UC Berkeley Spring 2002
- arxiv_id:
- quant-ph/0212002
- created:
- 2002-11-29
Full article ▸
|
|
related documents |
0509153v1 |
0510230v3 |
0408119v1 |
0603135v1 |
0703231v2 |
0510185v1 |
0504083v2 |
0408150v2 |
0612089v3 |
0410042v1 |
0607148v3 |
0403140v2 |
0304131v1 |
0504067v3 |
0511272v1 |
0505007v3 |
0303175v1 |
0302022v1 |
0212096v1 |
0610235v2 |
0407095v1 |
0306042v1 |
0405081v1 |
0401053v1 |
0512241v1 |
|