|
related topics |
{algorithm, log, probability} |
{group, space, representation} |
{let, theorem, proof} |
{measurement, state, measurements} |
{operator, operators, space} |
{state, states, entangled} |
{states, state, optimal} |
|
Explicit Multiregister Measurements for Hidden Subgroup Problems
Cristopher Moore, Alexander Russell
abstract: We present an explicit measurement in the Fourier basis that solves an
important case of the Hidden Subgroup Problem, including the case to which
Graph Isomorphism reduces. This entangled measurement uses $k=\log_2 |G|$
registers, and each of the $2^k$ subsets of the registers contributes some
information. While this does not, in general, yield an efficient algorithm, it
generalizes the relationship between Subset Sum and the HSP in the dihedral
group, and sheds some light on how quantum algorithms for Graph Isomorphism
might work.
- oai_identifier:
- oai:arXiv.org:quant-ph/0504067
- categories:
- quant-ph
- arxiv_id:
- quant-ph/0504067
- created:
- 2005-04-08
- updated:
- 2006-06-02
Full article ▸
|
|
related documents |
9903071v1 |
0511272v1 |
0505007v3 |
9905026v1 |
0201152v1 |
0207131v1 |
9706003v4 |
0302022v1 |
0010034v1 |
0304131v1 |
0403140v2 |
0206089v2 |
0410042v1 |
9907020v2 |
0609220v1 |
0010021v1 |
0607148v3 |
0612089v3 |
0303175v1 |
0609166v1 |
0210077v1 |
0605026v1 |
0609160v1 |
0703220v1 |
0508156v3 |
|