Affiliation: Quantum Artificial Intelligence Laboratory, NASA
Title: Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study on Optimization and beyond.
Abstract: In this talk, I will give an overview of the NASA Quantum Artificial Intelligence Laboratory (QuAIL) team’s ongoing quantum computing investigations, with a focus on quantum and hybrid quantum-classical algorithms for challenging combinatorial optimization problems. I’ll discuss NASA’s work in assessing and advancing the potential of quantum computing, illustrating advances in algorithms, both near- and longer-term, and the benefits of algorithm-hardware co-design. I’ll also discuss physics-inspired classical algorithms that can be used at application scale today. The talk will conclude with a discussion of research challenges, particularly in optimization, and of the potential of quantum computing for computational challenges arising in future NASA missions.
Biography: Eleanor G. Rieffel leads the Quantum Artificial Intelligence Laboratory (QuAIL) at the NASA Ames Research Center and is the NASA Senior Researcher for Advanced Computing and Data Analytics. Her research focuses on quantum algorithms, applications of quantum computing, resource estimation, evaluation and utilization of near-term quantum hardware, logical and fault-tolerant quantum architectures, distributed quantum computing, quantum error characterization, and fundamental resources for quantum computation. She received her Ph.D. in mathematics from UCLA. She is best known for her 2011 book Quantum Computing: A Gentle Introduction (MIT Press) with coauthor Wolfgang Polak.
Affiliation: Free University of Berlin
Title: Quantum Optimization from a Rigorous Perspective
Abstract: Quantum computing promises computational advantages over classical computers. We know a few dozen quantum algorithms that feature superpolynomial quantum advantages. If one reads the popular press, one might get the impression that most efforts are directed toward finding quantum advantages in applications, notably in optimization, machine learning, or quantum simulation. But if we are honest, we do not yet know as much as we would like about these fields from a rigorous perspective. In this talk, we will investigate what can be said about variational quantum algorithms for optimization from a rigorous perspective. We will then turn to results on quantum optimization on fault tolerant quantum computers [1-3]. Conceptually, we will see how quantum computers can approximate certain instances of practically relevant problems such as integer programming that are hard to approximate for classical computers [4]. Mathematically, we explore a new reduction, invoking ideas of cryptography. We will explore new quantum SAT solvers [5]. In an outlook, we will sketch some potential directions where the field might be going, including notions of decoded quantum interferometry.
[1] Physical Review Letters 131, 100803 (2023).
[2] Quantum 9, 1640 (2025).
[3] arXiv:2403.13927 (2024).
[4] Science Advances 10, eadj5170 (2024).
[5] In preparation (2025).
Affiliation: Global Technology Applied Research, JPMorganChase
Title: Equivalence of Quantum Approximate Optimization Algorithm and Linear-Time Quantum Annealing for the Sherrington-Kirkpatrick Model
Abstract: The quantum approximate optimization algorithm (QAOA) and quantum annealing are two of the most popular quantum optimization heuristics. While QAOA is known to be able to approximate quantum annealing, the approximation requires QAOA angles to vanish with the problem size n, whereas optimized QAOA angles are observed to be size-independent for small n and constant in the infinite-size limit. This fact led to a folklore belief that QAOA has a mechanism that is fundamentally different from quantum annealing. In this work, we provide evidence against this by analytically showing that QAOA energy approximates that of quantum annealing under two conditions, namely that angles vary smoothly from one layer to the next and that the sum is bounded by a constant. These conditions are known to hold for near-optimal QAOA angles empirically. Our results are enabled by novel formulae for QAOA energy with constant sum of angles and arbitrary depth and the series expansion of energy in sum of angles, which may be of independent interest. While our results are limited to the Sherrington-Kirkpatrick (SK) model, we show numerically that the expansion holds for random 2SAT and expect our main results to generalize to other constraint satisfaction problems. A corollary of our results is a quadratic improvement for the bound on depth required to compile Trotterized quantum annealing of the SK model.
Affiliation: Google Quantum AI
Title: Optimization by Decoded Quantum Interferometry
Abstract: We address a longstanding question in quantum computing: Can quantum computers provide exponential speedups for optimization problems? We introduce Decoded Quantum Interferometry (DQI), which reduces optimization problems to decoding problems by exploiting structure in the Fourier spectra of the objective functions. DQI achieves an exponential speedup for a previously-studied optimization problem, and is a radical departure from prior approaches, as it relies on neither the Abelian hidden subgroup problem nor a Hamiltonian formulation.
Biography: Noah Shutty is a researcher on the Quantum Algorithms team at Google Quantum AI. He received a PhD in physics from Stanford University in 2022, and a BS in physics and mathematics from the University of Michigan in 2015. He works in quantum algorithms and fault-tolerance; his research interests include error-correcting codes, decoding algorithms, and logic synthesis.
Affiliation: Sandia National Laboratories
Title: Decoded Quantum Interferometry and Max Cut
Abstract: Decoded Quantum Interferometry (DQI) is a promising recently proposed quantum algorithm for approximating discrete optimization problems that could offer an exponential quantum advantage. DQI provides the currently best-known approximation guarantees for some problems; however, it requires very special problem structure. We show that for Max Cut, the instances for which DQI gives a nontrivial approximation guarantee are solvable exactly by an efficient classical algorithm. In this case the problem structure that enables good DQI approximations also renders the problem classically tractable.
Affiliation: Los Alamos National Laboratory
Title: On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization
Abstract: Over the past decade, the usefulness of quantum computing hardware for combinatorial optimization has been the subject of much debate. In this presentation, we review a performance assessment of D-Wave Systems' “Advantage Performance Update” computer. We show that classes of contrived problems exist where this quantum annealer can provide run time benefits over a collection of established classical solution methods that represent the current state-of-the-art for benchmarking quantum annealing hardware. Although this work does not present an irrefutable performance benefit for this emerging quantum optimization technology, it does exhibit encouraging progress, signaling the potential impacts on practical optimization tasks in the future.
Biography: Dr. Carleton Coffrin joined LANL as a staff scientist in 2016 and currently leads LANL’s LDRD project “Accelerating Scientific Discovery with Quantum Annealing”. Dr. Coffrin received a PhD in Computer Science in 2012 with a focus on developing numerical methods for mathematical optimization. Since joining LANL, Dr. Coffrin’s research has focused on understanding the potential applications of quantum computers and benchmarking commercial quantum computers to forecast when application impact may occur. In addition to quantum computing research, Dr. Coffrin has expertise in benchmarking optimization methods for energy systems applications, especially the AC Optimal Power Flow problem, and was a core contributor to the design and operation of ARPA-e’s Grid Optimization Competition.
Affiliation: IBM Research
Title: Provable bounds for noise-free expectation values computed from noisy samples
Abstract: Quantum computing has emerged as a powerful computational paradigm capable of solving problems beyond the reach of classical computers. However, today’s quantum computers are noisy, posing challenges to obtaining accurate results. Here, we explore the impact of noise on quantum computing, focusing on the challenges in sampling bit strings from noisy quantum computers and the implications for optimization and machine learning. We formally quantify the sampling overhead to extract good samples from noisy quantum computers and relate it to the layer fidelity, a metric to determine the performance of noisy quantum processors. Further, we show how this allows us to use the conditional value at risk of noisy samples to determine provable bounds on noise-free expectation values. We discuss how to leverage these bounds for different algorithms and demonstrate our findings through experiments on real quantum computers involving up to 127 qubits. The results show strong alignment with theoretical predictions.
Affiliation: Argonne National Laboratory
Title: Q-OPT: A Toolkit for Quantum Optimization with QAOA
Abstract: Q-OPT is a software toolkit for building and optimizing Quantum Approximate Optimization Algorithm (QAOA) programs. It covers the full workflow: problem encoding, ansatz design, circuit synthesis, and the classical optimization loop. The encoding tool translates combinatorial problems into compact Hamiltonians. The ansatz library includes our research in Quantum Logical Search Ansatz and a Dynamic Quantum Variational Ansatz (DQVA) focused on Maximum Independent Set. The toolkit also includes noise-aware classical optimizers for variational algorithms.
In this talk I will outline the full stack and then focus on the circuit synthesis tools. Q-OPT includes two synthesis methods: a fast heuristic and an optimal circuit synthesizer, allowing users to trade compilation time for circuit quality. QuCLEAR is a fast synthesizer that extracts Clifford subcircuits and resolves them on a classical processor, leaving a shorter QAOA circuit for the quantum device. HOPPS (Hardware-Aware Optimal Phase Polynomial Synthesis) is a SAT-based method that synthesizes circuits with doubly optimal CNOT count or CNOT depth while respecting hardware connectivity. For large QAOA circuits, HOPPS supports an iterative block-wise circuit optimization strategy and a parallel framework that runs efficiently on HPC systems. Q-OPT streamlines the QAOA problem-solving process and prepares for future advances. We will continue to improve the toolkit and welcome feedback and collaboration. Our goal is to make quantum computing for combinatorial optimization more accessible and to automate the end-to-end workflow.
Affiliation: Oak Ridge National Laboratory
Title: Distributed Variational Optimization Algorithms on Large-scale Quantum-HPC Ecosystems
Abstract: We present an overview of distributed variational optimization algorithms designed to leverage quantum-centric supercomputing architectures (i.e., integrated quantum–HPC ecosystems), aimed at solving large-scale combinatorial optimization problems. Our focus is on the Distributed Quantum Approximate Optimization Algorithm (DQAOA), a scalable quantum-classical hybrid approach that partitions quantum workloads across multiple quantum processing units (QPUs) or simulators, coordinated by classical HPC infrastructure. A central contribution of this work is the application of DQAOA to real-world materials optimization challenges, which are naturally formulated as large, densely connected quadratic unconstrained binary optimization (QUBO) problems. These QUBO problems often exceed the capacity of current quantum hardware or simulator. We will showcase case studies in high-dimensional materials design, demonstrating how distributed quantum resources can accelerate the discovery of optimal material configurations beyond the capabilities of conventional approaches.