Epsilon-net method for optimizations over separable states

Details Epsilon-net method for optimizations over separable states Epsilon-net method for optimizations over separable states

2011-12-04

arxiv.org/abs/1112.0808v1

Physics

Quantum Physics

21 pages. Comments are welcome

Scientific paper

We give algorithms for the optimization problem: $\max_\rho \ip{Q}{\rho}$, where $Q$ is a Hermitian matrix, and the variable $\rho$ is a bipartite {\em separable} quantum state. This problem lies at the heart of several problems in quantum computation and information, such as the complexity of QMA(2). While the problem is NP-hard, our algorithms are better than brute force for several instances of interest. In particular, they give PSPACE upper bounds on promise problems admitting a QMA(2) protocol in which the verifier performs only logarithmic number of elementary gate on both proofs, as well as the promise problem of deciding if a bipartite local Hamiltonian has large or small ground energy. For $Q\ge0$, our algorithm runs in time exponential in $\|Q\|_F$. While the existence of such an algorithm was first proved recently by Brand{\~a}o, Christandl and Yard [{\em Proceedings of the 43rd annual ACM Symposium on Theory of Computation}, 343--352, 2011], our algorithm is conceptually simpler.

Affiliated with

Also associated with

No associations

Rating

Epsilon-net method for optimizations over separable states does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Epsilon-net method for optimizations over separable states, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Epsilon-net method for optimizations over separable states will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-393205