Let's say I have a quantum adiabatic computer in a black-box that works perfectly, doesn't suffer from decoherence/noise problems, etc. Are there any proven bounds for an adiabatic algorithm that guarantees an answer within some constant factor of an optimum solution? Say, for the NP-hard bin-packing problem, for which a variety of classical algorithms have proven approximation factors?

  • $\begingroup$ So are you asking about physical computers or idealized computers (and so essentially the complexity class established via complexity theory)? If it's the first then I remember reading somewhere that quantum computers can't be faster than the classical ones precisely because decoherence can't be dealt with and the bigger system you have, the worse it will be (i.e. your assumption of perfectly adiabatic system is just wishful thinking). On the other hand, if you are interested purely in the complexity class then this is not the right site for the question. $\endgroup$
    – Marek
    Jul 31, 2011 at 14:27
  • $\begingroup$ @Marek, I'm interested here in what an actual adiabatic quantum computer can accomplish (with a reasonable number of qubits) assuming that it works well enough for the quantum threshold theorem to apply. $\endgroup$ Jul 31, 2011 at 15:11
  • $\begingroup$ @TheSheepMan: the reference to approximation factors confuses me. If I'm not mistaken, an error-free adiabatic computation will always give you the optimal solution (or rather, will accurately decide whichever NP problem is encoded by the final Hamiltonian). You should clarify whether you are looking for upper bounds on the complexity of NP-complete problems by adiabatic computation (they aren't very good), lower bounds on solving NP-complete problems classically (they don't exist), or whether adiabatic computers have a provable edge over classical for approximation problems (probably not). $\endgroup$ Sep 21, 2011 at 10:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.