Search

We study the quantum dynamics of the encoding scheme proposed in [Nguyen et al., PRX Quantum 4, 010316 (2023)], which encodes optimization problems on graphs with arbitrary connectivity into Rydberg atom arrays. Here, a graph vertex is represented by a wire of atoms, and the (crossing) crossing-with-edge gadget is placed at the intersection of two wires to (de)couple their degrees of freedom and reproduce the graph connectivity. We consider the fundamental geometry of two vertex-wires intersecting via a single gadget and look at minimum gap scaling with system size along adiabatic protocols. We find that both polynomial and exponential scaling are possible and, by means of perturbation theory, we relate the exponential closing of the minimum gap to an unfavorable localization of the ground-state wavefunction. Then, 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 possible strategies to avoid this quantum bottleneck, leading to an exponential improvement in the adiabatic performance.

We explore strategies aimed at reducing the amount of computation, both quantum and classical, required to run the Quantum Approximate Optimization Algorithm (QAOA). First, following Wurtz et al. [Phys.Rev A 104:052419], we consider the standard QAOA with instance-independent "tree" parameters chosen in advance. These tree parameters are chosen to optimize the MaxCut expectation for large girth graphs. We provide extensive numerical evidence supporting the performance guarantee for tree parameters conjectured in [Phys.Rev A 103:042612] and see that the approximation ratios obtained with tree parameters are typically well beyond the conjectured lower bounds, often comparable to performing a full optimization. This suggests that in practice, the QAOA can achieve near-optimal performance without the need for parameter optimization. Next, we modify the warm-start QAOA of Tate et al. [Quantum 7:1121]. The starting state for the QAOA is now an optimized product state associated with a solution of the Goemans-Williamson (GW) algorithm. Surprisingly, the tree parameters continue to perform well for the warm-start QAOA. We find that for random 3-regular graphs with hundreds of vertices, the expected cut obtained by the warm-start QAOA at depth $p \gtrsim 3$ is 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 at low depth without the need for parameter optimization. For each instance studied, we classically compute the expected size of the QAOA distribution of cuts; producing the actual cuts requires running on a quantum computer., Comment: 15 pages, 4 figures

Fast, reliable logical operations are essential for the realization of useful quantum computers, as they are required to implement practical quantum algorithms at large scale. By redundantly encoding logical qubits into many physical qubits and using syndrome measurements to detect and subsequently correct errors, one can achieve very low logical error rates. However, for most practical quantum error correcting (QEC) codes such as the surface code, it is generally believed that due to syndrome extraction errors, multiple extraction rounds -- on the order of the code distance d -- are required for fault-tolerant computation. Here, we show that contrary to this common belief, fault-tolerant logical operations can be performed with constant time overhead for a broad class of QEC codes, including the surface code with magic state inputs and feed-forward operations, to achieve "algorithmic fault tolerance". Through the combination of transversal operations and novel strategies for correlated decoding, despite only having access to partial syndrome information, we prove that the deviation from the ideal measurement result distribution can be made exponentially small in the code distance. We supplement this proof with circuit-level simulations in a range of relevant settings, demonstrating the fault tolerance and competitive performance of our approach. Our work sheds new light on the theory of fault tolerance, potentially reducing the space-time cost of practical fault-tolerant quantum computation by orders of magnitude.

The ability to efficiently prepare ground states of quantum Hamiltonians via adiabatic protocols is typically limited by the smallest energy gap encountered during the quantum evolution. This presents a key obstacle for quantum simulation and realizations of adiabatic quantum algorithms in large systems, particularly when the adiabatic gap vanishes exponentially with system size. Using QuEra's Aquila programmable quantum simulator based on Rydberg atom arrays, we experimentally demonstrate a method to circumvent such limitations. Specifically, we develop and test a "sweep-quench-sweep" quantum algorithm in which the incorporation of a quench step serves as a remedy to the diverging adiabatic timescale. These quenches introduce a macroscopic reconfiguration between states separated by an extensively large Hamming distance, akin to quantum many-body scars. Our experiments show that this approach significantly outperforms the adiabatic algorithm, illustrating that such quantum quench algorithms can provide a shortcut to adiabaticity for large-scale many-body quantum systems.

