11
$\begingroup$

As the name already suggests, this question is a follow-up of this other. I was delighted with the quality of the answers, but I felt it would be immensely interesting if insights regarding optimization and approximation techniques were added, but might fall off-topic, hence this question.

From Blue's answer:

the rule of thumb in complexity theory is that if a quantum computer "can help" in terms of solving in polynomial time (with an error bound) iff the class of problem it can solve lies in BQP but not in P or BPP

How does this apply to approximation classes? Is there any specific topological, numerical, etc property of quantum computing that can be leveraged?

As an example of what could I be asking (but definitely not restricted to that!), take the Christofides algorithm: it exploits specific geometrical properties of the graph that it optimizes on (symmetry, triangle inequality): the salesman travels on a feasible world. But salesmen have also huge mass, and we can know their position and momentum at the same time with great precision. Maybe a quantum model could work as well for other kind of metrics with more relaxed restrictions, like the K-L divergence? In that case solving it would still be NP complete, but the optimization would apply for a broader topology. This example is maybe a long shot, but I hope you get what I mean. I don't really know if it makes sense at all, but the answer could also address it in that case :)

RELATED:

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The Quantum Approximate Optimization Algorithm is a good place to start for analyzing the relative performance of quantum algorithms on approximation problems. One result so far is that at p=1 QAOA can theoretically achieve an approximation ratio of 0.624 for MaxCut on 3-regular graphs. This result was obtained using brute force enumeration of the different possible cases. This is not a technique is which easily generalizable, so relatively little is known about the performance of QAOA on other problems.

As it currently stands QAOA uses very little structure in the combinatorial optimization problem and operates more along the lines of a direct search method. One possible consequence is that QAOA would be best used for problems where there is minimal structure. In this case there is nothing that classical algorithms could use to accelerate the search process.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Nice +1, thanks a lot! could you add some backup references? The text is somewhat difficult to follow by itself $\endgroup$
    – fr_andres
    Apr 6, 2018 at 10:42
  • 1
    $\begingroup$ Certainly, I have edited the answer, and also here is the relevant reference on QAOA arxiv.org/abs/1411.4028 $\endgroup$
    – hopefully coherent
    Apr 6, 2018 at 20:24

Your Answer

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

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