arxiv: 2605.07952 · v1 · submitted 2026-05-08 · 🪐 quant-ph · cond-mat.dis-nn· cond-mat.quant-gas· physics.atom-ph

Recognition: 2 theorem links

· Lean Theorem

Reducibility of native weighted graphs on Rydberg Arrays

J. D. Pritchard, J. Kombe

Authors on Pith no claims yet

Pith reviewed 2026-05-11 03:19 UTC · model grok-4.3

classification 🪐 quant-ph cond-mat.dis-nncond-mat.quant-gasphysics.atom-ph

keywords unit-disk graphsmaximum independent setRydberg atomskernelisationquantum optimizationweighted graphsclassical preprocessingnative embeddings

0 comments

The pith

Classical kernelisation leaves dense native unit-disk graphs for Rydberg processors with finite irreducible kernels.

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

The paper tests how far standard classical preprocessing can shrink maximum independent set and maximum weighted independent set instances whose graphs are directly realizable on Rydberg atom arrays. It shows that small or sparse unit-disk graphs often reduce to trivial size, yet denser connectivities keep small but nonzero kernels even after aggressive reductions. Vertex weights increase the chance of full reduction, while longer-range interactions decrease it. The remaining kernels would require non-native embeddings on quantum hardware that cost more resources than solving the original graph directly, so the work identifies which native instances stay genuinely hard for near-term devices.

Core claim

State-of-the-art kernelisation applied to random unit-disk graphs of the MIS and MWIS problems reduces many small or sparse instances to empty, but dense instances retain finite irreducible kernels; weights raise reducibility while longer interaction ranges lower it, and the kernels that survive would demand substantial embedding overheads on quantum hardware, making direct execution of the native graph the lower-cost option.

What carries the argument

Kernelisation techniques that repeatedly apply reduction rules to simplify graph instances of the maximum independent set problem before any solver is called.

If this is right

Near-term quantum optimisation benchmarks should focus on dense native unit-disk instances that survive classical reduction.
Direct execution of the original graph is cheaper than first reducing and then embedding when kernels remain.
Weighted versions of the problem become easier for classical preprocessing than unweighted ones.
Longer-range Rydberg interactions produce graphs that are harder to reduce classically.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Hybrid classical-quantum workflows could run reductions first and hand only the irreducible core to the quantum device.
The same pattern may appear in other hardware-native graphs beyond Rydberg arrays, such as those with fixed-range couplings.
Quantum advantage claims for optimisation may need to be tested specifically on instances whose kernels cannot be made trivial.

Load-bearing premise

Random unit-disk graphs of chosen size and density accurately represent the interaction graphs that can be realized on current Rydberg atom arrays.

What would settle it

A concrete dense random unit-disk graph instance that kernelisation reduces all the way to the empty graph, or a reduced kernel whose non-native embedding on Rydberg hardware uses fewer total atoms and gates than the original native instance.

Figures

Figures reproduced from arXiv: 2605.07952 by J. D. Pritchard, J. Kombe.

**Figure 2.** Figure 2: (a) shows an example of a L = 20 square array across different node densities ρ ∈ {0.7, 0.8, 0.9, 1.0}. For each problem instance (L, ρ, Rb) we generate #G = 1000 random graph instances (except for ρ = 1.0, where only 1 exists). We record the number of finite kernels (#K), shown in each box of [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3. In general we ran 100 random weight realisations for [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4. Scaling of the reduction factor [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

read the original abstract

We investigate the classical reducibility of random unit-disk graph (UDG) instances of the maximum independent set (MIS) and maximum weighted independent set (MWIS) problems, which can be natively realised in Rydberg atom quantum processors. Using state-of-the-art kernelisation techniques, we systematically probe how far classical preprocessing can simplify such native optimisation problems of varying size and connectivity. While many small or sparse instances can be fully reduced, dense graphs often retain finite irreducible kernels even after extensive reductions. Introducing vertex weights tends to increase reducibility, whereas extending the interaction range in the underlying UDG connectivity suppresses the reduction efficiency. By exploring where classical reductions cease to be effective, we aim to delineate the regime of problem instances that remain computationally demanding - those most relevant for testing and benchmarking near-term quantum optimisation hardware. We find that for the remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads, suggesting that directly running native instances may be more practical than embedding a reduced kernel.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper runs kernelisation on random unit-disk graphs for Rydberg MIS/MWIS and finds dense cases keep finite kernels while weights help and longer range hurts, but the random instances may not match the geometric structure of real atom arrays.

