Inapproximability of positive semidefinite permanents and quantum state tomography

DOI10.1007/S00453-023-01169-1arXiv2111.03142OpenAlexW4386402372MaRDI QIDQ6088302

Alexander Meiburg

Publication date: 13 December 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2111.03142

zbMATH Keywords

positive semidefiniteNP-hardHermitian matrixquantum state tomographymatrix permanent

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorics and complexity of partition functions
• The complexity of computing the permanent
• Matrix integrals and map enumeration: an accessible introduction
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• Maximizing products of linear forms, and the permanent of positive semidefinite matrices
• A remark on approximating permanents of positive definite matrices
• How to Integrate a Polynomial over a Sphere
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• The learnability of quantum states
• Sample-optimal tomography of quantum states
• Optimal, reliable estimation of quantum states
• Two Algorithmic Results for the Traveling Salesman Problem
• Iterative algorithm for reconstruction of entangled states
• Shadow tomography of quantum states
• Efficient quantum tomography
• The complexity of satisfiability problems
• The permanent analogue of the Hadamard determinant theorem
• On the complexity of \(k\)-SAT

This page was built for publication: Inapproximability of positive semidefinite permanents and quantum state tomography