Complexity of the separability problem

Cite this problem as Problem 44.

Problem

At a high level, the separability problem is to decide whether a bipartite mixed state is separable or far from separable. More precisely, let Sep(d,d) denote the convex set of separable density matrices acting on \mathbb{C}^d\otimes\mathbb{C}^d. The \epsilon-weak membership problem for Sep(d,d) is to decide whether a given bipartite density matrix \rho acting on \mathbb{C}^d\otimes\mathbb{C}^d (when given as d^2\times d^2 matrix entries) is in Sep(d,d) or \epsilon-far in trace distance from any state in Sep(d,d), promised that one is the case.

Question: what is the computational complexity of solving the \epsilon-weak membership problem for Sep(d,d) as a function of \epsilon and d?

Background

The complexity of the separability problem is intimately connected to the complexity of different quantum proof systems. The class QMA (Quantum Merlin-Arthur) is a quantum analogue of the class NP, where the verifier solves a decision problem with the help of a quantum proof state. An open question in complexity theory is whether QMA is as powerful as a variant called QMA(2), in which the verifier solves a decision problem with the help of two quantum proof states that are guaranteed to be unentangled with each other. Surprisingly, it appears that this “unentanglement guarantee” can be computationally powerful: it was shown in a sequence of works (Blier and Tapp [1], Aaronson, et al. [2], Chen and Drucker [3], Harrow and Montanaro [4]) that 3SAT can be decided by a polynomial-time quantum verifier that receives two O\left(\sqrt{n}\mbox{polylog}(n)\right)-qubit proofs where n is the number of variables in the 3SAT instance. In contrast it is believed that in the QMA setting (i.e. without the unentanglement guarantee) the minimum proof size is \Omega(n) qubits (i.e. linear). The only complexity class bounds on QMA(2) is that it contains QMA and is contained in NEXP (the exponential time version of NP). Both inclusions are trivial to prove. Surprisingly, they are the best known.

The connection with the separability problem is this: if for some constant \epsilon>0 there is a quasipolynomial time (i.e., dO(\log d)) algorithm for the \epsilon-weak membership problem for Sep(d,d), then this implies that QMA(2) is contained in EXP (which would be a better upper bound than NEXP). If furthermore there is a parallel quasipolynomial-time algorithm for the same separability problem, then QMA(2) would be contained in PSPACE.

Partial results

Gurvits [5], combined with a follow-up by Gharibian [6], showed that the \epsilon-weak membership problem for Sep(d,d) is NP-hard for ϵ\le1/p(d) where p(d) is some polynomial in d.

Brandao, Christandl and Yard [7] showed that there is a quasipolynomial time algorithm (i.e. one running in time dO(\log(d)) to decide a variant of the weak membership problem: it can decide between whether the input density matrix is separable or is \epsilon-far in the so-called LOCC norm, which can be smaller than the trace norm.

Shi and Wu [8] showed that that the optimization problem of computing \max_{\rho\in Sep(d,d)}Tr(Q\rho) over the set of separable states can be computed in time that is exponential in the Frobenius norm of Q.

References

  1. Blier, Hugue, and Alain Tapp. “All languages in NP have very short quantum proofs.” 2009 Third International Conference on Quantum, Nano and Micro Technologies. IEEE, 2009.
  2. Aaronson, Scott, et al. “The power of unentanglement.” 2008 23rd Annual IEEE Conference on Computational Complexity. IEEE, 2008.
  3. Chen, Jing, and Andrew Drucker. “Short multi-prover quantum proofs for SAT without entangled measurements.” arXiv preprint arXiv:1011.0716 (2010).
  4. Harrow, Aram W., and Ashley Montanaro. “Testing product states, quantum Merlin-Arthur games and tensor optimization.” Journal of the ACM (JACM) 60.1 (2013): 1-43.
  5. Gurvits, Leonid. “Classical deterministic complexity of Edmonds’ problem and quantum entanglement.” Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing. 2003.
  6. Gharibian, Sevag. “Strong NP-hardness of the quantum separability problem.” Quantum Information & Computation 10.3 (2010): 343-360.
  7. Brandão, Fernando GSL, Matthias Christandl, and Jon Yard. “A quasipolynomial-time algorithm for the quantum separability problem.” Proceedings of the forty-third annual ACM Symposium on Theory of Computing. 2011.
  8. Shi, Yaoyun, and Xiaodi Wu. “Epsilon-net method for optimizations over separable states.” Theoretical Computer Science 598 (2015): 51-63.