Quantum Algorithms for Systems of Linear Equations
Rolando Somma
Theoretical Division
Los Alamos National Laboratory
Joint work withAndrew Childs
MarylandRobin Kothari
Microsoft

Davide Orsucci
ViennaYigit Subasi
Los Alamos

Workshop at the Intersection of Machine Learning and Quantum Information
University of Maryland
September 2018

Quantum Algorithms for Systems of Linear Equations

References:• “Quantum linear systems algorithm with exponentially improved dependence on
precision”, A.M. Childs, R. Kothari, and R.D. Somma, SIAM J. Comp. 46, 1920 (2017).
• “Quantum algorithms for linear systems inspired by adiabatic quantum computing”, Y.
Subasi, R.D. Somma, and D. Orsucci, arXiv:1805.10549 (2018).

A brief history of results in quantum computing• Simulating quantum systems was the main motivation behind
Feynman’s idea of a quantum computer (1982).
• For example, algorithms for simulating the dynamics of n spin
systems with classical computers have complexity that is
exponential in n. Quantum algorithms, in principle, have only
complexity that is polynomial in n.

A brief history of results in quantum computing• Simulating quantum systems was the main motivation behind
Feynman’s idea of a quantum computer (1982).
• For example, algorithms for simulating the dynamics of n spin
systems with classical computers have complexity that is
exponential in n. Quantum algorithms, in principle, have only
complexity that is polynomial in n.
• Peter Shor discovers a quantum algorithm for efficient factorizationof integers with important applications to cryptography. Shor’salgorithm results in a superpolynomial quantum speedup (1994).
His result was a main motivation for the discovery of otherquantum algorithms.

A brief history of results in quantum computing• Simulating quantum systems was the main motivation behind
Feynman’s idea of a quantum computer (1982).
• For example, algorithms for simulating the dynamics of n spin
systems with classical computers have complexity that is
exponential in n. Quantum algorithms, in principle, have only
complexity that is polynomial in n.
• Peter Shor discovers a quantum algorithm for efficient factorizationof integers with important applications to cryptography. Shor’salgorithm results in a superpolynomial quantum speedup (1994).
His result was a main motivation for the discovery of otherquantum algorithms.

• L. Grover discovers a quantum algorithm for unstructured search
resulting in a polynomial (quadratic) quantum speedup (1997).A
main idea in Grover’s result (amplitude amplification) has been
extensively used in other quantum algorithms for problems such as
optimization, search, and more.

A brief history of results in quantum computing• Simulating quantum systems was the main motivation behind
Feynman’s idea of a quantum computer (1982).
• For example, algorithms for simulating the dynamics of n spin
systems with classical computers have complexity that is
exponential in n. Quantum algorithms, in principle, have only
complexity that is polynomial in n.
• Peter Shor descubre un algoritmo cuántico para factorizar enteros
con aplicaciones
importantes fora cybersecurity,
resultando
en unaOther
quantum algorithms
linear algebra
problems?
reducción exponencial de la complejidad clásica (1994). Si bien
computadoras cuánticas de gran tamaño no existen, este fue elprincipal resultado que disparó investigación en algoritmos
cuánticos• L. Grover discovers a quantum algorithm for unstructured search
resulting in a polynomial (quadratic) quantum speedup (1997).A
main idea in Grover’s result (amplitude amplification) has been
extensively used in other quantum algorithms for problems such as
optimization, search, and more.

Linear Equations: An important problem
Let’s consider the problem of solving a system of linear equations or
the related problem of inverting a matrix:

A.~x = ~b~x = A1~bLinear Equations: An important problem
Let’s consider the problem of solving a system of linear equations or
the related problem of inverting a matrix:

A.~x = ~bNxN

N-dimensional~x = A1~bLinear Equations: An important problem
Let’s consider the problem of solving a system of linear equations or
the related problem of inverting a matrix:

A.~x = ~b~x = A

1~b• There is a variety of classical algorithms to solve this problem.
Nevertheless, even when the matrix A and vector ƃ are sparse, thecomplexity of ``exact’’ classical algorithms is at least linear in N.

Linear Equations: An important problem
Let’s consider the problem of solving a system of linear equations or
the related problem of inverting a matrix:

A.~x = ~b~x = A

1~b• There is a variety of classical algorithms to solve this problem.
Nevertheless, even when the matrix A and vector ƃ are sparse, thecomplexity of ``exact’’ classical algorithms is at least linear in N.
• A result [HHL08]: Quantum computers can prepare a quantum state
proportional to the solution of the system in time that is polynomial in thecondition number, inverse of precision, and the logarithm of the dimension(under some assumptions).

Linear Equations: An important problem
Let’s consider the problem of solving a system of linear equations or
the related problem of inverting a matrix:

A.~x = ~b~x = A

