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: