Quantum computation and lattice problems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 Θ̃ (n2.5)-unique-SVP to the average case subset sum problem. This is a better connection than the known classical results.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science - Proceedings
EditorsD.C. Martin
Pages520-529
Number of pages10
StatePublished - 2002
EventThe 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada
Duration: Nov 16 2002Nov 19 2002

Other

OtherThe 34rd Annual IEEE Symposium on Foundations of Computer Science
CountryCanada
CityVancouver, BC
Period11/16/0211/19/02

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Quantum computation and lattice problems'. Together they form a unique fingerprint.

  • Cite this

    Regev, O. (2002). Quantum computation and lattice problems. In D. C. Martin (Ed.), Annual Symposium on Foundations of Computer Science - Proceedings (pp. 520-529)