read the letter

The main point here is that classical preprocessing can fully reduce many small or sparse unit-disk graphs for maximum independent set, but dense ones often leave a non-trivial kernel, and the authors conclude that embedding those kernels onto hardware would cost more than just running the original native instance. They also note that adding weights improves reducibility while stretching the interaction range makes reduction harder. That systematic sweep over size, density, weights, and range is the actual new piece; it takes standard kernelisation tools and applies them to graphs meant to stand in for Rydberg hardware problems, which had not been done at this granularity before. The trends they report are straightforward and useful for anyone trying to decide when to bother with classical reduction before a quantum run. The soft spot is the choice of random unit-disk graphs. Real Rydberg arrays place atoms on lattices or programmable grids, which imposes planarity, bounded degree, and spatial correlations that random graphs lack. If those constraints change how much kernelisation can do, then the claim that native execution beats embedding a reduced kernel does not automatically carry over to hardware-realizable instances. The abstract gives no detail on the exact kernelisation routines, the number of trials, or any statistical checks, so the quantitative limits on reducibility need verification from the full methods. This work is aimed at people who build or benchmark Rydberg solvers for graph problems and want to know where classical help stops. A reader working on near-term quantum optimization would get practical orientation from the trends even if the modeling choice needs tightening. It is solid enough on its own terms to deserve a serious referee rather than a desk reject; the question it asks is timely and the empirical design is reasonable once the instance generation is scrutinized.

Referee Report

2 major / 1 minor

Summary. The paper investigates the classical reducibility of random unit-disk graph (UDG) instances for the maximum independent set (MIS) and maximum weighted independent set (MWIS) problems, which are native to Rydberg atom quantum processors. Using state-of-the-art kernelisation techniques, it systematically probes instances of varying size and connectivity. The authors report that many small or sparse instances can be fully reduced, while dense graphs often retain finite irreducible kernels. Vertex weights tend to increase reducibility, whereas longer interaction ranges suppress reduction efficiency. They conclude that for remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads, suggesting that directly running native instances may be more practical than embedding a reduced kernel.

Significance. If the central empirical trends hold and the random UDG model is representative, this work helps delineate regimes of problem instances that remain computationally demanding after classical preprocessing, which is relevant for benchmarking near-term quantum optimization hardware. The systematic variation of parameters (size, density, weights, range) and reporting of clear trends provide useful empirical data on the limits of kernelisation for these native graphs. The study does not include machine-checked proofs or open code, but its computational approach could support reproducibility if methods and instances are fully detailed.

major comments (2)

[Graph generation and methods] The strongest claim—that remaining finite kernels would require non-native embeddings with substantial overheads, making direct native execution preferable—depends on random UDGs being representative of native Rydberg interaction graphs. Native graphs arise from fixed or programmable 2D atom positions (typically lattices), inducing UDGs with strict planarity, bounded degree sequences, and spatial edge correlations. Random UDGs lack these constraints and can produce topologically different instances. This assumption is load-bearing for the practical implications but is not tested via comparison to lattice-based or hardware-realizable graphs.
[Results and conclusions] The conclusion on embedding overheads for finite kernels is stated qualitatively without quantitative estimates. No specific kernel sizes, reduction ratios, or references to embedding costs (e.g., for the reported dense-graph kernels) are provided to support that the overheads are 'substantial' relative to direct native execution. This weakens the suggestion that direct native instances are more practical.

minor comments (1)

[Abstract and methods] The abstract and methods refer to 'state-of-the-art kernelisation techniques' without naming the specific algorithms or implementations used. Including these details (or pseudocode) would improve clarity and reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive comments, which highlight important aspects of scope and evidence strength in our work on the classical reducibility of unit-disk graphs. We address each major comment below, indicating where revisions will be incorporated.

