The goal of this project is to develop a specialized Quantum Approximate Optimization Algorithm (QAOA) quantum circuit simulator. QAOA is the most studied quantum optimization algorithm and is considered to be the prime candidate for demonstrating quantum advantage. There is a worldwide race underway amongst top quantum information science researchers to find combinatorial optimization problems and their instances that run efficiently and faster on quantum devices rather than on classical computers. One of the critical bottlenecks is to find circuit parameters faster on a classical computer to accelerate variational quantum-classical frameworks. The expected improvements to the developed simulator will dramatically increase the speed of QAOA simulations by at least one order of magnitude and significantly speed up research done on finding optimal QAOA circuit parameters. As a result, it will help the realization of quantum advantage by US scientists in this highly competitive field of science.
The technical goal of this project is to carry out computational and algorithmic investigations in various node elimination methods for tensor contraction in the development of a scalable quantum simulator. The plan is to build upon the success of the combinatorial scientific computing community in developing elimination algorithms for such tasks as minimizing the error and complexity in matrix computations and optimizing the time and space complexity in automatic differentiation, and recent developments in treewidth optimization algorithms. Additionally, in this project, emphasis will be placed on scaling up relevant graph algorithms to achieve acceptable time/quality trade-off for large-scale quantum simulators. Algorithmic and software products of this project will include a specialized QAOA quantum circuit open-source simulator equipped with fast optimization algorithms to accelerate tensor contraction methods. A high-quality simulator that scales to sufficiently large circuits is one of the major bottlenecks in discovering applications for demonstrating quantum advantage.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
