The Speakers

Affiliation: Google Quantum AI

Title: Strategies for Running the Quantum Approximate Optimization Algorithm at Hundreds of Logical Qubits 

Abstract: We explore two strategies aimed at reducing the amount of computation, both quantum and classical, required to run the Quantum Approximate Optimization Algorithm (QAOA). We focus on the example of MaxCut on random 3-regular graphs with up to a few hundred vertices. We imagine running these strategies on fault-tolerant hardware that can handle instances of this size.

First, following Wurtz et al., we consider the standard QAOA with instance-independent “tree” parameters chosen in advance. At level p, these tree parameters are chosen to optimize the MaxCut expectation for graphs with girth at least 2p + 1. We provide extensive numerical evidence supporting the performance guarantee for tree parameters conjectured by Wurtz et al., and see that the approximation ratios obtained with tree parameters are typically well beyond the conjectured lower bounds. Further, by using tree parameters as the initial point of a variational optimization, we see only slight improvements and get results comparable to performing a full optimization. This suggests a competitive and inexpensive alternative to the fully optimized QAOA.

Next, we modify the warm-start QAOA of Tate et al. The starting state for the QAOA is now an optimized product state associated with a solution of the Goemans-Williamson (GW) algorithm. We find that the tree parameters above continue to perform well for the warm-start QAOA. Using tree-parameters as the starting point of optimization, we find that for random 3-regular graphs with hundreds of vertices, the MaxCut expectation of the warm-start QAOA at depth p ≳ 3 is at least comparable to that of the standard GW algorithm.

Our numerics on random instances do not provide general performance guarantees but do provide substantial evidence that there exists a regime of instance sizes in which the QAOA finds good solutions in reasonable runtimes. For each instance studied, we classically compute the expected size of the QAOA distribution of cuts; producing the actual cuts requires running a quantum computer.

Affiliation: Global Technology Applied Research, JPMorganChase 

Title: Progress in Hardware Execution of Quantum Optimization Algorithms 

Abstract: Quantum algorithms must be scaled up to tackle real-world applications. Doing so requires overcoming the noise present on today's hardware. The quantum approximate optimization algorithm (QAOA) is a promising candidate for scaling up due to its modest resource requirements and documented asymptotic speedup over state-of-the-art classical algorithms for some problems. However, achieving better-than-classical performance with QAOA is believed to require fault tolerance. In this paper, we demonstrate a partially fault-tolerant implementation of QAOA using the [[k+2,k,2]] ``Iceberg'' error detection code. We observe that encoding the circuit with the Iceberg code improves the algorithmic performance as compared to the unencoded circuit for problems with up to 20 logical qubits on a trapped-ion quantum computer. Additionally, we propose and calibrate a model for predicting the code performance, and use it to characterize the limits of the Iceberg code and extrapolate its performance to future hardware with improved error rates. In particular, we show how our model can be used to determine necessary conditions for QAOA to outperform Goemans-Williamson algorithm on future hardware. Our results demonstrate the largest universal quantum computing algorithm protected by partially fault-tolerant quantum error detection on practical applications to date, paving the way towards solving real-world applications with quantum computers. 

Affiliation: University of California, Riverside

Title: QAOA: How to Exploit Symmetries 

Abstract: We consider Constrained Optimization Problems, focusing on the role of symmetries in their reduction. Let Hp  be the problem Hamiltonian and K a group of symmetries of Hp (not necessarily the full symmetry group). We explore how the action of K can reduce both the classical and quantum versions of the optimization problem. The action of K induces a decomposition W = ⊕Wi, with W0 being the subspace of K-invariants. For some K, commonly appearing as symmetries of objective functions, we outline the construction of a mixer Hamiltonian that facilitates a variant of QAOA using the same problem Hamiltonian Hp. This reduced QAOA operates within the invariant subspace W0 prior to the final measurement. We will discuss the advantages of this modified algorithm. 

Affiliation: Pennsylvania State University 

Title: Quantum-Enabled Optimal Placement of Meters in Power Systems

Abstract: Optimizing the placement of measuring infrastructure in power systems is critical for enhancing the efficiency, reliability, and safety of energy networks. The integration of renewable energy resources significantly increases the system’s operational complexity, making the strategic positioning of meters and sensors essential for accurate data collection, real-time monitoring, load balancing, and fault detection. This talk introduces a Physics-Informed Quantum Approximate Optimization Algorithm to efficiently place measuring infrastructure, thereby increasing system observability under heterogeneous disturbances from generations, loads, potential attacks, and reconfigurations. Recognizing the importance of quantum circuit parameters in variational quantum algorithms, we will also discuss a parameter warm-up strategy that incorporates the physical principles of power systems, aiming to provide a speedup over traditional methods. Simulation results will be introduced to demonstrate the effectiveness of this research.

Affiliation:

• Romina Yalovetzky: Global Technology Applied Research, JPMorganChase

• Martin Schuetz: Amazon Quantum Solutions Lab, Amazon Web Services 

Title: Hardness of the Maximum-Independent-Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups 

