Characterising the intersection of QMA and coQMA

2021 
We show that the functional analogue of $$\textsc {QMA} \cap \textsc {coQMA} $$ , denoted $$\mathrm{F}(\textsc {QMA} \cap \textsc {coQMA} )$$ , equals the complexity class Total Functional $$\textsc {QMA} $$ ( $$\textsc {TFQMA} $$ ). To prove this, we need to introduce an alternative definition of $$\textsc {QMA} \cap \textsc {coQMA} $$ in terms of a single quantum verification procedure. We show that if $$\textsc {TFQMA} $$ equals the functional analogue of $$\textsc {BQP} $$ ( $$\textsc {FBQP} $$ ), then $$\textsc {QMA} \cap \textsc {coQMA} = \textsc {BQP} $$ . We show that if there is a $$\textsc {QMA} $$ complete problem that (robustly) reduces to a problem in $$\textsc {TFQMA} $$ , then $$\textsc {QMA} \cap \textsc {coQMA} = \textsc {QMA} $$ . Our results thus imply that if some of the inclusions between functional classes $$\textsc {FBQP} \subseteq \textsc {TFQMA} \subseteq \textsc {FQMA} $$ are in fact equalities, then the corresponding inclusions in $$\textsc {BQP} \subseteq \textsc {QMA} \cap \textsc {coQMA} \subseteq \textsc {QMA} $$ are also equalities.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    15
    References
    0
    Citations
    NaN
    KQI
    []