Environment-assisted analog quantum search

Abstract

Two main obstacles for observing quantum advantage in noisy intermediate-scale quantum computers (NISQ) are the finite precision effects due to control errors, or disorders, and decoherence effects due to thermal fluctuations. It has been shown that dissipative quantum computation is possible in presence of an idealized fully-engineered bath. However, it is not clear, in general, what performance can be achieved by NISQ when internal bath degrees of freedom are not controllable. In this work, we consider the task of quantum search of a marked node on a complete graph of $n$ nodes in the presence of both static disorder and non-zero coupling to an environment. We show that, given fixed and finite levels of disorder and thermal fluctuations, there is an optimal range of bath temperatures that can significantly improve the success probability of the algorithm. Remarkably for a fixed disorder strength $\sigma$, the system relaxation time decreases for higher temperatures within a robust range of parameters. In particular, we demonstrate that for strong disorder, the presence of a thermal bath increases the success probability from $1/(n{\sigma }^2)$ to at least $1/2$. While the asymptotic running time is approximately maintained, the need to repeat the algorithm many times and issues associated with unitary over-rotations can be avoided as the system relaxes to an absorbing steady state. Furthermore, we discuss for what regimes of disorder and bath parameters quantum speedup is possible and mention conditions for which similar phenomena can be observed in more general families of graphs. Our work highlights that in the presence of static disorder, even non-engineered environmental interactions can be beneficial for a quantum algorithm.

References in corpus (12)

• Quantum Computing in the NISQ era and beyond
• Surface codes: Towards practical large-scale quantum computation
• Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
• Universal computation by quantum walk
• Dephasing assisted transport: Quantum networks and biomolecules
• Environment-Assisted Quantum Transport
• Spatial search by quantum walk
• Highly efficient energy excitation transfer in light-harvesting complexes: The fundamental role of noise-assisted transport
• Universal computation by multi-particle quantum walk
• Fixed-point quantum search with an optimal number of queries
• Exploiting structured environments for efficient energy transfer: The phonon antenna mechanism
• Fixed-Point Adiabatic Quantum Search

Cited by in corpus (11)

• Quantum spatial search on graphs subject to dynamical noise
• Machine learning transfer efficiencies for noisy quantum walks
• Quantum pricing-based column-generation framework for hard combinatorial problems
• Ion Trap Long-Range XY Model for Quantum State Transfer and Optimal Spatial Search
• Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor
• Improved Upper Bounds for the Hitting Times of Quantum Walks
• 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
• Optimal Conditions for Environment-Assisted Quantum Transport on the Fully Connected Network
• Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics
• Optimal quantum spatial search with one-dimensional long-range interactions