Collaborative Research: FET: Medium: Quantum Monte Carlo Speed Ups for Multilevel Computations and Other Statistical Algorithms

The goal of this project is to develop innovative computational methods that integrate classical and quantum algorithmic tools within the fields of statistics and operations research. The project focuses on applications involving models such as stochastic differential equations, and areas such as machine learning, and data analytics, which arise in various applied engineering and scientific disciplines. Leveraging the diverse expertise of the research team in classical and quantum algorithms, statistics, and operations research, the project will develop quantum-enhanced algorithms for decision-making under uncertainty in both single-stage and multi-stage settings, as well as quantum-accelerated multilevel Monte Carlo methods. These methods will enable, by means of substantially faster algorithms, significant advances in the design of efficient Bayesian inference and machine learning procedures. They will also benefit practitioners across various scientific domains in the physical and social sciences. The project's educational and outreach efforts include curriculum development, diversity initiatives, workshops, and partnerships with local schools. These efforts will broaden the participation of the computing community both in terms of the use of novel quantum methods but also in their application to a wide range of applications. The research plan builds on recent advancements in both quantum and classical algorithms, including contributions from the team members. By developing new quantum Monte Carlo estimators and leveraging advances in parallel randomized multilevel Monte Carlo methods, the team will systematically explore quadratic speed-ups through variable time quantum algorithms and quantum-inside-quantum Monte Carlo strategies. Specific objectives include developing quantum Monte Carlo strategies for solving Markov decision problems with a guaranteed query complexity comparable to evaluating a policy (not necessarily optimal). Another objective is the analysis of stochastic optimization problems with a zero-order oracle, achieving quadratic speed-ups compared to classical approaches. The researchers will further explore quantum accelerated algorithms for computing expectations under a wide range of equilibrium/Boltzmann distributions. Moreover, the investigators will establish upper and lower bounds that confirm the optimality of the quantum accelerated algorithms. 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.