We consider Grover's algorithm of quantum search for one or several integers out of N = 2n, where n is a number of quantum bits in the memory register. There is a black-box or subroutine containing information about hidden integers and it can easily recognize these integers but we do not know which ones out of N they are. To find the hidden items we can do no better with a classical computer than to apply the subroutine repeatedly to all possible integers until we hit on the special one and in the worst case we have to repeat this procedure N times. We have analyzed the Grover algorithm carefully and showed that it enables to speed up this search quadratically, although its realization requires to know a number of hidden items. The lower bound for the probability of successful solving the search problem has been obtained. The validity of the results was demonstrated by simulation of the Grover search algorithm using the package QuantumCircuit written in the Wolfram Mathematica language.
A quantum algorithm for estimating the phase, which determines the eigenvalue of a unitary operator, is discussed. It is assumed that the eigenvector of this operator and the corresponding quantum circuit are given. The memory register where the approximate phase value is stored consists of n qubits, which makes it possible to determine the phase accurate to 2 −n with the probability greater than 8/π 2 . By way of example, computations for the case of the quantum phase shift operator are performed. The simulation of the quantum algorithm and the computation of the eigenvalue are performed using the QuantumCircuit package written in the Wolfram Mathematica computer algebra system. This system is also used to perform all the computations and visualize the results.
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.
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.
In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs
O(q2) gates (and
O(q) qubits) to perform the exact Fourier transform over
F2q. Cleve and Watrous (FOCS 2000) improved this gate count to
O(q(logq)2(loglogq)) using the integer multiplication algorithm in
O(n(logn)(loglogn)) time for two
n-bit integers (best known at that time). Our first main result shows that this gate count can be improved to
O(q(logq)). In fact, if there is a multiplication circuit, to multiply two
n-bit integers, with
O(n(logn)α) gates; we get a QFT circuit with
O(q(logq)α) gates (improving upon
O(q(logq)α+1)) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with
o(q(logq)) gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with
O(q(loglog(q/ε))α+1) gates, where
ε is the approximating parameter. Our second main result again improves this to
O(q(loglog(q/ε))α) gates.