Total functions in QMA

Abstract

The complexity class ${\textsc {QMA}}$ is the quantum analog of the classical complexity class ${\textsc {NP}}$. The functional analogs of ${\textsc {NP}}$ and ${\textsc {QMA}}$, called functional ${\textsc {NP}}$ (${\textsc {FNP}}$) and functional ${\textsc {QMA}}$ (${\textsc {FQMA}}$), consist in either outputting a (classical or quantum) witness or outputting NO if there does not exist a witness. The classical complexity class total functional ${\textsc {NP}}$ (${\textsc {TFNP}}$) is the subset of ${\textsc {FNP}}$ for which it can be shown that the NO outcome never occurs. ${\textsc {TFNP}}$ includes many natural and important problems. Here we introduce the complexity class total functional ${\textsc {QMA}}$ (${\textsc {TFQMA}}$), the quantum analog of ${\textsc {TFNP}}$. We show that ${\textsc {FQMA}}$ and ${\textsc {TFQMA}}$ can be defined in such a way that they do not depend on the values of the completeness and soundness probabilities. We provide examples of problems that lie in ${\textsc {TFQMA}}$, coming from areas such as the complexity of k-local Hamiltonians and public key quantum money. In the context of black-box groups, we note that group non-membership, which was known to belong to ${\textsc {QMA}}$, in fact belongs to ${\textsc {TFQMA}}$. We also provide a simple oracle with respect to which we have a separation between ${\textsc {FBQP}}$ and ${\textsc {TFQMA}}$.