Consistency of Local Density Matrices Is QMA-Complete

DOI10.1007/11830924_40MaRDI QIDQ3595381zbMATH OpenOpenAlexFDO

Authors Yi-Kai Liu

Publication date 28 August 2007

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0604166

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Abstract: Suppose we have an n-qubit system, and we are given a collection of local density matrices rho_1,...,rho_m, where each rho_i describes a subset C_i of the qubits. We say that the rho_i are ``consistent if there exists some global state sigma (on all n qubits) that matches each of the rho_i on the subsets C_i. This generalizes the classical notion of the consistency of marginal probability distributions. We show that deciding the consistency of local density matrices is QMA-complete (where QMA is the quantum analogue of NP). This gives an interesting example of a hard problem in QMA. Our proof is somewhat unusual: we give a Turing reduction from Local Hamiltonian, using a convex optimization algorithm by Bertsimas and Vempala, which is based on random sampling. Unlike in the classical case, simple mapping reductions do not seem to work here.

Recommendations

• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• The Complexity of the Local Hamiltonian Problem
• Approximation algorithms for QMA-complete problems
• Two QCMA-complete problems

Cited in

(20)

• Ground-state spaces of frustration-free Hamiltonians
• On the power of a unique quantum witness
• Quantum simulation of quantum field theories as quantum chemistry
• scientific article; zbMATH DE number 6866233 (Why is no real title available?)
• The face lattice of the set of reduced density matrices and its coatoms
• The information theoretic interpretation of the length of a curve
• Quantum earth mover’s distance, a no-go quantum Kantorovich–Rubinstein theorem, and quantum marginal problem
• Eigenvalue distributions of reduced density matrices
• Global completability with applications to self-consistent quantum tomography
• Multi-theorem designated-verifier NIZK for QMA
• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
• Recoupling coefficients and quantum entropies
• Testing quantum circuits and detecting insecure encryption
• Rank reduction for the local consistency problem
• Zero-knowledge proof systems for QMA
• A variational principle for ground spaces
• Recoverability from direct quantum correlations
• Entropy constraints for ground energy optimization
• Application of fermionic marginal constraints to hybrid quantum algorithms
• Quantum marginals from pure doubly excited states

This page was built for publication: Consistency of Local Density Matrices Is QMA-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3595381)