Record Details

Faster quantum searching with almost any diffusion operator

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Faster quantum searching with almost any diffusion operator
 
Creator TULSI, A
 
Description Grover's search algorithm drives a quantum system from an initial state vertical bar s > to a desired final state vertical bar t > by using selective phase inversions of these two states. Earlier, we studied a generalization of Grover's algorithm that relaxes the assumption of the efficient implementation of I-s, the selective phase inversion of the initial state, also known as a diffusion operator. This assumption is known to become a serious handicap in cases of physical interest. Our general search algorithm works with almost any diffusion operator D-s with the only restriction of having vertical bar s > as one of its eigenstates. The price that we pay for using any operator is an increase in the number of oracle queries by a factor of O(B), where B is a characteristic of the eigenspectrum of D-s and can be large in some situations. Here we show that by using a quantum Fourier transform, we can regain the optimal query complexity of Grover's algorithm without losing the freedom of using any diffusion operator for quantum searching. However, the total number of operators required by the algorithm is still O(B) times more than that of Grover's algorithm. So our algorithm offers an advantage only if the oracle operator is computationally more expensive than the diffusion operator, which is true in most search problems.
 
Publisher AMER PHYSICAL SOC
 
Date 2016-01-15T08:27:34Z
2016-01-15T08:27:34Z
2015
 
Type Article
 
Identifier PHYSICAL REVIEW A, 91(5)
1050-2947
1094-1622
http://dx.doi.org/10.1103/PhysRevA.91.052307
http://dspace.library.iitb.ac.in/jspui/handle/100/18163
 
Language en