It is generally considered unlikely that quantum computers will be able to solve NP-complete problems efficiently. In the classical case one approach to tackle such problems is to use approximation algorithms. Has there been any research on approximation algorithms using quantum computing where quantumness gives significant speedup over classical approximation methods?
By "significant" I mean not necessarily exponential, but greater than for corresponding exact algorithms. In other words, I'm interested if relaxing the requirement that our algorithm yields the exact solution gives a significant advantage to quantum algorithms.