Quantum Computation and Lattice Problems

Details Quantum Computation and Lattice Problems Quantum Computation and Lattice Problems

2003-04-01

arxiv.org/abs/cs/0304005v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present the first explicit connection between quantum computation and lattice problems. Namely, we show 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. Moreover, we solve the hidden subgroup problem on the dihedral group by using an average case subset sum routine. By combining the two results, we get a quantum reduction from $\Theta(n^{2.5})$-unique-SVP to the average case subset sum problem.

Affiliated with

Also associated with

No associations

Rating

Quantum Computation and Lattice Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Computation and Lattice Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Computation and Lattice Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-125145