Realizing computationally complex quantum circuits in the presence of noise and imperfections is a challenging task. While fault-tolerant quantum computing provides a route to reducing noise, it requires a large overhead for generic algorithms. Here, we develop and analyze a hardware-efficient, fault-tolerant approach to realizing complex sampling circuits. We co-design the circuits with the appropriate quantum error correcting codes for efficient implementation in a reconfigurable neutral atom array architecture, constituting what we call a fault-tolerant compilation of the sampling algorithm. Specifically, we consider a family of $[[2^D , D, 2]]$ quantum error detecting codes whose transversal and permutation gate set can realize arbitrary degree-$D$ instantaneous quantum polynomial (IQP) circuits. Using native operations of the code and the atom array hardware, we compile a fault-tolerant and fast-scrambling family of such IQP circuits in a hypercube geometry, realized recently in the experiments by Bluvstein et al. [Nature 626, 7997 (2024)]. We develop a theory of second-moment properties of degree-$D$ IQP circuits for analyzing hardness and verification of random sampling by mapping to a statistical mechanics model. We provide evidence that sampling from hypercube IQP circuits is classically hard to simulate and analyze the linear cross-entropy benchmark (XEB) in comparison to the average fidelity. To realize a fully scalable approach, we first show that Bell sampling from degree-$4$ IQP circuits is classically intractable and can be efficiently validated. We further devise new families of $[[O(d^D),D,d]]$ color codes of increasing distance $d$, permitting exponential error suppression for transversal IQP sampling. Our results highlight fault-tolerant compiling as a powerful tool in co-designing algorithms with specific error-correcting codes and realistic hardware., Comment: 27 + 20 pages, 13 Figures

Quantum error correction is believed to be essential for scalable quantum computation, but its implementation is challenging due to its considerable space-time overhead. Motivated by recent experiments demonstrating efficient manipulation of logical qubits using transversal gates (Bluvstein et al., Nature 626, 58-65 (2024)), we show that the performance of logical algorithms can be substantially improved by decoding the qubits jointly to account for physical error propagation during transversal entangling gates. We find that such correlated decoding improves the performance of both Clifford and non-Clifford transversal entangling gates, and explore two decoders offering different computational runtimes and accuracies. By considering deep logical Clifford circuits, we find that correlated decoding can significantly improve the space-time cost by reducing the number of rounds of noisy syndrome extraction per gate. These results demonstrate that correlated decoding provides a major advantage in early fault-tolerant computation, and indicate it has considerable potential to reduce the space-time cost in large-scale logical algorithms., Comment: 7+12 pages, 5+3 figures

Suppressing errors is the central challenge for useful quantum computing, requiring quantum error correction for large-scale processing. However, the overhead in the realization of error-corrected ``logical'' qubits, where information is encoded across many physical qubits for redundancy, poses significant challenges to large-scale logical quantum computing. Here we report the realization of a programmable quantum processor based on encoded logical qubits operating with up to 280 physical qubits. Utilizing logical-level control and a zoned architecture in reconfigurable neutral atom arrays, our system combines high two-qubit gate fidelities, arbitrary connectivity, as well as fully programmable single-qubit rotations and mid-circuit readout. Operating this logical processor with various types of encodings, we demonstrate improvement of a two-qubit logic gate by scaling surface code distance from d=3 to d=7, preparation of color code qubits with break-even fidelities, fault-tolerant creation of logical GHZ states and feedforward entanglement teleportation, as well as operation of 40 color code qubits. Finally, using three-dimensional [[8,3,2]] code blocks, we realize computationally complex sampling circuits with up to 48 logical qubits entangled with hypercube connectivity with 228 logical two-qubit gates and 48 logical CCZ gates. We find that this logical encoding substantially improves algorithmic performance with error detection, outperforming physical qubit fidelities at both cross-entropy benchmarking and quantum simulations of fast scrambling. These results herald the advent of early error-corrected quantum computation and chart a path toward large-scale logical processors., Comment: See ancillary files: five supplementary movies and captions. Main text + Methods

