28
$\begingroup$

Background

The complexity classes BPP, BQP, and QMA are defined semantically. Let me try to explain a little bit what is the difference between a semantic definition and a syntactic one. The complexity class P is usually defined as the class of languages accepted in polynomial time by a deterministic Turing machine. Although it seems to be a semantic definition at first, $P$ has an easy syntactic characterization, i.e. deterministic Turing machines with a clock counting the steps up to a fixed polynomial (take a deterministic Turing machine, add a polynomial clock to it such that the new machine will calculate the length of the input $n$, then the value of the polynomial $p(n)$, and simulate the original machine for $p(n)$ steps. The languages accepted by these machines will be in $P$ and there is at least one such machine for each set in $P$). There are also other syntactic characterizations for $P$ in descriptive complexity like $FO(LFP)$, first-order logic with the least fixed point operator. The situation is similar for PP. Having a syntactic characterization is useful, for example a syntactic characterization would allow us to enumerate the sets in the class effectively, and if the enumeration is efficient enough, we can diagonalize against the class to obtain a separation result like time and space hierarchy theorems.

My main question is:

Is there a syntactic characterization for BPP, BQP, or QMA?

I would also like to know about any time or space hierarchy theorem for semantic classes mentioned above.

The motivation for this question came from here. I used Google Scholar, the only result that seemed to be relevant was a citation to a master's thesis titled "A logical characterization of the computational complexity class BPP and a quantum algorithm for concentrating entanglement", but I was not able find an online version of it.

Improve this question
$\endgroup$
6
  • $\begingroup$ When you say, "we can diagonalize against the class to obtain a separation result..", please clarify. I know we can diagonalize against the class TIME(f(n)) to separate TIME(f) from TIME(g) where g = $\omega(f)$ (up to logarithmic terms), but is there such a diagonalization we can use against P to separate it from something else? $\endgroup$
    – Henry Yuen
    Commented Aug 11, 2010 at 17:10
  • 1
    $\begingroup$ Also, this is not a real answer, but using reasonable complexity assumptions, BPP = P (the result due to Implagiazzo and Wigderson), of course BPP would then be a syntactic class. What would be interesting would be to show that finding a syntactic characterization of BPP would imply derandomization of BPP. $\endgroup$
    – Henry Yuen
    Commented Aug 11, 2010 at 17:14
  • $\begingroup$ @Henry Yuen: We can prove P is not equal to EXP, but this also follows from the time hierarchy theorem. A more interesting question would be if there is a result that does not follow from the hierarchy theorems, but I can't think of one right now. Diagonalization results I can think of right now use simulation and therefore it seems to me that the strongest way of stating such a theorem will be w.r.t. the resource, but I may be wrong. This seems to be interesting and I will check if I can find a counterexample to my intuition. $\endgroup$
    – Kaveh
    Commented Aug 11, 2010 at 17:30
  • $\begingroup$ @Henry Yuen: Your second comment is also interesting, though I can't think of any reason why a syntactic characterization would imply derandomization by itself. $\endgroup$
    – Kaveh
    Commented Aug 11, 2010 at 17:32
  • 3
    $\begingroup$ @Henry: "finding a syntactic characterization of BPP would imply derandomization of BPP" would be very cool to prove. No idea how to prove it though. However (if I understand what you mean by "syntactic characterization") a syntactic characterization would imply a time hierarchy for BPP. I think the survey in Robin's nice answer covers this. $\endgroup$
    – Ryan Williams
    Commented Aug 12, 2010 at 3:09

2 Answers 2

Reset to default
17
$\begingroup$

No, I don't think any syntactic characterization is known for BPP, BQP or QMA. (BPP might turn out to be P, and then we'd have such a characterization of course.)

In particular we don't know any languages that are complete for either of these classes. A lot of people believe that classes like QMA do not even have complete languages. (See John Watrous' survey, where he says that "indeed it would be surprising if QMA were shown to have a complete problem having a vacuous promise.")

There are hierarchy theorems for BPP with 1 bit of advice, but I don't think we have any for BPP, BQP or QMA. For the advice-based results, see Hierarchy Theorems for Probabilistic Polynomial Time.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ well, local hamiltonian is complete for QMA, but it is a promise problem. Also, 5-QSAT is complete. As Watrous puts it, "vacuous promise" which means "decision problem". So, it is not expected that a complete decision problem exists for any semantic class. $\endgroup$
    – Marcos Villagra
    Commented Aug 12, 2010 at 1:38
  • $\begingroup$ "Language" traditionally means decision problem. That's why I said none of these classes are known to have complete languages. They all have complete promise problems, of course. $\endgroup$
    – Robin Kothari
    Commented Aug 12, 2010 at 2:46
3
$\begingroup$

This is more a comment than an answer (since I can't leave comments, yet):

I've looked into this question briefly this past winter. As far as I know there is no syntactic definitions of BPP, BQP, or QMA. If you introduce post selection to BQP then you have a syntactic definition, but that is only because PostBQP = PP and PP is syntactic.

@Henry Yuen I also don't understand why a syntactic definition of anything would imply derandomization... of course if BPP was also FOL + LFP then we would have derandomization but if BPP was FOL + other gadget then we would not know that without proving that LFP and the other gadget do the same things.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Artem, I don't understand why it would imply derandomization either, but as Ryan Williams said, it would be a very cool thing to prove. In my view, having that sort of thing would mean, informally, that all roads lead to derandomization of BPP, or that BPP is bound to be derandomized. Not only are some reasonable circuit lower bounds conditions for derandomization, but also the property of having a "syntactic characterization" (whatever that may mean formally)? That seems quite special. Well - this is all just mindsand, of course. $\endgroup$
    – Henry Yuen
    Commented Aug 12, 2010 at 6:14

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.