Yangjing Dong

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.

Shallow quantum circuits have attracted increasing attention in recent years, due to the fact that current noisy quantum hardware can only perform faithful quantum computation for a short amount of time. The constant-depth quantum circuits $\mathsf{QAC}^0$, a quantum counterpart of $\mathsf{AC}^0$ circuits, are the polynomial-size and constant-depth quantum circuits composed of only single-qubit unitaries and polynomial-size generalized Toffoli gates. The computational power of $\mathsf{QAC}^0$ has been extensively investigated in recent years. In this paper, we are concerned with $\mathsf{QLC}^0$ circuits, which are linear-size $\mathsf{QAC}^0$ circuits, a quantum counterpart of $\mathsf{LC}^0$. * We show that depth-$d$ $\mathsf{QAC}^0$ circuits working on $n$ input qubits and $a$ ancilla qubits have approximate degree at most $\tilde{O}((n+a)^{1-2^{-d}})$, improving the $\tilde{O}((n+a)^{1-3^{-d}})$ degree upper bound of previous works. Consequently, this directly implies that to compute the parity function, $\mathsf{QAC}^0$ circuits need at least $\tilde{O}(n^{1+2^{-d}})$ circuit size. * We present the first agnostic learning algorithm for $\mathsf{QLC}^0$ channels using subexponential running time and queries. Moreover, we also establish exponential lower bounds on the query complexity of learning $\mathsf{QAC}^0$ channels under both the spectral norm distance of the Choi matrix and the diamond norm distance. * We present a tolerant testing algorithm which determines whether an unknown quantum channel is a $\mathsf{QLC}^0$ channel. This tolerant testing algorithm is based on our agnostic learning algorithm. Our approach leverages low-degree approximations of $\mathsf{QAC}^0$ circuits and Pauli analysis as key technical tools. Collectively, these results advance our understanding of agnostic learning for shallow quantum circuits.