QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge

Abstract

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.

Published at SICOMP. Retracted section regarding statistical zero-knowledge arguments for QMA

References in corpus (7)

• Restrictions on Transversal Encoded Quantum Gate Sets
• N-representability is QMA-complete
• Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model
• Quantum Money from Hidden Subspaces
• Non-interactive classical verification of quantum computation
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Tight quantum security of the Fiat-Shamir transform for commit-and-open identification schemes with applications to post-quantum signature schemes

Cited by in corpus (16)

• Non-interactive classical verification of quantum computation
• Jordan products of quantum channels and their compatibility
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Preparation and verification of tensor network states
• Secure Software Leasing
• Electronic Structure in a Fixed Basis is QMA-complete
• Multi-theorem (Malicious) Designated-Verifier NIZK for QMA
• On The Round Complexity of Secure Quantum Computation
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds
• Entropy scaling law and the quantum marginal problem: simplification and generalization
• Classical proofs of quantum knowledge
• Classically Verifiable NIZK for QMA with Preprocessing
• Certified Everlasting Zero-Knowledge Proof for QMA
• Post-quantum Zero Knowledge in Constant Rounds
• Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round
• Non-Destructive Zero-Knowledge Proofs on Quantum States, and Multi-Party Generation of Authorized Hidden GHZ States