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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
15
References
0
Citations
NaN
KQI