<p>A comment upgraded to partial answer:</p>

<p>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
<a href="http://www.scottaaronson.com/blog/?p=139" rel="nofollow noreferrer">http://www.scottaaronson.com/blog/?p=139</a>
or this answer by Peter Shor on MathOverflow
<a href="https://mathoverflow.net/questions/45106/quantum-pcp-theorem/45167#45167">https://mathoverflow.net/questions/45106/quantum-pcp-theorem/45167#45167</a></p>

<p>Concerning quantum approximation alpgorithms, you can look at this reference "Approximation algorithms for QMA-complete problems" 
<a href="http://arxiv.org/abs/1101.3884" rel="nofollow noreferrer">http://arxiv.org/abs/1101.3884</a></p>

CC BY-SA 3.0
2011-10-08T09:44:26.470Z
2011-10-08T09:44:26.470Z
2017-04-13T12:57:54.777Z
Anthony Leverrier
<p>I'm personally not aware of any work in the direction of <em>quantum</em> approximation algorithms in the sense of relative approximations (vs additive approximations) (though that doesn't necessarily mean they don't exist). </p>

<p>Note that if your intent is to design <em>poly-time</em> 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.</p>

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

CC BY-SA 3.0
2011-10-27T02:07:35.063Z
2011-10-27T02:07:35.063Z
Sevag Gharibian
<p>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.</p>

<p>Also, approximate counting speeds up a lot of sampling-based approximation algorithms.</p>

CC BY-SA 3.0
2011-11-21T08:37:54.320Z
2011-11-21T08:37:54.320Z
Aram Harrow
<p>An approximation algorithm for Optimization Algorithms is presented <a href="http://arxiv.org/pdf/1411.4028v1.pdf" rel="nofollow">here</a> - 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. </p>

CC BY-SA 3.0
2016-03-21T04:40:03.703Z
2016-03-21T04:40:03.703Z
user3483902
<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2011-10-06T08:53:36.467Z
I think this is quite a hot topic. People are in particular trying to prove (or not) a quantum PCP theorem. Concerning quantum approximation alpgorithms, you can look at this reference "Approximation algorithms for QMA-complete problems" http://arxiv.org/abs/1101.3884
Anthony Leverrier
CC BY-SA 3.0
2011-10-08T00:55:46.143Z
the closer thing I can think of is quantum property testing. Here we do have exponential separations.
Marcos Villagra
CC BY-SA 3.0
2011-10-08T05:44:44.653Z
@AnthonyLeverrier maybe this could be an answer ?
Suresh Venkat
<quantum-computing><approximation-algorithms>
Quantum approximation algorithms
Michal Kotowski
# Quantum approximation algorithms

(Asked by: username_0 on 2011-10-06)

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.

**Tags:** quantum-computing, approximation-algorithms

> **Comments:**
> **username_1**: I think this is quite a hot topic. People are in particular trying to prove (or not) a quantum PCP theorem. Concerning quantum approximation alpgorithms, you can look at this reference "Approximation algorithms for QMA-complete problems" http://arxiv.org/abs/1101.3884  
> **username_2**: the closer thing I can think of is quantum property testing. Here we do have exponential separations.  
> **username_3**: @AnthonyLeverrier maybe this could be an answer ?  

---

## 4 answers

### Answer by username_1 on 2011-10-08. Score: 14

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 by username_4 on 2011-10-27. Score: 9

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 by username_5 on 2011-11-21. Score: 7

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 by username_6 on 2016-03-21. Score: 0

An approximation algorithm for Optimization Algorithms is presented [here](http://arxiv.org/pdf/1411.4028v1.pdf) - 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.


---