read point-by-point responses

Referee: [Graph generation and methods] The strongest claim—that remaining finite kernels would require non-native embeddings with substantial overheads, making direct native execution preferable—depends on random UDGs being representative of native Rydberg interaction graphs. Native graphs arise from fixed or programmable 2D atom positions (typically lattices), inducing UDGs with strict planarity, bounded degree sequences, and spatial edge correlations. Random UDGs lack these constraints and can produce topologically different instances. This assumption is load-bearing for the practical implications but is not tested via comparison to lattice-based or hardware-realizable graphs.

Authors: We agree that random unit-disk graphs do not incorporate the additional structural constraints present in lattice-based Rydberg arrays, such as planarity, bounded degree sequences, and spatial edge correlations. Our use of random UDGs follows established modeling practices in the Rydberg optimization literature to isolate the effects of size, density, and weights on reducibility. We acknowledge that this choice limits direct extrapolation to hardware instances. In the revised manuscript, we will add a discussion paragraph clarifying this distinction, noting that the reported trends (e.g., the suppressing effect of density and interaction range) are expected to be relevant but that targeted comparisons to lattice graphs remain an important direction for future work. This revision clarifies the scope without altering the core empirical results. revision: partial
Referee: [Results and conclusions] The conclusion on embedding overheads for finite kernels is stated qualitatively without quantitative estimates. No specific kernel sizes, reduction ratios, or references to embedding costs (e.g., for the reported dense-graph kernels) are provided to support that the overheads are 'substantial' relative to direct native execution. This weakens the suggestion that direct native instances are more practical.

Authors: We accept that the claim regarding embedding overheads is currently qualitative and would be strengthened by quantitative support. While the manuscript reports the retention of finite irreducible kernels for dense graphs, specific kernel sizes, reduction ratios, and explicit comparisons to embedding costs are not detailed in the conclusions. In the revised version, we will include quantitative data drawn from our experiments (such as average irreducible kernel sizes and reduction ratios for dense instances) together with references to typical minor-embedding overhead factors in Rydberg hardware. This will allow a more concrete assessment of whether direct native execution is preferable for the remaining kernels. revision: yes

Circularity Check

0 steps flagged

No significant circularity in empirical computational study

full rationale

The paper is an empirical investigation that generates random unit-disk graphs, applies standard kernelisation algorithms for MIS/MWIS, and reports observed reduction outcomes. No derivation chain exists that reduces a claimed result to its own inputs by construction, no parameters are fitted and then relabeled as predictions, and no load-bearing premises rest on self-citations. The central findings on kernel sizes and embedding overheads are direct computational outputs rather than tautological restatements of the input model or prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard assumptions from graph theory and quantum hardware modeling with no new entities or fitted parameters introduced beyond varying experimental inputs like graph density and range.

axioms (1)

domain assumption Random unit-disk graphs accurately model the connectivity realizable in Rydberg atom arrays
Invoked in the setup of native optimisation problems throughout the abstract.

pith-pipeline@v0.9.0 · 5480 in / 1271 out tokens · 42261 ms · 2026-05-11T03:19:34.952353+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We find that for the remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

118 extracted references · 118 canonical work pages · 1 internal anchor

[1]

Removing these vertices and ad- justing the objective value (in the weighted case) yields a smaller problem instanceG ′=(V ′, E′), termed the kernel

Reduction Philosophy Given a graphG=(V, E)with vertex weightsw∶V→ R≥0, a reduction rule identifies a set of vertices whose membership in an optimal solution is fully determined by its local structure. Removing these vertices and ad- justing the objective value (in the weighted case) yields a smaller problem instanceG ′=(V ′, E′), termed the kernel. Applyi...

work page
[2]

A complete list and details can be found in Table 1 of [100]

