Decoherence enhances performance of quantum walks applied to graph isomorphism testing
arXiv:1606.02661 · doi:10.1103/PhysRevA.94.062317
Abstract
Computational advantages gained by quantum algorithms rely largely on the coherence of quantum devices and are generally compromised by decoherence. As an exception, we present a quantum algorithm for graph isomorphism testing whose performance is optimal when operating in the partially coherent regime, as opposed to the extremes of fully coherent or classical regimes. The algorithm builds on continuous-time quantum stochastic walks (QSWs) on graphs and the algorithmic performance is quantified by the distinguishing power (DIP) between non-isomorphic graphs. The QSW explores the entire graph and acquires information about the underlying structure, which is extracted by monitoring stochastic jumps across an auxiliary edge. The resulting counting statistics of stochastic jumps is used to identify the spectrum of the dynamical generator of the QSW, serving as a novel graph invariant, based on which non-isomorphic graphs are distinguished. We provide specific examples of non-isomorphic graphs that are only distinguishable by QSWs in the presence of decoherence.
arXiv commentTo appear in Physical Review A, 6 pages, 3 figures
References in corpus (28)
- Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
- Dephasing assisted transport: Quantum networks and biomolecules
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Realization of a quantum walk with one and two trapped ions
- Cavity Loss Induced Generation of Entangled Atoms
- Quantum walk of a trapped ion in phase space
- Proposal for teleportation of an atomic state via cavity decay
- Quantum algorithms for algebraic problems
- Entangled light from white noise
- Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
- Thermodynamics of Quantum Jump Trajectories
- Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
- Decoherence in quantum walks - a review
- Decoherence can be useful in quantum walks
- Two-particle quantum walks applied to the graph isomorphism problem
- Quantum stochastic walks: A generalization of classical random walks and quantum walks
- Classical approach to the graph isomorphism problem using quantum walks
- Fast Escape from Quantum Mazes in Integrated Photonics
- Entanglement between charge qubits induced by a common dissipative environment
- Inverse counting statistics for stochastic and open quantum systems: the characteristic polynomial approach
- Dephasing-assisted transport in linear triple quantum dots
- Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs
- Fluctuating Currents in Stochastic Thermodynamics I. Gauge Invariance of Asymptotic Statistics
- A quantum-walk-inspired adiabatic algorithm for graph isomorphism
- Constructing physically intuitive graph invariants
- Comparing algorithms for graph isomorphism using discrete- and continuous-time quantum random walks
- Fisher Information With Respect to Cumulants
Cited by in corpus (5)
- Experimental Quantum Fast Hitting on Hexagonal Graphs
- From classical to quantum walks with stochastic resetting on networks
- Machine learning transfer efficiencies for noisy quantum walks
- Efficient learning of mixed-state tomography for photonic quantum walk
- Recurrence in discrete-time quantum stochastic walks