Query-Optimal Estimation of Unitary Channels in Diamond Distance

Abstract: We will present an algorithm to learn an unknown unitary channel acting on a d-dimensional qudit to diamond-norm error ε, using O(d²/ε) applications of the unknown channel and only one qudit. This algorithm uses the optimal number of qudits and number of queries, even if one has access to the inverse or controlled versions of the unknown unitary. This improves over prior work, which achieves entanglement infidelity δ using O(d²/√δ) applications in parallel, thereby requiring Ω(d²) qudits. Based on joint work with Jeongwan Haah, Robin Kothari, and Ryan O'Donnell.
Bio: Ewin Tang is a fifth-year graduate student in computer science at the University of Washington, advised by James Lee. Her interests are broadly in randomized and quantum algorithms. Specifically, her work focuses on quantum linear algebra and learning of quantum systems. In one line of work, using techniques from sketching and sampling algorithms, she showed major barriers to practical speedups for several significant quantum machine learning algorithms.