I have an algorithm that on all examples I was running finds an arbitrary approximation of global minimum of binary quadratic program. The algorithm find the minimum in polynomial time. Binary quadratic program is NP-complete, and I cannot prove theoretically, that the algorithm always finds the right solution (it always does in practice). The memory requirement for the algorithm is in current implementation $ n^8 $, where n is the dimension of the problem, it can be reduced to $ n^4 $ leading to possibility to solve the problem in about 50 dimensions, although running time is large - the algorithm have to solve the semi-definite program in $ n^4 $ dimension.

Is there any practical application this algorithm can be used?
What benchmarks tests should be performed to demonstrate practical usefulness of the algorithm?

I'm not sure I'm allowed to post the link, so you can find details of the algorithm, and its python implementation though the link in my profile, or here, if link works.

PS. I apologize if this is off topic question, I got algorithm by a complete chance, and have no idea where and how to communicate it.

PPS. I know it goes completely against the public opinion, but this is a testable objective, so give it a chance to survive, at least to the moment when it finds counterexample, or can be used as a practical application without a proof.

  • $\begingroup$ Silly comment: I have learned that BQP does not always mean bounded-error quantum polynomial time. $\endgroup$ Jan 31, 2011 at 18:34
  • $\begingroup$ BQP is removed. $\endgroup$
    – mkatkov
    Jan 31, 2011 at 18:37
  • $\begingroup$ Oh. I did not mean “Do not use the word BQP for other meanings than what I know!” $\endgroup$ Jan 31, 2011 at 20:18
  • $\begingroup$ I was kicked to death by the experts, so I prefer to follow any expert's advise, that does not change meaning, to get something useful. $\endgroup$
    – mkatkov
    Jan 31, 2011 at 20:27
  • $\begingroup$ You could outline your idea here to give people an idea of what you are talking about. Also, your statement "if it cannot be proved it can be used" (from your blog) disturbs me. $\endgroup$
    – Raphael
    Jan 31, 2011 at 23:14

1 Answer 1


The Biq Mac library provides a collection of instances four your problem.

  • $\begingroup$ (!) The approximation and heuristic methods works in the problem space, and not in the quadratic monomial space, that means they will always outperform. I read it as there is no practical application for exact algorithm, that is slower then approximated one. (!!) Therefore exact algorithm is interesting only when there is a proof it is exact, then I do not see how to communicate the observation :(. $\endgroup$
    – mkatkov
    Feb 1, 2011 at 14:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.