Fast quantum algorithm for differential equations
Can quantum computers solve partial differential equations (PDEs) exponentially faster than classical computers? A major challenge is the condition number of the matrices obtained from discretizing PDEs, which often grows polynomially with the matrix size and eliminates the possibility of exponential quantum speedup. I will discuss an algorithmic technique and a new quantum encoding of the solution that overcome this bottleneck and yield a quantum algorithm with a polylogarithmic cost for a large class of PDEs, thus restoring the possibility of exponential quantum speedup. More broadly, I will demonstrate how reformulating a problem in a way amenable to quantum computation can overcome limitations that would otherwise arise from directly translating classical methods into quantum algorithms.

