Epsilon-net method for optimizations over separable states

We give algorithms for the optimization problem: maxρ⁡〈Q,ρ〉maxρ⁡〈Q,ρ〉, where Q is a Hermitian matrix, and the variable ρ is a bipartite 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 a logarithmic number of elementary gates on both proofs, as well as the promise problem of deciding if a bipartite local Hamiltonian has a large or small ground energy. For Q≥0Q≥0, our algorithm runs in time exponential in ‖Q‖F‖Q‖F. While the existence of such an algorithm was first proved recently by Brandão, Christandl and Yard (2011) [8], our algorithm is conceptually simpler.