# Freiburg 2019 – wissenschaftliches Programm

## Sitzungen | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

# FM: Fall Meeting

## FM 21: Quantum Computation: Algorithms

### FM 21.3: Talk

### Montag, 23. September 2019, 17:15–17:30, 2006

Quantum Algorithm for Solving Tri-Diagonal Linear Systems of Equations — •Almudena Carrera Vazquez^{1,2}, Albert Frisch^{3}, Dominik Steenken^{3}, Harry S. Barowski^{3}, Ralf Hiptmair^{2}, and Stefan Woerner^{1} — ^{1}IBM Research, Zurich, Switzerland — ^{2}ETH Zurich, Zurich, Switzerland — ^{3}IBM Systems, Boeblingen, Germany

Numerical simulations, optimisation problems, statistical analysis and computer graphics are only a few examples from the wide range of real-life applications which rely on solving large systems of linear equations. The best classical methods can approximate the solution of sparse systems in time poly(N,s,κ,log(1/є)), where N denotes the number of unknowns, s the sparsity, κ its condition number and є the accuracy of the approximation. In 2009, A. Harrow, A. Hassidim and S. Lloyd (HHL) proposed a quantum algorithm with a running time of poly(logN, s, κ, 1/є) under the assumptions of the availability of efficient methods for loading the data, Hamiltonian simulation and extracting the solution. This talk presents efficient implementations for the missing oracles and analyzes the overall performance of the algorithm. The main result presented is a novel procedure for reducing the dependency of the complexity on the error from 1/є to log^{3}(1/є). This method could also be used more generally to obtain a similar reduction in the gate complexity of a circuit for Hamiltonian simulation. A complete implementation of the HHL algorithm running in polylog(N,κ,1/є) is given for the case of a special class of tri-diagonal symmetric matrices.