Searching via walking: How to find a marked clique of a complete graph using quantum walks
| Authors | |
|---|---|
| Year of publication | 2010 |
| Type | Article in Periodical |
| Magazine / Source | Physical Review A |
| MU Faculty or unit | |
| Citation | |
| Web | http://pra.aps.org/abstract/PRA/v81/i6/e062324 |
| Field | Informatics |
| Keywords | Quantum walks; graphs; cliques |
| Description | We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has N vertices and the subgraph has K vertices, the particle becomes localized on the subgraph in O(N/K) steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resources needed for a quantitative comparison of the efficiency of classical and quantum searches, the number of oracle calls. |
| Related projects: |