Examples of Fundamental Reduction Rules In the following we give a brief description of a subset of reduction rules used inLearnAndReduce. A complete list and details can be found in Table 1 of [100]. a. Isolated Vertex.If a vertexvhas a open neigh- bourhood (simply called the neighbourhood)N(v)={u∣ (v, u)∈E}=∅, thenvmust belong to every MIS/MWIS solution...

work page
[3]

TheLearnAndReduceframework [74] incorporates ma- chine learning to accelerate these expensive reductions

Learned Reduction: KaMIS’sLearnAndReduce Although many reduction rules are inexpensive, sev- eral of the most powerful ones - such as advanced neighbourhood-dominance checks, generalised twin rules, or deep folding cascades - can be costly to evaluate. TheLearnAndReduceframework [74] incorporates ma- chine learning to accelerate these expensive reductions...

work page
[4]

2 (c) shows the same analysis for the largest studied array ofL=50

Fig. 2 (c) shows the same analysis for the largest studied array ofL=50. The vast majority of graphs did yield a finite kernel with e.g. the largest mean reduction factor forρ=0.9 (atR b = √

work page
[5]

The remaining connectivities are showing even smaller reductions, and we again find very similar behaviour for the different fillingsρin the array

dropping by a factor of 3 from ¯ξ∼0.35 (L=20) down to ¯ξ∼0.12 forL=50. The remaining connectivities are showing even smaller reductions, and we again find very similar behaviour for the different fillingsρin the array. Even forR b = √ 8 andρ<1 did we find graphs which are not fully reducible, where arrays with a larger defect density appear to be harder f...

work page
[6]

had a finite kernel), here we see that cer- tain weighted instances are solved to optimality (empty kernel)

was deemed ‘hard’ (i.e. had a finite kernel), here we see that cer- tain weighted instances are solved to optimality (empty kernel). Furthermore, Fig. 3 (b) shows that we find larger mean reduction factors compared to the MIS case. This behaviour is consistent with the interpretation that 6 0.7 0.8 0.9 1.0 ρ 1 √ 2 2 √ 5 √ 8 3 Rb (a) 1 √ 2 2 √ 5 √ 8 3 Rb 0...

work page 2000
[7]

V. T. Paschos,Applications of combinatorial optimiza- tion, Vol. 3 (John Wiley & Sons, 2014)

work page 2014
[8]

R. M. Karp, Reducibility among combinatorial prob- lems, inComplexity of Computer Computations: Pro- ceedings of a symposium on the Complexity of Computer Computations, edited by R. E. Miller, J. W. Thatcher, and J. D. Bohlinger (Springer US, Boston, MA, 1972) pp. 85–103

work page 1972
[9]

C. H. Papadimitriou and K. Steiglitz,Combinatorial op- timization: algorithms and complexity(Courier Corpo- ration, 1998)

work page 1998
[10]

Korte and J

B. Korte and J. Vygen, Combinatorial optimization: Theory and algorithms (Springer Berlin Heidelberg, Berlin, Heidelberg, 2018)

work page 2018
[11]

Quantum Computation by Adiabatic Evolution

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

work page Pith review arXiv 2000
[12]

Farhi, J

E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem, Science292, 472 (2001), https://www.science.org/doi/pdf/10.1126/science.1057726

work page doi:10.1126/science.1057726 2001
[13]

Glover, G

F. Glover, G. Kochenberger, R. Hennig, and Y. Du, Quantum bridge analytics i: a tutorial on formulating and using qubo models, Annals of Operations Research 314, 141 (2022)

work page 2022
[14]

Kadowaki and H

T. Kadowaki and H. Nishimori, Quantum annealing in the transverse ising model, Phys. Rev. E58, 5355 (1998)

work page 1998
[15]

Das and B

A. Das and B. K. Chakrabarti, Colloquium: Quantum annealing and analog quantum computation, Rev. Mod. Phys.80, 1061 (2008)

work page 2008
[16]

Hauke, H

P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, Perspectives of quantum annealing: methods and implementations, Reports on Progress in Physics83, 054401 (2020)

work page 2020
[17]

Rajak, S

