Continuous-Time Quantum Search on Balanced Trees

2016/01/06 by Pascal Philipp, Luís Tarrataca, Stefan Boettcher · 2 citations
Physics and Astronomy · #quant-ph

paper · pdf · doi:10.1103/physreva.93.032305

published as Phys. Rev. A 93, 032305 (2016)

arxiv created 2016/01/06 · arxiv updated 2016/03/09

Abstract

We examine the effect of network heterogeneity on the performance of quantum search algorithms. To this end, we study quantum search on a tree for the oracle Hamiltonian formulation employed by continuous-time quantum walks. We use analytical and numerical arguments to show that the exponent of the asymptotic running time ∼ N^β changes uniformly from β=0.5 to β=1 as the searched-for site is moved from the root of the tree towards the leaves. These results imply that the time complexity of the quantum search algorithm on a balanced tree is closely correlated with certain path-based centrality measures of the searched-for site.

Cited by

• Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs
• Quantum phase discrimination with applications to quantum search on graphs

Related

• Quantum Search on Computation Trees
• Tree search and quantum computation
• Quantum Search with Multiple Walk Steps per Oracle Query
• Engineering the Success of Quantum Walk Search Using Weighted Graphs
• Generalised Quantum Tree Search