# Solving linear system $Ax=b$ with exponential speed-up via binary optimization?

The main disadvantage of HHL algorithm for solving $$A|x\rangle = |b\rangle$$ is that exponential speed-up is reached only in case we are interested in value $$\langle x|M|x\rangle$$, where $$M$$ is a matrix. In case we want to know solution $$|x\rangle$$ itself, we neeed to do measurement which cancel the speed-up out completely.

In the article Experimental realization of quantum algorithm for solving linear systems of equations a method encoding matrix $$A$$ into a Hamiltonian and using adibatic quantum computation for solving the linear system is proposed. Unfortunately, the authors do not discuss complexity of the algorithm in terms of the dimensions of matrix $$A$$ but only a condition number of $$A$$.

This article inpired me to translate problem $$A|x\rangle = |b\rangle$$ to a binary optimization task:

• each row of $$A|x\rangle = |b\rangle$$ is $$\sum_{j=1}^{n}a_{ij}x_j = b_i$$
• hence solution of $$A|x\rangle = |b\rangle$$ fulfills $$f(x)=\sum_{i=1}^{n}(\sum_{j=1}^{n}a_{ij}x_j - b_i)^2=0$$
• minizing $$f(x)$$, we come to the solution
• since variables $$x_i \in \mathbb{R}$$ (I do not assume complex matrix $$A$$ and vector $$|b\rangle$$), we have to express them in binary number system, e.g. $$x_i = \sum_{k=-m_1}^{m_2}2^k x_{ik}$$, where $$m_1, m_2 \in \mathbb{N}$$ specify accuracy and $$x_{ik}$$ is $$k$$th bit in binary representation of variable $$x_i$$

In the end, we came to binary optimization task $$\sum_{i=1}^{n}\left(\sum_{j=1}^{n}a_{ij}\sum_{k=-m_1}^{m_2}2^k x_{jk} - b_i\right)^2 \rightarrow \min$$

Such minimization can be done with algorithms like QAOA or VQE, or a quantum annealing machine. However, in this case we do not have any proof (only empirical) that such algorithms bring about any advantage over classical computing.

But a QUBO solver based on Grover's algorithm is proposed in Grover Adaptive Search for Constrained Polynomial Binary Optimization. Since Grover's algorithm provides quadratic speed-up we are now better off than in case of quantum annealers (or QAOA or VQE).

Additionally, assuming that we are able to construct qRAM, we can employ improved Grover, introduced in The Effective Solving of the Tasks from NP by a Quantum Computer, which reaches exponential speed-up.

In the end, we would be able to solve a linear system with exponential speed-up offered by HHL and at the same time to get rid of HHL disadvantages.

Does this idea make sense or is there some flaw? I am a little bit unsure about the measurement - we need to measure results of $$n$$ qubits representig $$|x\rangle$$ (i.e. $$2^n$$ basis states). So, my proposal would suffer from the same problem as HHL algorithm. But if this is the case, how can Grover reach a speed up? We also need to measure the results encoded in $$n$$ qubits.

I would appreciate any comment and ideas.

• Just on the part related to Grover: out of $N=2^n$ possible states that you need to try classically, you only need to do $\sim\sqrt{N}$ Grover iterations and then measure one resulting state vector which amounts to $n$ single-qubit measurements. Jun 17 at 11:03
• @weatherreport: I see..but in case of HHL I need to reconstruct whole quantum state which cancel out the speed up. Right? Jun 20 at 11:39