A. Rajak, S. Suzuki, A. Dutta, and B. K. Chakrabarti, Quantum annealing: An overview, Philosophical Trans- actions of the Royal Society A381, 20210417 (2023)

work page 2023
[18]

Cerezo, A

M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algo- rithms, Nature Reviews Physics3, 625 (2021)

work page 2021
[19]

Astrakhantsev, G

N. Astrakhantsev, G. Mazzola, I. Tavernelli, and G. Carleo, Phenomenological theory of variational quan- tum ground-state preparation, Phys. Rev. Res.5, 033225 (2023)

work page 2023
[20]

Peruzzo, J

A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nature Communications5, 4213 (2014)

work page 2014
[21]

Kandala, A

A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware- efficient variational quantum eigensolver for small molecules and quantum magnets, Nature549, 242 (2017)

work page 2017
[22]

Hempel, C

C. Hempel, C. Maier, J. Romero, J. McClean, T. Monz, H. Shen, P. Jurcevic, B. P. Lanyon, P. Love, R. Bab- bush, A. Aspuru-Guzik, R. Blatt, and C. F. Roos, Quan- tum chemistry calculations on a trapped-ion quantum simulator, Phys. Rev. X8, 031022 (2018)

work page 2018
[23]

Kokail, C

C. Kokail, C. Maier, R. van Bijnen, T. Brydges, M. K. Joshi, P. Jurcevic, C. A. Muschik, P. Silvi, R. Blatt, C. F. Roos, and P. Zoller, Self-verifying variational quantum simulation of lattice models, Nature569, 355 (2019)

work page 2019
[24]

A Quantum Approximate Optimization Algorithm

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

work page internal anchor Pith review Pith/arXiv arXiv 2014
[25]

Wecker, M

D. Wecker, M. B. Hastings, and M. Troyer, Progress to- wards practical quantum variational algorithms, Phys. Rev. A92, 042303 (2015)

work page 2015
[26]

Wurtz and P

J. Wurtz and P. Love, Maxcut quantum approximate optimization algorithm performance guarantees forp> 1, Phys. Rev. A103, 042612 (2021)

work page 2021
[27]

Farhi, J

E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size, Quantum6, 759 (2022)

work page 2022
[28]

Blekos, D

K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer, A review on Quantum Approximate Optimization Algorithm and its variants, Physics Reports1068, 1 (2024)

work page 2024
[29]

Lucas, Ising formulations of many np problems, Fron- tiers in physics2, 5 (2014)

A. Lucas, Ising formulations of many np problems, Fron- tiers in physics2, 5 (2014)

work page 2014
[30]

Zhang, K

H. Zhang, K. Boothby, and A. Kamenev, Cyclic quan- tum annealing: searching for deep low-energy states in 5000-qubit spin glass, Scientific Reports14, 30784 (2024)

work page 2024
[31]

L. F. P´ erez Armas, S. Creemers, and S. Deleplanque, Solving the resource constrained project scheduling problem with quantum annealing, Scientific Reports14, 16784 (2024)

work page 2024
[32]

M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lant- ing, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolka- cheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wil- son, and G. Rose, Quantum annealing with ...

work page 2011
[33]

De Santis, S

D. De Santis, S. Tirone, S. Marmi, and V. Giovan- netti, Optimized QUBO formulation methods for quan- tum computing, Quantum Science and Technology11, 015056 (2026)

work page 2026
[34]

A. D. King, A. Nocera, M. M. Rams, J. Dziarmaga, R. Wiersema, W. Bernoudy, J. Raymond, N. Kaushal, N. Heinsdorf, R. Harris, K. Boothby, F. Altomare, M. Asad, A. J. Berkley, M. Boschnak, K. Chern, H. Christiani, S. Cibere, J. Connor, M. H. Dehn, R. Deshpande, S. Ejtemaee, P. Farre, K. Hamer, E. Hoskinson, S. Huang, M. W. Johnson, S. Kortas, E. Ladizinsky, ...

work page doi:10.1126/science.ado6285 2025
[35]

Zaribafiyan, D

