When Diabatic Trumps Adiabatic in Quantum Optimization

Abstract

We provide and analyze examples that counter the widely made claim that tunneling is needed for a quantum speedup in optimization problems. The examples belong to the class of perturbed Hamming-weight optimization problems. In one case, featuring a plateau in the cost function in Hamming weight space, we find that the adiabatic dynamics that make tunneling possible, while superior to simulated annealing, result in a slowdown compared to a diabatic cascade of avoided level-crossings. This, in turn, inspires a classical spin vector dynamics algorithm that is at least as efficient for the plateau problem as the diabatic quantum algorithm. In a second case whose cost function is convex in Hamming weight space, the diabatic cascade results in a speedup relative to both tunneling and classical spin vector dynamics.

16 pages, 8 figures

Cited by in corpus (7)

• Quantum Annealing Correction with Minor Embedding
• Recent advances for quantum classifiers
• Training A Quantum Optimizer
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Approximating the quantum approximate optimization algorithm with digital-analog interactions
• The performance of the quantum adiabatic algorithm on spike Hamiltonians