CaltechAUTHORS
  A Caltech Library Service

Quantum algorithms for some hidden shift problems

van Dam, Wim and Hallgren, Sean and Ip, Lawrence (2003) Quantum algorithms for some hidden shift problems. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM Proceedings Series. Association for Computing Machinery , New York, pp. 489-498. ISBN 0-89871-538-5 http://resolver.caltech.edu/CaltechAUTHORS:20111025-084937526

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111025-084937526

Abstract

Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structure of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received fax 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. 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:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/S009753970343141XDOIUNSPECIFIED
http://epubs.siam.org/sicomp/resource/1/smjcat/v36/i3/p763_s1PublisherUNSPECIFIED
Additional Information:© 2003 Association for Computing Machinery. Supported by an HP-MSRI postdoc fellowship. Supported in part by an NSF Mathematical Sciences Postdoctoral Fellowship and in part by the NSF though the Institute for Quantum Information at the California Institute of Technology. Most of this work 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. Supported by NSF Grant CCR-0049092, DARPA Grant F306-02-00-2-0601 and DARPA QUIST Grant F30602-01-2-2054. Part of this work was done while the author was a visitor at the Institute for Quantum Information at the California Institute of Technology. We would like to thank the anonymous referee who pointed out the application of 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 last minute suggestions.
Funders:
Funding AgencyGrant Number
HP-MSRI Postdoc FellowshipUNSPECIFIED
NSF Mathematical Sciences Postdoctoral Fellowship UNSPECIFIED
NSF Institute for Quantum Information UNSPECIFIED
Defense Advanced Research Projects Agency (DARPA) QUISTF306-02-01-2-0524
NSFCCR-0049092
Defense Advanced Research Projects Agency (DARPA)F306-02-00-2-0601
Defense Advanced Research Projects Agency (DARPA) QUISTF306-02-01-2-2054
Record Number:CaltechAUTHORS:20111025-084937526
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20111025-084937526
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27395
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 Oct 2011 16:42
Last Modified:26 Oct 2011 16:42

Repository Staff Only: item control page