Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on $n$-bits in time $\text{poly}(n) 2^{n/2}$. In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly …