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 '11 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$ – TheSheepMan Jul 31 '11 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$ – Niel de Beaudrap Sep 21 '11 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.