Share Email Print
cover

Proceedings Paper

Grover's search algorithm with an entangled database state
Author(s): Paul M. Alsing; Nathan McDonald
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

Grover's oracle based unstructured search algorithm is often stated as "given a phone number in a directory, find the associated name." More formally, the problem can be stated as "given as input a unitary black box Uf for computing an unknown function f:{0,1}n →{0,1}find x=x0 an element of {0,1}n such that f(x0) =1, (and zero otherwise). The crucial role of the externally supplied oracle Uf (whose inner workings are unknown to the user) is to change the sign of the solution 0 x , while leaving all other states unaltered. Thus, Uf depends on the desired solution x0. This paper examines an amplitude amplification algorithm in which the user encodes the directory (e.g. names and telephone numbers) into an entangled database state, which at a later time can be queried on one supplied component entry (e.g. a given phone number t0) to find the other associated unknown component (e.g. name x0). For N=2n names x with N associated phone numbers t , performing amplitude amplification on a subspace of size N of the total space of size N2 produces the desired state 0 0 x t in √N steps. We discuss how and why sequential (though not concurrent parallel) searches can be performed on multiple database states. Finally, we show how this procedure can be generalized to databases with more than two correlated lists (e.g. x t s r ...).

Paper Details

Date Published: 3 June 2011
PDF: 17 pages
Proc. SPIE 8057, Quantum Information and Computation IX, 80570R (3 June 2011); doi: 10.1117/12.883092
Show Author Affiliations
Paul M. Alsing, Air Force Research Lab. (United States)
Nathan McDonald, Air Force Research Lab. (United States)


Published in SPIE Proceedings Vol. 8057:
Quantum Information and Computation IX
Eric Donkor; Andrew R. Pirich; Howard E. Brandt, Editor(s)

© SPIE. Terms of Use
Back to Top