Quantum algorithms have introduced a new paradigm in computing, but they typically estimate expectation values by sampling output probabilities of a quantum computer. In order to reduce the uncertainty of such an expectation value, one needs to repeat measurements in a quantum algorithm many times.
We consider the measurement cost of a large class of variational quantum algorithms in our preprint [1], such as imaginary time evolution and quantum natural gradient descent. All these approaches, which we refer to as metric-aware variational algorithms, depend on both a matrix and a vector object. This matrix object is a metric tensor and hence contains valuable information — which is responsible for the superior performance of natural gradient. However, this matrix might be expensive to estimate on a quantum computer due to its quadratic number of entries — which need to be measured independently.
We quantify how many measurements are required to obtain the natural gradient vector to a fixed precision and establish general scaling results. Surprisingly, after a large number of iterations, the cost of estimating the metric tensor is negligible. We furthermore establish that for a large number of qubits, estimating the gradient vector will dominate the measurement costs.
[1] B. van Straaten & B. Koczor, Measurement cost of metric-aware variational quantum algorithms. arXiv preprint: arXiv:2005.05172
