In analogy with the classical complexity class Total Functions from NP (TFNP), we introduce the complexity class of Total Functions from QMA (TFQMA). In this complexity class one is given a family of quantum circuits Qn that takes as input a classical string x of length n and a quantum state psi, such that for all x, there exists a witness, i.e. a psi such that Q_n(x,psi)=1 with probability > 2/3. The functional problem is then, given Q_n and x, find a psi such that Q_n(x,psi)=1 with probability > 2/3. The complexity of this class lies between the functional analogs of BQP and QMA, denoted FBQP and FQMA respectively. We provide examples of problems that lie in FQMA, 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 QMA, in fact belongs to TFQMA. We conclude by discussing the relation between TFQMA, public key quantum money, and the complexity of quantum states.

Apr
24

Comments are closed.