Data Convergence — Quantum Computing — Algorithms
A wide variety of quantum computing algorithms have been proposed with the perspective of obtaining solution to some of the classically unsolvable problems. The currently available quantum computers are far away from it’s utilization for commercial applications , yet many algorithms are developed for near term applications and study of optimization and speedup capability of quantum processing unit.
Let’s take a glance at the working principles of few of the quantum algorithms before moving into detail explanations of the same.
Moving on to the first quantum algorithm to show up an exponential speed up compared to classical algorithm in solving a specific algorithm that is Simon’s algorithm .Although it’s relatively elementary and not applicable to any practical problem .The Simon’s problem is set in model of query complexity and was devised by Daniel Simon in 1994.The hard problems tend to have an exponential big-O and Simon’s algorithm solves a particular periodicity problem in polynomial fast time .It also provides solution to universally applicable and naturally occurring periodicity questions. In Simon’s problem we are given a function that is periodic in Z-2^n sense and we find period a. This periodicity endows function can be used to separate the domain into two equal parts.
As the quantum phases can be used to output results of a quantum algorithm. These phases can be estimated by the quantum phase estimation algorithm which in turn incorporates another quantum algorithm to ensure precise estimation. Since it estimates eigen value(phase) of eigenvector of a unitary operator it is also referred as quantum eigenvalue estimation algorithm. It can be implemented coherently using all phased plus states at once . That means we get 0 if phase is zero and 1 if phase is pi.
Quantum fourier transform is quantum implementation of discrete fourier transform over the amplitude of a wave function. It’s a linear transformation of quantum bits. It helps find patterns in input sequence and identify frequency of repetition .It was invented by Don Coppersmith. Quantum fourier transform is used in many other quantum algorithms like shor’s algorithm for factoring and discrete logarithm computation , The quantum phase estimation algorithm for finding eigenvalues of unitary operator , and algorithms for hidden subgroup problem.
The variational quantum eigensolver algorithm is a hybrid quantum classical algorithm used to find eigen values of large matrix . The VQE algorithm applies classical optimization to minimize the energy expectation of an ansatz state to find the ground state energy of a molecule. This can also be extended to find excited energies of molecules. It’s hybrid in the sense that the quantum subroutine is run inside of classical optimization. This algorithm is use for problem involving modelling nature , chemistry , combinatorial optimization problems .
A polynomial time quantum algorithm for integer factoring widely known as Shor’s algorithm. It was given by Peter shor in the year 1994 for factoring a number N in O((log N)3) time. This speed of calculation subsequently challenges the RSA encryption which uses prime factorization.
The deterministic algorithm or the deutsch — Jozsa algorithm proposed by David Deutsch and Richard Jozsa in 1992. It gives a deterministic output either constant (0 , 1) or a balance to determine the function falls in which of the two category. It is one of the first type of quantum algorithm that is exponentially faster than any possible deterministic classical algorithm.
The restricted version of Deutsch — Jozsa algorithm is Bernstein — Vazirani algorithm .Proposed by Ethan Bernstein and Umesh Vazirani in the year 1992.Using a single query it finds the string encoded in the function instead of distinguishing between classes of function.
Grover’s algorithm for searching an item in an unsorted database uses the concept of inverting the phase of the element which we are looking for and the amplifying it . The repetition of this step results in increment of probability of occurrence the element that is being searched . It was proposed by renowned computer scientist Lov Grover in the year 1996.This algorithm is used for obtaining solution for graph colouring , max cut as well as travel salesman problems.
Coming to a class of decision problem in computational complexity called bounded error probabilistic polynomial time (BPP)that is solvable in polynomial time with error probability bounded away from 1/3 for all instances .Whereas BQP , a class of decision problem in complexity theory is solvable by a quantum computer in polynomial time .It is the quantum analogue of complexity class BPP. The probability of error is 1/3 . We can rum the algorithm a constant number of times and achieve any desired probability by majority with correctness less than one. The complexity class is unchanged by allowing error as high as (1/2-n-C) ,C being any positive constant and n as length of input. The relationship of BQP with other problem spaces can be viewed as :
Despite the speedups quantum algorithms enable for certain problems, in the case of NP-Hard problems, quantum algorithms still fundamentally scale super polynomially. Just as we have quantum algorithm for an NP-Hard problem, that doesn’t mean that finding an exact solution for the problem isn’t still hard ,there are still many room for development .While the development of large scale , error corrected quantum computers are evolving , we can proceed to enhance our understanding of the algorithms in much greater detail .
Reference :
1) https://www.scottaaronson.com/blog/?p=208
2) https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/lec7.pdf
3) https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf
5) https://eccc.weizmann.ac.il/report/2018/107/ Oracle Separation of BQP and PH by Ran Raz, Avishay Tal
