  Variational quantum algorithms are promising tools for near-term quantum
computers as their shallow circuits are robust to experimental imperfections.
Their practical applicability, however, strongly depends on how many times
their circuits need to be executed for sufficiently reducing shot-noise. We
consider metric-aware quantum algorithms: variational 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
quantum Fisher information matrix as a metric tensor to correct the gradient
vector for the co-dependence of the circuit parameters. We rigorously
characterise 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.
