Pith. sign in

REVIEW 3 major objections 4 minor 86 references

Quantum Compilation Toolkit for Rydberg Atom Arrays with Implications for Problem Hardness and Quantum Speedups

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that a three-module pipeline—deterministic graph reduction, a hardware compatibility check, and hardware-efficient embedding—can map generic maximum independent set problems onto unit-disk Rydberg atom arrays in sizes…

desk verdict Solid compilation pipeline with a strong reduction module; the optimized top-down embedder's exactness is asserted, not proven, and that needs fixing before the central claim stands. read the letter →

arxiv 2412.14976 v2 pith:2BKWEJK2 submitted 2024-12-19 quant-ph cond-mat.dis-nncond-mat.quant-gasphysics.atom-ph

Martin J. A. Schuetz , Ruben S. Andrist , Grant Salton , Romina Yalovetzky , Rudy Raymond , Yue Sun , Atithi Acharya , Shouvanik Chakrabarti
show 2 more authors
Marco Pistoia Helmut G. Katzgraber
This is my paper · ORCID
classification quant-phcond-mat.dis-nncond-mat.quant-gasphysics.atom-ph
keywords maximumindependentsetRydbergatomarraysunit-diskgraphsgraphkernelizationreductionembeddingquantumcompilationeasy-hard-easytransition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's aim is to widen the class of maximum independent set (MIS) problems that near-term Rydberg atom arrays can tackle, beyond the geometric unit-disk instances the hardware natively encodes. It proposes an end-to-end compilation pipeline with three modules: a reducer that strips provably safe subgraphs via isolated clique removal, a checker that flags graphs needing ancilla overhead, and embedders that place atoms on a lattice while preserving the MIS answer. The demonstration cases are large real-world networks: the Cora citation graph shrinks from about 2700 nodes to a 79-node core whose largest component has nine nodes, on sub-second laptop timescales. The same reduction tool, applied to Rydberg-native random instances, reveals an easy-hard-easy transition with a critical average degree near six, which the authors offer as a way to identify instances where quantum speedups are more likely to matter. If the pipeline works as claimed, generic MIS workloads—not just native unit-disk ones—become accessible to analog quantum hardware after classical preprocessing.

What carries the argument

Two mechanisms carry the argument. The first is isolated clique removal, a kernelization rule that recursively finds simplicial (corner) vertices and removes them with their neighborhood; because a corner vertex can always replace any other selected vertex of its clique without changing the independent set size, the reduction is provably optimal and can shrink graphs by orders of magnitude. The second is the Rydberg gadget construction of Ref. [41], where each logical variable is spread over an odd-length chain of atoms and chain crossings are decorated with interacting or non-interacting gadgets; ground states of the resulting unit-disk graph correspond one-to-one with ground states of the logical MIS problem. The top-down embedder's four overhead-reducing moves—reordering chain endpoints, shortening chains, replacing end gadgets with direct terminal interactions, and rewiring via biased breadth-first search—all work within this gadget language, and the paper's overhead reduction from about $4n^2$ to about $1.45n^2$ qubits is the quantitative payoff of preserving that correspondence with fewer gadgets.

What would settle it

Run the top-down embedder with each of the four modifications in isolation on every graph with up to six nodes, then compare the independence number and the set of logical assignments induced by the ground states of the embedded physical Hamiltonian with the logical MIS ground states by exhaustive enumeration. Any mismatch—for example, an embedded graph whose optimal independent sets contain an atom-chain pattern that decodes to a non-maximal logical set—would falsify exactness. A faster targeted test is to check, on a few hundred random annealing moves of the rewiring stage, that every accepted move preserves chain parity and minimum spacing between interacting qubits.

Watch

Extended reading notes

Core claim

The central claim is that generic, potentially large-scale MIS instances on arbitrary graphs can be mapped to smaller MIS instances on unit-disk graphs that Rydberg arrays implement natively, while preserving optimality. The reducer's isolated-clique-removal rule selects exposed corner nodes—vertices whose neighbors form a clique—adds them to the independent set, and deletes them together with their neighborhood; a cut-and-paste argument shows each such node is in some maximum independent set, so kernel solutions lift exactly to original solutions. The compatibility checker gives a necessary condition for native embeddability based on maximum degree and triangle counts under Union-Jack connectivity. The bottom-up embedder learns atom placements by minimizing graph edit distance with a random-key optimizer and refines them with ancilla quantum wires placed by constrained shortest-path search, while the top-down embedder builds on the generic exact embedding scheme of Ref. [41], reordering, shortening, terminating, and rewiring atom chains to reduce qubit count while keeping the ground-state correspondence. The paper reports a hardware run on a 256-qubit Rydberg device for the largest component of the reduced Cora graph, where an eight-atom quantum wire enforces the one missing edge and the MIS solution found on hardware matches noise-free simulation.

Load-bearing premise

The load-bearing premise is that the top-down embedder's four shortcut moves—reordering chain endpoints, shortening chains, terminal interactions without gadgets, and biased-BFS rewiring—always preserve the exact match between ground states of the logical graph and ground states of the embedded unit-disk graph, with correctness inherited rather than re-proved for each move.

Editorial extensions