Abstract: Rydberg atom arrays are among the leading contenders for the demonstration of quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi et al., Science 376, 1209 (2022)], we study the maximum independent-set problem (MIS) on unit-disk graphs, which is the native problem this type of quantum hardware solves. We carry out extensive numerical studies and assess problem hardness, using both exact and heuristic algorithms. We find that quasiplanar instances with Union-Jack-like connectivity can be solved to optimality for up to thousands of nodes within minutes, with both custom and generic commercial solvers on commodity hardware, without any instance-specific fine-tuning. We also perform a scaling analysis, showing that by relaxing the constraints on the classical simulated annealing algorithms considered in Ebadi et al., our implementation is competitive with the quantum algorithms. Conversely, instances with larger connectivity or less structure are shown to display a time-to-solution potentially orders of magnitudes larger. Based on these results, we propose protocols to systematically tune problem hardness, motivating experiments with Rydberg atom arrays on instances orders of magnitude harder (for established classical solvers) than previously studied. 

Affiliation: Flatiron Institute, Simons Foundation

Title: Designing Peptides and Proteins with Quantum Computers 

Abstract: Proteins are long chains of amino acids produced in living cells from the 20 natural or "canonical" amino acids; peptides are shorter chains amenable to chemical synthesis from natural or synthetic amino acids.  The particular sequence of amino acids in a given protein or peptide determines the three-dimensional structure into which it spontaneously folds, and the structure in turn determines the function.  Over the last 40 years, computational methods have been essential for understanding the sequence-fold-function relationship, and have permitted the rational design of new sequences able to fold into new structures with useful new functions, including as drugs, biomaterials, and designer enzymes.  Machine learning methods have recently bolstered this, by learning sequence-structure-function patterns from the canonical amino acids in natural proteins.  However, synthetic peptide design remains challenging, both for want of training data when synthetic amino acids are used, and because of the enormous combinatorial optimization problems that must be solved when designing a sequence for a particular application.  The growth in the number of commercially-available synthetic amino acids has made these optimization problems even less tractable on classical hardware.

Quantum computers can potentially provide means of searching exponentially larger search spaces when solving hard optimization problems.  This provides a potential path to breaking through the tractability ceiling that limits the size and complexity of protein and peptide design problems that can be solved on classical computers.  In this talk, I will present work carried out on the D-Wave quantum annealer to design natural and synthetic proteins and peptides on current-generation quantum hardware.  I will present a synthetic peptide designed on QPU that was synthesized and experimentally confirmed to fold into the designed structure.  I will also discuss ongoing work to improve the qubit efficiency of the mapping of the design problem to quantum hardware, and to incorporate the full set of guidance terms used by classical protein and peptide designers to control the design process.  Finally, I will present initial results extending protein and peptide design to gate-based quantum computers using state-of-the-art quantum optimization algorithms such as QAOA, and will discuss implications for related problems (which also have classical tractability ceilings) in multibody molecular docking and protein and peptide structure prediction. 

Affiliation: QuEra

Title: Quantum Optimization with Analog and Dynamically Reconfigurable Gate-Based Neutral Atoms

Abstract: Recently, neutral atom-based quantum computers have emerged as a promising modality for scalable and robust quantum computing. Starting with analog-mode devices that implement computation using time-dependent quantum Hamiltonian dynamics, QuEra has demonstrated compelling applications using optimization with hybrid algorithms and generative sampling, machine learning with reservoir computing, and simulation with quenches and state preparation. QuEra’s next-generation devices currently under development will be gate based, using a dynamically reconfigurable architecture that moves atoms in parallel mid-circuit, enabling an efficient all-to-all connectivity on over 200 qubits. This connectivity and scale, coupled with high-fidelity parallel entangling gates, enables an experimental testbed for many optimization algorithms, such as QAOA. This talk will present prior optimization results using analog-mode, introduce the structure of digital-mode programs, and present an initial outlook of applications using digital-mode neutral atoms. 

Affiliation: Los Alamos National Laboratory

Title: Theoretical Approximation Ratios for Warm-Start QAOA on 3-Regular Max-Cut Instances at Depth p=1

Abstract: We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle θ, we consider warm-starts where the initial state is a product state where each qubit position is angle θ away from either the north or south pole of the Bloch sphere; of the two possible qubit positions the position of each qubit is decided by some classically obtained cut encoded as a bitstring b. 

We illustrate through plots how the properties of b and the initialization angle θ influence the bound on the  approximation ratios of warm-started QAOA. We consider various classical algorithms (and the cuts they produce which we use to generate the warm-start). Our results strongly suggest that  there does not exist any choice of initialization angle that yields a (worst-case) approximation ratio that simultaneously beats standard QAOA and the classical algorithm used to create the warm-start. 

Additionally, we show that at θ = 60°, warm-started QAOA is able to (effectively) recover the cut used to generate the warm-start, thus suggesting that in practice, this value could be a promising starting angle to explore alternate solutions in a heuristic fashion. 

Affiliation: NASA Quantum Artificial Intelligence Lab

Title: Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping

Abstract: We present Noise-Directed Adaptive Remapping (NDAR), a heuristic meta-algorithm for approximately solving binary optimization problems by dynamically leveraging certain types of physical noise. We consider access to a noisy quantum processor with dynamics that feature a global attractor state. In a standard setting, such noise is detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that biases the output distribution towards higher-quality solutions. The end result is that noise aids our variational optimization as opposed to hindering it. We present improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device, reporting approximation ratios 0.9-0.96 for random, fully connected graphs on n=82 qubits, using only depth p=1 QAOA with NDAR. This compares to 0.34-0.51 for standard p=1 QAOA with the same number of function calls.