|
| related topics |
| {algorithm, log, probability} |
| {group, space, representation} |
| {states, state, optimal} |
| {measurement, state, measurements} |
| {state, algorithm, problem} |
| {let, theorem, proof} |
| {equation, function, exp} |
|
From optimal measurement to efficient quantum algorithms for the hidden
subgroup problem over semidirect product groups
Dave Bacon, Andrew M. Childs, Wim van Dam
abstract: We approach the hidden subgroup problem by performing the so-called pretty
good measurement on hidden subgroup states. For various groups that can be
expressed as the semidirect product of an abelian group and a cyclic group, we
show that the pretty good measurement is optimal and that its probability of
success and unitary implementation are closely related to an average-case
algebraic problem. By solving this problem, we find efficient quantum
algorithms for a number of nonabelian hidden subgroup problems, including some
for which no efficient algorithm was previously known: certain metacyclic
groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including
the Heisenberg group, r=2). In particular, our results show that entangled
measurements across multiple copies of hidden subgroup states can be useful for
efficiently solving the nonabelian HSP.
- oai_identifier:
- oai:arXiv.org:quant-ph/0504083
- categories:
- quant-ph
- comments:
- 18 pages; v2: updated references on optimal measurement
- doi:
- 10.1109/SFCS.2005.38
- arxiv_id:
- quant-ph/0504083
- journal_ref:
- Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS
2005), pp. 469-478
- created:
- 2005-04-11
- updated:
- 2005-04-26
Full article ▸
|
|
| related documents |
| 0510185v1 |
| 0408150v2 |
| 9802040v2 |
| 0703231v2 |
| 0008059v3 |
| 9910033v4 |
| 0603135v1 |
| 0408119v1 |
| 0612089v3 |
| 9907020v2 |
| 0410042v1 |
| 0403140v2 |
| 0607148v3 |
| 0304131v1 |
| 0511272v1 |
| 0505007v3 |
| 9904079v3 |
| 0510230v3 |
| 0610235v2 |
| 0609220v1 |
| 0609166v1 |
| 0206023v2 |
| 0609160v1 |
| 0508156v3 |
| 0610105v1 |
|