If this is right

  • Real-world MIS instances such as citation networks can be solved after reduction in sub-second laptop time, with some instances (Florentine, Les Miserables) reduced completely to the null graph, meaning the reducer alone acts as an exact solver.
  • For the tested sparse residual graphs, the optimized top-down embedding reduces the qubit overhead prefactor from about $3.99n^2$ to about $1.45n^2$, so a hypothetical 1000-qubit device can embed logical instances up to roughly $n=27$ nodes rather than $n=15$.
  • Rydberg-native random instances near filling fraction $\sim 0.8$ show a large spread in reduction with a critical average degree near six, giving a tunable knob for generating hard kernels where quantum speedups would be sought.
  • Combining the reducer with downstream solvers changes exponential run time from roughly $2^{\alpha n}$ to $2^{\tilde{\alpha} n}$ with $\tilde{\alpha}=(1-\xi)\alpha$, so a 50 percent reduction yields about a quadratic speedup for exact solvers.
  • The pipeline is modular: the reducer can be paired with the generic embedding of Ref. [41], and the checker's local node-level flags can guide where ancilla roll-outs are needed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the easy-hard-easy crossover at average degree near six suggests a practical recipe for benchmark construction—sample hard instances just above the critical density and keep only those that survive reduction—so future speedup claims can be reported against the kernel size rather than the original instance size.
  • Editorial inference: because the top-down embedder's four modifications are asserted rather than individually proved to preserve the logical-to-physical ground-state correspondence, a certified version would verify parity and spacing after every accepted annealing move, which is straightforward to automate for graphs up to a few dozen nodes.
  • Editorial inference: the reported reduction factors transfer directly to other NP-hard graph problems with similar local structure, such as MaxCut or graph coloring on power-law networks, where dangling bonds can be removed and labeled in post-processing using the same corner-node logic.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes and implements an end-to-end compilation pipeline for solving maximum independent set (MIS) problems on Rydberg atom arrays with unit-disk connectivity. The pipeline has three modules: a deterministic clique-based graph reducer that removes exposed corner nodes while preserving the optimal MIS value; a hardware compatibility checker that flags, with a necessary-but-not-sufficient condition, whether a graph can be natively embedded in a Union-Jack-type Rydberg layout; and two embedders, a bottom-up approximate embedder based on random-key optimization and a top-down embedder based on the gadget construction of Ref. [41] with additional overhead-reducing optimizations. The authors demonstrate the reducer on random and real-world graphs, observe an easy-hard-easy crossover in the reduction factor, quantify embedding overhead as roughly 1.45n^2 for a family of reduced Erdős–Rényi graphs, and run a small end-to-end demonstration on the Cora citation graph using QuEra Aquila hardware.

Significance. If the central claims hold, the paper provides a practically useful toolkit that substantially widens the class of MIS instances that can be approached with near-term Rydberg devices. The reducer is a clean, provably optimality-preserving implementation of isolated clique removal, and the paper correctly labels the compatibility checker as necessary-but-not-sufficient. The easy-hard-easy observations are interesting heuristics for selecting instances for future quantum experiments. The most significant quantitative claim, however, is the near-threefold reduction in embedding overhead (from about 4n^2 to about 1.45n^2) while retaining exactness of the logical-to-physical ground-state correspondence. That claim is currently supported more by informal assertion than by proof or automated verification, and it is load-bearing for the stated goal of mapping generic MIS instances to native Rydberg MIS problems.

major comments (3)
  1. [Sec. IV.C.2, "Overhead reduction" and "Embedding algorithm"] The paper repeatedly states that the optimized top-down embedding provides an "exact one-to-one correspondence between the ground states of the logical and embedded graphs" and that the top-down scheme gives "exact embeddings with MIS optimality guarantees." However, the four overhead-reducing modifications are justified only informally, with the final modification invoking "provided that parity and spacing requirements are observed." No invariant or proof is given that the simulated-annealing/BFS rewiring maintains the copy-gadget encoding from Ref. [41] for every accepted move. In particular, Modification 3 places a chain's terminal qubit next to an odd-numbered qubit of another chain; if that terminal also falls within the blockade radius of a third chain, a spurious edge is created and the ground-state correspondence is lost. Because this exactness is the load-bearing component of the paper's central claim, the authors should provide a correctness lemma (or a formal reduction to the gadget theorem of Ref. [41]) for the optimized placement, or clearly relabel the optimized top-down embedder as heuristic and revise the corresponding claims.
  2. [Sec. VI.C, Fig. 16] The overhead scaling N_qubits ≈ 1.45(2)n^2 is reported for 250 reduced Erdős–Rényi graphs, but the paper does not describe any verification that the optimized embeddings counted in this experiment are actually valid, i.e., that they contain no spurious Rydberg edges, satisfy the required parity conditions, and preserve the logical-to-physical ground-state correspondence. If some of the counted embeddings are invalid, the fitted prefactor does not represent the qubit cost of correct embeddings and the comparison with the generic 3.99(1)n^2 scheme is not meaningful. Please report a validation procedure, the fraction of instances for which correctness can be certified, and, if necessary, exclude or flag failures.
  3. [Sec. V, Figs. 13 and 15] The "easy-hard-easy" transition and the "critical average degree" are extracted from the reduction factor ξ alone. The paper does hedge this as a "signature" and notes that the existence of a phase transition was not determined, which is commendable. Nevertheless, the surrounding text draws stronger conclusions, such as "allows to tune problem hardness" and the claim that instances with large kernel are the ones where quantum speedups are more likely. The reduction factor measures susceptibility to this particular clique-removal rule, not an independent measure of MIS computational hardness. The conclusions about problem hardness and quantum speedups should be correspondingly qualified, unless an independent hardness metric is supplied.
