
Proceedings Paper
Grover's search algorithm with an entangled database stateFormat | Member Price | Non-Member Price |
---|---|---|
$17.00 | $21.00 |
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
Published in SPIE Proceedings Vol. 8057:
Quantum Information and Computation IX
Eric Donkor; Andrew R. Pirich; Howard E. Brandt, Editor(s)
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
