Benjamin Lovitz

We present explicit quantum channels with stictly sub-additive minimum output Rényi entropy for all p>1, improving upon prior constructions which handled p>2. Our example is provided by explicit constructions of linear subspaces with high geometric measure of entanglement. Our construction applies in both the bipartite and multipartite settings. As further applications, we use our construction to find entanglement witnesses with many highly negative eigenvalues, and to construct highly entangled mixed quantum states.

The problem of quantum state classification asks how accurately one can identify an unknown quantum state that is promised to be drawn from a known set of pure states. In this work, we introduce the notion of $k$-\emph{learnability}, which captures the ability to identify the correct state using at most $k$ guesses, with zero error. We show that deciding whether a given family of states is $k$-learnable can be solved via semidefinite programming. When there are $n$ states, we present polynomial-time (in $n$) algorithms for determining $k$-learnability for two cases: when $k$ is a fixed constant or the dimension of the states is a fixed constant. When both $k$ and the dimension of the states are part of the input, we prove that there exist succinct certificates placing the problem in NP, and we establish NP-hardness by a reduction from the classical $k$-clique problem. Together, our findings delineate the boundary between efficiently solvable and intractable instances of quantum state classification in the perfect (zero-error) regime.