Eigenvalue estimation of differential operators with a quantum algorithm
Thomas Szkopek, Vwani Roychowdhury, Eli Yablonovitch, Daniel S. Abrams · Physical Review A · 2005
We demonstrate how linear differential operators could be emulated by a quantum processor, should one ever be built, using the Abrams-Lloyd algorithm. Given a linear differential operator of order $2S$, acting on functions $\ensuremath{\psi}({x}_{1},{x}_{2},\dots{},{x}_{D})$ with $D$ arguments, the computational cost required to estimate a low order eigenvalue to accuracy $\ensuremath{\Theta}(1∕{N}^{2})$ is $\ensuremath{\Theta}((2(S+1)(1+1∕\ensuremath{ u})+D)\mathrm{ln}\phantom{\rule{0.2em}{0ex}}N)$ qubits and $O({N}^{2(S+1)(1+1∕\ensuremath{ u})}{\mathrm{ln}}^{c}\phantom{\rule{0.2em}{0ex}}{N}^{D})$ gate operations, where $N$ is the number of points to which each argument is discretized, $\ensuremath{ u}$ and $c$ are implementation dependent constants of $O(1)$. Optimal classical methods require $\ensuremath{\Theta}({N}^{D})$ bits and $\ensuremath{\Omega}({N}^{D})$ gate operations to perform the same eigenvalue estimation. The Abrams-Lloyd algorithm thereby leads to exponential reduction in memory and polynomial reduction in gate operations, provided the domain has sufficiently large dimension $D>2(S+1)(1+1∕\ensuremath{ u})$. In the case of Schr\"odinger's equation, ground state energy estimation of two or more particles can in principle be performed with fewer quantum mechanical gates than classical gates.