Physics – Quantum Physics
Scientific paper
2011-12-04
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.
Shi Yaoyun
Wu Xiaodi
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-393205