The quantum adiabatic search with decoherence in the instantaneous energy eigenbasis

Abstract

In Phys. Rev. A {\bf 71}, 060312(R) (2005) the robustness of the local adiabatic quantum search to decoherence in the instantaneous eigenbasis of the search Hamiltonian was examined. We expand this analysis to include the case of the global adiabatic quantum search. As in the case of the local search the asymptotic time complexity for the global search is the same as for the ideal closed case, as long as the Hamiltonian dynamics is present. In the case of pure decoherence, where the environment monitors the search Hamiltonian, we find that the time complexity of the global quantum adiabatic search scales like $N^{3/2}$, where $N$ is the list length. We moreover extend the analysis to include success probabilities $p<1$ and prove bounds on the run time with the same scaling as in the conditions for the $p\to 1$ limit. We supplement the analytical results by numerical simulations of the global and local search.

Material added, journal reference added

References in corpus (12)

• Quantum Mechanics helps in searching for a needle in a haystack
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Holonomic Quantum Computation
• Quantum Search by Local Adiabatic Evolution
• Robustness of adiabatic quantum computation
• Quantum limit of decoherence: Environment induced superselection of energy eigenstates
• Adiabatic approximation in open quantum systems
• Genuine quantum trajectories for non-Markovian processes
• Noise resistance of adiabatic quantum computation using random matrix theory
• Adiabatic Approximation for weakly open systems
• Robustness of the adiabatic quantum search
• From quantum circuits to adiabatic algorithms

Cited by in corpus (28)

• Decoherence in adiabatic quantum computation
• Error correcting codes for adiabatic quantum computation
• Internal Consistency of Fault-Tolerant Quantum Error Correction in Light of Rigorous Derivations of the Quantum Markovian Limit
• Robust quantum optimizer with full connectivity
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Non-Markovian decoherence in the adiabatic quantum search algorithm
• Performance of two different quantum annealing correction codes
• Mean Field Analysis of Quantum Annealing Correction
• Quantum Computation Beyond the Circuit Model
• Relaxation vs. adiabatic quantum steady state preparation: which wins?
• Analog Nature of Quantum Adiabatic Unstructured Search
• Adiabatic Quantum Search in Open Systems
• Complex instruction set computing architecture for performing accurate quantum $Z$ rotations with less magic
• Variationally Scheduled Quantum Simulation
• Effects of dissipation in an adiabatic quantum search algorithm
• Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Signatures of Open and Noisy Quantum Systems in Single-Qubit Quantum Annealing
• The adiabatic theorem in the presence of noise
• Error Suppression for Hamiltonian Quantum Computing in Markovian Environments
• Success of digital adiabatic simulation with large Trotter step
• Quantum annealing with twisted fields
• Landau-Zener evolution under weak measurement: Manifestation of the Zeno effect under diabatic and adiabatic measurement protocols
• Arbitrary-time error suppression for Markovian adiabatic quantum computing using stabilizer subspace codes
• VanQver: The Variational and Adiabatically Navigated Quantum Eigensolver
• Hilbert Space Average Method and adiabatic quantum search
• Hardware-efficient quantum annealing with error mitigation via classical shadow
• Adiabatic Quantum Computing
• Bounding Run-Times of Local Adiabatic Algorithms