  The Quantum Fisher Information (QFI) is a central metric in promising
algorithms, such as Quantum Natural Gradient Descent and Variational Quantum
Imaginary Time Evolution. Computing the full QFI matrix for a model with $d$
parameters, however, is computationally expensive and generally requires
$\mathcal{O}(d^2)$ function evaluations. To remedy these increasing costs in
high-dimensional parameter spaces, we propose using simultaneous perturbation
stochastic approximation techniques to approximate the QFI at a constant cost.
We present the resulting algorithm and successfully apply it to prepare
Hamiltonian ground states and train Variational Quantum Boltzmann Machines.
