Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks

Abstract

We establish a lower bound concerning the computational complexity of Grover's algorithms on fractal networks. This bound provides general predictions for the quantum advantage gained for searching unstructured lists. It yields a fundamental criterion, derived from quantum transport properties, for the improvement a quantum search algorithm achieves over the corresponding classical search in a network based solely on its spectral dimension, $d_s$. Our analysis employs recent advances in the interpretation of the venerable real-space renormalization group (RG) as applied to quantum walks. It clarifies the competition between Grover's abstract algorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. The latter is characterized in terms of the quantum walk dimension $d_w^Q$ and the spatial (fractal) dimension $d_f$ that is summarized simply by the spectral dimension of the network. The analysis simultaneously determines the optimal time for a quantum measurement and the probability for successfully pin-pointing a marked element in the network. The RG further encompasses an optimization scheme devised by Tulsi that allows to tune this probability to certainty, leaving quantum transport as the only limiting process. It considers entire families of problems to be studied, thereby establishing large universality classes for quantum search, which we verify with extensive simulations. The methods we develop could point the way towards systematic studies of universality classes in computational complexity to enable modification and control of search behavior.

arXiv comment12 pages, revtex-4.1, enclosed is also a Mathematica Notebook to reproduce and experiment with the calculations; related information can be found at http://www.physics.emory.edu/faculty/boettcher/

References in corpus (47)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Quantum Computation and Decision Trees
• Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
• A Quantum Random Walk Search Algorithm
• Universal computation by quantum walk
• Quantum walks of correlated particles
• Quantum walks: a comprehensive review
• Spatial search by quantum walk
• Single-Spin Addressing in an Atomic Mott Insulator
• Two-particle bosonic-fermionic quantum walk via 3D integrated photonics
• Realization of quantum walks with negligible decoherence in waveguide lattices
• Universal quantum computation using the discrete time quantum walk
• Anderson localization of entangled photons in an integrated quantum walk
• Universal computation by multi-particle quantum walk
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• Decoherence and disorder in quantum walks: From ballistic spread to localization
• Operating Quantum States in Single Magnetic Molecules: Implementation of Grover's Quantum Algorithm
• Implementing the quantum random walk
• Weak limits for quantum random walks
• Complete 3-Qubit Grover Search on a Programmable Quantum Computer
• Faster quantum walk algorithm for the two dimensional spatial search
• Localization of Two-Dimensional Quantum Walks
• Spatial search by quantum walk is optimal for almost all graphs
• Spatial search and the Dirac equation
• Entanglement in coined quantum walks on regular graphs
• Quantum Walk on a Line with Two Entangled Particles
• Classical approach to the graph isomorphism problem using quantum walks
• Efficient Quantum Walk on a Quantum Processor
• Direct Probe of Topological Invariants Using Bloch Oscillating Quantum Walks
• Quantum walk approach to search on fractal structures
• Quantum walks can find a marked element on any graph
• One- and two-dimensional quantum walks in arrays of optical traps
• Anderson localization in generalized discrete time quantum walks
• Weak Limit of the 3-State Quantum Walk on the Line
• Quantum search on graphene lattices
• Search on a Fractal Lattice using a Quantum Random Walk
• General framework for quantum search algorithms
• Relation between Random Walks and Quantum Walks
• Continuous Time Quantum Walks in finite Dimensions
• The spectral dimension controls the decay of the quantum first detection probability
• Analysis of Coined Quantum Walks with Renormalization
• Comparing algorithms for graph isomorphism using discrete- and continuous-time quantum random walks
• Geometry and Dynamics for Hierarchical Regular Networks
• Renormalization and Scaling in Quantum Walks
• Spatial Search Algorithms on Hanoi Networks
• Renormalization of the Unitary Evolution Equation for Coined Quantum Walks

Cited by in corpus (6)

• Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
• Spatial search by continuous-time quantum walks on renormalized Internet networks
• Quantum search on Hanoi network
• Transport and Localization in Quantum Walks on a Random Hierarchy of Barriers
• Quantum Ultra-Walks: Walks on a Line with Hierarchical Spatial Heterogeneity
• Universal scaling hypothesis of quantum spatial search in complex networks