Quantum algorithms and the Fourier transform [microform]
- Bib ID:
- 3773236
- Format:
- Book and Microform
- Author:
- Ip, Lawrence Poi Heng
- Online Version:
- http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3183815
Broken link? let us search Trove , the Wayback Machine , or Google for you.
- Description:
- 77 p.
- ISBN:
- 0542252422
- Summary:
-
The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems. We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element. We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries. For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms.
This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements. We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the "strong standard method" cannot be used to implement the optimal set of measurements. For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem.
As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.
- Notes:
-
- (UnM)AAI3183815
- Source: Dissertation Abstracts International, Volume: 66-07, Section: B, page: 3794.
- Chair: Umesh V. Vazirani.
- Thesis (Ph.D.)--University of California, Berkeley, 2004.
- Reproduction:
- Microfiche. Ann Arbor, Mich. : University Microfilms International.
- Subject:
- Computer Science
- Other authors/contributors:
- University of California, Berkeley
- Copyright:
-
Copyright varies by issue and article
Copyright varies with each issue and article. You may have full rights to copy, or may be able to copy only under some circumstances, for example a portion for research or study. Order a copy where circumstances allow through Copies Direct or Contact us for further information.
- Reason for copyright status:
- Serials have an open range of dates.
Copyright status was determined using the following information:
- Material type:
- Literary Dramatic Musical
Copyright status may not be correct if data in the record is incomplete or inaccurate. Other access conditions may also apply. For more information please see: Copyright in library collections.
Request this item
Request this item to view in the Library’s reading room.