We recast Grover's generalised search algorithm in a geometric language even when the states are not approximately orthogonal. We provide a possible search algorithm based on an arbitrary unitary transformation which can speed up the steps still further. We discuss the lower and upper bounds on the transition matrix elements when the unitary operator changes with time, thereby implying that quantum search process can not be too fast or too slow. This is a remarkable feature of quantum computation unlike classical one. Quantum mechanical uncertainty relation puts bounds on search process. Also we mention the problems of perturbation and other issues in time-dependent search operation.
We recast Grover's generalised search algorithm in a geometric language even when the states are not approximately orthogonal. We provide a possible search algorithm based on an arbitrary unitary transformation which can speed up the steps still further. We discuss the lower and upper bounds on the transition matrix elements when the unitary operator changes with time, thereby implying that quantum search process can not be too fast or too slow. This is a remarkable feature of quantum computation unlike classical one. Quantum mechanical uncertainty relation puts bounds on search process. Also we mention the problems of perturbation and other issues in time-dependent search operation.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
In this work we study Grover's algorithm for quantum computers. This algorithm promises to search in an unstructured database in time comparable with a square root of the number of objects. A description of basic quantum computer principles is followed by the original Grover's formulation and a proof of the algorithm, as well as a later geometrical description of the algorithm. We also mention their suitability for educational purposes. We also include a description of the Grover's algorithm in a programming language, which makes it possible to simulate a quantum computing on classical computers.
A fast quantum search algorithm for continuous variables is presented. The result is the quantum continuous variable analog of Grover's algorithm originally proposed for qubits. A continuous variable analog of the Hadamard (i.e., Fourier transform) operation is used in conjunction with inversion about the average of quantum states to allow the approximate identification of an unknown quantum state in a way that gives a square-root speed-up over search algorithms using classical continuous variables. Also, we show that this quantum search algorithm is robust for a generalised Fourier transformation on continuous variables.
We have developed a non-unitary extension of Grover's search algorithm by changing the hidden geometry of Hilbert space carried by diffusion operator. Our algorithm finds the solution for search problem by performing a unique bigger rotation rather than small rotations in order polynomial times in the size N of search space. We analyze the complexity of implementing the non-unitary operation and we observed that the price paid by performing this rotation is due the normalization. In Kraus operator approach we need O(N) repetition of the algorithm to have a chance of measuring a solution in a post-selection, this is no better than the classical solution. However, the quantum singular value transform in addition with block encoding and Chebyshev polynomial approximation, we got complexity O(N) and reach the Grover's bound with an extra resource of one single qubit, compared with the standard Grover's algorithm.
The rapid progress of computer science has been accompanied by a corresponding evolution of computation, from classical computation to quantum computation. As quantum computing is on its way to becoming an established discipline of computing science, much effort is being put into the development of new quantum algorithms. One of quantum algorithms is Grover's algorithm, which is used for searching an element in an unstructured list of N elements with quadratic speed-up over classical algorithms. In this work, Quantum Computer Language (QCL) is used to make a Grover's quantum search simulation in a classical computer document.
Search is one of the most commonly used primitives in quantum algorithm design. It is known that quadratic speedups provided by Grover’s algorithm are optimal, and no faster quantum algorithms for Search exist. While it is known that at least some quantum computation is required to achieve these speedups, the existing bounds do not rule out the possibility of an equally fast hybrid quantum-classical algorithm where most of the computation is classical. In this work, we study such hybrid algorithms, and we show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. In addition, we generalize this result to algorithms with subconstant success probabilities.