Consistency of Local Density Matrices Is QMA-Complete

DOI10.1007/11830924_40zbMATH Open1155.68399arXivquant-ph/0604166OpenAlexW2131575873MaRDI QIDQ3595381FDOQ3595381

Authors: Yi-Kai Liu 

Publication date: 28 August 2007

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

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.

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

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

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• The face lattice of the set of reduced density matrices and its coatoms
• Quantum earth mover’s distance, a no-go quantum Kantorovich–Rubinstein theorem, and quantum marginal problem
• The information theoretic interpretation of the length of a curve
• 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
• Zero-knowledge proof systems for QMA
• Rank reduction for the local consistency problem
• 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)