  Hybrid quantum-classical algorithms appear to be the most promising approach
for near-term quantum applications. An important bottleneck is the classical
optimization loop, where the multiple local minima and the emergence of barren
plateaux make these approaches less appealing. To improve the optimization the
Quantum Natural Gradient (QNG) method [Quantum 4, 269 (2020)] was introduced -
a method that uses information about the local geometry of the quantum
state-space. While the QNG-based optimization is promising, in each step it
requires more quantum resources, since to compute the QNG one requires $O(m^2)$
quantum state preparations, where $m$ is the number of parameters in the
parameterized circuit. In this work we propose two methods that reduce the
resources/state preparations required for QNG, while keeping the advantages and
performance of the QNG-based optimization. Specifically, we first introduce the
Random Natural Gradient (RNG) that uses random measurements and the classical
Fisher information matrix (as opposed to the quantum Fisher information used in
QNG). The essential quantum resources reduce to linear $O(m)$ and thus offer a
quadratic "speed-up", while in our numerical simulations it matches QNG in
terms of accuracy. We give some theoretical arguments for RNG and then
benchmark the method with the QNG on both classical and quantum problems.
Secondly, inspired by stochastic-coordinate methods, we propose a novel
approximation to the QNG which we call Stochastic-Coordinate Quantum Natural
Gradient that optimizes only a small (randomly sampled) fraction of the total
parameters at each iteration. This method also performs equally well in our
benchmarks, while it uses fewer resources than the QNG.