minor comments (4)
  1. [Sec. VI.C and Fig. 16 caption] There are a few typographical errors: "hyptothetical" in the Fig. 16 caption and "top-dowm" in Sec. VI.C. These should be corrected.
  2. [Sec. IV.C.2, Eq. (7)] Equation (7) uses an approximate equality and an expression involving binomial coefficients, but the text describes it as the resulting qubit count. Please clarify the exact boundary and corner terms, since the later fits (3.99n^2 versus 1.45n^2) are central quantitative outputs.
  3. [General] The paper does not include a code or data availability statement. For a toolkit paper with many algorithmic claims and empirical fits, providing the implementation (or at least detailed pseudocode for the top-down embedder's BFS/rewiring step) would substantially improve reproducibility.
  4. [Table I and Appendix A] The power-law fit for run times on real-world networks is based on only ten data points; the stated exponent alpha ≈ 1.02(6) should be described as indicative rather than as a demonstrated asymptotic scaling.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation found; the pipeline's components are self-contained, with a minor same-group benchmark citation and one non-circular omitted proof in the top-down embedder.

full rationale

The claimed pipeline maps generic MIS instances to Rydberg-native UD MIS instances through three independent modules, and I could not exhibit an equation-level reduction of any output to its inputs. The reducer's optimality is justified by a cut-and-paste argument and standard external literature; the reduction factors, run-time scalings, and overhead prefactors (3.99 versus 1.45) are empirical descriptors fitted to data, not parameters that are then relabeled as predictions. The same-group citation that appears in the hardness discussion is Ref. [28] (Andrist et al., overlapping authors), used to import the conductance-like hardness parameter H and reported PMIS values for the benchmark instances in Sec. V; H is not an input to the reduction or embedding derivations, so this is a minor, non-load-bearing self-citation. I also explicitly flag an omitted proof rather than a circularity: Sec. IV.C.2's optimized top-down embedding asserts that chain reordering, shortening, terminal interactions, and rewiring preserve exactness 'provided that parity and spacing requirements are observed,' but the paper gives no invariant or automated verification that the simulated-annealing/biased-BFS search maintains those conditions. This is a load-bearing correctness risk for the strongest claim, but it is not a self-definitional or fitted-input circularity because the exact gadget construction is inherited from external Ref. [41] and the paper does not define the output in terms of the input. Score 2 reflects the minor self-citation; the central derivation retains independent content.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The central derivation uses only the standard corner-node reduction theorem and the standard Rydberg blockade mapping. The main uncharged premise is that the optimized embedding construction always respects parity and spacing, which the paper asserts without proof. The empirical prefactors and critical degree are fit to data but are used descriptively, not to derive correctness.

free parameters (3)
  • Generic embedding overhead prefactor = 3.99(1)
    Least-squares power-law fit to qubit counts for 250 reduced ER kernel graphs in Fig. 16; used as the baseline overhead for the scheme from Ref. [41].
  • Optimized embedding overhead prefactor = 1.45(2)
    Same fit for the proposed top-down embedding; this is the paper's main quantitative overhead-reduction claim.
  • Critical average degree = ~6 (edges per node)
    Read from reduction-vs-density curves for random geometric, UJ, and BA graphs (Figs. 13, 15, 19); used to define the onset of the hard regime.
assumptions (6)
  • standard math An exposed (corner) vertex with no neighbors outside its clique belongs to some maximum independent set.
    Invoked in Sec. IV.A 'Optimality' via the cut-and-paste argument; the paper provides a proof sketch and cites Refs. [48,49,57,59].
  • domain assumption Atoms on a square lattice with sqrt(2) <= Rb/a < 2 generate exactly the Union-Jack unit-disk connectivity used throughout.
    Used in Secs. III, IV.B, and the hardware demo; a standard modeling assumption for Rydberg arrays (Ref. [22]).
  • domain assumption The classical Hamiltonian H = -sum n_i + U sum n_i n_j with U>1 has ground states equal to the maximum independent sets.
    Used in Sec. III to justify solving MIS via Rydberg blockade; standard in the Rydberg optimization literature.
  • ad hoc to paper The optimized top-down embedding preserves the exact logical-to-physical ground-state correspondence from Ref. [41].
    The paper's modifications in Sec. IV.C.2 (reordering, shortening, terminal interactions, rewiring) are described as preserving parity and spacing requirements, but no proof is given that the annealing/BFS search always maintains the required conditions.
  • domain assumption Reduction factor xi, or kernel size, is a meaningful hardness proxy for quantum algorithms.
    Sec. V adopts the classical kernelization definition of hardness from Ref. [48] and extends it to the search for quantum speedups; the paper itself notes this should involve a full suite of reductions.
  • domain assumption The conductance-like hardness parameter H from Refs. [22,23,28] characterizes difficulty for Rydberg quantum algorithms.
    Used in Sec. V to compare reduction performance against previously studied hard instances; this is an external benchmark assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Compilation Toolkit for Rydberg Atom Arrays with Implications for Problem Hardness and Quantum Speedups." pith.science (2026). https://pith.science/paper/2BKWEJK2

@misc{pith2026241214976,
  author       = {Pith},
  title        = {Pith review of: Quantum Compilation Toolkit for Rydberg Atom Arrays with Implications for Problem Hardness and Quantum Speedups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2BKWEJK2}},
  note         = {Machine review of arXiv:2412.14976}
}
read the original abstract

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 sub-second time scales, 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 or not 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.

Figures

Figures reproduced from arXiv: 2412.14976 by the authors.

