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 would appreciate any comment and ideas.

EDIT: I did some further research in the above. I realized that my first proposal ignored signs. So, I added for each variable a signum binary variable (qubit). Each binary representation of variable in the linear system is now multiplied by term $$(2s_i - 1)$$. The term is -1 for $$s_i = 0$$ and 1 for $$s_i = 1$$. As a result, we are able to solve any linear system in real numbers. However, introducing new binary variables for signs complicates the optimization. Because of squares in the objective function, we get terms like $$s_is_jx_ix_j$$. This means that the optimization is no longer QUBO but HUBO (higher-order unconstrained binary optimization).

Fortunatelly, this can be overcome with method discussed e.g. in paper Towards Prediction of Financial Crashes with a D-Wave Quantum Computer, allowing to convert many-body interaction Hamiltonian to Ising one but at cost of ancilla qubits. In the end we are left with QUBO task but with more qubits - signs and ancillas.

• 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. Commented Jun 17, 2021 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? Commented Jun 20, 2021 at 11:39
• I might be missing something but isn’t $| x\rangle$ exponential anyway? What does it mean to “know the solution $|x\rangle$ itself”? After HHL you have a quantum state equal to $|x\rangle$, but you have to do something with it to learn any classical information. Commented Oct 22, 2021 at 16:20
• @MarkS: I meant that I need to carry out quantum tomography to get all members of the solution. While in case of binary optimization approach there is no such complication. Commented Oct 23, 2021 at 7:45
• I like the lecture that Seth Lloyd gave in 2011 at Keio University. He mentions that this point is very subtle and was noted/confusing in the initial review of the paper. Commented Nov 3, 2021 at 19:45