User:Irvings1/Quantum algorithm for linear systems of equations

The Quantum algorithm for linear systems of equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, is a quantum algorithm for solving linear systems formulated in 2009. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

The algorithm is one of only a few known algorithms known to provide an exponential improvement over their classical counterparts, along with Shor's factoring algorithm and Feyman's quantum simulation of complex systems. Provided the linear system is an sparse and has a low condition number $\kappa$, and the user is interested in the result of a scalar measurement on the solution vector, and not the values of the solution vector itself, the algorithm has a runtime of O(logN*k^2), offering an exponential speedup over the fastest classical algorithm, which runs in O(N*sqrt(k)), where $N$ is the number of variables in the linear system.

An implementation of the quantum algorithm for linear systems of equations was first demonstrated in 2013 by both Barz et al. and Pan et al in parallel. The demonstrations consisted of solving 2x2 linear equations on a photonic quantum computer.

Due to the prevalence of linear systems in virtually all areas of science and engineering, the quantum algorithm for linear systems of equations has the potential to be the most practically useful quantum algorithms so far. This is an important milestone for quantum computing, as previous algorithms offering exponential speedup do not have obvious real-world applications.

Procedure

The problem we are trying to solve is: given a Hermitian $NxN$ matrix $A$ and a unit vector ${\overrightarrow {b}}$, find the solution vector ${\overrightarrow {x}}$ satisfying $A{\overrightarrow {x}}={\overrightarrow {b}}$. This algorithm assumes that the user is not interested in the values of ${\overrightarrow {x}}$ itself, but rather the result of applying some operator $M$ onto x, $\langle x|M|x\rangle$.

First, the algorithm represents the vector ${\overrightarrow {b}}$ as a quantum state of the form:

$|b\rangle =\sum _{i\mathop {=} 1}^{N}b_{i}|i\rangle$.

Next, Hamiltonian simulation techniques are used to apply the unitary operator $e^{iAt}$ to $|b\rangle$ for a superposition of different times $t$. This ability to exponentiate $A$ translates, via the well known technique of phase estimation, into the ability to decompose $|b\rangle$ into the eigenbasis of $A$ and to find the corresponding eigenvalues $\lambda _{j}$.

Informally, the state of the system after this decomposition is close to:

$\sum _{j\mathop {=} 1}^{N}\beta _{j}|u_{j}\rangle |\lambda _{j}\rangle$,

where $u_{j}$ is the eigenvector basis of $A$, and $|b\rangle =\sum _{j\mathop {=} 1}^{N}\beta _{j}|u_{j}\rangle$.

We would then like to perform the linear map taking $|\lambda _{j}\rangle$ to $C\lambda _{j}^{-1}|\lambda _{j}\rangle$, where $C$ is a normalizing constant. As this operation is not unitary, it has some probability of failing. After it succeeds, we uncompute the $|\lambda _{j}\rangle$ register and are left with a state proportional to:

$\sum _{i\mathop {=} 1}^{N}\beta _{i}\lambda _{j}^{-1}|u_{j}\rangle =A^{-1}|b\rangle =|x\rangle$,

Where $|x\rangle$ is a quantum-mechanical representation of the desired solution vector $x$. To read out all components of x would require the procedure be repeated at least $N$ times. However, it is often the case that one is not interested in $x$ itself, but rather some expectation value x^T M x, where M is some linear operator. By mapping M to a quantum-mechanical operator and performing the quantum measurement corresponding to M, we obtain an estimate of the expectation value <x|M|x> = x^T M , as desired. This allows for a wide variety of features of the vector x to be extracted including normalization, weights in different parts of the state space, moments, etc.

Explanation of the Algorithm

Initialization

Firstly, the algorithm requires that the matrix $A$ be Hermitian so that it can be converted into a unitary operator. In the case were $A$ is not Hermitian, define

$\mathbf {C} ={\begin{bmatrix}0&A\\A^{t}&0\end{bmatrix}}.$

As $C$ is Hermitian, the algorithm can now be used to solve $Cy={\begin{bmatrix}b\\0\end{bmatrix}}.$ to obtain $y={\begin{bmatrix}0\\x\end{bmatrix}}$.

Secondly, The algorithm also requires an efficient procedure to prepare $|b\rangle$, the quantum representation of b. It is assumed that there exists some linear operator $B$ that can take some arbitrary quantum state $|initial\rangle$ to $|b\rangle$ efficiently or that this algorithm is a subroutine in a larger algorithm and is given $|b\rangle$ as input. Any error in the preparation of state $|b\rangle$ is ignored.

Finally, the algorithm assumes that the state $|\psi _{0}\rangle$ can be prepared efficiently. Where

