An official website of the United States government
Abstract Quantum annealing (QA) is a continuous-time heuristic quantum algorithm for solving or approximately solving classical optimization problems. The algorithm uses a schedule to interpolate between a driver Hamiltonian with an easy-to-prepare ground state and a problem Hamiltonian whose ground state encodes solutions to an optimization problem. The standard implementation relies on the evolution being adiabatic: keeping the system in the instantaneous ground state with high probability and requiring a time scale inversely related to the minimum energy gap between the instantaneous ground and excited states. However, adiabatic evolution can lead to evolution times that scale exponentially with the system size, even for computationally simple problems. Here, we study whether non-adiabatic evolutions with optimized annealing schedules can bypass this exponential slowdown for one such class of problems called the frustrated ring model. For sufficiently optimized annealing schedules and system sizes of up to 39 qubits, we provide numerical evidence that we can avoid the exponential slowdown. Our work highlights the potential of highly-controllable QA to circumvent bottlenecks associated with the standard implementation of QA.
more »
« less
This content will become publicly available on April 1, 2026
Quantum Adiabatic Optimization with Rydberg Arrays: Localization Phenomena and Encoding Strategies
Quantum adiabatic optimization seeks to solve combinatorial problems using quantum dynamics, requiring the Hamiltonian of the system to align with the problem of interest. However, these Hamiltonians are often incompatible with the native constraints of quantum hardware, necessitating encoding strategies to map the original problem into a hardware-conformant form. While the classical overhead associated with such mappings is easily quantifiable and typically polynomial in problem size, it is much harder to quantify their overhead on the quantum algorithm, e.g., the transformation of the adiabatic timescale. In this work, we address this challenge on the concrete example of the encoding scheme proposed in [Nguyen , PRX Quantum , 010316 (2023)], which is designed to map optimization problems on arbitrarily connected graphs into Rydberg atom arrays. We consider the fundamental building blocks underlying this encoding scheme and determine the scaling of the minimum gap with system size along adiabatic protocols. Even when the original problem is trivially solvable, we find that the encoded problem can exhibit an exponentially closing minimum gap. We show that this originates from a quantum coherent effect, which gives rise to an unfavorable localization of the ground-state wave function. On the QuEra Aquila neutral atom machine, we observe such localization and its effect on the success probability of finding the correct solution to the encoded optimization problem. Finally, we propose quantum-aware modifications of the encoding scheme that avoid this quantum bottleneck and lead to an exponential improvement in the adiabatic performance. This highlights the crucial importance of accounting for quantum effects when designing strategies to encode classical problems onto quantum platforms.
more »
« less
- Award ID(s):
- 2012023
- PAR ID:
- 10654728
- Publisher / Repository:
- American Physical Society
- Date Published:
- Journal Name:
- PRX Quantum
- Volume:
- 6
- Issue:
- 2
- ISSN:
- 2691-3399
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find the problem hardness is controlled by the solution degeneracy and number of local minima, and experimentally benchmark the quantum algorithm’s performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.more » « less
-
In physics and chemistry, quantum systems are typically modeled using energy constraints formulated as Hamiltonians. Investigations into such systems often focus on the evolution of the Hamiltonians under various initial conditions, an approach summarized as Adiabatic Quantum Computing (AQC). Although this perspective may initially seem foreign to functional programmers, we demonstrate that conventional functional programming abstractions—specifically, the Traversable and Monad type classes—naturally capture the essence of AQC. To illustrate this connection, we introduce EnQ, a functional programming library designed to express diverse optimization problems as energy constraint computations (ECC). The library comprises three core components: generating the solution space, associating energy costs with potential solutions, and searching for optimal or near-optimal solutions. Because EnQ is implemented using standard Haskell, it can be executed directly through conventional classical Haskell compilers. More interestingly, we develop and implement a process to compile EnQ programs into circuits executable on quantum hardware. We validate EnQ’s effectiveness through a number of case studies, demonstrating its capacity to express and solve classical optimization problems on quantum hardware, including search problems, type inference, number partitioning, clique finding, and graph coloring.more » « less
-
Abstract The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT (All-SAT) and Max-SAT problems. G-QAOA is less resource-intensive and more adaptable for these problems than Grover’s algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles.more » « less
-
This thesis investigates quantum algorithms for eigenstate preparation, with a primary focus on solving eigenvalue problems such as the Schrodinger equation by utilizing near-term quantum computing devices. These problems are ubiquitous in several scientific fields, but more accurate solutions are specifically needed as a prerequisite for many quantum simulation tasks. To address this, we establish three methods in detail: quantum adiabatic evolution with optimal control, the Rodeo Algorithm, and the Variational Rodeo Algorithm.The first method explored is adiabatic evolution, a technique that prepares quantum states by simulating a quantum system that evolves slowly over time. The adiabatic theorem can be used to ensure that the system remains in an eigenstate throughout the process, but its implementation can often be infeasible on current quantum computing hardware. We employ a unique approach using optimal control to create custom gate operations for superconducting qubits and demonstrate the algorithm on a two-qubit IBM cloud quantum computing device. We then explore an alternative to adiabatic evolution, the Rodeo Algorithm, which offers a different approach to eigenstate preparation by using a controlled quantum evolution that selectively filters out undesired components in the wave function stored on a quantum register. We show results suggesting that this method can be effective in preparing eigenstates, but its practicality is predicated on the preparation of an initial state that has significant overlap with the desired eigenstate. To address this, we introduce the novel Variational Rodeo Algorithm, which replaces the initialization step with dynamic optimization of quantum circuit parameters to increase the success probability of the Rodeo Algorithm. The added flexibility compensates for instances in which the original algorithm can be unsuccessful, allowing for better scalability. This research seeks to contribute to a deeper understanding of how quantum algorithms can be employed to attain efficient and accurate solutions to eigenvalue problems. The overarching goal is to present ideas that can be used to improve understanding of nuclear physics by providing potential quantum and classical techniques that can aid in tasks such as the theoretical description of nuclear structures and the simulation of nuclear reactions.more » « less
