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 Vazquez1,2, Albert Frisch3, Dominik Steenken3, Harry S. Barowski3, Ralf Hiptmair2, and Stefan Woerner1 — 1IBM Research, Zurich, Switzerland — 2ETH Zurich, Zurich, Switzerland — 3IBM 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 log3(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.