$|\psi _{0}\rangle :={\sqrt {2/T}}*\sum _{\tau \mathop {=} 0}^{T-1}sin{\pi ({\tfrac {\tau +{\tfrac {1}{2}}}{T}}})*|\tau \rangle$

for some large $T$. The coefficients of $|\psi _{0}\rangle$ are chosen to minimize a certain quadratic loss function which induces error in the $U_{invert}$ subroutine described below.

Phase Estimation

Phase estimation is used to transform the Hermitian matrix $A$ into a unitary operator, which can then be applied at will. This is possible if A is s-sparse and efficiently row computable, meaning it has at most s nonzero entries per row and given a row index these entries can be computed in time O(s). Under these assumptions, quantum phase estimation allows $e^{i}At$ to be simulated in time $O(log(N)s^{2}t)$.

Uinvert Subroutine

The key subroutine to the algorithm, denoted $U_{invert}$, is defined as follows:

1. Prepare $|\psi _{0}\rangle ^{C}$ on register C

2. Apply the conditional Hamiltonian evolution (sum)

3. Apply the Fourier transform to the register C. Denote the resulting basis states with $|k\rangle$ for k = 0,...,T-1. Define $\lambda _{k}:=2\pi k/t_{0}$.

4. Adjoin a three-dimensional register S in the state

$|h(\lambda _{k})\rangle ^{S}:={\sqrt {1-f(\lambda _{k})^{2}-g(\lambda _{k})^{2}}}|nothing\rangle ^{S}+f(\lambda _{k})|well\rangle ^{S}+g(\lambda _{k})|ill\rangle ^{S}$,

5. Reverse steps 1-3, uncomputing any garbage produced along the way.

for functions f, g, defined below. Here 'nothing' indicates that the desired matrix inversion hasnt taken place. 'well' indicates that it has, and 'ill' means that part of $|b\rangle$ is in the ill-conditioned subspace of A.

Main Loop

The body of the algorithm follows the amplitude amplification procedure: starting with $U_{invert}B|initial\rangle$, the following operation is repeatedly applied:

$U_{invert}BR_{init}B^{\dagger }U_{invert}^{\dagger }R_{succ}$

Where

$R_{succ}=I^{2}-2|well\rangle \langle well|^{2}$,

and

$R_{init}=I^{2}-2|initial\rangle \langle initial|$,

After each repetition, $S$ is measured until the a successful measurement of 'well' is obtained. Let $p$ denote the success probability of the measurement. Rather than repeating ${\frac {1}{p}}$ times to minimize error, amplitude amplification allows the algorithm to achieve the same error resilience using only $O({\frac {1}{\sqrt {p}}})$ repetitions.

Scalar Measurement

After successfully measuring 'well' on $S$ we are left with a state proportional to:

$\sum _{i\mathop {=} 1}^{N}\beta _{i}\lambda _{j}^{-1}|u_{j}\rangle =A^{-1}|b\rangle =|x\rangle$.

Finally, we perform the quantum-mechanical operator corresponding to M and obtain an estimate of the value of $\langle x|M|x\rangle$.

Run Time Analysis

Classical Efficiency

The best classical algorithm which produces the actual solution vector ${\overrightarrow {x}}$ is Gaussian Elimination, which runs in $O(N^{3})$ time.

If A is s-sparse, where s is significantly smaller than N, then the Conjugate Gradient method can be used to find the solution vector ${\overrightarrow {x}}$ can be found in $O(N*Log(N))$ time by minimizing the quadratic function $|A{\overrightarrow {x}}-{\overrightarrow {b}}|^{2}$.

When only a summary statistic of the solution vector ${\overrightarrow {x}}$ is needed, as is the case for the quantum algorithm for linear systems of equations, a classical computer can find an estimate of ${\overrightarrow {x}}^{\dagger }M{\overrightarrow {x}}$ in $O(N{\sqrt {\kappa }})$.

Quantum Efficiency

The quantum algorithm for solving linear systems of equations originally proposed by Harrow et. al was shown to be $O(\kappa ^{2}logN)$. The runtime of this algorithm was subsequently improved to $O(\kappa log^{3}\kappa logN)$ by Andris Ambainis.

Optimality

-- An important factor in the performance of the matrix inversion algorithm is k, the condition number of A, or the ratio between A's largest and smallest eigenvalues. as the Condition number grows, A becomes closer to a matrix which cannot be inverted, and the solutions become less stable. Such a matrix is said to be "ill-conditioned". This algorithm generally assumes that the singular values of A lie between 1/k and 1, in which case the run time will scale with k^2. Therefore, the greatest advantage this algorithm has over classical algorithms occurs when k is poly(logN), in which case an exponential speedup is achieved.

