skip to main content

This content will become publicly available on May 5, 2023

Title: Quantum optimization of maximum independent set using Rydberg atom arrays
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.
Authors:
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; more » ; ; ; ; « less
Award ID(s):
1734011
Publication Date:
NSF-PAR ID:
10326834
Journal Name:
Science
ISSN:
0036-8075
Sponsoring Org:
National Science Foundation
More Like this
  1. Triangle enumeration is a fundamental problem in large-scale graph analysis. For instance, triangles are used to solve practical problems like community detection and spam filtering. On the other hand, there is a large amount of data stored on database management systems (DBMSs), which can be modeled and analyzed as graphs. Alternatively, graph data can be quickly loaded into a DBMS. Our paper shows how to adapt and optimize a randomized distributed triangle enumeration algorithm with SQL queries, which is a significantly different approach from programming graph algorithms in traditional languages such as Python or C++. We choose a parallel columnarmore »DBMS given its fast query processing, but our solution should work for a row DBMS as well. Our randomized solution provides a balanced workload for parallel query processing, being robust to the existence of skewed degree vertices. We experimentally prove our solution ensures a balanced data distribution, and hence workload, among machines. The key idea behind the algorithm is to evenly partition all possible triplets of vertices among machines, sending edges that may form a triangle to a proxy machine; this edge redistribution eliminates shuffling edges during join computation and therefore triangle enumeration becomes local and fully parallel. In summary, our algorithm exhibits linear speedup with large graphs, including graphs that have high skewness in vertex degree distributions.« less
  2. Estimation of Shannon and Rényi entropies of unknown discrete distributions is a fundamental problem in statistical property testing. In this paper, we give the first quantum algorithms for estimating α-Rényi entropies (Shannon entropy being 1-Rényi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for α-Rényi entropy estimation for all α ≥ 0, including tight bounds for the Shannon entropy, the Hartley entropy (α = 0), and the collision entropy (α = 2). We also provide quantum upper bounds for estimating min-entropy (α = +∞) as well as the Kullback-Leibler divergence.more »We complement our results with quantum lower bounds on α- Rényi entropy estimation for all α ≥ 0. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH) [1], however, with many new technical ingredients: (1) we improve the error dependence of the BHH framework by a fine-tuned error analysis together with Montanaro’s approach to estimating the expected output of quantum subroutines [2] for α = 0, 1; (2) we develop a procedure, similar to cooling schedules in simulated annealing, for general α ≥ 0; (3) in the cases of integer α ≥ 2 and α = +∞, we reduce the entropy estimation problem to the α-distinctness and the ⌈log n⌉-distinctness problems, respectively.« less
  3. The molecules 1,4-cyclohexadiene (unconjugated 1,4-CHD) and 1,3-cyclohexadiene (conjugated 1,3-CHD) both have two double bonds, but these bonds interact in different ways. These molecules have long served as examples of through-bond and through-space interactions, respectively, and their electronic structures have been studied in detail both experimentally and theoretically, with the experimental assignments being especially complete. The existence of Rydberg states interspersed with the valence states makes the quantum mechanical calculation of their spectra a challenging task. In this work, we explore the electronic excitation energies of 1,4-CHD and 1,3-CHD for both valence and Rydberg states by means of complete active spacemore »second-order perturbation theory (CASPT2), extended multi-state CASPT2 (XMS-CASPT2), and multiconfiguration pair-density functional theory (MC-PDFT); it is shown by comparison to experiment that MC-PDFT yields the most accurate results. We found that the inclusion of Rydberg orbitals in the active space not only enables the calculation of Rydberg excitation energies but also improves the accuracy of the valence ones. A special characteristic of the present analysis is the calculation of the second moments of the excited-state orbitals. Because we find that the CASPT2 densities agree well with the CASSCF ones and since the MC-PDFT methods gets accurate excitation energies based on the CASSCF densities, we believe that we can trust these moments as far as giving a more accurate picture of the diffuseness of the excited-state orbitals in these prototype molecules than has previously been available.« less
  4. The condensation of half-light half-matter exciton polaritons in semiconductor optical cavities is a striking example of macroscopic quantum coherence in a solid-state platform. Quantum coherence is possible only when there are strong interactions between the exciton polaritons provided by their excitonic constituents. Rydberg excitons with high principal value exhibit strong dipole–dipole interactions in cold atoms. However, polaritons with the excitonic constituent that is an excited state, namely Rydberg exciton polaritons (REPs), have not yet been experimentally observed. Here, we observe the formation of REPs in a single crystal CsPbBr 3 perovskite cavity without any external fields. These polaritons exhibit strongmore »nonlinear behavior that leads to a coherent polariton condensate with a prominent blue shift. Furthermore, the REPs in CsPbBr 3 are highly anisotropic and have a large extinction ratio, arising from the perovskite’s orthorhombic crystal structure. Our observation not only sheds light on the importance of many-body physics in coherent polariton systems involving higher-order excited states, but also paves the way for exploring these coherent interactions for solid-state quantum optical information processing.« less
  5. We address the problem of scaling up local-search or sampling-based inference in Markov logic networks (MLNs) that have large shared sub-structures but no (or few) tied weights. Such untied MLNs are ubiquitous in practical applications. However, they have very few symmetries, and as a result lifted inference algorithms--the dominant approach for scaling up inference--perform poorly on them. The key idea in our approach is to reduce the hard, time-consuming sub-task in sampling algorithms, computing the sum of weights of features that satisfy a full assignment, to the problem of computing a set of partition functions of graphical models, each definedmore »over the logical variables in a first-order formula. The importance of this reduction is that when the treewidth of all the graphical models is small, it yields an order of magnitude speedup. When the treewidth is large, we propose an over-symmetric approximation and experimentally demonstrate that it is both fast and accurate.« less