Yuxiang Chen

We prove the decidability results for a sub-class of local state transformation problems, a fundamental problem in quantum information theory and quantum communication complexity. A local state transformation is specified by two bipartite quantum states $\rho^{AB}$ and $\sigma^{AB}$. Two non-communicating parties, Alice and Bob are provided with unbounded copies of the source state $\rho^{AB}$. The goal is to determine whether they can generate the target state that is arbitrarily close to the target state $\sigma^{AB}$ without communication. Ghazi, Kamath, and Sudan initiated the study of the decidability of the classical counterpart, non-interactive simulation of joint distributions, by introducing a machinery built on the theory of analysis on Boolean functions. With such a machinery, the decidability of non-interactive simulation of joint distributions was fully resolved by subsequent works. However, the decidability of local state transformations remains largely open. Qin and Yao resolved the case where the source state $\rho^{AB}$ is a noisy maximally entangled state. In this work, we show that whenever the source state $\rho^{AB}$ is classical, then local state transformations are decidable. Specifically, given $\delta>0$, the algorithm either outputs local operations that transform the source state to a state that is $\delta$-close to the target state or asserts that such local operations do not exist.