7

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.

Martin Vesely
  • 13,891
  • 4
  • 28
  • 65
  • 1
    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. – Nikita Nemkov Jun 17 '21 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? – Martin Vesely Jun 20 '21 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. – Mark Spinelli Oct 22 '21 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. – Martin Vesely Oct 23 '21 at 07:45
  • If $\vert x\rangle$ is a sum of $2^n$ basis vectors, and you want to learn each of the $N=2^n$ basis vectors, then you'll still need $2^n$ operations regardless, right? Isn't that the point of HHL's paper when they say "Indeed, merely to write out the solution takes time of order $N$. Frequently, however, one is interested not in the full solution to the equations, but rather in computing some function of that solution, such as determining the total weight of some subset of the indices"? – Mark Spinelli Oct 25 '21 at 21:23
  • @MarkS: Yes, you are right. So, there is no added value in my approach. – Martin Vesely Nov 03 '21 at 16:03
  • 2
    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. – Mark Spinelli Nov 03 '21 at 19:45

0 Answers0