Quantum computation and lattice problems

Oded Regev

doi:10.1137/S0097539703440678

Quantum computation and lattice problems

Oded Regev

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	738-760
Number of pages	23
Journal	SIAM Journal on Computing
Volume	33
Issue number	3
DOIs	https://doi.org/10.1137/S0097539703440678
State	Published - 2004

Keywords

Hidden subgroup problem
Lattices
Quantum computation
Shortest vector problem

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/S0097539703440678

Cite this

@article{ea869549989a428e8996778670646674,

title = "Quantum computation and lattice problems",

abstract = "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.",

keywords = "Hidden subgroup problem, Lattices, Quantum computation, Shortest vector problem",

author = "Oded Regev",

year = "2004",

doi = "10.1137/S0097539703440678",

language = "English (US)",

volume = "33",

pages = "738--760",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Quantum computation and lattice problems

AU - Regev, Oded

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - Hidden subgroup problem

KW - Lattices

KW - Quantum computation

KW - Shortest vector problem

UR - http://www.scopus.com/inward/record.url?scp=3142689917&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3142689917&partnerID=8YFLogxK

U2 - 10.1137/S0097539703440678

DO - 10.1137/S0097539703440678

M3 - Article

AN - SCOPUS:3142689917

SN - 0097-5397

VL - 33

SP - 738

EP - 760

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

Quantum computation and lattice problems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this