Figure 1
Figure 1. FIG. 1: Schematic illustration of the proposed compilation pipeline, shown here for the Cora citation graph with [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3: Schematic illustration of the cut-and-paste argument [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (15 more)
Figure 4
Figure 4. Figure 4: FIG. 4: Hardware compatibility diagram. Graphs are classi [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5: Example for simple hardware compatibility checks. [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6: Example for the RKO-based generative approximate [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7: Representation of the generic embedding scheme [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: FIG. 8 [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: FIG. 9: Example application of our general-purpose reducer to a hardware-native random UJ instance with [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: FIG. 10: Reduction results for larger, hardware-native, random UJ instance with [PITH_FULL_IMAGE:figures/full_fig_p013_10.png]
Figure 11
Figure 11. Figure 11: FIG. 11: Optimal MIS solution through repeated reduction [PITH_FULL_IMAGE:figures/full_fig_p014_11.png]
Figure 12
Figure 12. Figure 12: FIG. 12: Box plot for the reduction factor [PITH_FULL_IMAGE:figures/full_fig_p015_12.png]
Figure 13
Figure 13. Figure 13: FIG. 13: Violin plot for the reduction factor [PITH_FULL_IMAGE:figures/full_fig_p015_13.png]
Figure 14
Figure 14. Figure 14: FIG. 14: MIS solutions obtained for the largest component of the Cora core graph via analog Hamiltonian simulation (AHS) on [PITH_FULL_IMAGE:figures/full_fig_p016_14.png]
Figure 15
Figure 15. Figure 15: FIG. 15: Reduction applied to random geometric graphs in two space dimensions. [PITH_FULL_IMAGE:figures/full_fig_p018_15.png]
Figure 16
Figure 16. Figure 16: FIG. 16: Number of qubits required for hardware-native em [PITH_FULL_IMAGE:figures/full_fig_p019_16.png]
Figure 17
Figure 17. Figure 17: FIG. 17: Box plot for algorithmic run time (in seconds) for [PITH_FULL_IMAGE:figures/full_fig_p020_17.png]
Figure 19
Figure 19. Figure 19: FIG. 19: Reduction factor [PITH_FULL_IMAGE:figures/full_fig_p021_19.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

86 extracted references · 51 canonical work pages

  1. [41]

    to effectively support the required connectivity with the help of ancilla qubits. C. Graph Embedding We now outline two complementary embedding strate- gies for Rydberg atom arrays. Our first (bottom-up) ap- proach targetsapproximate embeddings with minimal re- sourcerequirements, whileoursecond(top-down)scheme provides exact embeddings with optimality gu...

  2. [1]

    Bottom-Up Embedding Scheme We first describe an approximate, hardware-efficient (bottom-up) embedding heuristic we refer to asGAGE (Generative Approximate Graph Embedder), in which optimized atomic (vertex) positions and the correspond- ing physical graph are learned via iterative training. Our scheme makes use of the random-key formalism to ef- ficiently...

  3. [2]

    interacting

    Top-Down Embedding Scheme Our second embedding approach builds on the generic embedding scheme outlined in Ref. [41]. This scheme is designed to provide a (physical, hardware-native) embed- ding for any potential (logical) input graph, regardless of its size, edge density or specific interactions, with an ex- act one-to-one correspondence between the grou...

    1921

  4. [3]

    Wurtz, P

    J. Wurtz, P. L. S. Lopes, N. Gemelke, A. Keesling, and S. Wang, Industry applications of neutral-atom quan- tum computing solving Independent Set problems(2022), arXiv:2205.08500

    arXiv 2022

  5. [4]

    W. K. Hale,Frequency assignment: Theory and applica- tions, Proceedings of the IEEE68, 1497 (1980)

    work page 1980

  6. [5]

    Our results are displayed in Figs

    Reduction run times In this section, we provide results for the algorithmic run times of our clique-based reduction algorithm when applied to both random UJ instances and real-world net- works. Our results are displayed in Figs. 17 and 18, re- spectively. For random UJ instances, we find that all re- duction runs finish on sub-second time scales per insta...

    2000

  7. [6]

    Our results for random BA and ER graphs are shown in Fig

    Reduction of synthetic (random) graphs In this section, we provide additional results on the clique-based reduction of synthetic (random) graphs, similar to the results shown for RG graphs in the main text. Our results for random BA and ER graphs are shown in Fig. 19

  8. [7]

    C. H. Papadimitriou and K. Steiglitz,Combinatorial Op- timization: Algorithms and Complexity(Courier Corpo- ration, North Chelmsford, 1998)

    work page 1998

Show all 86 references
  1. [8]

    Korte and J

    B. Korte and J. Vygen, Combinatorial Optimization, vol. 2 (Springer, New York, 2012)

    2012

  2. [9]

    Abbas, A

    A. Abbas, A. Ambainis, B. Augustino, A. Bärtschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko, D. J. Egger, B. G. Elmegreen, et al., Challenges and op- portunities in quantum optimization , Nature Reviews Physics 6, 718 (2024), URLhttps://doi.org/10.1038/ s42254-024-00770-9

    2024

  3. [10]

    Kadowaki and H

    T. Kadowaki and H. Nishimori, Quantum anneal- ing in the transverse ising model , Phys. Rev. E 58, 5355 (1998), URL https://link.aps.org/doi/10. 1103/PhysRevE.58.5355

    1998

  4. [11]

    Y. Dong, A. V. Goldberg, A. Noe, N. Parot- sidis, M. G. C. Resende, and Q. Spaen, A meta- heuristic algorithm for large maximum weight in- dependent set problems , Networks 85, 91 (2025), https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.22247, URL https://onlinelibrary.wile...

    2025 doi

  5. [12]

    Boginski, S

    V. Boginski, S. Butenko, and P. M. Pardalos,Statistical analysis of financial networks, Computational Statistics and Data Analysis48, 431 (2005)

    2005

  6. [13]

    Kalra, F

    A. Kalra, F. Qureshi, and M. Tisi, Portfolio as- set identification using graph algorithms on a Quan- tum Annealer, SSRN (2018), URL https://ssrn.com/ abstract=3333537

    2018

  7. [14]

    Pistoia, and Y

    D.Herman, C.Googin, X.Liu, Y.Sun, A.Galda, I.Safro, M. Pistoia, and Y. Alexeev, Quantum computing for finance, Nature Reviews Physics 5, 450 (2023), URL https://doi.org/10.1038/s42254-023-00603-1

    2023 doi

  8. [15]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A quan- 22 tum approximate optimization algorithm (2014), arXiv:1411.4028

    2014 arXiv

  9. [16]

    Zhou, S.-T

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum Approximate Optimization Al- gorithm: Performance, mechanism, and implemen- tation on near-term devices , Phys. Rev. X 10, 021067 (2020), URL https://link.aps.org/doi/10. 1103/PhysRevX.10.021067

    2020

  10. [17]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution (2000), arXiv:quant-ph/0001106

    2000 arXiv

  11. [18]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lund- gren, and D. Preda, A quantum adiabatic evolution al- gorithm applied to random instances of an np-complete problem, Science 292, 472 (2001), URL https://www. science.org/doi/abs/10.1126/science.1057726

    2001 doi

  12. [19]

    Das and B

    A. Das and B. K. Chakrabarti,Colloquium: Quantum annealing and analog quantum computation, Rev. Mod. Phys. 80, 1061 (2008), URL https://link.aps.org/ doi/10.1103/RevModPhys.80.1061

    2008 doi

  13. [20]

    Hauke, H

    P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. Oliver,Perspectives of quantum annealing: meth- ods and implementations, Rep. Prog. Phys. 83, 054401 (2020)

    2020

  14. [21]

    M. F. Serret, B. Marchand, and T. Ayral,Solving opti- mization problems with Rydberg analog quantum comput- ers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks, Phys. Rev. A 102, 052617 (2020), URL https://link.aps.org/doi/ 10.1103...

    2020 doi

  15. [22]

    Ebadi, A

    S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, et al.,Quantum optimization of Maximum Independent Set using Rydberg atom arrays, Science376, 1209 (2022), URL https://doi.org/10.1126/science. abo6587

    2022 doi

  16. [23]

    Lucas, Ising formulations of many NP problems , Front

    A. Lucas, Ising formulations of many NP problems , Front. Physics2, 5 (2014)

    2014

  17. [24]

    Glover, G

    F. Glover, G. Kochenberger, and Y. Du,Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models, 4OR 17, 335 (2019)

    2019

  18. [25]

    Pichler, S.-T

    H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Quantum optimization for Maximum Independent Set using Rydberg atom arrays(2018), arXiv:1808.10816

    2018 arXiv

  19. [26]

    Pichler, S.-T

    H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Computational complexity of the Rydberg Block- ade in two dimensions(2018), arXiv:1809.04954

    2018 arXiv

  20. [27]

    K.Kim, M.Kim, J.Park, A.Byun, andJ.Ahn, Quantum computing dataset of maximum independent set problem on king lattice of over hundred rydberg atoms, Scientific Data 11, 111 (2024), URL https://doi.org/10.1038/ s41597-024-02926-9

    2024

  21. [28]

    R. S. Andrist, M. J. A. Schuetz, P. Minssen, R. Yalovet- zky, S. Chakrabarti, D. Herman, N. Kumar, G. Salton, R. Shaydulin, Y. Sun, et al., Hardness of the maximum-independent-set problem on unit-disk graphs and prospects for quantum speedups, Phys. Rev. Res. 5, 043277 (2023),...

    2023

  22. [29]

    M. Cain, S. Chattopadhyay, J.-G. Liu, R. Samajdar, H.Pichler, andM.D.Lukin, Quantum speedup for combi- natorial optimization with flat energy landscapes(2023), arXiv:2306.13123

    2023 arXiv

  23. [30]

    B. F. Schiffer, D. S. Wild, N. Maskara, M. Cain, M. D. Lukin, and R. Samajdar, Circumventing su- perexponential runtimes for hard instances of quan- tum adiabatic optimization , Phys. Rev. Res. 6, 013271 (2024), URL https://link.aps.org/doi/10. 1103/PhysRevResearch.6.013271

    2024

  24. [31]

    J. R. Finžgar, M. J. A. Schuetz, J. K. Brubaker, H. Nishi- mori, and H. G. Katzgraber,Designing quantum anneal- ing schedules using bayesian optimization, Phys. Rev. Res. 6, 023063 (2024), URL https://link.aps.org/ doi/10.1103/PhysRevResearch.6.023063

    2024 doi

  25. [32]

    J. R. Finžgar, A. Kerschbaumer, M. J. Schuetz, C. B. Mendl, and H. G. Katzgraber, Quantum-informed re- cursive optimization algorithms , PRX Quantum 5, 020327 (2024), URL https://link.aps.org/doi/10. 1103/PRXQuantum.5.020327

    2024

  26. [33]

    M. S. Könz, W. Lechner, H. G. Katzgraber, and M. Troyer, Embedding overhead scaling of optimiza- tion problems in quantum annealing , PRX Quantum 2, 040322 (2021), URLhttps://link.aps.org/doi/10. 1103/PRXQuantum.2.040322

    2021

  27. [34]

    P. I. Bunyk, E. M. Hoskinson, M. W. Johnson, E. Tolka- cheva, F. Altomare, A. J. Berkley, R. Harris, J. P. Hilton, T. Lanting, A. J. Przybysz, et al.,Architectural consid- erations in the design of a superconducting quantum an- nealing processor, IEEE Transactions on Applied S...

    2014

  28. [35]

    M. D. Lukin, M. Fleischhauer, R. Cote, L. M. Duan, D. Jaksch, J. I. Cirac, and P. Zoller, Dipole Blockade and quantum information processing in mesoscopic atomic ensembles, Phys. Rev. Lett. 87, 037901 (2001), URL https://link.aps.org/doi/10. 1103/PhysRevLett.87.037901

    2001

  29. [36]

    Levine, A

    H. Levine, A. Keesling, G. Semeghini, A. Omran, T. T. Wang, S. Ebadi, H. Bernien, M. Greiner, V. Vuletić, H. Pichler, et al.,Parallel implementation of high-fidelity multiqubit gates with neutral atoms, Phys. Rev. Lett. 123, 170503 (2019), URL https://link.aps.org/doi/ 10.1103...

    2019 doi

  30. [37]

    Saffman, T

    M. Saffman, T. G. Walker, and K. Mølmer, Quan- tum information with Rydberg atoms, Rev. Mod. Phys. 82, 2313 (2010), URL https://link.aps.org/doi/10. 1103/RevModPhys.82.2313

    2010

  31. [38]

    B. N. Clark, C. J. Colbourn, and D. S. Johnson,Unit disk graphs, Discrete Mathematics86, 165 (1990), ISSN 0012- 365X, URLhttps://www.sciencedirect.com/science/ article/pii/0012365X9090358O

    1990

  32. [39]

    M. Kim, K. Kim, J. Hwang, E.-G. Moon, and J. Ahn, Rydberg quantum wires for Maximum Independent Set problems, Nature Physics 18, 755 (2022), URL https: //doi.org/10.1038/s41567-022-01629-5

    2022 doi

  33. [40]

    Dlaska, K

    C. Dlaska, K. Ender, G. B. Mbeng, A. Kruckenhauser, W. Lechner, and R. van Bijnen, Quantum optimiza- tion via four-body rydberg gates, Phys. Rev. Lett. 128, 120503 (2022), URL https://link.aps.org/doi/10. 1103/PhysRevLett.128.120503

    2022

  34. [42]

    Vinci, T

    W. Vinci, T. Albash, G. Paz-Silva, I. Hen, and D. A. Lidar, Quantum annealing correction with minor em- bedding, Phys. Rev. A 92, 042310 (2015), URL https: //link.aps.org/doi/10.1103/PhysRevA.92.042310

    2015 doi

  35. [43]

    Sugie, Y

    Y. Sugie, Y. Yoshida, N. Mertig, T. Takemoto, H. Ter- amoto, A. Nakamura, I. Takigawa, S.-i. Minato, M. Ya- maoka, and T. Komatsuzaki, Minor-embedding heuris- tics for large-scale annealing processors with sparse hard- ware graphs of up to 102,400 nodes , Soft Comput- ing 25, ...

    2021

  36. [44]

    A. Byun, M. Kim, and J. Ahn,Finding the maximum independent sets of platonic graphs using rydberg atoms, PRX Quantum 3, 030305 (2022), URL https://link. aps.org/doi/10.1103/PRXQuantum.3.030305

    2022 doi

  37. [45]

    A. Byun, J. Jung, K. Kim, M. Kim, S. Jeong, H. Jeong, and J. Ahn, Rydberg-atom graphs for quadratic unconstrained binary optimization problems (2023), arXiv:2309.14847

    2023 arXiv

  38. [46]

    Butenko and S

    S. Butenko and S. Trukhanov, Using critical sets to solve the maximum independent set problem , Opera- tions Research Letters 35, 519 (2007), ISSN 0167- 6377, URL https://www.sciencedirect.com/science/ article/pii/S0167637706000952

    2007

  39. [47]

    Nguyen, J.-G

    M.-T. Nguyen, J.-G. Liu, J. Wurtz, M. D. Lukin, S.- T. Wang, and H. Pichler, Quantum optimization with arbitrary connectivity using Rydberg atom arrays, PRX Quantum 4, 010316 (2023), URL https://link.aps. org/doi/10.1103/PRXQuantum.4.010316

    2023 doi

  40. [48]

    A. G. de Oliveira, E. Diamond-Hitchcock, D. M. 23 Walker, M. T. Wells-Pestell, G. PelegrÃ, C. J. Picken, G. P. A. Malcolm, A. J. Daley, J. Bass, and J. D. Pritchard, Demonstration of weighted graph optimization on a rydberg atom array using local light-shifts(2024), arXiv:2404.02658

    2024 arXiv

  41. [49]

    Bluvstein, H

    D. Bluvstein, H. Levine, G. Semeghini, T. T. Wang, S. Ebadi, M. Kalinowski, A. Keesling, N. Maskara, H. Pichler, M. Greiner, et al., A quantum processor based on coherent transport of entangled atom arrays, Na- ture 604, 451 (2022), URLhttps://doi.org/10.1038/ s41586-022-04592-6

    2022

  42. [50]

    Bluvstein, S

    D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, et al.,Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2024), URL https://doi.org/10.1038/s41586-023-06927-3

    2024 doi

  43. [51]

    Butenko, P

    S. Butenko, P. Pardalos, I. Sergienko, V. Shylo, and P. Stetsyuk, in Proceedings of the 2002 ACM Sympo- sium on Applied Computing(Association for Computing Machinery, New York, NY, USA, 2002), SAC ’02, pp. 542–546, ISBN 1581134452, URLhttps://doi.org/10. 1145/508791.508897

    2002

  44. [52]

    Wurtz, A

    J. Wurtz, A. Bylinskii, B. Braverman, J. Amato-Grill, S. H. Cantu, F. Huber, A. Lukin, F. Liu, P. Weinberg, J. Long, et al.,Aquila: Quera’s 256-qubit neutral-atom quantum computer(2023), arXiv:2306.11727

    2023 arXiv

  45. [53]

    Strash, inComputing and Combinatorics, edited by T

    D. Strash, inComputing and Combinatorics, edited by T. N. Dinh and M. T. Thai (Springer International Publishing, Cham, 2016), pp. 345–356, ISBN 978-3-319- 42634-1

    2016

  46. [54]

    Hespe, C

    D. Hespe, C. Schulz, and D. Strash, Scalable kernel- ization for maximum independent sets, ACM J. Exp. Algorithmics 24 (2019), ISSN 1084-6654, URL https: //doi.org/10.1145/3355502

    2019 doi

  47. [55]

    S. Lamm, C. Schulz, D. Strash, R. Williger, and H. Zhang, Exactly Solving the Maxi- mum Weight Independent Set Problem on Large Real-World Graphs (2019), pp. 144–158, https://epubs.siam.org/doi/pdf/10.1137/1.9781611975499.12, URL https://epubs.siam.org/doi/abs/10.1137/1. 97816...

    2019 doi

  48. [56]

    A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore, Automating the construction of internet portals with ma- chine learning, Information Retrieval3, 127 (2000)

    2000

  49. [57]

    Namata, B

    G. Namata, B. London, L. Getoor, and B. Huang, in 10th International Workshop on Mining and Learning with Graphs(2012), vol. 8, p. 249

    2012

  50. [58]

    Chang, W

    L. Chang, W. Li, and W. Zhang, in Proceedings of the 2017 ACM International Conference on Management of Data (Association for Computing Machinery, New York, NY, USA, 2017), SIGMOD ’17, pp. 1181–1196, ISBN 9781450341974, URL https://doi.org/10.1145/ 3035918.3035939

    2017

  51. [59]

    Gyger, M

    F. Gyger, M. Ammenwerth, R. Tao, H. Timme, S. Sni- girev, I. Bloch, and J. Zeiher,Continuous operation of large-scale atom arrays in optical lattices, Phys.Rev.Res. 6, 033104 (2024), URLhttps://link.aps.org/doi/10. 1103/PhysRevResearch.6.033104

    2024

  52. [60]

    H. J. Manetsch, G. Nomura, E. Bataille, K. H. Leung, X. Lv, and M. Endres,A tweezer array with 6100 highly coherent atomic qubits(2024), arXiv:2403.12021

    2024 arXiv

  53. [61]

    C. S. Adams, J. D. Pritchard, and J. P. Shaffer, Ry- dberg atom quantum technologies, Journal of Physics B: Atomic, Molecular and Optical Physics 53, 012002 (2019), URLhttps://dx.doi.org/10.1088/1361-6455/ ab52ef

    2019 doi

  54. [62]

    Henriet, L

    L. Henriet, L. Beguin, A. Signoles, T. Lahaye, A. Browaeys, G.-O. Reymond, and C. Jurczak, Quan- tum computing with neutral atoms , Quantum 4, 327 (2020), ISSN 2521-327X, URL https://doi.org/10. 22331/q-2020-09-21-327

    2020

  55. [63]

    Butenko, P

    S. Butenko, P. Pardalos, I. Sergienko, V. Shylo, and P. Stetsyuk,Estimating the size of correcting codes using extremal graph problems(Springer New York, New York, NY, 2009), pp. 227–243, ISBN 978-0-387-98096-6, URL https://doi.org/10.1007/978-0-387-98096-6_12

    2009 doi

  56. [64]

    Glover, M

    F. Glover, M. Lewis, and G. Kochenberger, Log- ical and inequality implications for reducing the size and difficulty of quadratic unconstrained bi- nary optimization problems, European Journal of Op- erational Research 265, 829 (2018), ISSN 0377- 2217, URL https://www.scienced...

    2018

  57. [65]

    S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck,Finding near-optimal independent sets at scale, Journal of Heuristics23, 207 (2017), URLhttps://doi. org/10.1007/s10732-017-9337-x

    2017 doi

  58. [66]

    Großmann, S

    E. Großmann, S. Lamm, C. Schulz, and D. Strash, in Proceedings of the Genetic and Evolutionary Computa- tion Conference(Association for Computing Machinery, New York, NY, USA, 2023), GECCO ’23, pp. 293–302, ISBN 9798400701191, URL https://doi.org/10.1145/ 3583131.3590353

    2023

  59. [67]

    Y. Liu, T. Safavi, A. Dighe, and D. Koutra,Graph sum- marization methods and applications: A survey, ACM Comput. Surv. 51 (2018), ISSN 0360-0300, URLhttps: //doi.org/10.1145/3186727

    2018 doi

  60. [68]

    Hashemi, S

    M. Hashemi, S. Gong, J. Ni, W. Fan, B. A. Prakash, and W. Jin, A comprehensive survey on graph re- duction: Sparsification, coarsening, and condensation (2024), arXiv:2402.03358

    2024 arXiv

  61. [69]

    Lewis and F

    M. Lewis and F. Glover,Quadratic unconstrained binary optimization problem preprocessing: Theory and empiri- cal analysis, Netw. 70, 79 (2017), ISSN 0028-3045, URL https://doi.org/10.1002/net.21751

    2017 doi

  62. [70]

    M. A. Londe, L. S. Pessoa, C. E. Andrade, and M. G. C. Resende, Early years of biased random-key genetic algo- rithms: A systematic review (2024), 2405.01765, URL https://arxiv.org/abs/2405.01765

    2024 arXiv

  63. [71]

    updates. Upon completion, after a series of training steps, RKO outputs an approximate graphG of low cost that is as similar as possible to the input graphG, given the hardware connectivity constraints. Let us illustrate the GAGE embedding scheme as de- scribed above with a si...

  64. [72]

    Narimani, S

    A. Narimani, S. S. C. Rezaei, and A. Zaribafiyan,Com- binatorial optimization by decomposition on hybrid cpu– non-cpu solver architectures(2017), arXiv:1708.03439

    2017 arXiv

  65. [73]

    H. N. Djidjev, E. A. R. Pelofske, and G. Hahn,Decompo- sition algorithms for solving np-hard problems on a quan- tum annealer, Journal of Signal Processing Systems93 (2020), ISSN 1939-8018, URL https://www.osti.gov/ biblio/1822729

    2020

  66. [74]

    M. E. J. Newman, Networks: an introduction (Oxford University Press, Oxford; New York, 2010), ISBN 9780199206650 0199206651, URL http://www.amazon. com/Networks-An-Introduction-Mark-Newman/dp/ 0199206651/ref=sr_1_5?ie=UTF8&qid=1352896678&sr= 8-5&keywords=complex+networks

    2010

  67. [75]

    A. A. Chaves, M. G. C. Resende, M. J. A. Schuetz, J. K. Brubaker, H. G. Katzgraber, E. F. de Arruda, and R. M. A. Silva, A random-key optimizer for com- binatorial optimization (2024), 2411.04293, URLhttps: 24 //arxiv.org/abs/2411.04293

    2024

  68. [76]

    M. A. Londe, L. S. Pessoa, C. E. Andrade, and M. G. Resende, Biased random-key genetic algorithms: A re- view, European Journal of Operational Research (2024), ISSN 0377-2217, URL https://www.sciencedirect. com/science/article/pii/S0377221724002303

    2024

  69. [77]

    M. J. Schuetz, J. K. Brubaker, H. Montagu, Y. van Dijk, J. Klepsch, P. Ross, A. Luckow, M. G. Resende, and H. G. Katzgraber, Optimization of robot-trajectory planning with nature-inspired and hy- brid quantum algorithms , Phys. Rev. Appl. 18, 054045 (2022), URL https://link.ap...

    2022

  70. [78]

    A. A. Chaves, M. G. C. Resende, and R. M. A. Silva, in Metaheuristics: 15th International Conference, MIC 2024, Lorient, France, June 4-7, 2024, Proceedings, Part I (Springer-Verlag, Berlin, Heidelberg, 2024), pp. 15– 20, ISBN 978-3-031-62911-2, URLhttps://doi.org/10. 1007/978...

    2024

  71. [79]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Op- timization by Simulated Annealing, Science 220, 671 (1983), URL https://www.science.org/doi/abs/10. 1126/science.220.4598.671

    1983

  72. [80]

    Perseguers, Hardness-dependent adiabatic schedules for analog quantum computing(2024), 2410.08995, URL https://arxiv.org/abs/2410.08995

    S. Perseguers, Hardness-dependent adiabatic schedules for analog quantum computing(2024), 2410.08995, URL https://arxiv.org/abs/2410.08995

    2024 arXiv

  73. [81]

    Leyton-Brown, H

    K. Leyton-Brown, H. H. Hoos, F. Hutter, and L. Xu,Un- derstanding the empirical hardness of np-complete prob- lems, Commun. ACM 57, 98 (2014), ISSN 0001-0782, URL https://doi.org/10.1145/2594413.2594424

    2014

  74. [82]

    Y. Song, M. Kim, H. Hwang, W. Lee, and J. Ahn, Quantum simulation of cayley-tree ising hamiltonians with three-dimensional rydberg atoms, Phys. Rev. Res. 3, 013286 (2021), URLhttps://link.aps.org/doi/10. 1103/PhysRevResearch.3.013286

    2021

  75. [83]

    R. A. Rossi and N. K. Ahmed, inAAAI (2015), URL http://networkrepository.com

    2015

  76. [84]

    Barthelemy, Spatial networks , Physics Re- ports 499, 1 (2011), ISSN 0370-1573, URL https://www.sciencedirect.com/science/article/ pii/S037015731000308X

    M. Barthelemy, Spatial networks , Physics Re- ports 499, 1 (2011), ISSN 0370-1573, URL https://www.sciencedirect.com/science/article/ pii/S037015731000308X

    2011

  77. [85]

    Barabási and R

    A.-L. Barabási and R. Albert, Emergence of scal- ing in random networks , Science 286, 509 (1999), https://www.science.org/doi/pdf/10.1126/science.286.5439.509, URL https://www.science.org/doi/abs/10.1126/ science.286.5439.509

    1999 doi

  78. [86]

    Wurtz, S

    J. Wurtz, S. H. Sack, and S.-T. Wang, Solving non- native combinatorial optimization problems using hy- brid quantum-classical algorithms, IEEE Transactions on Quantum Engineering pp. 1–15 (2024)

    2024

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.