In this thesis, we study quantum algorithms, espectially using the quan- tum Fourier transform. At rst, we introduce quantum Fourier transform on groups and using this, we study how to solve problems with quantum algorithms.
In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.
Quantum computing over the past few decades has experienced a huge boost, due in part to the discovery of algorithms such as the Shor's algorithm which promises a significant reduction in complexity compared to its analogues of classical computing. The main objective of this thesis is to introduce improvements in some algorithms based on the quantum Fourier transform, more specifically in the phase estimation algorithm and the order-finding algorithm. In addition to this, the problem of efficient generation of quantum states is also studied, where as a result a method has been developed for the efficient generation of quantum states.
I describe the role of symmetry in two quantum algorithms, with a focus on how that symmetry is made manifest by the Fourier transform. The Fourier transform can be considered in a wider context than the familiar one of functions on Rn or Z/nZ; instead it can be defined for an arbitrary group where it is known as representation theory. The first quantum algorithm solves an instance of the hidden subgroup problem--distinguishing conjugates of the Borel subgroup from each other in groups related to PSL(2; q). I use the symmetry of the subgroups under consideration to reduce the problem to a mild extension of a previously solved problem. This generalizes a result of Moore, Rockmore, Russel and Schulman[33] by switching to a more natural measurement that also applies to prime powers. In contrast to the first algorithm, the second quantum algorithm is an attempt to use naturally continuous spaces. Quantum walks have proved to be a useful tool for designing quantum algorithms. The natural equivalent to continuous time quantum walks is evolution with the Schrodinger equation, under the kinetic energy Hamiltonian for a massive particle. I take advantage of quantum interference to find the center of spherical shells in high dimensions. Any implementation would be likely to take place on a discrete grid, using the ability of a digital quantum computer to simulate the evolution of a quantum system. In addition, I use ideas from the second algorithm on a different set of starting states, and find that quantum evolution can be used to sample from the evolute of a plane curve. The method of stationary phase is used to determine scaling exponents characterizing the precision and probability of success for this procedure.