A. Zaribafiyan, D. J. J. Marchand, and S. S. Changiz Rezaei, Systematic and deterministic graph mi- nor embedding for cartesian products of graphs, Quan- tum Information Processing16, 136 (2017)

work page 2017
[36]

Pelofske, Comparing three generations of D-Wave quantum annealers for minor embedded combinatorial optimization problems, Quantum Science and Technol- ogy10, 025025 (2025)

E. Pelofske, Comparing three generations of D-Wave quantum annealers for minor embedded combinatorial optimization problems, Quantum Science and Technol- ogy10, 025025 (2025)

work page 2025
[37]

Choi, Minor-embedding in adiabatic quantum com- putation: I

V. Choi, Minor-embedding in adiabatic quantum com- putation: I. the parameter setting problem, Quantum Information Processing7, 193 (2008)

work page 2008
[38]

Choi, Minor-embedding in adiabatic quantum com- putation: Ii

V. Choi, Minor-embedding in adiabatic quantum com- putation: Ii. minor-universal graph design, Quantum Information Processing10, 343 (2011)

work page 2011
[39]

P. Date, R. Patton, C. Schuman, and T. Potok, Effi- ciently embedding QUBO problems on adiabatic quan- tum computers, Quantum Information Processing18, 117 (2019)

work page 2019
[40]

Ceselli and M

A. Ceselli and M. Premoli, On good encodings for quan- tum annealer and digital optimization solvers, Scientific Reports13, 5628 (2023)

work page 2023
[41]

Kim, S.-W

S. Kim, S.-W. Ahn, I.-S. Suh, A. W. Dowling, E. Lee, and T. Luo, Quantum annealing for combinatorial op- timization: a benchmarking study, npj Quantum Infor- mation11, 77 (2025)

work page 2025
[42]

F. A. Quinton, P. A. S. Myhr, M. Barani, P. Crespo del Granado, and H. Zhang, Quantum annealing applica- tions, challenges and limitations for optimisation prob- lems compared to classical solvers, Scientific Reports15, 12733 (2025)

work page 2025
[43]

Henriet, L

L. Henriet, L. Beguin, A. Signoles, T. Lahaye, A. Browaeys, G.-O. Reymond, and C. Jurczak, Quan- tum computing with neutral atoms, Quantum4, 327 (2020)

work page 2020
[44]

Morgado and S

M. Morgado and S. Whitlock, Quantum simulation and computing with rydberg-interacting qubits, AVS Quan- tum Science3, 10.1116/5.0036562 (2021)

work page doi:10.1116/5.0036562 2021
[45]

Bluvstein, H

