3
$\begingroup$

According to Wikipedia, APX contains those optimization problems in NP for which there exists a polynomial time algorithm which approximates the objective function multiplicatively to within a constant factor. A restricted subclass is PTAS (Polynomial Time Approximation Scheme), which makes no restrictions on the multiplicative approximation factor.

Are there quantum versions of the classes? Specifically, I mean if there is a commonly studied class containing optimization problems in QMA for which there exist polynomial time approximations to within a constant multiplicative factor (or possibly even any multiplicative factor). By briefly looking online, I could not find anything.

Possibly these approximate versions are included in BQP, although I'm not sure if one can say whether, in the classical case, P and APX are "the same", even if they both contains problems which can be solved in polynomial time.

$\endgroup$
2
  • 1
    $\begingroup$ I don’t know, but quantum algorithms outshine classical algorithms when we ask for precision up to additive error (and not multiplicative error) because there’s no sign problem… $\endgroup$ Commented May 3 at 12:14
  • 1
    $\begingroup$ Also, by analogy to MAX-3SAT-3 (which is an example given on Wikipedia) you could ask about some restricted local Hamiltonian problem where each qubit can only appear in a constant number of local terms? $\endgroup$ Commented May 3 at 12:18

1 Answer 1

1
$\begingroup$

Marked CW because I'm probably speaking with improper authority.


The classes FPTAS, PTAS, and APX are defined with respect to a classical polynomial-time algorithm to give the appropriate approximate answer; I don't know of any commonly-used name of any complexity class that allows for a quantum (BQP) algorithm to give the same.

We do know, as a consequence of the PCP theorem, that there are a lot of "hardness-of-approximation"-type results, implying that if a particular optimization problem had a polynomial-time algorithm to give an answer up to $(1\pm\varepsilon)$ of the correct answer for some constant $\varepsilon$ then P=NP. There are refinements of these hardness-of-approximation results, for example based on the Unique-Games Conjecture as well.

Regarding quantum algorithms, in particular I understand that there was some general hope that the QAOA algorithm would be able to beat the best-possible classical bound for certain NP-hard problems (such as MAX E3LIN). The original work wanted to show that the QAOA algorithm could saturate the Unique-Games bound (while still being below the PCP bound lest NP$\subseteq$BQP); later work seems to imply that QAOA, although having a lot of promise for shallow-depth circuits, doesn't so easily beat the best classical algorithms.

Also, the above classes APX, FPTAS, and PTAS generally ask for an answer to an optimization problem that is up to some multiplicative error $1/\varepsilon$ of the optimal question, and further the optimal answer (such as a TSP-tour length) must be non-negative. But quantum algorithms really begin to outperform classical algorithms when we ask for additive error, and when we are looking for answers that could be negative as well, because BQP algorithms help with the sign problem.

Lastly there is an equivalent, and as of yet unproven, quantum PCP conjecture relating how close of an error we can get with respect to the Local Hamiltonian Problem. You might want to search for the Guided Local Hamiltonian Problem, which seems to give a sliding scale between BPP, BQP, and QMA based on an error parameter $\varepsilon$.

$\endgroup$
1
  • $\begingroup$ It seems then that there isn't an answer to my question. However you provide a nice summary of results for approximate algorithms, so I approved your answer. Thanks for the references! $\endgroup$ Commented May 24 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.