1~b• There is a variety of classical algorithms to solve this problem.
Nevertheless, even when the matrix A and vector ƃ are sparse, thecomplexity of ``exact’’ classical algorithms is at least linear in N.
• A result [HHL08]: Quantum computers can prepare a quantum state
proportional to the solution of the system in time that is polynomial in thecondition number, inverse of precision, and the logarithm of the dimension(under some assumptions).
• Note: This is a somewhat different problem (QLSP) and classical algorithms
may do better in this case. However, the QLSP is BQP-Complete.

Quantum Linear System Problem (QLSP)

A.~x = ~bAssumptions

•
•
•
•

A is Hermitian of dimension NxN
A is s-sparse
A is invertible and its condition number is 𝜅<∞
The spectral norm of A is bounded by 1

Quantum Linear System Problem (QLSP)

A.~x = ~bAssumptions

•
•
•
•

A is Hermitian of dimension NxN
A is s-sparse
A is invertible and its condition number is 𝜅<∞
The spectral norm of A is bounded by 1

Quantum Linear System Problem (QLSP)

A.~x = ~bAssumptions

•
•
•
•

A is Hermitian of dimension NxN
A is s-sparse
A is invertible and its condition number is 𝜅<∞
The spectral norm of A is bounded by 1

Quantum Linear System Problem (QLSP)

A.~x = ~bAssumptions

•
•
•
•

A is Hermitian of dimension NxN
A is s-sparse
A is invertible and its condition number is 𝜅<∞
The spectral norm of A is bounded by 1

Quantum Linear System Problem (QLSP)

A.~x = ~bAssumptions

•
•
•
•

A is Hermitian of dimension NxN
A is s-sparse
A is invertible and its condition number is 𝜅<∞
The spectral norm of A is bounded by 1

Let CA (t, ✏) be the cost of simulating e iAt with precision ✏Quantum Linear System Problem (QLSP)

A.~x = ~bAssumptions

•
•
•
•

A is Hermitian of dimension NxN
A is s-sparse
A is invertible and its condition number is 𝜅<∞
The spectral norm of A is bounded by 1

Let CA (t, ✏) be the cost of simulating e iAt with precision ✏Hamiltonian simulation
Note: Recent advances in Hamiltonian simulation resulted in
CA (t, ✏) = Õ(tsTA log(t/✏))••Complexity almost linear in the evolution timeComplexity is polylogarithmic in the inverse of a precision parameter

D. Berry, A. Childs, R. Cleve, R. Kothari, and RDS, PRL 114, 090502 (2015)
D. Berry, A. Childs, and R. Kothari, FOCS 2015, 792 (2015)
G.H. Low and I. Chuang, PRL 118, 010501 (2017)

Quantum Linear System Problem (QLSP)
Some applications:•

In physics, where the goal is to compute the expectation value of the inverseof a matrix. This idea was used in [1] for obtaining the resistance of a network.

•

In stat mech, where, e.g., estimating the hitting time of a Markov chain also
reduces to computing the expectation value of the inverse of a matrix [2]•In ML, for solving problems related to least-squares estimation [3], byapplying the pseudoinverse:•

For solving certain linear differential equations [4]:[1] G. Wang, arXiv:1311.1851 (2013). [2] A. Chowdhury and R. Somma, QIC 17, 0041 (2017)[3] N. Wiebe, D. Braun, and S. Lloyd, PRL 109, 050505 (2012).
[4] D. Berry, A. Childs, A. Ostrander, and G. Wang, CMP 356, 1057 (2017)

Quantum Linear System Problem (QLSP)A note: Even for those applications, a number of assumptions must be made inorder to obtain quantum speedups. These assumptions include efficient
preparation of certain states (of exp many amplitudes), nice scaling of thecondition number, and solving certain problems like computing expectation
values. For these reasons, shown quantum speedups are typically polynomial.

