Quantum memory advantage for quantum process tomography

Quantum process tomography is the task of characterizing an unknown quantum channel using black-box queries. A central question in quantum information is whether protocols that can store and jointly process quantum information (coherent protocols) offer a fundamental advantage in query complexity over those that must measure after each use (incoherent protocols). While this separation is well-established for state tomography, the scaling for general channels remained an open problem.

The authors determine the optimal query complexity for incoherent process tomography by proving a matching lower bound for adaptive protocols. They model each round of an adaptive incoherent protocol as a single-round tester acting on the channel's Choi operator. By constructing a hard family of channels centered around the completely depolarizing channel and using a posterior-tilt method, they analyze how the posterior distribution of the channel parameters evolves along a transcript. This allows them to prove that any adaptive incoherent protocol requires Omega(d_in^3 d_out^3 / epsilon^2) queries to achieve epsilon-accuracy in the diamond norm.

The study establishes that incoherent protocols, even when allowed arbitrary classical adaptivity and fresh ancilla assistance, are strictly less efficient than coherent protocols. Specifically, the query complexity for incoherent tomography is Theta(d_in^3 d_out^3 / epsilon^2), whereas coherent protocols achieve Theta(d_in^2 d_out^2 / epsilon^2). This confirms that the ability to maintain quantum coherence across channel uses provides a polynomial speedup in the number of queries required for full process tomography.

This result provides a definitive separation between coherent and incoherent learning resources for quantum processes. It clarifies that the advantage of quantum memory is not merely a matter of implementation but a fundamental constraint on the information-theoretic efficiency of learning unknown quantum dynamics. The findings generalize previous results for state tomography and provide a rigorous foundation for understanding the limits of quantum channel characterization.