Quantum average-case distances*

The commonly used distance measures, such as trace distance or diamond norm, quantify the maximal statistical distinguishability of protocols utilizing objects of interest. Here we propose new measures of distance that quantify average-case statistical distinguishability via random quantum circuits. 

We consider the average Total Variation Distance (TVD) between two quantum protocols in which quantum states, measurements, or channels are intertwined with random quantum circuits, followed by standard-basis measurement. We show that for random circuits forming approximate unitary 4-designs, the average TVDs can be approximated by simple functions of the objects of interest. Importantly, these functions define bona fide distance measures with many desired properties such as subadditivity or (restricted) data-processing inequalities.

Based on analytical and numerical examples, we argue that average-case distances are more natural for characterizing NISQ devices than conventional distances. This is because when used to compare an ideal device to its noisy, experimental implementation, the latter quantify the worst-case performance of a device. On the contrary, average-case distances capture the generic behavior in experiments involving only moderate-depth quantum circuits.