  We provide several advances to the understanding of the class of Quantum
Merlin-Arthur proof systems (QMA), the quantum analogue of NP. Our central
contribution is proving a longstanding conjecture that the Consistency of Local
Density Matrices (CLDM) problem is QMA-hard under Karp reductions. The input of
CLDM consists of local reduced density matrices on sets of at most k qubits,
and the problem asks if there is an n-qubit global quantum state that is
consistent with all of the k-qubit local density matrices. The containment of
this problem in QMA and the QMA-hardness under Turing reductions were proved by
Liu [APPROX-RANDOM 2006]. Liu also conjectured that CLDM is QMA-hard under Karp
reductions, which is desirable for applications, and we finally prove this
conjecture. We establish this result using the techniques of simulatable codes
of Grilo, Slofstra, and Yuen [FOCS 2019], simplifying their proofs and
tailoring them to the context of QMA.
  In order to develop applications of CLDM, we propose a framework that we call
locally simulatable proofs for QMA: this provides QMA proofs that can be
efficiently verified by probing only k qubits and, furthermore, the reduced
density matrix of any k-qubit subsystem of an accepting witness can be computed
in polynomial time, independently of the witness. Within this framework, we
show advances in quantum zero-knowledge. We show the first commit-and-open
computational zero-knowledge proof system for all of QMA, as a quantum analogue
of a "sigma" protocol. We then define a Proof of Quantum Knowledge, which
guarantees that a prover is effectively in possession of a quantum witness in
an interactive proof, and show that our zero-knowledge proof system satisfies
this definition. Finally, we show that our proof system can be used to
establish that QMA has a quantum non-interactive zero-knowledge proof system in
the secret parameter setting.
