Enhanced quantum searching via entanglement and partial diffusion

PHYSICA D-NONLINEAR PHENOMENA

卷:237

Article

Younes, A.¹  Rowe, J.²  Miller, J.³ 

[1] Univ Alexandria, Fac Sci, Dept Math & Comp Sci, Alexandria, Egypt

[2] Univ Birmingham, Sch Comp Sci, Birmingham B15 2TT, W Midlands, England

[3] Univ York, Dept Elect, York YO10 5DD, Heslington, England

关键词: quantum search;    amplitude amplification;    entanglement;   

DOI  :  10.1016/j.physd.2007.12.005

来源: Elsevier

【 摘 要 】

In this paper, we will define a quantum operator that performs the standard inversion about the mean only on a subspace of the system (Partial Diffusion Operator). This operator is used together with entanglement in a quantum search algorithm that runs in O(root N/M) for searching an unstructured list of size N with M matches such that 1 <= M <= N. We will show that the performance of the algorithm is more reliable than known fixed operators quantum search algorithms especially for multiple matches where we can get a solution after a single iteration with probability over 90% if the number of matches is approximately more than one-third of the search space. We will show that the algorithm will be able to handle the case where the number of matches M is unknown in advance in O(root N/M) such that 1 <= M <= N. (C) 2007 Elsevier B.V. All rights reserved.

【 授权许可】

Free