Quantum Multi-Resolution Measurement with application to Quantum Linear Solver
Yoshiyuki Saito, Xinwei Lee, Cai, Dongsheng, Nobuyoshi Asai · arXiv (Cornell University) · 2023
Quantum computation consists of a quantum state corresponding to a solution, and measurements with some observables. To obtain a solution with an accuracy $ε$, measurements $O(n/ε^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 $ε$ in $O(n\log(1/ε))$ measurements using a pair of functions. The QMRM computational cost with an accuracy $ε$ is smaller than $O(n/ε^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 $ε$ in $O(n\log(1/ε))$ measurements.