We propose a numerical approach to design highly efficient adiabatic schedules for analog quantum computing, focusing on the maximum-independent-set problem and neutral atom platforms. On the basis of a representative dataset of small graphs, we present numerical evidence that the optimum schedules depend principally on the hardness of the problem rather than on its size. These schedules perform better than the benchmark protocols and admit a straightforward implementation in the hardware. This allows us to extrapolate the results to larger graphs and to successfully solve moderately hard problems using QuEra’s 256-qubit Aquila computer. We believe that extending our approach to hybrid algorithms could be the key to solving the hardest instances with the current technology, making yet another step toward real-world applications.
We propose a numerical approach to design highly efficient adiabatic schedules for analog quantum computing, focusing on the maximum-independent-set problem and neutral atom platforms. On the basis of a representative dataset of small graphs, we present numerical evidence that the optimum schedules depend principally on the hardness of the problem rather than on its size. These schedules perform better than the benchmark protocols and admit a straightforward implementation in the hardware. This allows us to extrapolate the results to larger graphs and to successfully solve moderately hard problems using QuEra’s 256-qubit Aquila computer. We believe that extending our approach to hybrid algorithms could be the key to solving the hardest instances with the current technology, making yet another step toward real-world applications.
The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.
We used an analog neutral atom quantum computer, known as Aquila to solve the maximum independent set problem for a given graph through the Rydberg blockade effect. Aquila, developed by QuEra, is a 256-qubit analog quantum computer designed to operate at room temperature, employing neutral rubidium-87 atoms as its basis for qubit construction. It offers the flexibility to design qubit topologies and dynamically control the physical properties of individual qubits to simulate various quantum systems. By accessing Aquila through the Amazon Braket service, experiments are conducted to determine the maximum independent sets of various king’s graphs. The experimental results were analyzed. Suggestions were given for future research directions in the field of analog neutral atom quantum computers.
In recent years, neutral atom-based quantum computation has been established as a competing alternative for the realization of fault-tolerant quantum computation. However, as with other quantum technologies, various sources of noise limit their performance. With processors continuing to scale up, new techniques are needed to characterize and compare them in order to track their progress. In this work, we present two systematic benchmarks that evaluate these quantum processors at scale. We use the quantum adiabatic algorithm (QAA) and the quantum approximate optimization algorithm (QAOA) to solve maximal independent set (MIS) instances of random unit-disk graphs. These benchmarks are scalable, relying not on prior knowledge of the system's evolution but on the quality of the MIS solutions obtained. Rather than isolating individual sources of noise, they provide an application-level figure of merit: improvements in a QPU and its implementation of the protocols should be reflected in higher-quality MIS solutions. We benchmark quera_aquila and pasqal_fresnel on problem sizes up to 102 and 85 qubits, respectively. Overall, quera_aquila performs better on QAOA and QAA instances. Finally, we generate MIS instances of up to 1000 qubits, providing scalable benchmarks for evaluating future, larger processors as they become available. The proposed protocols can therefore serve as a common reference for comparisons, allowing future work to assess whether advances in hardware translate into measurable improvements in MIS solution quality.
Harnessing the analog capacity of quantum processors at the algorithmic level is key to solving computationally hard problems. Neutral atoms offer analog capabilities supporting hundreds of qubits, but state-of-the-art adiabatic protocol struggles with nonadiabatic errors, restricting scalability due to finite coherence times. To address this, we propose and experimentally demonstrate a tailored analog counterdiabatic quantum computing (ACQC) protocol to enhance the computational capabilities of neutral atoms by mitigating non-adiabatic transitions and facilitating rapid and high-quality solutions. We apply it to solve the maximum independent set problem with up to 100 qubits, achieving over 3-fold speedup in convergence time and solution quality within a short evolution time of the processor, as compared to adiabatic method. Our method shows scalibility of the application of neutral atom processors establishing ACQC as a promising pathway toward quantum advantage for real-world industrial applications.
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 on unit-disk graphs with a broader range of classical solvers beyond the scope of the original paper. 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.
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.