Query-optimal estimation of unitary channels in diamond distance

We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a textsfd-dimensional qudit, we aim to output a classical description of a unitary that is varepsilon-close to the unknown unitary in diamond norm. We design an algorithm achieving error varepsilon using O(textsfd2/varepsilon) applications of the unknown channel and only one qudit. This improves over prior results, which use O(textsfd3/varepsilon2) [via standard process tomography] or O(textsfd2.5/varepsilon) [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to "bootstrap" an algorithm that can produce constant-error estimates to one that can produce varepsilon-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires Omega(textsfd2/varepsilon) applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.