Classical optimization problems can be solved by adiabatically preparing the ground state of a quantum Hamiltonian that encodes the problem. The performance of this approach is determined by the smallest gap encountered during the evolution. Here, we consider the maximum independent set problem, which can be efficiently encoded in the Hamiltonian describing a Rydberg atom array. We present a general construction of instances of the problem for which the minimum gap decays superexponentially with system size, implying a superexponentially large time to solution via adiabatic evolution. The small gap arises from locally independent choices, which cause the system to initially evolve and localize into a configuration far from the solution in terms of Hamming distance. We investigate remedies to this problem. Specifically, we show that quantum quenches in these models can exhibit signatures of quantum many-body scars, which in turn, can circumvent the superexponential gaps. By quenching from a suboptimal configuration, states with a larger ground state overlap can be prepared, illustrating the utility of quantum quenches as an algorithmic tool., Comment: 12+3 pages, 8+4 figures, comments welcome

Designing quantum algorithms with a speedup over their classical analogs is a central challenge in quantum information science. Motivated by recent experimental observations of a superlinear quantum speedup in solving the Maximum Independent Set problem on certain unit-disk graph instances [Ebadi et al., Science 376, 6598 (2022)], we develop a theoretical framework to analyze the relative performance of the optimized quantum adiabatic algorithm and a broad class of classical Markov chain Monte Carlo algorithms. We outline conditions for the quantum adiabatic algorithm to achieve a quadratic speedup on hard problem instances featuring flat low-energy landscapes and provide example instances with either a quantum speedup or slowdown. We then introduce an additional local Hamiltonian with no sign problem to the optimized adiabatic algorithm to achieve a quadratic speedup over a wide class of classical simulated annealing, parallel tempering, and quantum Monte Carlo algorithms in solving these hard problem instances. Finally, we use this framework to analyze the experimental observations., Comment: 9+27 pages, 5+8 figures

The Quantum Approximate Optimization Algorithm (QAOA) is designed to maximize a cost function over bit strings. While the initial state is traditionally a uniform superposition over all strings, it is natural to try expediting the QAOA: first use a classical algorithm to produce some good string, and then run the standard QAOA starting in the computational basis state associated with that string. Here we report numerical experiments that show this method of initializing the QAOA fails dramatically, exhibiting little to no improvement of the cost function. We provide multiple analytical arguments for this lack of improvement, each of which can be made rigorous under different regimes or assumptions, including at nearly linear depths. We emphasize that our negative results only apply to our simple incarnation of the warm-start QAOA and may not apply to other approaches in the literature. We hope that our theoretical analysis will inform future algorithm design., Comment: 31 pages, 1 figure, 7 tables

We introduce a unified framework to compute the solution space properties of a broad class of combinatorial optimization problems. These properties include finding one of the optimum solutions, counting the number of solutions of a given size, and enumeration and sampling of solutions of a given size. Using the independent set problem as an example, we show how all these solution space properties can be computed in the unified approach of generic tensor networks. We demonstrate the versatility of this computational tool by applying it to several examples, including computing the entropy constant for hardcore lattice gases, studying the overlap gap properties, and analyzing the performance of quantum and classical algorithms for finding maximum independent sets., Comment: Github repo: https://github.com/QuEraComputing/GenericTensorNetworks.jl

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., Comment: 10 pages, 5 figures, Supplementary materials at the end

