Grover's Search Algorithm with an Entangled Database State
Abstract
Grover s oracle based unstructured search algorithm is often stated as given a phone number in a directory, find the associated name. 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=2^n names x with N associated phone numbers t , performing amplitude amplification on a subspace of size N of the total space of size N^2 produces the desired state |x0>|t0> 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> ).
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 2011
- Accession Number
- ADA559750
Entities
People
- Nathan D. McDonald
- Paul M. Alsing
Organizations
- Air Force Research Laboratory