# Is it possible to design an efficient approximation algorithm for one NP-complete problem based on Shor's algorithm?

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?

• 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 Mar 30 '12 at 16:22
• I think it is not known if Factoring is $\sf{P\text{-}hard}$, so the likely answer is none at the moment. – Kaveh Mar 30 '12 at 17:15
• @Kaveh why do you say that? P-hardness is wrt logspace reductions. How are logspace reductions related to this question? – Sasho Nikolov May 17 '15 at 7:26
• @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 May 17 '15 at 7:31
• @Kaveh Fair enough. Greg is digging out old questions :) – Sasho Nikolov May 17 '15 at 8:28

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.