Quantum spatial search on graphs subject to dynamical noise
arXiv:1809.01969 · doi:10.1103/PhysRevA.98.052347
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 , proving that also the latter is optimal in the computational limit , being nearly optimal also for small . 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.
arXiv commentAccepted version
References in corpus (29)
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum Computation and Decision Trees
- Spatial search by quantum walk
- 1/f noise: implications for solid-state quantum information
- Low-frequency noise as a source of dephasing of a qubit
- Non-Gaussian low-frequency noise as a source of qubit decoherence
- Spatial search by quantum walk is optimal for almost all graphs
- Quantum Walks on a Random Environment
- Dynamics of quantum correlations in colored environments
- Noise resistance of adiabatic quantum computation using random matrix theory
- Quantum walk approach to search on fractal structures
- Global Symmetry is Unnecessary for Fast Quantum Search
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Connectivity is a Poor Indicator of Fast Quantum Search
- Classical Diffusion of a quantum particle in a noisy environment
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Optimal quantum spatial search on random temporal networks
- Non-Markovian continuous-time quantum walks on lattices with dynamical noise
- Non-Markovian dynamics of single- and two-qubit systems interacting with Gaussian and non-Gaussian fluctuating transverse environments
- Continuous-Time Quantum Search on Balanced Trees
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Continuous-time quantum walk on spatially correlated noisy lattices
- Noisy quantum walks of two indistinguishable interacting particles
- Continuous Time Quantum Walks in finite Dimensions
- Time evolution of continuous-time quantum walks on dynamical percolation graphs
- Environment-assisted analog quantum search
- Vertices cannot be hidden from quantum spatial search for almost all random graphs
- Quasi-Hamiltonian Method for Computation of Decoherence Rates
- GPU-accelerated algorithms for many-particle continuous-time quantum walks
Cited by in corpus (18)
- 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
- Spatial search by continuous-time quantum walks on renormalized Internet networks
- Running Measurement Protocol for the Quantum First-detection problem
- Non-Markovianity is not a resource for quantum spatial search on a star graph subject to generalized percolation
- Noise-tolerant quantum speedups in quantum annealing without fine tuning
- A framework for optimal quantum spatial search using alternating phase-walks
- Multiple-scale integro-differential perturbation method for generic non-Markovian environments
- Multimarked Spatial Search by Continuous-Time Quantum Walk
- Optimal spatial searches with long-range tunneling
- Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems
- Application of graph theory in quantum computer science