D. Bluvstein, H. Levine, G. Semeghini, T. T. Wang, S. Ebadi, M. Kalinowski, A. Keesling, N. Maskara, H. Pichler, M. Greiner, V. Vuleti` c, and M. D. Lukin, A quantum processor based on coherent transport of entangled atom arrays, Nature604, 451 (2022)

work page 2022
[46]

S. J. Evered, D. Bluvstein, M. Kalinowski, S. Ebadi, T. Manovitz, H. Zhou, S. H. Li, A. A. Geim, T. T. Wang, N. Maskara, H. Levine, G. Semeghini, M. Greiner, V. Vuleti´ c, and M. D. Lukin, High-fidelity parallel entangling gates on a neutral-atom quantum computer, Nature622, 268 (2023)

work page 2023
[47]

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, J. P. Bonilla Ataides, N. Maskara, I. Cong, X. Gao, P. Sales Ro- driguez, T. Karolyshyn, G. Semeghini, M. J. Gullans, M. Greiner, V. Vuleti´ c, and M. D. Lukin, Logical quan- tum processor based on reconfigurable atom arrays, Na- ture62...

work page 2024
[48]

H. J. Manetsch, G. Nomura, E. Bataille, K. H. Le- ung, X. Lv, and M. Endres, A tweezer array with 6100 highly coherent atomic qubits, arXiv:2403.12021 [quant- ph] (2024)

work page arXiv 2024
[49]

N.-C. Chiu, E. C. Trapp, J. Guo, M. H. Abobeih, L. M. Stewart, S. Hollerith, P. Stroganov, M. Kalinowski, A. A. Geim, S. J. Evered, S. H. Li, L. M. Peters, D. Blu- vstein, T. T. Wang, M. Greiner, V. Vuleti´ c, and M. D. Lukin, Continuous operation of a coherent 3,000-qubit system (2025), arXiv:2506.20660 [quant-ph]

work page arXiv 2025
[50]

A. G. de Oliveira, E. Diamond-Hitchcock, D. M. 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, PRX Quan- tum6, 010301 (2025)

work page 2025
[51]

M. D. Lukin, M. Fleischhauer, R. Cote, L. M. Duan, D. Jaksch, J. I. Cirac, and P. Zoller, Dipole Block- ade and Quantum Information Processing in Mesoscopic Atomic Ensembles, Phys. Rev. Lett.87, 037901 (2001)

work page 2001
[52]

Levine, A

H. Levine, A. Keesling, G. Semeghini, A. Omran, T. T. Wang, S. Ebadi, H. Bernien, M. Greiner, V. Vuleti´ c, H. Pichler, and M. D. Lukin, Parallel implementation of high-fidelity multiqubit gates with neutral atoms, Phys. Rev. Lett.123, 170503 (2019)

work page 2019
[53]

Saffman, T

M. Saffman, T. G. Walker, and K. Mølmer, Quantum information with Rydberg atoms, Rev. Mod. Phys.82, 2313 (2010)

work page 2010
[54]

Pichler, S.-T

H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Quantum Optimization for Maximum Indepen- dent Set Using Rydberg Atom Arrays, 1808.10816 [quant-ph] (2018)

work page arXiv 2018
[55]

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, 1809.04954 [quant-ph] (2018)

work page arXiv 2018
[56]

Ebadi, A

S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuleti` c, and M. D. Lukin, Quantum Optimization of Maximum Inde- pendent Set using Rydberg Atom Arrays, Scienc...

work page 2022
[57]

K. Kim, M. Kim, J. Park, A. Byun, and J. Ahn, Quan- tum computing dataset of maximum independent set problem on king lattice of over hundred Rydberg atoms, Scientific Data11, 111 (2024)

work page 2024
[58]

Goswami, R

K. Goswami, R. Mukherjee, H. Ott, and P. Schmelcher, Solving optimization problems with local light-shift en- coding on Rydberg quantum annealers, Phys. Rev. Res. 6, 023031 (2024)

work page 2024
[59]

Wurtz, P

J. Wurtz, P. L. S. Lopes, C. Gorgulla, N. Gemelke, A. Keesling, and S. Wang, Industry applications of neutral-atom quantum computing solving independent set problems (2024), arXiv:2205.08500 [quant-ph]

work page arXiv 2024
[60]

M. Kim, K. Kim, J. Hwang, E.-G. Moon, and J. Ahn, Rydberg quantum wires for maximum independent set problems, Nature Phys.18, 755 (2022)

work page 2022
[61]

A. Byun, M. Kim, and J. Ahn, Finding the maximum in- dependent sets of platonic graphs using rydberg atoms, PRX Quantum3, 030305 (2022)

work page 2022
[62]

Dalyac, L.-P

C. Dalyac, L.-P. Henry, M. Kim, J. Ahn, and L. Hen- riet, Exploring the impact of graph locality for the resolution of mis with neutral atom devices (2023), arXiv:2306.13373 [quant-ph]

work page arXiv 2023
[63]

A. Byun, J. Jung, K. Kim, M. Kim, S. Jeong, H. Jeong, and J. Ahn, Rydberg-atom graphs for quadratic un- constrained binary optimization problems, Advanced Quantum Technologies7, 2300398 (2024)

work page 2024
[64]

A. Byun, S. Jeong, and J. Ahn, Programming higher- 10 order interactions of rydberg atoms, Physical Review A 110, 042612 (2024)

work page 2024
[65]

Jeong, M

S. Jeong, M. Kim, M. Hhan, J. Park, and J. Ahn, Quan- tum programming of the satisfiability problem with ry- dberg atom graphs, Phys. Rev. Res.5, 043037 (2023)

