This study explores the use of subspace methods in combination with counterdiabatic driving in a Rydberg atom system to solve the Maximum Independent Set (MIS) problem. Although exact counterdiabatic driving offers excellent performance, it comes at an unscalable computational cost. In this work, we demonstrate that counterdiabatic driving can be significantly improved by restricting the analysis to a relevant subspace of the system. We first show that both direct diagonalization and the Krylov method for obtaining the counterdiabatic matrix can be accelerated through the use of subspace techniques, while still maintaining strong performance. We then demonstrate that the cost function used in the standard Krylov method can be further optimized by employing a subspace-based cost function. These findings open up new possibilities for applying counterdiabatic driving in a practical and efficient manner to a variety of quantum systems.
This study explores the use of subspace methods in combination with counterdiabatic driving in a Rydberg atom system to solve the Maximum Independent Set (MIS) problem. Although exact counterdiabatic driving offers excellent performance, it comes at an unscalable computational cost. In this work, we demonstrate that counterdiabatic driving can be significantly improved by restricting the analysis to a relevant subspace of the system. We first show that both direct diagonalization and the Krylov method for obtaining the counterdiabatic matrix can be accelerated through the use of subspace techniques, while still maintaining strong performance. We then demonstrate that the cost function used in the standard Krylov method can be further optimized by employing a subspace-based cost function. These findings open up new possibilities for applying counterdiabatic driving in a practical and efficient manner to a variety of quantum systems.
We describe and analyze an architecture for quantum optimization to solve maximum independent set (MIS) problems using neutral atom arrays trapped in optical tweezers. Optimizing independent sets is one of the paradigmatic, NP-hard problems in computer science. Our approach is based on coherent manipulation of atom arrays via the excitation into Rydberg atomic states. Specifically, we show that solutions of MIS problems can be efficiently encoded in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg blockade mechanism. By studying the performance of leading classical algorithms, we identify parameter regimes, where computationally hard instances can be tested using near-term experimental systems. Practical implementations of both quantum annealing and variational quantum optimization algorithms beyond the adiabatic principle are discussed.
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 that the problem hardness is controlled by the solution degeneracy and number of local minima, and we 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.
Unitary processes allow for the transfer of work to and from Hamiltonian systems. However, to achieve nonzero power for the practical extraction of work, these processes must be performed within a finite time, which inevitably induces excitations in the system. We show that depending on the time scale of the process and the physical realization of the external driving employed, the use of counterdiabatic quantum driving to extract more work is not always effective. We also show that by virtue of the two-time energy measurement definition of quantum work, the cost of counterdiabatic driving can be significantly reduced by selecting a restricted form of the driving Hamiltonian that depends on the outcome of the first energy measurement. Lastly, we introduce a measure, the exigency, that quantifies the need for an external driving to preserve quantum adiabaticity which does not require knowledge of the explicit form of the counterdiabatic drivings, and can thus always be computed. We apply our analysis to systems ranging from a two-level Landau-Zener problem to many-body problems, namely, the quantum Ising and Lipkin-Meshkov-Glick models.
We propose and implement a comprehensive quantum compilation toolkit for solving the maximum independent set (MIS) problem on quantum hardware based on Rydberg atom arrays. Our end-to-end pipeline involves three core components to efficiently map generic MIS instances onto Rydberg arrays with unit-disk connectivity, with modules for graph reduction, hardware compatibility checks, and graph embedding. The first module (reducer) provides hardware-agnostic and deterministic reduction logic that iteratively reduces the problem size via lazy clique removals. We find that real-world networks can typically be reduced by orders of magnitude on subsecond timescales, thus significantly cutting down the eventual load for quantum devices. Moreover, we show that reduction techniques may be an important tool in the ongoing search for potential quantum speedups, given their ability to identify hard problem instances. In particular, for Rydberg-native MIS instances, we observe signatures of an easy-hard-easy transition and quantify a critical degree indicating the onset of a hard problem regime. The second module (compatibility checker) implements a hardware compatibility checker that quickly determines whether a given input graph may be compatible with the restrictions imposed by Rydberg quantum hardware. The third module (embedder) describes hardware-efficient graph embedding routines to generate (approximate) encodings with controllable overhead and optimized ancilla placements. We exemplify our pipeline with experiments run on the QuEra Aquila device available on Amazon Braket. In aggregate, our work provides a set of tools that extends the class of problems that can be tackled with near-term Rydberg atom arrays.
The digital version of adiabatic quantum computing enhanced by counterdiabatic driving, known as digitized counterdiabatic quantum computing, has emerged as a paradigm that opens the door to fast and low-depth algorithms. In this work, we explore the extension of this paradigm to high-dimensional systems. Specifically, we consider qutrits in the context of quadratic problems, obtaining the qutrit Hamiltonian codifications and the counterdiabatic drivings. Our findings show that qutrits can improve the solution quality up to 90 times compared to the qubit counterpart. We tested our proposal on 1000 random instances of the multiway number partitioning, max 3-cut, and portfolio optimization problems, demonstrating that, in general, without prior knowledge, it is better to use qutrits and, apparently, high-dimensional systems in general instead of qubits. Finally, considering the state-of-the-art quantum platforms, we show the experimental feasibility of our high-dimensional counterdiabatic quantum algorithms at least in a fully digital form. This work paves the way for the efficient codification of optimization problems in high-dimensional spaces and their efficient implementation using counterdiabatic quantum computing.
Rydberg atom quantum optimizers naturally encode the maximum independent set problem on geometric graphs. However, to solve general combinatorial optimization problems on more complex topologies, an embedding is required to overcome the limited-range native interactions. Such embeddings use gadgets, specific arrangements of atoms, which inevitably introduce ancillary atoms. Here, we show that this apparent overhead instead provides an intrinsic resource for error correction. Specifically, we demonstrate that the Parity Architecture-based Rydberg embedding naturally forms a classical error-correcting code, a principle that extends to other Rydberg blockade-based embeddings. Within superatom substructures, exact Rydberg-excitation-number constraints provide local error syndromes at no additional hardware cost and give rise to a strictly nonlinear code. To correct bit-flip errors, we introduce the precisely tailored Cluster decoder, which exploits these local constraints and the underlying gadget structure. Numerically, this approach achieves an error threshold of pth≳26% across different layout geometries. Experimentally, on the QuEra Aquila QPU, the Cluster decoder recovers exact optimization solutions with an average success rate of ≳8% for systems of up to 107 atoms, even when bare hardware and standard greedy post-processing find none. A Rydberg atom array embedding is therefore not merely a hardware mapping of an optimization problem, but a co-designed architecture for quantum optimization in which embedding, computation, and error correction emerge from the same physical structure.