Abstract : I will review work by myself and others in recent years on the use of randomization in circuit optimization. I will present general results showing that any deterministic compiler for approximate synthesis problems can be lifted to a better random compiler. I will discuss the subtle issue of what "better" means and how it is sensitive to the metric and computation task at hand. I will then review specific randomized algorithms for quantum simulations, including randomized Trotter (Su & Childs) and my group's work on the qDRIFT and SPARSTO algorithms. I will conclude by commenting on the derandomization of random algorithms!

Abstract : With the advent of quantum supremacy, we have an unprecedented opportunity to explore quantum algorithms in new ways. The emergence of general-purpose quantum processors opens up empirical exploration of quantum algorithms far beyond what has been possible to date. Challenging computational problems arising in the practical world are often tackled by heuristic algorithms. While heuristic algorithms work well in practice, by definition they have not been analytically proven to be the best approach or to outperform the best previous approach. Instead, heuristic algorithms are empirically tested on benchmark and real-world problems. With the empirical evaluation NISQ hardware enables, we expect a broadening of established applications of quantum computing. What to run and how best to utilize these still limited quantum devices to gain insight into quantum algorithms remain open research questions. We discuss opportunities and challenges for using NISQ devices to evaluate quantum algorithms, including in elucidating quantum mechanisms and their uses for quantum computational purposes, in the design of novel or refined quantum algorithms, in compilation, error-mitigation, and robust algorithms design, and in techniques for evaluating quantum algorithms empirically.

Abstract : In this talk, Martonosi will cover two main themes. First, from her perspective as a Princeton Computer Science professor, she will offer research experiences and perspectives for future Quantum Computing architecture and programming trends. for Quantum Computing. In addition, from her recent rotation to serve a term leading the Computer and Information Science and Engineering (CISE) directorate at the US National Science Foundation (NSF), she will speak more broadly about US NSF funding approach for QC research and education.