Quantum spatial search on graphs subject to dynamical noise

Abstract

We address quantum spatial search on graphs and its implementation by continuous-time quantum walks in the presence of dynamical noise. In particular, we focus on search on the complete graph and on the star graph of order $N$, proving that also the latter is optimal in the computational limit $N\gg 1$, being nearly optimal also for small $N$. The noise is modeled by independent sources of random telegraph noise (RTN), dynamically perturbing the links of the graph. We observe two different behaviours depending on the switching rate of RTN: fast noise only slightly degrades performance, whereas slow noise is more detrimental and, in general, lowers the success probability. In particular, we still find a quadratic speed-up for the average running time of the algorithm, while for the star graph with external target node we observe a transition to classical scaling. We also address how the effects of noise depend on the order of the graphs, and discuss the role of the graph topology. Overall, our results suggest that realizations of quantum spatial search are possible with current technology, and also indicate the star graph as the perfect candidate for the implementation by noisy quantum walks, owing to its simple topology and nearly optimal performance also for just few nodes.

Accepted version

References in corpus (10)

• Spatial search by quantum walk
• Low-frequency noise as a source of dephasing of a qubit
• Quantum Walks on a Random Environment
• Noise resistance of adiabatic quantum computation using random matrix theory
• Connectivity is a Poor Indicator of Fast Quantum Search
• Continuous-time quantum walk on spatially correlated noisy lattices
• Noisy quantum walks of two indistinguishable interacting particles
• Continuous Time Quantum Walks in finite Dimensions
• Environment-assisted analog quantum search
• Vertices cannot be hidden from quantum spatial search for almost all random graphs

Cited by in corpus (17)

• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Continuous-time quantum walks on dynamical percolation graphs
• Lattice quantum magnetometry
• Feedback-assisted quantum search by continuous-time quantum walks
• Deterministic spatial search using alternating quantum walks
• Strategies to simulate dephasing-assisted quantum transport on digital quantum computers
• Scattering as a quantum metrology problem: a quantum walk approach
• Continuous-time quantum walks in the presence of a quadratic perturbation
• Running Measurement Protocol for the Quantum First-detection problem
• Spatial search by continuous-time quantum walks on renormalized Internet networks
• Noise-tolerant quantum speedups in quantum annealing without fine tuning
• Non-Markovianity is not a resource for quantum spatial search on a star graph subject to generalized percolation
• A framework for optimal quantum spatial search using alternating phase-walks
• Multimarked Spatial Search by Continuous-Time Quantum Walk
• Optimal spatial searches with long-range tunneling
• Application of graph theory in quantum computer science
• Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems