Journal
SIAM JOURNAL ON COMPUTING
Volume 33, Issue 3, Pages 738-760Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0097539703440678
Keywords
lattices; quantum computation; shortest vector problem; hidden subgroup problem
Ask authors/readers for more resources
We present the first explicit connection between quantum computation and lattice problems. Namely, our main result is a solution to the unique shortest vector problem (SVP) under the assumption that there exists an algorithm that solves the hidden subgroup problem on the dihedral group by coset sampling. Additionally, we present an approach to solving the hidden subgroup problem on the dihedral group by using an average case subset sum routine.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available