Linear Equations

Introduction

Solving a system of linear equations is non-trivial. The problem can be formulated as:

$A \vec x = \vec b$

where $A$ is given as a matrix of coefficients, $\vec x$ represents the variables to be solved and $\vec b$ is given as the values to be used in the solution. Rearranging the terms:

$\vec x = A^{-1} \vec b$

The problem now becomes one of finding the inverse of the $A$ matrix. It can be shown that the complexity of this operation is $O(n^3)$. If $A$ is sparse, the complexity can be shown to be proportional to $O(N log N)$.

Seth, Lloyd and his colleagues at MIT had presented a Quantum algorithm with a complexity proportional to $O(logN)$. The complete presentation can be viewed at https://arxiv.org/pdf/1302.1210.pdf.

My attempt is to unravel the important aspects of the algorithm.

The algorithm

Let

$|\psi_0> = {\sqrt {2 \over T}} {\sum_{\tau = 0}^{T-1}} sin { {{\pi} (\tau + {1 \over 2})} \over T}|\tau>$

where T is an integer > 0

Apply ${\sum_{\tau = 0}^{T-1}}|\tau>|<\tau|^C ⊗{e^{iA\tau t_o} \over T} on |\psi_0>^C⊗|b_i>$

The above operation will generate eigen values and eigen vector using quantum phase transformation described at https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm.

Fourier transforming the first register (there are 2 registers in the quantum phase transformation article above) gives the state

${\sum_{j=1}^N}{\sum_{k=0}^{T-1}} \alpha_{kj} \beta_j |k>|{u_j>}$

where |k> are the Fourier basis states.

Define:

${\vec \lambda_k} = {{2 \pi k} \over {t_0}}$

${\sum_{j=1}^N}{\sum_{k=0}^{T-1}} {\alpha_{kj}} {\beta_j} |{\vec \lambda_k}>|{u_j}>$

Adding an ancillary qubit and rotating conditioned on $|\vec \lambda_k>$ gives:

${\sum_{j=1}^N}{\sum_{k=0}^{T-1}} {\alpha_{kj}} {\beta_j} {|{\vec \lambda_k}>} {|u_j>} ( {\sqrt {1 - {C^2 \over {\vec \lambda_k^2}}}} |0> + {C \over {\vec \lambda_k}} |1>)$

If the quantum phase estimation is correct:

$\alpha_{kj} = 1$ if ${\vec \lambda_k|} = {\lambda_j}$ and $\alpha_{kj}=0$ otherwise

${\sum_{j=1}^N} {\beta_j}|u_j>( {\sqrt {1 - {C^2 \over {\vec \lambda_j^2}}}} |0> + {C \over {\vec \lambda_j}} |1>)$

The probability of the |1> qubit corresponds to the solution |x>

${\sqrt { 1 \over {{\sum_{j=1}^N}{C^2|{\beta_j|^2}/{|\lambda_j|^2}}}}}{\sum_{j=1}^N} {\beta_j}{C \over {\lambda_j}} |u_j>$

Since lambdas are eigen values, the inversion is assumed as solution which is the case when the matrix is diagnoal and sparse

For a discussion of this work and some circuits see https://quantumcomputing.stackexchange.com/questions/2439/quantum-algorithm-for-linear-systems-of-equations-hhl09-step-2-preparation