Quantum Multi-Resolution Measurement with application to Quantum Linear Solver

Quantum computation consists of a quantum state corresponding to a solution, and measurements with some observables. To obtain a solution with an accuracy $\epsilon$, measurements $O(n/\epsilon^2)$ are required, where $n$ is the size of a problem. The cost of these measurements requires a large computing time for an accurate solution. In this paper, we propose a quantum multi-resolution measurement (QMRM), which is a hybrid quantum-classical algorithm that gives a solution with an accuracy $\epsilon$ in $O(n\log(1/\epsilon))$ measurements using a pair of functions. The QMRM computational cost with an accuracy $\epsilon$ is smaller than $O(n/\epsilon^2)$. We also propose an algorithm entitled QMRM-QLS (quantum linear solver) for solving a linear system of equations using the Harrow-Hassidim-Lloyd (HHL) algorithm as one of the examples. We perform some numerical experiments that QMRM gives solutions to with an accuracy $\epsilon$ in $O(n\log(1/\epsilon))$ measurements.