Quantum Computing Group
Novel Quantum Algorithms
This project for DOE Advanced Scientific Computing Research aims to discover novel quantum primitives via the study of classical numerical transforms. This work defines a quantum primitive as a quantum subroutine that is used across many different quantum algorithms. Currently, few such primitives exist in modern quantum algorithms, limiting their scope and reach. Inspired by the quantum Fourier transform, this work involves a systematic search for novel quantum primitives over the known fast classical transforms. Some first targets for this approach include the Hermite, orthogonal polynomial, and generalized Fourier transforms. The discovery of quantum analogues for any of these transforms would immediately lead to fast-forwarding algorithms for quantum simulation. Moreover, they would also cross-pollinate with the current quantum primitives, enhancing the potential for many new quantum algorithms with applications from physics to chemistry to mathematics to cryptography—and beyond.
A complementary direction to this targeted search for fast classical transforms that are convertible to quantum transforms is a study of the necessary and sufficient conditions needed for a fast classical transform to convert to a quantum transform, either at all or with known speed-up potential. This approach will be synergistic with the previous one as the discovery of such conditions will narrow the search scope for targeting fast classical transforms. Meanwhile, uncovering convertible fast classical transforms will constrain potential candidates to reveal necessary and sufficient conditions.
Throughout the entire process, benchmarking of candidate and confirmed quantum transforms will be performed on near-term quantum devices to analyze the feasibility of short- and medium-term application of these noisy intermediate-scale quantum (NISQ)-era quantum algorithm transforms, as well as to discern their long-term applicability to larger and more noise-resilient quantum computers.