A large ongoing research effort focuses on obtaining a quantum advantage in the solution of combinatorial optimization problems on near-term quantum devices. A particularly promising platform implementing quantum optimization algorithms are arrays of trapped neutral atoms, laser coupled to highly excited Rydberg states. However, encoding combinatorial optimization problems in atomic arrays is challenging due to limited interqubit connectivity of the native finite-range interactions. Here, we present a four-body Rydberg parity gate, enabling a direct and straightforward implementation of the parity architecture, a scalable architecture for encoding arbitrarily connected interaction graphs. Our gate relies on adiabatic laser pulses and is fully programmable by adjusting two hold times during operation. We numerically demonstrate implementations of the quantum approximate optimization algorithm (QAOA) for small-scale test problems. Variational optimization steps can be implemented with a constant number of system manipulations, paving the way for experimental investigations of QAOA beyond the reach of numerical simulations.
A large ongoing research effort focuses on obtaining a quantum advantage in the solution of combinatorial optimization problems on near-term quantum devices. A particularly promising platform implementing quantum optimization algorithms are arrays of trapped neutral atoms, laser coupled to highly excited Rydberg states. However, encoding combinatorial optimization problems in atomic arrays is challenging due to limited interqubit connectivity of the native finite-range interactions. Here, we present a four-body Rydberg parity gate, enabling a direct and straightforward implementation of the parity architecture, a scalable architecture for encoding arbitrarily connected interaction graphs. Our gate relies on adiabatic laser pulses and is fully programmable by adjusting two hold times during operation. We numerically demonstrate implementations of the quantum approximate optimization algorithm (QAOA) for small-scale test problems. Variational optimization steps can be implemented with a constant number of system manipulations, paving the way for experimental investigations of QAOA beyond the reach of numerical simulations.
Arrays of identical neutral atoms trapped in optical tweezers are a promising candidate for use in quantum computing. These platforms are highly scalable to large numbers of qubits and neutral atoms boost several attractive features as long coherence times and the possibility to be entangled via strong dipole-dipole interactions by driving them to highly excited Rydberg states. \nThe Thesis work is developed inside the framework of the QRydDemo project, whose aim in the next few years is to realize a neutral atom quantum processor with several hundred qubits. The smallest building blocks for the quantum computer are one and two-qubit gates: to entangle two atoms in the quantum register, a controlled-phase (CZ) gate will be implemented by shining fine-tuned laser pulses onto them. In this work, after giving a theoretical description of the Hamiltonian of two neutral atoms in the quantum register, a numerical simulation of this system is exploited to reproduce the behavior of the two-qubit CZ gate. Realistic effects are taken into account as finite temperature, imperfect Rydberg blockade, or decay out of the Rydberg state. A protocol with constant pulses is analyzed and its optimal parameters are found through classical optimizers. Then, time-dependent pulses are introduced and the optimal pulses are found through the optimal control algorithm dCRAB in an open-loop optimization. For the experimental realization of the gate, this analysis is of pivotal importance to know in which aspect more effort has to be put to maximize the experimental precision of the operation and thus improving the performance of the whole device \n
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.
Programmable quantum systems based on Rydberg atom arrays have recently been used for hardwareefficient tests of quantum optimization algorithms [Ebadi et al., Science, 376, 1209 (2022)] with hundreds of qubits.In particular, the maximum independent set problem on so-called unit-disk graphs, was shown to be efficiently encodable in such a quantum system.Here, we extend the classes of problems that can be efficiently encoded in Rydberg arrays by constructing explicit mappings from a wide class of problems to maximum-weighted independent set problems on unit-disk graphs, with at most a quadratic overhead in the number of qubits.We analyze several examples, including maximum-weighted independent set on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization.Numerical simulations on small system sizes indicate that the adiabatic time scale for solving the mapped problems is strongly correlated with that of the original problems.Our work provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems with arbitrary connectivity, beyond the restrictions imposed by the hardware geometry.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.
Programmable quantum systems provide insights into many-body quantum phenomena and enable new methods for computation and metrology. The frontier challenge for these systems is scaling up in the number of quantum particles while retaining a high degree of quantum control. In recent years arrays of neutral atoms have emerged as a scalable and powerful platform for tackling these challenges, thanks to their large number of qubits, flexible geometry, and a well-established toolbox for preparation, detection, coherent control. At the forefront of quantum science and engineering, these systems have been used for quantum simulation of various spin models and have also demonstrated building blocks of quantum computation. In this thesis I will present advances in development of large two-dimensional atom arrays, where hundreds of individual atoms are trapped, rearranged, and initialized in various defect-free arrangements in one or two dimensions. Afterwards, interactions between atoms is controlled via coherent excitation to highly excited Rydberg states, resulting in strong long-range van der Waals forces. We utilize these interaction for quantum simulation of many-body spin Hamiltonians by demonstrating preparation of several exotic phases of matter, study phase transitions, and probe non-equilibrium dynamics. Further, we study the quantum speedup in solving a hard combinatorial optimization problem via efficiently mapping the problem onto the Rydberg atom array. We also utilize Rydberg interactions to demonstrate high-fidelity two-qubit gate operations in a reconfigurable atom array architecture. Lastly I will demonstrate recent technical improvements that have enabled larger system sizes, higher fidelity rydberg excitations, and local control of individual atoms, paving the way for novel approaches for studying quantum many-body phenomena.
Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems. Here we present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms, which we call quantum wires, to natively embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture. For graphs with quasi-unit-disk connectivity, in which only a few long-range edges are required, our approach requires a significantly lower overhead in the number of ancilla qubits than previous proposals, facilitating the implementation on currently available hardware. To demonstrate the approach, we perform annealing of weighted graphs on a programmable atom array using local light shifts to encode problem-specific weights across graphs of varying sizes. This approach successfully identifies the solutions to the original MWIS and QUBO graph instances. Our work expands the operational toolkit of near-term neutral atom arrays, enhancing their potential for scalable quantum optimization.