For qubits, Monte Carlo estimation of the average fidelity of Clifford unitaries is efficient: it requires a number of experiments that is independent of the number
n of qubits and classical computational resources that scale only polynomially in
n. Here, we identify the requirements for efficient Monte Carlo estimation and the corresponding properties of the measurement operator basis when replacing two-level qubits by
p-level qudits. Our analysis illuminates the intimate connection between mutually unbiased measurements and the existence of unitaries that can be characterized efficiently. It allows us to propose a ``hierarchy'' of generalizations of the standard Pauli basis from qubits to qudits according to the associated scaling of resources required in Monte Carlo estimation of the average fidelity.
We show that the minimum experimental effort to estimate the average error of a quantum gate scales as 2(n) for n qubits and requires classical computational resources ∼n(2)2(3n) when no specific assumptions on the gate can be made. This represents a reduction by 2(n) compared to the best currently available protocol, Monte Carlo characterization. The reduction comes at the price of either having to prepare entangled input states or obtaining bounds rather than the average fidelity itself. It is achieved by applying Monte Carlo sampling to so-called 2-designs or two classical fidelities. For the specific case of Clifford gates, the original version of Monte Carlo characterization based on the channel-state isomorphism remains an optimal choice. We provide a classification of the available efficient strategies to determine the average gate error in terms of the number of required experimental settings, average number of actual measurements, and classical computational resources.
To certify that an experimentally implemented quantum transformation is a certain unitary operation
U on a
d-dimensional Hilbert space, it suffices to determine fidelities of output states for
d+1 suitably chosen pure input states [Reich et al., Phys. Rev. A 88, 042309 (2013)]. The set of these
d+1 probe states can consist of
d orthogonal states that form a basis and one additional state which is a balanced superposition of all
d basis states. Here we provide an analytical lower bound on quantum process fidelity for two-qubit quantum gates which results from the knowledge of average state fidelity for the basis states and the fidelity of the superposition state. We compare this bound with the Hofmann bound that is based on knowledge of average state fidelities for two mutually unbiased bases. We also discuss the possible extension of our findings to
N-qubit operations.
Shadow estimation is a powerful framework for predicting quantum properties from randomized measurements. While
3-design protocols achieve optimal worst-case performance, the minimal number of measurement bases required for such optimality has remained open. Here we prove that
Θ(d2) measurement bases are both necessary and sufficient for worst-case optimal shadow estimation and construct an explicit basis family. In stark contrast, any state
2-design already suffices for average-case optimality: the mean squared shadow norm of normalized observables is bounded by a universal constant, and we prove strong concentration for Haar-random states, yielding constant sample complexity for generic pure-state fidelity estimation. Easily implementable
2-designs -- from mutually unbiased bases, cyclic measurements, or shallow
O(logn)-depth circuits -- enable optimal average-case protocols with remarkably simple measurement strategies. Our results establish a fundamental complexity separation: worst-case estimation requires
Θ(d2) bases, whereas average-case performance requires only
Θ(d) bases, with broad implications for quantum information theory and near-term experiments.
Abstract Quantum state tomography (QST) represents an essential tool for the characterization, verification, and validation (QCVV) of quantum processors. Only for a few idealized scenarios, there are analytic results for the optimal measurement set for QST. E.g., in a setting of non-degenerate measurements, an optimal minimal set of measurement operators for QST has eigenbases which are mutually unbiased. However, in other set-ups, dependent on the rank of the projection operators and the size of the quantum system, the optimal choice of measurements for efficient QST needs to be numerically approximated. We have generalized this problem by introducing the framework of customized efficient QST. Here we extend customized QST and look for the optimal measurement set for QST in the case where some of the quantum gates applied in the measurement process are noisy. To achieve this, we use two distinct noise models: first, the depolarizing channel, and second, over- and under-rotation in single-qubit and to two-qubit gates (for further information, please see Methods). We demonstrate the benefit of using entangling gates for the efficient QST measurement schemes for two qubits at realistic noise levels, by comparing the fidelity of reconstruction of our optimized QST measurement set to the state-of-the-art scheme using only product bases.
Quantum fidelity estimation is essential for benchmarking quantum states and processes on noisy quantum devices. While stabilizer operations form the foundation of fault-tolerant quantum computing, nonstabilizer resources further enable universal quantum computation through state injection. In this work, we propose several efficient quantum fidelity estimation protocols for both quantum states and channels within the resource theory of nonstabilizerness, focusing on qudit systems with odd prime dimensions. Our fidelity estimation algorithms require measuring only a constant number of phase-space point operator expectation values, with operators selected randomly according to an importance weighting scheme tailored to the target state. Notably, we demonstrate that mathematically defined nonstabilizerness measures---such as Wigner rank and mana---quantify the sample complexity of the proposed protocols, thereby endowing them with a clear operational interpretation in the fidelity estimation task. This connection reveals a fundamental trade-off: while fidelity estimation for general quantum states and channels requires resources that scale exponentially with their nonstabilizerness, the task remains tractable for states and channels that admit efficient classical simulation.