<p>There are ways to see that either the answer is probably no, or that the question means more than one thing and has a negotiable answer.   On the one hand, the PCP theorem says that many, but not all, NP-hard problems are still NP-hard to approximate.   The standard belief is that Grover's search algorithm, which gives you a quadratic speedup but no more than that, is the best quantum algorithm for the hardest NP-hard problems.  This leaves fairly little wiggle room to expect any quantum algorithm to have any special relation to approximation to NP-hard problems in general.</p>

<p>Some NP-hard problems are easier to approximate than the ones amenable to the PCP theorem.   However, the difficulty of approximation is then highly variable.</p>

<p>Meanwhile Shor's algorithm does something very specific:   It finds the period of a periodic function on the integers or on $\mathbb{Z}^n$.   This problem is also in the complexity class SZK, for example.   Maybe you could cook up an approximation problem to an NP-hard problem that lands you in SZK or period-finding, but I suspect that there aren't any known, natural examples of that.</p>

CC BY-SA 3.0
2015-05-17T04:40:16.330Z
2015-05-17T04:40:16.330Z
Greg Kuperberg
<p>Is it possible to design an efficient approximation algorithm for an $\sf{NP\text{-}complete}$ problem based on reductions from Shor's algorithm? </p>

<p>Are known any (classical) approximation algorithms for an $\sf{NP\text{-}complete}$ problem that uses Factoring as oracle?</p>

CC BY-SA 3.0
2012-03-30T16:22:29.227Z
While it might be possible, a deterrent to doing so would be that the true running time of the resulting approximation algorithm would be unknown (and it might not even be polynomial!)
Suresh Venkat
CC BY-SA 3.0
2012-03-30T17:15:39.057Z
I think it is not known if Factoring is $\sf{P\text{-}hard}$, so the likely answer is none at the moment.
Kaveh
CC BY-SA 3.0
2015-05-17T07:26:33.097Z
@Kaveh why do you say that? P-hardness is wrt logspace reductions. How are logspace reductions related to this question?
Sasho Nikolov
CC BY-SA 3.0
2015-05-17T07:31:20.950Z
@Sasho, this is from 3 years ago so I don't recall exactly, but I think I meant that we don't know how to do it for P so it is _unlikely_ we know how to do it for NP. :)
Kaveh
CC BY-SA 3.0
2015-05-17T08:28:26.857Z
@Kaveh Fair enough. Greg is digging out old questions :)
Sasho Nikolov
<cc.complexity-theory><quantum-computing><factoring>
Is it possible to design an efficient approximation algorithm for one NP-complete problem based on Shor's algorithm?
d. th. man
# Is it possible to design an efficient approximation algorithm for one NP-complete problem based on Shor's algorithm?

(Asked by: username_0 on 2012-03-30)

Is it possible to design an efficient approximation algorithm for an $\sf{NP\text{-}complete}$ problem based on reductions from Shor's algorithm?

Are known any (classical) approximation algorithms for an $\sf{NP\text{-}complete}$ problem that uses Factoring as oracle?

**Tags:** cc.complexity-theory, quantum-computing, factoring

> **Comments:**
> **username_1**: While it might be possible, a deterrent to doing so would be that the true running time of the resulting approximation algorithm would be unknown (and it might not even be polynomial!)  
> **username_2**: I think it is not known if Factoring is $\sf{P\text{-}hard}$, so the likely answer is none at the moment.  
> **username_3**: @username_2 why do you say that? P-hardness is wrt logspace reductions. How are logspace reductions related to this question?  
> **username_2**: @Sasho, this is from 3 years ago so I don't recall exactly, but I think I meant that we don't know how to do it for P so it is _unlikely_ we know how to do it for NP. :)  
> **username_3**: @username_2 Fair enough. Greg is digging out old questions :)  

---

## 1 answers

### Answer by username_4 on 2015-05-17. Score: 6

There are ways to see that either the answer is probably no, or that the question means more than one thing and has a negotiable answer. On the one hand, the PCP theorem says that many, but not all, NP-hard problems are still NP-hard to approximate. The standard belief is that Grover's search algorithm, which gives you a quadratic speedup but no more than that, is the best quantum algorithm for the hardest NP-hard problems. This leaves fairly little wiggle room to expect any quantum algorithm to have any special relation to approximation to NP-hard problems in general.

Some NP-hard problems are easier to approximate than the ones amenable to the PCP theorem. However, the difficulty of approximation is then highly variable.

Meanwhile Shor's algorithm does something very specific: It finds the period of a periodic function on the integers or on $\mathbb{Z}^n$. This problem is also in the complexity class SZK, for example. Maybe you could cook up an approximation problem to an NP-hard problem that lands you in SZK or period-finding, but I suspect that there aren't any known, natural examples of that.


---