If the run-time of the algorithm could be made polylogarithmic in k, then any problem solvable on n qubits could be solved in poly(n) time, causing a complexity heirarchy collapse (BQP=PSPACE), which is highly unlikely. Even improving k-dependence to $k{^{1}-\delta }$ for $\delta >0$ would imply that BQP=PSPACE. Similarly, improving the error dependence to poly log(1/$\epsilon$ would imply that BQP includes PP.

Error Analysis

Performing the phase estimation, which is the dominant source of error, is done by simulating $e^{iAt}$. Assuming that $A$ is s-sparse, this can be done with an error bounded by a constant $\epsilon$, which will translate to the additive error achieved in the output state $|x\rangle$.

The phase estimation step errs by $O({\frac {1}{t_{0}}})$ in estimating $\lambda$, which translates into a relative error of $O({\frac {1}{\lambda t_{0}}})$ in $\lambda ^{-1}$. If $\lambda >=1/\kappa$, taking $t_{0}=O({\kappa }{\epsilon })$ induces a final error of $\epsilon$. This requires that the overall run-time efficiency be increased proportional to $O({\frac {1}{\epsilon }})$ to minimize error.

Experimental Realization

While there does not yet exist a quantum computer that can truly offer a speedup over a classical computer, implementation of a "proof of concept" remains an important milestone in the developement of a new quantum algorithm. Demonstrating the quantum algorithm for linear systems of equations remained a challenge for years after its proposal until 2013 when it was demonstrated by both Barz et al. and Pan et al. in parallel.

Barz et al.

On February 5, 2013 Barz et al. demonstrated the quantum algorithm for linear systems of equations on a photonic quantum computing architecture. This implementation used two consecutive entangling gates ont he same pair of polarization-encoded qubits. Two separately controlled-NOT gates were realized where the successful operation of the first was heralded by a measurement of two ancillary photons. Barz et al. found that the fidelity in the obtained output state ranged from 64.7% to 98.1% due to the influence of higher-order emissions from spontaneous parametric down-conversion.

Pan et al.

On February 8, 2013 Pan et. al reported a proof-of-concept experimental demonstration of the quantum algorithm using a 4-qubit nuclear magnetic resonance quantum information processor. The implementation was tested using simple linear systems of only 2 variables. Across three experiments they obtain the solution vector with over 96% fidelity.

Applications

Introduction

Quantum computers are devices that harness quantum mechanics to perform computations in ways that classical computers cannot. For certain problems, quantum algorithms supply exponential speedups over their classical counterparts, the most famous example being Shor's factoring algorithm. Few such exponential speedups are known, and those that are (such as the use of quantum computers to simulate other quantum systems) have so far found limited use outside the domain of quantum mechanics. This algorithm provides an exponentially faster method of estimating features of the solution of a set of linear equations, which is a problem ubiquitous in science an engineering, both on its own and as a subroutine in more complex problems.

Linear Differential Equation Solving

Differential equations are used for an enormous variety of applications, including industrial design and weather prediction. This paper considers sparse systems of first-order linear differential equations. Using standard techniques to convert linear differential equations with high-order derivatives into first-order linear differential equations.

http://arxiv.org/abs/1010.2745

Least-Squares Fitting

Wiebe et al. provide a new quantum algorithm to determine the quality of a least-squares fit in which a continuous function is used to approximate a set of discrete points by extending the quantum algorithm for linear systems of equations. As the amount of discrete points increases, the time required to produce a least-squares fit using even a quantum computer running a quantum state tomography algorithm becomes very large. Wiebe et al. find that in many cases, their algorithm can efficiently find a concise approximation of the data points, eliminating the need for the higher-complexity tomography algorithm.

Machine Learning and Big Data Analysis

Machine learning is the study of systems that can identify trends in data. Tasks in machine learning frequently nivolve manipulating and classifying a large volume of data in high-dimensional vector spaces. The runtime of classical machine learning algorithms is limited by a polynomial dependance on both the volume of data and the dimensions of the space. Quantum computers are capable of manipulating high-dimensional vectors using tensor product spaces are are thus the perfect platform for machine learning algorithms.

The quantum algorithm for linear systems of equations has been applied to a support vector machine, which is an optimized linear or non-linear binary classifier. A support vector machine can be used for supervised machine learning, in which training set of already classified data is available, or unsupervised machine learning, in which all data given to the system is unclassified. Rebentrost et al. show that a quantum support vector machine can be used for big data classification and achieve an exponential speedup over classical computers.