Improvements on quantum binary searching algorithm

Abstract

In order to solve the ordered quantum database search problem, a quantum binary searching algorithm was proposed which can be used to implement the whole searching process in four steps. Considering the characteristic of quantum parallelism, this paper further improves the searching process, which can be realized in only two steps, and presents the circuit implementation. In this scheme, the number of the quantum logic gates doesn’t increase. Moreover, the losing-solution issue in the quantum binary searching algorithm can be efficiently prevented.

Keywords

Quantum State / Target State / Discrete Logarithm / Quantum Circuit / Circuit Implementation

References

[1] Shor P W, Algorithm for Quantum Computation: Discrete Logarithms and Factoring, 35th Annual Symposium on Foundations of Computer Science, 1994, 124.

[2] GroverL. K.. Phys.Rev.Lett., 1997, 79: 325

[3] FeynmanR. P.. Int. J. Theor. Phys., 1982, 21: 467

[4] FeynmanR. P.. Found. Phys., 1986, 16: 507

[5] NielsonM. A., ChuangI. L.. Quantum Computation and Quantum Information, 2000, United Kingdom, Cambridge University Press, 171

[6] BarencoA., BennettC. H., CleveR.. Physical Review A, 1995, 52: 3457

[7] JiangM., ZhangZ.-k., DongD.-y., Tzyh-JongT.. Journal of Optoelectronics·Laster, 2007, 18: 981