Chia-Ying Lin

Learning about quantum states is a fundamental problem in physics and quantum computing. As people are often interested in certain properties of quantum states instead of a complete description, shadow tomography has gained significant attention, where the goal is to learn the expectation values of $M$ observables $O_1, \ldots, O_M$ with $\varepsilon$ accuracy. In near-term devices, however, noise is prevalent and often unexpected. Thus, it is crucial to design algorithms that work well in the worst case. We study the practical single-copy setting and assume $\gamma$-fraction of the \emph{outcomes} can be arbitrarily corrupted by an adversary. We show that all non-adaptive shadow tomography algorithms must incur an error of $\varepsilon=\tilde{\Omega}(\gamma\min\{\sqrt{M}, \sqrt{d}\})$ for some choice of observables, even with unlimited copies. Unfortunately, the classical shadows algorithm by \cite{huang2020predicting} and naive algorithms that directly measure each observable suffer even more. We design an algorithm that achieves an error of $\varepsilon=\tilde{O}(\gamma\max_{i\in[M]}\|O_i\|_{HS})$, which nearly matches our worst-case error lower bound for $M\ge d$ and guarantees better accuracy when the observables have stronger structure. Remarkably, the algorithm only needs $n=\frac{1}{\gamma^2}\log(M/\delta)$ copies to achieve that error with probability at least $1-\delta$, matching the sample complexity of the classical shadows algorithm that achieves the same error without corrupted measurement outcomes. Our algorithm is conceptually simple and easy to implement. Classical simulation for fidelity estimation shows that our algorithm enjoys much stronger robustness than~\cite{huang2020predicting} under adversarial noise. Finally, based on a reduction from full-state tomography to shadow tomography, we prove that for rank $r$ states, both the near-optimal asymptotic error of $\eps=\tilde{O}(\gamma\sqrt{r})$ \emph{and} copy complexity $\tilde{O}(dr^2/\eps^2)=\tilde{O}(dr/\gamma^2)$ can be achieved for adversarially robust state tomography, closing the large gap in \cite{AliakbarpourBCL2025robustquantum} where optimal error can only be achieved using pseudo-polynomial number of copies in $d$.

Learning the closest matrix product state (MPS) representation of a quantum state is known to enable useful tools for prediction and analysis of complex quantum systems. In this work, we study the problem of learning MPS in following setting: given many copies of an input MPS, the task is to recover a classical description of the state. The best known polynomial-time algorithm, introduced by [LCLP10, CPF+10], requires linear circuit depth and $O(n^5)$ samples, and has seen no improvement in over a decade. The combination of linear circuit depth and large sample complexity, neither known to be optimal, renders existing algorithms impractical for near-term quantum devices with limited resources. We show a new efficient MPS learning algorithm that runs in $O(\log n)$ depth and has sample complexity $O(n^3)$. Also, we can generalize our algorithm to learn the closest MPS state, in which the input state is not guaranteed to be close to the MPS with a fixed bond dimension. Our algorithms also improve both sample complexity and circuit depth of the previous known algorithm. On the lower bound side, we show that every algorithm must use $\Omega(n)$ copies of the state.