Total Functions in QMA
arXiv:1805.00670 · doi:10.1007/s11128-020-02959-0
Abstract
The complexity class QMA is the quantum analog of the classical complexity class NP. The functional analogs of NP and QMA, called functional NP (FNP) and functional QMA (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 NP (TFNP) is the subset of FNP for which it can be shown that the NO outcome never occurs. TFNP includes many natural and important problems. In the present work we introduce the complexity class of Total Functional QMA (TFQMA), the quantum analog of TFNP. We show that FQMA and TFQMA can be defined in such a way that they do not depend on the values of the completeness and soundness probabilities. In so doing we introduce new notions such as the eigenbasis and spectrum of a quantum verification procedure which are of interest by themselves. We then provide examples of problems that lie in 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 QMA, in fact belongs to TFQMA. We also provide a simple oracle with respect to which we have a separation between FBQP and TFQMA. In the conclusion we discuss the relation between TFQMA, public key quantum money, and the complexity of quantum states.
arXiv comment24 pages. Final version to be published in Quantum Information Processing
References in corpus (16)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Quantum Algorithms Revisited
- Quantum fingerprinting
- Quantum measurements and the Abelian Stabilizer Problem
- Quantum Copy-Protection and Quantum Money
- Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
- Succinct quantum proofs for properties of finite groups
- A Quantum Lovasz Local Lemma
- When a local Hamiltonian must be frustration-free
- The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
- On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
- A constructive commutative quantum Lovasz Local Lemma, and beyond
- An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma
- Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete
- A Constructive Quantum Lovász Local Lemma for Commuting Projectors