Discipline: Computer Sciences and Information Management
Subcategory: Computer Science & Information Systems
Session: 4
Room: Virginia B
Bhaskar Roberts - Princeton University
Co-Author(s): Brennan Schaffner, University of St. Thomas, St. Paul, MN; Finn Voichick, Washington University in St. Louis, St. Louis, MO
Motivation: We are interested in simulating quantum mechanical systems using quantum computers, since it is exponentially more costly to represent a quantum system on a classical computer. We studied how a sequence of single-qubit rotations can be composed with quantum walk operators to implement the Jacobi-Anger expansion, a polynomial that is foundational to simulating common Hamiltonians [1]. Problems Being Investigated: J. Haah recently gave an algorithm to find a sequence of single-qubit rotations that implement a polynomial function chosen by the user [2]. However, no implementation of this algorithm is available. Furthermore, the algorithm runs in O(N^3) time, which is too slow for use on large-degree polynomials. Also, the algorithm only works on polynomials that satisfy certain parity constraints. We implemented Haah’s algorithm in Python and Mathematica and studied several improvements. We wanted to know on which platform, Python or Mathematica, was the algorithm faster. We also wanted to extend the algorithm to decompose polynomials that don’t satisfy the parity constraints. Finally, we are studying how to avoid root-finding, the bottleneck of the algorithm. Methods and Results: We implemented the algorithm in Python and Mathematica because both are widely used, and they support arbitrary-precision arithmetic, which is required for the algorithm. (For Python we used the Sympy library to perform arbitrary-precision arithmetic). We tested our code on a Macbook Air. We found the Mathematica implementation was significantly faster than the Python version, especially at high precision. For instance, for a fixed precision of 10^-4, with N = 145, we measured runtimes of 6*10^4 s for Python, and 1*10^1 s for Mathematica. The difference in runtime is largely because Mathematica is faster at root-finding. We plan to make this code publically available. We also improved Haah’s algorithm to make it work on a larger class of polynomials: we can decompose even polynomials that don’t satisfy the parity constraints. Part of the algorithm involves finding the roots of the given polynomial, and constructing two new polynomials from those roots. We found that by partitioning the roots differently, we don’t need to require parity constraints on the input polynomial. A similar technique is described in [3]. Conclusion and Future Research: Going forward, we hope to find alternatives to root-finding, the bottleneck of Haah’s algorithm. The Bauer method for decomposing matrices [3] has shown promising initial results. References: [1] Low, G.H. and Chuang, I.L., “Optimal Hamiltonian Simulation by Quantum Signal Processing”. Phys. Rev. Lett. 118, 010501 (2017). [2] Haah, J., “Product Decomposition of Periodic Functions in Quantum Signal Processing,” (2018), arXiv:1806.10236. [3] Goodman, T.N., Micchelli, C.A., Rodriguez, G. et al. “Spectral Factorization of Laurent Polynomials”. Advances in Computational Mathematics (1997) 7: 429. https://doi.org/10.1023/A:1018915407202.
Funder Acknowledgement(s): This research was conducted through an NSF REU program (CAAR) at the University of Maryland, College Park. The primary author was funded by Dr. An Zhu.
Faculty Advisor: Andrew Childs, amchilds@umd.edu
Role: I helped implement Haah's algorithm in Python and Mathematica. I also designed the improvement to the algorithm which allows it to work on a larger class of polynomials (without parity constraints). Finally, I helped implement and test alternatives to root-finding.