CaltechAUTHORS
  A Caltech Library Service

Quantum Algorithms for Some Hidden Shift Problems

van Dam, Wim and Hallgren, Sean and Ip, Lawrence (2006) Quantum Algorithms for Some Hidden Shift Problems. SIAM Journal on Computing, 38 (3). pp. 763-778. ISSN 0097-5397. http://resolver.caltech.edu/CaltechAUTHORS:DAMsiamjc06

[img]
Preview
PDF - Published Version
See Usage Policy.

199Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:DAMsiamjc06

Abstract

Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structures of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of "unknown shift" problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. For one of these problems, the shifted Legendre symbol problem, we give evidence that the problem is hard to solve classically, by showing a reduction from breaking algebraically homomorphic cryptosystems. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/S009753970343141XDOIArticle
http://epubs.siam.org/sicomp/resource/1/smjcat/v36/i3/p763_s1PublisherArticle
Additional Information:©2006 Society for Industrial and Applied Mathematics. (Received July 15, 2003; accepted February 28, 2006; published October 24, 2006) We would like to thank the anonymous referee who pointed out the application of the shifted Legendre symbol problem to algebraically homomorphic cryptosystems, and Umesh Vazirani, whose many suggestions greatly improved this paper. We also thank Dylan Thurston and an anonymous referee for pointing out that algebraically homomorphic cryptosystems can be broken using Shor’s algorithm for discrete log. Thanks to Lisa Hales for helpful suggestions. This author’s work [W.v.D.] was supported in part by the NSA and ARDA under ARO contract W911NF-04-R-0009. Part of this work was done while the author was at MIT, University of California, Berkeley, MSRI, and HP Labs. This author’s work [S.H.] was supported at Caltech in part by an NSF Mathematical Sciences Postdoctoral Fellowship and in part by the NSF through the Institute for Quantum Information at the California Institute of Technology. Most of this work was done while the author was at the Mathematical Sciences Research Institute and the University of California, Berkeley, with partial support from DARPA QUIST grant F30602-01-2-0524. This author’s work [L.I.] was supported by NSF grant CCR-0049092, DARPA grant F30602-00-2-0601, and DARPA QUIST grant F30602-01-2-2054. This work was done while the author was at the University of California, Berkeley, and the Institute for Quantum Information at the California Institute of Technology.
Subject Keywords:quantum computing; efficient algorithms; Legendre symbol
Issue or Number:3
Record Number:CaltechAUTHORS:DAMsiamjc06
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:DAMsiamjc06
Alternative URL:http://dx.doi.org/10.1137/S009753970343141X
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7282
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:26 Jan 2007
Last Modified:27 Oct 2017 04:23

Repository Staff Only: item control page