We report the discovery of J1521-3538, a bright (V=12.2), very metal-poor ([Fe/H]=-2.8) strongly r-process enhanced field horizontal branch star, based on a high-resolution, high signal-to-noise Magellan/MIKE spectrum. J1521-3538 shows the largest r-process element over-abundance in any known r-process-enhanced star, with [Eu/Fe]=+2.2, and its chemical abundances of 22 neutron-capture elements closely match the scaled solar r-process pattern. J1521-3538 is also one of few known carbon-enhanced metal-poor stars with r-process enhancement (CEMP-r stars), as found after correcting the measured C abundance for the star's evolutionary status. We propose to extend the existing classification of moderately enhanced (+0.3<=[Eu/Fe]<=+1.0) r-I and strongly r-process enhanced ([Eu/Fe]>+1.0) r-II stars to include an r-III class, for r-process stars such as J1521-3538, with [Eu/Fe]>+2.0 and [Ba/Eu]<-0.5, or >100 times the solar ratio of europium to iron. Using cosmochronometry, we estimate J1521-3538 to be 12.5+-5 Gyr and 8.9+-5 Gyr old, using two different sets of initial production ratios. These ages are based on measurements of the Th line at 4019 A and other r-process element abundances. This is broadly consistent with the old age of a low-mass metal-poor field red horizontal branch star. J1521-3538 likely originated in a low-mass dwarf galaxy that was later accreted by the Milky Way, as evidenced by its highly eccentric orbit., Comment: 24 pages, includes a long table, 4 figures

We present detailed chemical abundances of three new bright (V ~ 11), extremely metal-poor ([Fe/H] ~ -3.0), r-process-enhanced halo red giants based on high-resolution, high-S/N Magellan/MIKE spectra. We measured abundances for 20-25 neutron-capture elements in each of our stars. J1432-4125 is among the most r-process rich r-II stars, with [Eu/Fe]= +1.44+-0.11. J2005-3057 is an r-I star with [Eu/Fe] = +0.94+-0.07. J0858-0809 has [Eu/Fe] = +0.23+-0.05 and exhibits a carbon abundance corrected for evolutionary status of [C/Fe]_corr = +0.76, thus adding to the small number of known carbon-enhanced r-process stars. All three stars show remarkable agreement with the scaled solar r-process pattern for elements above Ba, consistent with enrichment of the birth gas cloud by a neutron star merger. The abundances for Sr, Y, and Zr, however, deviate from the scaled solar pattern. This indicates that more than one distinct r-process site might be responsible for the observed neutron-capture element abundance pattern. Thorium was detected in J1432-4125 and J2005-3057. Age estimates for J1432-4125 and J2005-3057 were adopted from one of two sets of initial production ratios each by assuming the stars are old. This yielded individual ages of 12+-6 Gyr and 10+-6 Gyr, respectively., Comment: 30 pages, includes a long table, 5 figures

We present a high-resolution (R~35,000), high signal-to-noise (S/N>200) Magellan/MIKE spectrum of the star RAVE J094921.8-161722, a bright (V=11.3) metal-poor red giant star with [Fe/H] = -2.2, identified as a carbon-enhanced metal-poor (CEMP) star from the RAVE survey. We report its detailed chemical abundance signature of light fusion elements and heavy neutron-capture elements. We find J0949-1617 to be a CEMP star with s-process enhancement that must have formed from gas enriched by a prior r-process event. Light neutron-capture elements follow a low-metallicity s-process pattern, while the heavier neutron-capture elements above Eu follow an r-process pattern. The Pb abundance is high, in line with an s-process origin. Thorium is also detected, as expected from an r-process origin, as Th is not produced in the s-process. We employ nucleosynthesis model predictions that take an initial r-process enhancement into account, and then determine the mass transfer of carbon and s-process material from a putative more massive companion onto the observed star. The resulting abundances agree well with the observed pattern. We conclude that J0949-1617 is the first bonafide CEMP-r+s star identified. This class of objects has previously been suggested to explain stars with neutron-capture element patterns that originate from neither the r- or s-process alone. We speculate that J0949-1617 formed in an environment similar to those of ultra-faint dwarf galaxies like Tucana III and Reticulum II, which were enriched in r-process elements by one or multiple neutron star mergers at the earliest times.a, Comment: accepted for publication in ApJ