Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad

Abstract

We consider classical and quantum algorithms which have a duality property: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. This enables one to give guarantees that the algorithm will find such a nontrivial improvement: if few solutions exist which are much worse than random, then a nontrivial improvement is guaranteed. The quantum algorithm is based on a sudden of a Hamiltonian; while the algorithm is general, we analyze it in the specific context of MAX-$K$-LIN$2$, for both even and odd $K$. The classical algorithm is a "dequantization of this algorithm", obtaining the same guarantee (indeed, some results which are only conjectured in the quantum case can be proven here); however, the quantum point of view helps in analyzing the performance of the classical algorithm and might in some cases perform better.

arXiv commentv2 final version published in Quantum

References in corpus (11)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum walks: a comprehensive review
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Spatial search by quantum walk
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Anderson localization casts clouds over adiabatic quantum optimization
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Lieb-Robinson bounds for commutator-bounded operators

Cited by in corpus (9)

• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Finding spin-glass ground states using quantum walks
• An energetic perspective on rapid quenches in quantum annealing
• Analytical Framework for Quantum Alternating Operator Ansätze
• Fermionic Quantum Approximate Optimization Algorithm
• Fluctuation guided search in quantum annealing
• Counterdiabatic Driving with Performance Guarantees
• Grover Speedup from Many Forms of the Zeno Effect
• Performance of Domain-Wall Encoding for Quantum Annealing