work page 2023
[66]

Lanthaler, K

M. Lanthaler, K. Ender, C. Dlaska, and W. Lech- ner, Quantum optimization with globally driven neutral atom arrays (2024), arXiv:2410.03902 [quant-ph]

work page arXiv 2024
[67]

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 Quantum4, 010316 (2023)

work page 2023
[68]

Bombieri, Z

L. Bombieri, Z. Zeng, R. Tricarico, R. Lin, S. Notar- nicola, M. Cain, M. D. Lukin, and H. Pichler, Quan- tum Adiabatic Optimization with Rydberg Arrays: Lo- calization Phenomena and Encoding Strategies, PRX Quantum6, 020306 (2025)

work page 2025
[69]

Lechner, P

W. Lechner, P. Hauke, and P. Zoller, A quantum anneal- ing architecture with all-to-all connectivity from local interactions, Science Advances1, e1500838 (2015)

work page 2015
[70]

Lanthaler, C

M. Lanthaler, C. Dlaska, K. Ender, and W. Lech- ner, Rydberg-Blockade-Based Parity Quantum Opti- mization, Phys. Rev. Lett.130, 220601 (2023)

work page 2023
[71]

Stastny, H

S. Stastny, H. P. B¨ uchler, and N. Lang, Functional com- pleteness of planar rydberg blockade structures, Phys. Rev. B108, 085138 (2023)

work page 2023
[72]

J. Park, S. Jeong, M. Kim, K. Kim, A. Byun, L. Vig- noli, L.-P. Henry, L. Henriet, and J. Ahn, Rydberg-atom experiment for the integer factorization problem, Phys. Rev. Res.6, 023241 (2024)

work page 2024
[73]

M. J. A. Schuetz, R. S. Andrist, G. Salton, R. Yalovet- zky, R. Raymond, Y. Sun, A. Acharya, S. Chakrabarti, M. Pistoia, and H. G. Katzgraber, Quantum Compila- tion Toolkit for Rydberg Atom Arrays with Implications for Problem Hardness and Quantum Speedups (2025), arXiv:2412.14976 [quant-ph]

work page arXiv 2025
[74]

R. S. Andrist, M. J. 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, Physical Review Re- search5, 043277 (2023)

work page 2023
[75]

M. J. A. Schuetz, R. Yalovetzky, R. S. Andrist, G. Salton, Y. Sun, R. Raymond, S. Chakrabarti, A. Acharya, R. Shaydulin, M. Pistoia, and H. G. Katz- graber, qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem (2025), arXiv:2503.12551 [quant-ph]

work page arXiv 2025
[76]

Barahona, On the computational complexity of ising spin glass models, Journal of Physics A: Mathematical and General15, 3241 (1982)

F. Barahona, On the computational complexity of ising spin glass models, Journal of Physics A: Mathematical and General15, 3241 (1982)

work page 1982
[77]

S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck, Finding near-optimal independent sets at scale, Journal of Heuristics23, 207 (2017)

work page 2017
[78]

Hespe, C

D. Hespe, C. Schulz, and D. Strash, Scalable kernel- ization for maximum independent sets, ACM J. Exp. Algorithmics24, 10.1145/3355502 (2019)

work page doi:10.1145/3355502 2019
[79]

S. Lamm, C. Schulz, D. Strash, R. Williger, and H. Zhang, Exactly Solving the Maximum Weight Inde- pendent Set Problem on Large Real-World Graphs, in 2019 Proceedings of the Meeting on Algorithm Engineer- ing and Experiments (ALENEX)(2019) pp. 144–158, https://epubs.siam.org/doi/pdf/10.1137/1.9781611975499.12

work page doi:10.1137/1.9781611975499.12 2019
[80]

Großmann, K

E. Großmann, K. Langedal, and C. Schulz, Accelerat- ing reductions using graph neural networks and a new concurrent local search for the maximum weight inde- pendent set problem, arXiv preprint arXiv:2412.14198 (2024)

work page arXiv 2024

Showing first 80 references.