Measurement Cost of Metric-Aware Variational Quantum Algorithms

We consider metric-aware quantum algorithms that use a quantum computer to efficiently estimate both a matrix and a vector object. For example, the recently introduced quantum natural gradient approach uses the Fisher matrix as a metric tensor to correct the gradient vector for the codependence of the circuit parameters. We rigorously characterize and upper bound the number of measurements required to determine an iteration step to a fixed precision, and propose a general approach for optimally distributing samples between matrix and vector entries. Finally, we establish that the number of circuit repetitions needed for estimating the quantum Fisher information matrix is asymptotically negligible for an increasing number of iterations and qubits.