What is the complexity of the quantum unconstrained binary optimization (QUBO) algorithm in the number of queries to the quantum processor?

To clarify, I'm asking about the complexity on quantum annealers.

  • 1
    $\begingroup$ Hi and welcome to the Quantum Computing SE. Could you please be more specific? Do you mean universal gate-based quantum processor or quantum annealer? $\endgroup$ Sep 2 '20 at 6:53
  • 1
    $\begingroup$ If you are asking about the complexity of solving the QUBO problem on a quantum computer: note that the QUBO problem is NP-complete (mentioned e.g. here), and hence it seems unlikely that quantum computers will have a better complexity (in general) than classical computers. $\endgroup$
    – smapers
    Sep 2 '20 at 13:44
  • 1
    $\begingroup$ @MartinVesely I was asking about quantum annealers. Sorry for the initial lack of clarity. $\endgroup$ Sep 3 '20 at 8:19
  • 1
    $\begingroup$ @ShenZhuoran you can (and are encouraged to) edit your post to add more information and context whenever needed $\endgroup$
    – glS
    Sep 4 '20 at 9:28

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.