Quantum approximation algorithms

Question

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.

Answer 1

A comment upgraded to partial answer:

There is quite some work these days on a conjectured (or not) quantum version of the PCP theorem: see for example this blog post by Scott Aaronson http://www.scottaaronson.com/blog/?p=139 or this answer by Peter Shor on MathOverflow https://mathoverflow.net/questions/45106/quantum-pcp-theorem/45167#45167

Concerning quantum approximation alpgorithms, you can look at this reference "Approximation algorithms for QMA-complete problems" http://arxiv.org/abs/1101.3884

Answer 2

I'm personally not aware of any work in the direction of quantum approximation algorithms in the sense of relative approximations (vs additive approximations) (though that doesn't necessarily mean they don't exist).

Note that if your intent is to design poly-time quantum approx algs for, say, NP-hard problems, many problems like MAX-CUT already have tight classical approx algs (assuming the Unique Games Conjecture or by PCP). So it likely makes sense to begin by studying a problem which has a gap in the known approximation ratio versus hardness results.

The other direction is hardness of approximation -- see e.g. http://arxiv.org/abs/0811.3412 and http://arxiv.org/abs/1012.3319 for partial positive and negative progress regarding a possible quantum PCP theorem.

Answer 3

Kind of a trivial answer, but there's estimating the acceptance probability of a quantum circuit, or of any of the equivalent problems, such as approximating the Jones polynomial, or the solution of a linear system of equations, or the trace of a power of a large sparse matrix.

Also, approximate counting speeds up a lot of sampling-based approximation algorithms.

Answer 4

An approximation algorithm for Optimization Algorithms is presented here - the paper presents an quantum approximation algorithm for an objective function that has a unitary gate that has its locality as an optimum of the objective function. For a fixed $i$, and one that varies with the size of input the quantum algorithm finds an approximation to the optimal solution. They have studied the application to MaxSat, and MAX-CUT(for some cases of regular graphs) optimization problems. The objective function for an optimization problem is seen as a special unitary operator, that concentrates the solution, and thereby achieves the approximation.