Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Marek Jul 31 '11 at 14:27
@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. – TheSheepMan Jul 31 '11 at 15:11
@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). – Niel de Beaudrap Sep 21 '11 at 10:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.