Rolando Somma: Quantum Algorithms for Systems of Linear Equations

Channel:
United States QuICS
Subscribers:
2,450
Published on ● Video Link: https://www.youtube.com/watch?v=JlIyLNndHaU


Duration: 55:53
1,665 views
0

A talk by Rolando Somma at the Quantum Machine Learning Workshop, hosted September 24-28, 2018 by the Joint Center for Quantum Information and Computer Science at the University of Maryland (QuICS).

Abstract: Harrow, Hassidim, and Lloyd (HHL) proved that, for a matrix A of dimension NxN and a vector b of dimension N, there exists a quantum algorithm that prepares a quantum state proportional to the solution of the linear system A.x=b. When the matrix A is sparse and well-conditioned, the HHL algorithm has complexity that is polynomial in 1/ε and log(N), where ε is greater than 0 is the precision. This result represents a quantum speedup with respect to classical algorithms. In this talk I will describe improved quantum algorithms for the linear system’s problem with a significant reduction in complexity and other resources. One such quantum algorithm has complexity that depends logarithmically in 1/ε, exponentially improving the complexity dependence on precision while keeping essentially the same dependence on other parameters. The other quantum algorithm is based on quantum adiabatic evolutions and does not use complex subroutines like phase estimation or variable time amplitude amplification that require several ancillary qubits.



Other Videos By QuICS


2019-05-28Anurag Anshu: Quantum decoupling (...) and the entanglement cost of one-shot quantum protocols
2019-04-04Ramis Movassagh: Supercritical Entanglement: counter-examples to the area law for quantum matter
2019-03-29Serge Fehr: Security of the Fiat-Shamir Transformation in the Quantum Random Oracle Model
2018-10-31Mario Szegedy: A New Algorithm for Product Decomposition in Quantum Signal Processing
2018-10-31Scott Aaronson: Gentle Measurement of Quantum States and Differential Privacy
2018-10-31Seth Lloyd: Quantum Generative Adversarial Networks
2018-10-31Norbert Linke: Quantum Machine Learning with Trapped Ions
2018-10-31Kristan Temme: Supervised Learning with Quantum Enhanced Feature Spaces
2018-10-31Soheil Feizi: Generative Adversarial Networks: Formulation, Design and Computation
2018-10-31Nathan Wiebe: Optimizing Quantum Optimization Algorithms via Faster Quantum Gradient Computation
2018-10-31Rolando Somma: Quantum Algorithms for Systems of Linear Equations
2018-10-31Anupam Praksah: A Quantum Interior Point Method for LPs and SDPs
2018-10-31Furong Huang: Discovery of Latent Factors in High-dimensional Data Using Tensor Methods
2018-10-31Fernando Brandao: Quantum Speed-up for SDPs and Kernel Learning
2018-10-31Srinivasan Arunachalam: Strengths and weaknesses of quantum examples for learning
2018-10-31Vedran Dunjko: A Route towards Quantum-Enhanced Artificial Intelligence
2018-10-31Elad Hazan: Efficient Optimization for Machine Learning: Beyond Stochastic Gradient Descent
2017-10-11John Preskill: QEC in 2017—Past, present, and future
2017-10-11Sepehr Nezami: Quantum Error Correction of Reference Frame Information
2017-10-11Anirudh Krishna: Performance of hyperbolic surface codes
2017-10-11Brian Swingle: Entanglement, Wormholes, and Quantum Error Correction


Tags:
machine learning