The HHL Algorithm for the QLSP [5][HHL08] There exists a quantum algorithm that solves the QLSP with complexityÕ [(Tb + CA (/✏, ✏/))][5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

The HHL Algorithm for the QLSP [5][HHL08] There exists a quantum algorithm that solves the QLSP with complexityÕ [(Tb + CA (/✏, ✏/))]Considering that many Hamiltonians can be simulated efficiently on quantum
computers, the complexity dependence on the dimension is small (e.g., logarithmic)[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

Improvements of the HHL Algorithm [6][HHL08] There exists a quantum algorithm that solves the QLSP with complexityÕ [(Tb + CA (/✏, ✏/))]Considering that many Hamiltonians can be simulated efficiently on quantum
computers, the complexity dependence on the dimension is small (e.g., logarithmic)
Further improvements by Ambainis (Variable Time Amplitude Amplification or VTAA):[6] There exists a quantum algorithm that solves the QLSP with complexity⇥⇤
3Õ Tb + CA (/✏ , ✏)[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)[6] A. Ambainis, STACS 14, 636 (2012)Improvements of the HHL Algorithm [6][HHL08] There exists a quantum algorithm that solves the QLSP with complexityÕ [(Tb + CA (/✏, ✏/))]Considering that many Hamiltonians can be simulated efficiently on quantum
computers, the complexity dependence on the dimension is small (e.g., logarithmic)
Further improvements by Ambainis (Variable Time Amplitude Amplification or VTAA):[6] There exists a quantum algorithm that solves the QLSP with complexity⇥⇤
3
Almost linear in 𝜅!
Õ Tb + CA (/✏ , ✏)•Note that the best Hamiltonian simulation methods have query and gate
complexities almost linear in evolution time and logarithmic in precision[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)[6] A. Ambainis, STACS 14, 636 (2012)

A quick view of the HHL algorithm and VTAA

[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

A quick view of the HHL algorithm and VTAA

[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

A quick view of the HHL algorithm and VTAA

|bi !

N
X1
j=0

[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)[6] A. Ambainis, STACS 14, 636 (2012)

cj |vj iI | ˜ j iE

A quick view of the HHL algorithm and VTAA

|bi !

N
X1
j=0

cj |vj iI | ˜ j iE

This register contains the eigenvalue estimate (superposition):• It suffices to have the estimate with relative precision 𝜖• Order log(𝜅/𝜖) ancillary qubits[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

A quick view of the HHL algorithm and VTAA

|bi !

N
X1
j=0

cj |vj iI | ˜ j iE

Then we implement the conditional rotation: | ˜ j iE ! | ˜ j iE[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

1|0iO +
˜
 j

s

1

1
|1iO
2
2
˜

j

!

A quick view of the HHL algorithm and VTAA

|bi !

N
X1
j=0

cj |vj iI | ˜ j iE

Then we implement the conditional rotation: | ˜ j iE ! | ˜ j iE

Undo phase estimation[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

1|0iO +
˜
 j

s

1

1
|1iO
2
2
˜

j

!

A quick view of the HHL algorithm and VTAA

|bi !

N
X1
j=0

cj |vj iI | ˜ j iE

Then we implement the conditional rotation: | ˜ j iE ! | ˜ j iE

Undo phase estimation

1|0iO +˜ js1

Amplitude amplification for amplifying the amplitude of the |0iO state[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

1
|1iO
2
2
˜

j

!

A quick view of the HHL algorithm and VTAA
Roughly, the scaling of the HHL algorithm can be analyzed from the worst case:p|bi = (1/)|v1/ i + 1 1/2 |v1 i[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

A quick view of the HHL algorithm and VTAA
Roughly, the scaling of the HHL algorithm can be analyzed from the worst case:p|bi = (1/)|v1/ i + 1 1/2 |v1 i
The action of 1/ A will roughly create the equal superposition state, so both areequally important[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

A quick view of the HHL algorithm and VTAA
Roughly, the scaling of the HHL algorithm can be analyzed from the worst case:p|bi = (1/)|v1/ i + 1 1/2 |v1 i
The action of 1/ A will roughly create the equal superposition state, so both areequally important
For the desired precision we need to evolve with A for time of order 𝜅/𝜖[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

A quick view of the HHL algorithm and VTAA
Roughly, the scaling of the HHL algorithm can be analyzed from the worst case:p|bi = (1/)|v1/ i + 1 1/2 |v1 i
The action of 1/ A will roughly create the equal superposition state, so both areequally important
For the desired precision we need to evolve with A for time of order 𝜅/𝜖The action of 1/ (𝜅 A ) on the state reduces its amplitude by order 1/ 𝜅 and order 𝜅amplitude amplification rounds are needed[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

A quick view of the HHL algorithm and VTAA
Roughly, the scaling of the HHL algorithm can be analyzed from the worst case:p|bi = (1/)|v1/ i + 1 1/2 |v1 i
The action of 1/ A will roughly create the equal superposition state, so both areequally important
For the desired precision we need to evolve with A for time of order 𝜅/𝜖The action of 1/ (𝜅 A ) on the state reduces its amplitude by order 1/ 𝜅 and order 𝜅amplitude amplification rounds are needed
From here we see that we need to evolve with A for time that is, at least, order 𝜅2/𝜖[5] Harrow, Hassidim, Lloyd, PRL 103, 150502 (2009)

A quick view of the HHL algorithm and VTAA
How can we improve this time complexity to something that is almost linear in thecondition number?

[6] A. Ambainis, STACS 14, 636 (2012)

A quick view of the HHL algorithm and VTAA
How can we improve this time complexity to something that is almost linear in thecondition number?
One answer is via Variable Time Amplitude Amplification (VTAA) [6][6] A. Ambainis, STACS 14, 636 (2012)

A quick view of the HHL algorithm and VTAA
How can we improve this time complexity to something that is almost linear in thecondition number?
One answer is via Variable Time Amplitude Amplification (VTAA) [6]
The rough idea is as follows (again, considering the worst case):p|bi = (1/)|v1/ i + 1 1/2 |v1 i
•
•
•
•
•
•

First we do a bad-precision phase estimation to distinguish large from small
eigenvalues. This may be done evolving with A for time independent of 𝜅
Then we implement a rough approximation of 1/ 𝜅 A to eigenstates of large
eigenvalue
We need order 𝜅 amplitude amplification steps
We implement an accurate approximation of 1/ 𝜅 A to eigenstates of small
eigenvalue
Amplitude amplification for order 1 steps
Undo phase estimation or apply the Fourier transform[6] A. Ambainis, STACS 14, 636 (2012)

A quick view of the HHL algorithm and VTAA
How can we improve this time complexity to something that is almost linear in thecondition number?
One answer is via Variable Time Amplitude Amplification (VTAA) [6]
The rough idea is as follows (again, considering the worst case):p|bi = (1/)|v1/ i + 1 1/2 |v1 i
•
•
•
•
•
•

First we do a bad-precision phase estimation to distinguish large from small
eigenvalues. This may be done evolving with A for time independent of 𝜅
Then we implement a rough approximation of 1/ 𝜅 A to eigenstates of large
eigenvalue
We need order 𝜅 amplitude amplification steps
We implement an accurate approximation of 1/ 𝜅 A to eigenstates of small
eigenvalue
Amplitude amplification for order 1 steps
Undo phase estimation or apply the Fourier transform
The complexity of VTAA in terms of precision is worse than that of HHL[6] A. Ambainis, STACS 14, 636 (2012)

This talk: two quantum algorithms for the QSLP•I will present two quantum algorithms for the QLSP that improve previous resultsin different ways:[7] There exists a quantum algorithm that solves the QLSP with complexityÕ [(Tb + CA ( log(/✏, ✏/))][7] A. Childs, R. Kothari, RDS, SIAM J. Comp. 46, 1920 (2017).

This talk: two quantum algorithms for the QSLP•I will present two quantum algorithms for the QLSP that improve previous resultsin different ways:[7] There exists a quantum algorithm that solves the QLSP with complexityÕ [(Tb + CA ( log(/✏, ✏/))]•This results in an exponential improvement on the precision parameter[7] A. Childs, R. Kothari, RDS, SIAM J. Comp. 46, 1920 (2017).

This talk: two quantum algorithms for the QSLP•I will present two quantum algorithms for the QLSP that improve previous resultsin different ways:[7] There exists a quantum algorithm that solves the QLSP with complexityÕ [(Tb + CA ( log(/✏, ✏/))]••This results in an exponential improvement on the precision parameter
It can be improved using a version of VTAA to:[7] There exists a quantum algorithm that solves the QLSP with complexityÕ [Tb + CA ( log(/✏, ✏))]

[7] A. Childs, R. Kothari, RDS, SIAM J. Comp. 46, 1920 (2017).

This talk: two quantum algorithms for the QSLPWhy these improvements are important?
•

The previous result allowed us to prove a polynomial quantum speedup for hitting
time estimation in terms of the spectral gap of a Markov chain and precision (A.
Chowdhury, R.D. Somma, QIC 17, 0041 (2017)).

•

Having a small complexity dependence on precision is important for, e.g.,
computing expectation values of observables at the quantum metrology limit.

This talk: two quantum algorithms for the QSLP•I will present two quantum algorithms for the QLSP that improve previous resultsin different ways:[8] There exists a quantum algorithm that solves the QLSP by evolving with
Hamiltonians that are linear combinations of (products of) A, the projector in theinitial state, and Pauli matrices. The overall evolution time is Õ(/✏)[8] Y. Subasi, RDS, D. Orsucci, arXiv:1805.10549 (2018).

This talk: two quantum algorithms for the QSLP•I will present two quantum algorithms for the QLSP that improve previous resultsin different ways:[8] There exists a quantum algorithm that solves the QLSP by evolving with
Hamiltonians that are linear combinations of (products of) A, the projector in theinitial state, and Pauli matrices. The overall evolution time is Õ(/✏)Using Hamiltonian simulation, this transfers to complexity Õ(Tb /✏ + CA (/✏, ✏))[8] Y. Subasi, RDS, D. Orsucci, arXiv:1805.10549 (2018).

This talk: two quantum algorithms for the QSLP•I will present two quantum algorithms for the QLSP that improve previous resultsin different ways:[8] There exists a quantum algorithm that solves the QLSP by evolving with
Hamiltonians that are linear combinations of (products of) A, the projector in theinitial state, and Pauli matrices. The overall evolution time is Õ(/✏)Using Hamiltonian simulation, this transfers to complexity Õ(Tb /✏ + CA (/✏, ✏))•The method is very different and based on adiabatic evolutions. It does not
require of complicated subroutines such as phase estimation and variable time
amplitude amplification, therefore reducing the number of ancillary qubits
substantially.

[8] Y. Subasi, RDS, D. Orsucci, arXiv:1805.10549 (2018).

This talk: two quantum algorithms for the QSLPWhy this improvement is important?
•

Phase estimation and VTAA require several ancillary qubits (beyond those neededfor Hamiltonian simulation)•

Within two weeks of posting our result, a group implemented our algorithm in
NMR, claiming that it is the largest simulated instance so far (8x8) [9][9] J. Wen, et.al., arXiv:1806.0329 (2018)

First algorithm: A Fourier approach for solving the QSLPFirst algorithm: A Fourier approach for solving the QSLPFirst algorithm: A Fourier approach for solving the QSLP

• 1/A is not unitary and we need to find a unitary implementation for it. We thengo through a sequence of approximations:First algorithm: A Fourier approach for solving the QSLP

• 1/A is not unitary and we need to find a unitary implementation for it. We thengo through a sequence of approximations:

we are getting closer: Linear
combination of unitaries

First algorithm: A Fourier approach for solving the QSLPFirst algorithm: A Fourier approach for solving the QSLP

20

10

1.0

0.5

0.5

10

20

1.0

First algorithm: A Fourier approach for solving the QSLP

20

10

1.0

0.5

0.5

10

20

1.0

First algorithm: A Fourier approach for solving the QSLP

20

10

1.0

0.5

0.5

1.0

10

20

The maximum “evolution time” under A in the approximation of
1/A isFirst algorithm: A Fourier approach for solving the QSLP• So far we approximated 1/A, within the desired accuracy, by a finite linear
combination of unitaries. Each unitary corresponds to evolving with A for certain
time, and the max evolution time is almost linear in the condition number

First algorithm: A Fourier approach for solving the QSLP• So far we approximated 1/A, within the desired accuracy, by a finite linear
combination of unitaries. Each unitary corresponds to evolving with A for certain
time, and the max evolution time is almost linear in the condition number
QLSP

Hamiltonian simulation

Implementing a linear combination of unitaries
Suppose we want to implement the operator
where

i

0,

1+

2 = 1, and Ui unitary

1 U1 +

2 U2 to some state |iImplementing a linear combination of unitaries
Suppose we want to implement the operator
where

|0i
| i

i

p

0,

1+

1 |0i +

V

1 U1 +

2 = 1, and Ui unitarypUi

2 U2 to some state |

i

2 |1i

V†
( 1 U1 +2 U2 )|

i|0i +p

1 2 (U1

U2 )| i|1i

Implementing a linear combination of unitaries
Suppose we want to implement the operator
where

|0i
| i

i

p

0,

1+

1 |0i +

V

1 U1 +

2 = 1, and Ui unitarypUi

2 U2 to some state |

i

2 |1i

V†
( 1 U1 +2 U2 )|

Correct parti|0i +p

1 2 (U1

U2 )| i|1i

Incorrect part(orthogonal)

Implementing a linear combination of unitaries
Suppose we want to implement the operator
where

|0i
| i

i

p

0,

1+

1 |0i +

V

1 U1 +

2 = 1, and Ui unitarypUi

2 U2 to some state |

i

2 |1i

V†
( 1 U1 +2 U2 )|

Correct parti|0i +p

1 2 (U1

U2 )| i|1i

Incorrect part(orthogonal)

This idea can be generalized to the case where the goal is to implement

M
X1
i=0

i Ui

Implementing a linear combination of unitaries
Suppose we want to implement the operator
where

|0i

i

p

0,

1+

1 |0i +

V2 = 1, and Ui unitary

p

Ui

| i

1 U1 +

2 U2 to some state |

2 |1i

V†
( 1 U1 +2 U2 )|

Correct parti|0i +p

1 2 (U1

U2 )| i|1i

Incorrect part(orthogonal)

This idea can be generalized to the case where the goal is to implement

M
X1
i=0

M 1
1 X
(
i=0

i Ui )|

ii|0 . . . 0i + |⇠ ? i

i Ui

Implementing a linear combination of unitaries
Suppose we want to implement the operator
where

|0i

i

p

0,

1+

1 |0i +

V2 = 1, and Ui unitary

p

Ui

| i

1 U1 +

2 U2 to some state |

2 |1i

V†
( 1 U1 +2 U2 )|

Correct parti|0i +p

1 2 (U1

U2 )| i|1i

Incorrect part(orthogonal)

This idea can be generalized to the case where the goal is to implement

M
X1
i=0

M 1
1 X
(
i=0

i Ui )|

ii|0 . . . 0i + |⇠ ? i

Amplitude amplification to
obtain the correct parti Ui

First algorithm: A Fourier approach for solving the QSLP•We use the LCU approach to implement the Fourier approximation of 1/A

First algorithm: A Fourier approach for solving the QSLP•We use the LCU approach to implement the Fourier approximation of 1/A•

Note: We assume that the gate complexity of the operation V is small withrespect to other complexities•

Adding up all the coefficients in the linear combination of unitaries, we obtain= Õ()First algorithm: A Fourier approach for solving the QSLP•We use the LCU approach to implement the Fourier approximation of 1/A•

Note: We assume that the gate complexity of the operation V is small withrespect to other complexities•

Adding up all the coefficients in the linear combination of unitaries, we obtain= Õ()•This is also the number of amplitude amplification rounds

First algorithm: A Fourier approach for solving the QSLP•We use the LCU approach to implement the Fourier approximation of 1/A•

Note: We assume that the gate complexity of the operation V is small withrespect to other complexities•

Adding up all the coefficients in the linear combination of unitaries, we obtain= Õ()•This is also the number of amplitude amplification rounds•

Then, the overall complexity of this approach isÕ [(Tb + CA ( log(/✏, ✏/))]First algorithm: A Fourier approach for solving the QSLP•We use the LCU approach to implement the Fourier approximation of 1/A•

Note: We assume that the gate complexity of the operation V is small withrespect to other complexities•

Adding up all the coefficients in the linear combination of unitaries, we obtain= Õ()•This is also the number of amplitude amplification rounds•

Then, the overall complexity of this approach isÕ [(Tb + CA ( log(/✏, ✏/))]This is almost quadratic in the condition number. To improve it to almost linear
we use a version of VTAA that doesn’t ruin the logarithmic scaling in precisionFirst algorithm: A Fourier approach for solving the QSLP••VTAA for HHL relies heavily on phase estimation, bringing a prohibitive
complexity dependence on precision
But in our case we only need to distinguish the regions for the eigenvalues withhigh confidence, so the scaling in precision is logarithmic

First algorithm: A Fourier approach for solving the QSLP••••VTAA for HHL relies heavily on phase estimation, bringing a prohibitive
complexity dependence on precision
But in our case we only need to distinguish the regions for the eigenvalues withhigh confidence, so the scaling in precision is logarithmic
The final algorithm is VTAA applied to another algorithm that is built upon asequence of steps.
At each step we do the following: i) We determine the region of the eigenvalue
with high confidence. ii) We apply 1/A within the necessary precision for that
region (replacing the condition number)First algorithm: A Fourier approach for solving the QSLP••VTAA for HHL relies heavily on phase estimation, bringing a prohibitive
complexity dependence on precision
But in our case we only need to distinguish the regions for the eigenvalues withhigh confidence, so the scaling in precision is logarithmic•

The final algorithm is VTAA applied to another algorithm that is built upon asequence of steps.
At each step we do the following: i) We determine the region of the eigenvalue
with high confidence. ii) We apply 1/A within the necessary precision for that
region (replacing the condition number)•

The overall complexity of this approach is•Õ [Tb + CA ( log(/✏, ✏))]

First algorithm: A Fourier approach for solving the QSLP••VTAA for HHL relies heavily on phase estimation, bringing a prohibitive
complexity dependence on precision
But in our case we only need to distinguish the regions for the eigenvalues withhigh confidence, so the scaling in precision is logarithmic•

The final algorithm is VTAA applied to another algorithm that is built upon asequence of steps.
At each step we do the following: i) We determine the region of the eigenvalue
with high confidence. ii) We apply 1/A within the necessary precision for that
region (replacing the condition number)•

The overall complexity of this approach is•Õ [Tb + CA ( log(/✏, ✏))]

Using the best Hamiltonian simulation methods, this is almost linear in the condition
number and polylog in inverse of precisionSecond algorithm: An “adiabatic” approach for the QSLPSecond algorithm: An “adiabatic” approach for the QSLP•The idea here is to prepare the eigenstate of a Hamiltonian by preparing asequence continuously related eigenstates of a family of Hamiltonians

Second algorithm: An “adiabatic” approach for the QSLP••The idea here is to prepare the eigenstate of a Hamiltonian by preparing asequence continuously related eigenstates of a family of Hamiltonians
We want the eigenstate to be the desired quantum state (after tracing out
ancillary systems)

Second algorithm: An “adiabatic” approach for the QSLP••The idea here is to prepare the eigenstate of a Hamiltonian by preparing asequence continuously related eigenstates of a family of Hamiltonians
We want the eigenstate to be the desired quantum state (after tracing out
ancillary systems)
Pb? A.~x = Pb?~b = 0
B † B|xi = 0 , B = Pb? .A

Second algorithm: An “adiabatic” approach for the QSLP••The idea here is to prepare the eigenstate of a Hamiltonian by preparing asequence continuously related eigenstates of a family of Hamiltonians
We want the eigenstate to be the desired quantum state (after tracing out
ancillary systems)
Pb? A.~x = Pb?~b = 0

H

B † B|xi = 0 , B = Pb? .A

The following properties can be proven:••

The desired state is the unique ground state of H
The eigenvalue gap is order 1/ 𝜅2

Second algorithm: An “adiabatic” approach for the QSLP••The idea here is to prepare the eigenstate of a Hamiltonian by preparing asequence continuously related eigenstates of a family of Hamiltonians
We want the eigenstate to be the desired quantum state (after tracing out
ancillary systems)
Pb? A.~x = Pb?~b = 0

H

B † B|xi = 0 , B = Pb? .A

The following properties can be proven:••

The desired state is the unique ground state of H
The eigenvalue gap is order 1/ 𝜅2•

We now seek the family of interpolating Hamiltonians

Second algorithm: An “adiabatic” approach for the QSLP•We assume for the moment that A>1/ 𝜅Second algorithm: An “adiabatic” approach for the QSLP•We assume for the moment that A>1/ 𝜅•

We define the interpolating matrix A(s) = (1s)I + sA , 0  s  1Second algorithm: An “adiabatic” approach for the QSLP•We assume for the moment that A>1/ 𝜅•

We define the interpolating matrix A(s) = (1•Similarly, we define H(s) = B † (s)B(s) , B(s) = Pb? A(s)s)I + sA , 0  s  1Second algorithm: An “adiabatic” approach for the QSLP•We assume for the moment that A>1/ 𝜅•

We define the interpolating matrix A(s) = (1•Similarly, we define H(s) = B † (s)B(s) , B(s) = Pb? A(s)•This is like solving an increasingly difficult system of linear equations!

s)I + sA , 0  s  1Second algorithm: An “adiabatic” approach for the QSLP•We assume for the moment that A>1/ 𝜅•

We define the interpolating matrix A(s) = (1•Similarly, we define H(s) = B † (s)B(s) , B(s) = Pb? A(s)•This is like solving an increasingly difficult system of linear equations!

s)I + sA , 0  s  1

|xi

s=1
H(1) = A.Pb? .A|bis=0
H(0) = Pb?

Second algorithm: An “adiabatic” approach for the QSLP•We assume for the moment that A>1/ 𝜅•

We define the interpolating matrix A(s) = (1•Similarly, we define H(s) = B † (s)B(s) , B(s) = Pb? A(s)•This is like solving an increasingly difficult system of linear equations!

Ls)I + sA , 0  s  1

|xi

s=1
H(1) = A.Pb? .A|bis=0
H(0) = Pb?

•

The minimum eigenvalue gap is order 1/ 𝜅2 and the length of the path L is log(𝜅)The randomization method to prepare eigenstates []
sq
s2
s1

|xi
H(1) = A.Pb? .A

|bi

s=0
H(0) = Pb?

•

By performing a sequence of projective measurements at sufficiently close
points, we can prepare the related eigenstates with high probability

The randomization method to prepare eigenstates []
sq
s2
s1

|xi
H(1) = A.Pb? .A

|bi

s=0
H(0) = Pb?

•

By performing a sequence of projective measurements at sufficiently close
points, we can prepare the related eigenstates with high probability•

Each measurement can be simulated by evolving with the corresponding
Hamiltonian for random time. This reduces coherences between eigenstates

The randomization method to prepare eigenstates []
sq
s2
s1

|xi
H(1) = A.Pb? .A

|bi

s=0
H(0) = Pb?

•

By performing a sequence of projective measurements at sufficiently close
points, we can prepare the related eigenstates with high probability•

Each measurement can be simulated by evolving with the corresponding
Hamiltonian for random time. This reduces coherences between eigenstates•

The expected evolution time with the Hamiltonians in the randomization✓ 2◆
method satisfies
L
TRM = O✏The randomization method to prepare eigenstates []
sq
s2
s1

|xi
H(1) = A.Pb? .A

|bi

s=0
H(0) = Pb?

•

By performing a sequence of projective measurements at sufficiently close
points, we can prepare the related eigenstates with high probability•

Each measurement can be simulated by evolving with the corresponding
Hamiltonian for random time. This reduces coherences between eigenstates•

The expected evolution time with the Hamiltonians in the randomization✓ 2◆
method satisfies
L is the path lengthL
TRM = O𝛥 is the min gap✏
𝜖 is the error (trace norm)

The randomization method for the QLSP []
sq
s2
s1

|xi
H(1) = A.Pb? .A

|bi

s=0
H(0) = Pb?

•

By performing a sequence of projective measurements at sufficiently close
points, we can prepare the related eigenstates with high probability•

Each measurement can be simulated by evolving with the corresponding
Hamiltonian for random time. This reduces coherences between eigenstates•

The expected evolution time with the Hamiltonians in the randomization✓ 2◆
method satisfies
 log2 ()TRM = O✏The randomization method for the QLSP []•The strong dependence of the evolution time with the spectral gap suggests
one to consider other Hamiltonians that have the same eigenstate but a larger
eigenvalue gap

The randomization method for the QLSP []•The strong dependence of the evolution time with the spectral gap suggests
one to consider other Hamiltonians that have the same eigenstate but a larger
eigenvalue gap•

For this problem, spectral gap amplification [10] is useful:H(s) ! H 0 (s) = B † (s) ⌦+ B(s) ⌦[10] R.D. Somma and S. Boixo, SIAM J. Comp. 593 (2013)

+

=

✓

0
B † (s)B(s)0◆The randomization method for the QLSP []•The strong dependence of the evolution time with the spectral gap suggests
one to consider other Hamiltonians that have the same eigenstate but a larger
eigenvalue gap•

For this problem, spectral gap amplification [10] is useful:H(s) ! H 0 (s) = B † (s) ⌦•+ B(s) ⌦

+

=

✓

0
B † (s)B(s)0◆Some results:
Let |x(s)i be the eigenstate of 0-eigenvalue of H(s).

Then, |x(s)i|1i is an eigenstate of 0-eigenvalue of H 0 (s).
This eigenstate is separated from others by an eigenvalue gap[10] R.D. Somma and S. Boixo, SIAM J. Comp. 593 (2013)p(s)

The randomization method for the QLSP []•The strong dependence of the evolution time with the spectral gap suggests
one to consider other Hamiltonians that have the same eigenstate but a larger
eigenvalue gap•

For this problem, spectral gap amplification is useful:H(s) ! H 0 (s) = B † (s) ⌦•+ B(s) ⌦

+

=

✓

0
B † (s)B(s)0◆Some results:
Let |x(s)i be the eigenstate of 0-eigenvalue of H(s).

Then, |x(s)i|1i is an eigenstate of 0-eigenvalue of H 0 (s).
This eigenstate is separated from others by an eigenvalue gap

•

p

(s)

Note that the path length did not change. The only change for the RM is theuse of a different Hamiltonian.

The randomization method for the QLSP []•Using the randomization method with the new Hamiltonian, the expected✓◆
evolution time is log2 ()TRM = O✏The randomization method for the QLSP []•Using the randomization method with the new Hamiltonian, the expected✓◆
evolution time is log2 ()TRM = O✏•

The case of non-positive matrix A can be analyzed similarly using
A(s) = (1s)( zanc ⌦ I) + s( xanc ⌦ A)

The randomization method, the QLSP, and the gate model
For A > 0, the Hamiltonian is H 0 (s) = (I|bihb|)((1s)I + sA)

+ H.c.

The randomization method, the QLSP, and the gate model
For A > 0, the Hamiltonian is H 0 (s) = (I|bihb|)((1s)I + sA)

If |bi is sparse and A is sparse, then H 0 (s) is also sparse+ H.c.

The randomization method, the QLSP, and the gate model
For A > 0, the Hamiltonian is H 0 (s) = (I|bihb|)((1s)I + sA)

+ H.c.

If |bi is sparse and A is sparse, then H 0 (s) is also sparse

We can use a Hamiltonian simulation method to build a quantum circuit thatsimulates the evolution. The quantum circuit will use queries.
•

The complexity in terms of queries for |bihb| is Õ(Tb /✏)•The complexity in terms of queries for A is almost order CA (/✏, ✏)The randomization method, the QLSP, and the gate model
For A > 0, the Hamiltonian is H 0 (s) = (I|bihb|)((1s)I + sA)

+ H.c.

If |bi is sparse and A is sparse, then H 0 (s) is also sparse

We can use a Hamiltonian simulation method to build a quantum circuit thatsimulates the evolution. The quantum circuit will use queries.
•

The complexity in terms of queries for |bihb| is Õ(Tb /✏)•The complexity in terms of queries for A is almost order CA (/✏, ✏)•The scaling in the precision parameter can be done polyligarithmic by using
faster methods for eigenpath traversal [11][11] S. Boixo, E. Knill, and R.D. Somma, arXiv:1005.3034 (2010)

Some conclusions and observations• Quantum computing seems promising. Several quantum algorithms forproblems in linear algebra with significant speedups exist• I presented quantum algorithms to solve the quantum linear systems
problem. The techniques can be generalized to apply other operators(other than the inverse of a matrix) to quantum states.
• The advantages of the first algorithm are in that the complexity
dependence on precision is only polylogarithmic, exponentially
improving previous algorithms for this problem• The advantages of the second algorithm are in that it doesn’t require
many ancillary qubits and the problem reduces to a simple Hamiltonian
simulation problem• It would be important to understand the applicability of this algorithm toscientific problems beyond the ones I mentioned. How important are theproblems and algorithms?