Robin Kothari: Quantum Linear Systems Algorithms with Exponentially Improved Dependence on Precision

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


Duration: 51:00
1,532 views
0

Robin Kothari (MIT)
Quantum Linear Systems Algorithms with Exponentially Improved Dependence on Precision
QuICS Workshop on the Frontiers of Quantum Information and Computer Science (September 28, 2015)

Consider the linear system of equations Ax=b. Harrow, Hassidim, and Lloyd showed that if A and b satisfy appropriate conditions, it is possible to output a quantum state whose entries are proportional to the entries of x. Their algorithm runs in time polynomial in log N and 1⁄ϵ, where N is the size of A, and ϵ is the desired precision in the output state. We present an improved algorithm whose running time is polynomial in log N and log(1⁄ϵ), exponentially improving the dependence on precision while keeping the same dependence on other parameters.



Other Videos By QuICS


2015-10-06Debbie Leung: On the Power of PPT-preserving and Non-signalling Codes
2015-10-06Aram Harrow: Quantum Adiabatic Optimization Versus Quantum Monte Carlo
2015-10-06Michael Bremner: Average-case Complexity Vs. Approx. Simulation of Commuting Quantum Computations
2015-10-06Chris Monroe: Time to Build a Real Quantum Computer
2015-10-06Māris Ozols: Entropy Power Inequalities for Qudits
2015-10-06Thomas Vidick: A Multiprover Interactive Proof System for the Local Hamiltonian Problem
2015-10-06James Whitfield: Applications of Chemical Group Theory to Quantum Simulation
2015-10-06Graeme Smith: Additivity in Classical and Quantum Shannon Theory
2015-10-06Robin Blume-Kohout: Gate Set Tomography: 2 Qubits and 10^{-5} Error Bars
2015-10-06Steve Flammia: Sparse Quantum Codes with (Almost) Good Distance
2015-10-06Robin Kothari: Quantum Linear Systems Algorithms with Exponentially Improved Dependence on Precision
2015-10-06David Gosset: Gapped and Gapless Phases of Frustration-free Spin-1/2 chains
2015-10-06Beni Yoshida: Classifying Fault-tolerant Logical Gates by Group Cohomology (or SPT Phases)
2015-10-06Mark Zhandry: Quantum Query Solvability: A Refinement of Quantum Query Complexity and Applications
2015-10-06Mario Szegedy: Issues Concerning the Area Law in Quantum Physics
2015-10-06Lorenza Viola: Fixed-point Engineering in Quasi-local Open-system Dynamics
2015-10-06Scott Aaronson: Black Holes, Firewalls, and the Complexity of States and Unitaries