Quantum state verification in the quantum linear systems problem

We analyze the complexity of quantum state verification in the context of solving systems of linear equations of the form Ax=b. We show that any quantum operation that verifies whether a given quantum state is within a constant distance from the solution of the quantum linear systems problem requires q=Ω(κ) uses of a unitary that prepares a quantum state proportional to b, and its inverse in the worst case. Here, κ is the condition number of the matrix A. For typical instances, we show that q=Ω(sqrt(κ)) with high probability. These lower bounds are almost achieved if quantum state verification is performed using known quantum algorithms for the quantum linear systems problem. The lower bounds for prepare-and-measure verification protocols are quadratically worse. An implication of our results is that variational and related approaches to this problem are significantly less efficient than other known approaches, which are guaranteed to converge.