Quantum Search Algorithms

Christoph Dürr, xb b b

Jamal S. Rahhal, Dia I. Abualnadi, Mohammed Hawa

Quantum computing promises a leap in performance over classical computing. Its computational power was revealed after the introduction of some quantum algorithms such as Grover's search algorithm. Many classical algorithms especially that deal with Error Correcting Codes are introduced to solve an exhaustive search problem. The quantum techniques promise an optimal search speed that is of special importance when the size of the searched domain is quite large. In this paper we devise the use of quantum search algorithm introduced by Grover to implement the viterbi algorithm (VA). Due to lack of resources and the nature of implementing quantum algorithms, only theoretical results are obtained. The use of quantum search algorithm showed that we can reduce the number of search computations exponentially. For example if the classical VA requires 262144 searching operations for a signalling length of 1024 intervals, the quantum algorithm will need only 512 searching operations when single search quantum viterbi algorithm (SSQVA) is used. And for the multi search quantum viterbi algorithm (MSQVA) it needs 16384 searching operations for the same signalling length.

Jerzy Klamka

Huiquan Wang, Junjie Wu, Xuejun Yang +2 more

The Google's PageRank algorithm is one of the most famous algorithms in data mining. A quantum version of this algorithm has been proposed in 2012. It is a meaningful step towards the quantum search engine but it can not search solutions. In this paper, we integrate a special operator of quantum search into the quantum PageRank algorithm to make a new quantum algorithm. We called it the Search Rank algorithm. This new algorithm is able to search solutions and rank results according to their importance at the same time. It is the first algorithm possessing this ability as far as we know. And it outperforms all classical algorithms when searching an unsorted database.

Nanyang Xu, Zhu Jin, Xinhua Peng +2 more

Grover's algorithm has achieved great success. But quantum search algorithms still are not complete algorithms because of Grover's Oracle. We concerned on this problem and present a new quantum search algorithm in adiabatic model without Oracle. We analyze the general difficulties in quantum search algorithms and show how to solve them in the present algorithm. As well this algorithm could deal with both single-solution and multi-solution searches without modification. We also implement this algorithm on NMR quantum computer. It is the first experiment which perform a real quantum database search rather than a marked-state search.