Pith. sign in

REVIEW 5 major objections 6 minor 4 cited by

Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors

T0 review · 5 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read The paper shows that density and treewidth tune the classical difficulty of unit-disk MIS instances natively embeddable on neutral-atom hardware, and projects quantum advantage at about 1000 atoms and a 1 kHz repetition rate.

desk verdict Useful and honest benchmark paper, but the classical-hardness claim rests on CPLEX alone and the 1000-atom estimate is a roadmap wish; needs revisions before the headline is safe. read the letter →

arxiv 2502.04291 v1 pith:NJM4JD2X submitted 2025-02-06 quant-ph

Pierre Cazals , Aymeric François , Loïc Henriet , Lucas Leclerc , Malory Marin , Yassine Naghmouchi , Wesley da Silva Coelho , Florian Sikora
show 4 more authors
Vittorio Vitale Rémi Watrigant Monique Witt Garzillo Constantin Dalyac
This is my paper · ORCID
classification quant-ph
keywords maximumindependentsetunit-diskgraphsneutralatomquantumprocessorsannealingRydbergblockadetreewidthdensityCPLEXbenchmark
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 seeks to show that the maximum independent set problem on unit-disk graphs (UD-MIS), the native combinatorial optimization task for neutral-atom quantum processors, can be turned into a genuinely hard classical benchmark by tuning geometric parameters. Drawing on parameterized complexity results, it identifies density, thickness, and treewidth as the knobs that separate easy instances from hard ones, with low values making UD-MIS tractable. On triangular-lattice instances natively embeddable in the hardware, the authors show that for a fixed graph size the CPLEX branch-and-bound time to solution grows by several orders of magnitude as density increases, and that a direct quantum-vs-classical comparison on small instances shows the quantum procedure is about three orders of magnitude slower. The paper's forward projection is that demonstrating a computational advantage will require scaling to roughly a thousand atoms with a 1 kHz repetition rate, a target it presents as a hardware engineering challenge rather than a fundamental barrier.

What carries the argument

The generator is a fixed triangular trap layout (200 sites, 5 µm spacing); density ρ is the fraction of selected sites among the closest L = N/ρ central traps, and the resulting graph is a unit-disk graph directly implementable on the hardware. Hardness is probed along three nested parameters: density (max centers per unit grid), thickness (min centers in any slab of a one-unit-wide slab decomposition), and treewidth (a measure of how close a graph is to a tree); known results make low values easy, e.g., a thickness-t UD graph is solvable in O($t^{2}$ $2^{{2t}}$ n). The classical side is benchmarked with CPLEX branch-and-cut counting deterministic ticks; the quantum side uses adiabatic annealing and a time-to-solution computed from the probability of sampling the maximum independent set.

What would settle it

Take the same triangular-lattice UD-MIS instances used in the paper (N from 100 to 1000, density 0.1 to 1.0) and solve them with a second independent exact solver, for example a branch-and-reduce MIS solver, recording runtime in comparable deterministic steps; if the second solver's runtime does not reproduce the orders-of-magnitude growth with density reported for CPLEX, the central classical-hardness claim is falsified.

Watch

Extended reading notes

Core claim

The central discovery is that one can generate native UD-MIS instances whose classical difficulty is tunable: on graphs sampled from a fixed triangular trap layout, increasing the density from sparse to intermediate values increases CPLEX runtime by several orders of magnitude at constant system size, until the fully regular ρ=1 layout becomes easy again. This hardness correlates with approximate treewidth and is consistent with the known parameterized algorithms: bounded thickness or treewidth admits FPT algorithms, so breaking those bounds drives exponential growth. On the quantum side, both simulated and hardware annealing show growing gap-to-solution with size and density, but at small scale the quantum time-to-solution (shots needed for 99% success) is about three orders of magnitude larger than CPLEX's time, and the extrapolation places the crossover around a thousand atoms at a 1 kHz repetition rate.

Load-bearing premise

The paper's classical-hardness conclusions assume that CPLEX with its default settings is a representative state-of-the-art solver for the triangular-lattice graphs it generates; if a different solver scales much better on those graphs, the reported orders-of-magnitude runtime increases and the three-orders-of-magnitude quantum disadvantage would shrink.

Editorial extensions

If this is right

  • UD-MIS benchmarks on neutral-atom hardware no longer need to rely on accidentally easy King's-lattice graphs; density and treewidth give a systematic way to generate classically hard instances at a chosen system size.
  • The three-orders-of-magnitude quantum time-to-solution gap is dominated by the repetition rate (a few Hz), not by state-preparation physics, so raising the repetition rate toward 100 Hz–1 kHz is the most direct hardware route to competitive exact quantum solving.
  • The extrapolated crossover at about 1000 atoms with a 1 kHz repetition rate is within reach of demonstrated 6100-atom arrays, making the target a concrete near-term milestone.
  • Degree-centrality weights raise classical MWIS runtime up to about 16 times at N=500 by widening the root gap, showing that weights are an independent hardness knob beyond geometry.
  • The non-monotonic behavior at ρ=1 warns that maximally dense native instances are not the hardest; the hard region sits at intermediate densities.

Reading between the lines

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

  • Editorial: The same density/treewidth mechanism should transfer to other NP-hard problems on unit-disk graphs (maximum clique, minimum vertex cover), since they share the separator and FPT structure; a testable extension is to benchmark those problems on the same triangular-lattice generator.
  • Editorial: The classical scaling may be specific to CPLEX; a natural next experiment is to run the identical instances with a branch-and-reduce exact solver or a tuned heuristic to separate instance hardness from solver behavior.
  • Editorial: If the 1 kHz repetition rate is achieved, the predicted crossover implies a concrete operating point for advantage experiments: N≈1000 with intermediate density (roughly ρ=0.3–0.7), where CPLEX ticks grow fastest.
  • Editorial: A planted-solution variant of the degree-centrality weighting scheme could push the root gap even higher, potentially raising the 16 times runtime factor into a new hardness regime.
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

5 major / 6 minor

Summary. The paper proposes a method for generating unit-disk-graph maximum independent set (UD-MIS) instances that are 'native' to neutral-atom hardware, using density, treewidth, and degree-centrality weights as hardness parameters motivated by fixed-parameter tractability and PTAS results. It reports CPLEX scaling benchmarks showing that increasing these parameters raises runtime by orders of magnitude, and it reports numerical and experimental quantum-annealing results showing that, for small instances, the quantum solver has a larger time-to-solution than CPLEX. The authors conclude that current neutral-atom processors are not competitive for exact MIS at small scale and estimate that roughly 1000 atoms at a 1 kHz repetition rate would be needed for a serious shot at computational advantage.

Significance. If the central claims hold, the paper provides a structured generator of native neutral-atom benchmark instances with tunable hardness and a useful, honest small-scale quantum/classical comparison. The paper's strengths include importing established FPT and PTAS bounds as external benchmarks rather than fitting its own theory, reporting real QPU data with documented error mitigation, and giving a concrete triangular-lattice instance generator. The main weaknesses are that all classical scaling conclusions rest on a single solver (CPLEX), that the quantum comparison uses a schedule optimized only at N=20 and appears to compare tick counts with shot counts, and that the theoretical 'density' parameter may not coincide with the operational fill fraction used in the benchmarks. These issues are load-bearing for the 'prohibitive runtime' and 'three orders of magnitude' claims, so the work currently requires revision rather than acceptance.

major comments (5)
  1. [Sec. IIIA, Figs. 1c, 2, A1] All classical runtime conclusions are drawn from CPLEX with default settings, despite the paper's own statement that 'assessing the hardness of a problem requires testing a variety of classical optimizers'. The claim that CPLEX runtimes 'serve as upper bounds on the best possible solving times achievable by classical solvers' is true only in the trivial sense that the true optimal classical time is at most the observed CPLEX time; it cannot support the 'prohibitive' hardness interpretation. A slow run of one solver is not evidence that other exact or heuristic solvers are also slow, and Ref. [38] reports large performance spreads among MIS solvers on unit-disk graphs. Please add at least one independent exact solver and one heuristic solver to the scaling benchmarks, or explicitly reframe the hardness conclusions as statements about CPLEX. This is load-bearing because the 1000-atom/1 kHz extrapolation is predicated on these scaling curves.
  2. [Sec. IV, App. D2] The quantum annealing schedule was obtained by Bayesian optimization on N=20 graphs and then applied without re-optimization to instances up to N=80 and to weighted instances. Since TTSQ depends exponentially on the probability of sampling the MIS, a suboptimal schedule at larger sizes can inflate TTSQ and bias the quantum/classical comparison. Please provide a sensitivity analysis (for example, TTSQ under several schedules per size, or a demonstration that the optimized schedule transfers) or explicitly state that the comparison holds only for the fixed default schedule rather than for the best achievable quantum performance.
  3. [Sec. IA, Figs. 1c-1d, Sec. V] TTSC is measured in CPLEX deterministic ticks while TTSQ is defined as the number of shots; these are not comparable time units. The conclusion that quantum solutions are slower by 'approximately three orders of magnitude' requires an explicit conversion to a common wall-clock unit, using the stated ~300 ticks per second and the QPU repetition rate. Please present the comparison in seconds and state the assumed hardware parameters at the point of comparison.
  4. [Sec. IIB, Sec. IIIB, App. D1] The theoretical density parameter used in the FPT/PTAS results (the maximum number of disk centers in a unit grid) is not the same as the empirical fill fraction ρ of Appendix D1 (the fraction of occupied traps in a triangular layout). The text says 'Therefore, in Sec. III, we will study in particular how the hardness behaves as a function of the density' immediately after defining the theoretical quantity, but the benchmarks vary the trap-occupancy fraction. Please either establish quantitatively that varying ρ controls the theoretical density in the relevant regime, or rename the operational parameter and separate the theoretical motivation from the empirical scaling claim.
  5. [Sec. IIID, Sec. IVC, App. A] The MWIS formulation in Appendix A and Sec. IVA assumes weights wi∈[0,1], but the degree-centrality weighting scheme in Eq. (8) produces weights in [1,1001] when δbar=1000. The paper does not state that these weights are rescaled before being inserted into the QUBO or quantum Hamiltonian. Without normalization, the penalty α in Eq. (10) may not dominate the vertex weights, so the ground state of the encoded Hamiltonian need not correspond to the MWIS. Please state explicitly how the weights were normalized in all weighted simulations and experiments, or adjust the model definition.
minor comments (6)
  1. [Fig. 1 caption and Sec. IIIB] The caption of Fig. 1 and the text of Sec. IIIB appear to disagree about which axis is density and which is graph size; please align the caption with the text and ensure both axes are clearly labeled in the figure.
  2. [Sec. IIIA] The sentence 'the solver operated at approximately 300 ticks per second on a 32-core CPU (Dual AMD Rome 7742, 128 cores total)' is ambiguous about which core count was actually used; please specify the exact configuration.
  3. [Sec. IIA] The phrase 'UD graphs, which share structural properties with planar graphs' is imprecise because unit-disk graphs can contain arbitrarily large cliques; please state the precise separator property from Ref. [73] that justifies the 2^{O(√n)} algorithm.
  4. [Sec. IIID, Ref. [81]] The manuscript cites an upcoming paper by the same group for the formal analysis of the weight-based hardness; the present paper would be more self-contained if the needed formal statements were summarized in an appendix or if the dependency on [81] were removed.
  5. [App. B] The sentence 'The numerical benchmark we ran is the most important one done compared to existing literature' is an unsupported evaluative claim and should be removed or substantiated with a concrete comparison to prior benchmark suites.
  6. [App. D2, Fig. A4] The definition of thickness in Sec. IIB is given informally ('minimum number of disk centers contained in any slab within a slab decomposition'); please state the slab width and orientation precisely, since the FPT result depends on this definition.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity: the hardness-parameter claims are backed by external complexity-theory results and independent CPLEX measurements, while the only self-citations are minor and non-essential.

full rationale

The paper's central derivation chain is not circular. The claimed hardness parameters (density, thickness, treewidth) are taken from external, established parameterized-complexity and approximation results (van Leeuwen's FPT algorithm for thickness, treewidth-based algorithms, and the PTAS for UD-MIS), not from quantities fitted in this paper. The classical runtime scaling is measured directly with CPLEX in deterministic ticks; no fitted parameter is renamed as a prediction. The quantum annealing schedule is an explicitly optimized input, optimized on small training graphs and then used as a fixed protocol, so the subsequent quantum-vs-classical comparison is a benchmark rather than a self-derived prediction. The only self-citations are minor: Ref. [13] is used to justify a post-processing routine, and Ref. [81], an 'upcoming work' by the same group, is cited for a formal sub-exponential analysis and for the theoretical explanation of the weighting scheme. These citations are not load-bearing for the paper's main empirical conclusions. The limitation that classical hardness is assessed with a single solver, CPLEX, is a genuine correctness concern about whether the reported 'prohibitive' scaling generalizes to other solvers, but it is not a circularity: the paper does not derive its conclusion from the same CPLEX data by definition. The paper also explicitly flags missing formal support ('A formal theoretical analysis is beyond the scope of this paper, but is part of ongoing work [81]'), which further confirms that the missing piece is not smuggled in as a forced conclusion.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claims rely on external complexity-theory results and on several modeling choices: that CPLEX ticks measure classical difficulty, that the triangular-lattice layout faithfully realizes the intended UD graph, and that the annealing schedule tuned on small graphs transfers to larger and weighted instances. These are not derived in the paper and are the main sources of uncertainty. No new physical entities are introduced.

free parameters (2)
  • Degree-centrality weight spread delta_bar = 1000
    Equation (8), "empirically chosen" in Sec. IIID; controls the hardness of the proposed MWIS weighting scheme.
  • Annealing schedule control points (Omega, delta) = not disclosed; optimized via Bayesian optimization
    Appendix D2: schedule optimized on N=20 random UD graphs to maximize PMIS, then used for all reported quantum results. The reported quantum gap depends on this fitted schedule.
assumptions (5)
  • standard math Known FPT algorithms for UD-MIS parameterized by thickness and treewidth, and PTAS by density, are correct and applicable.
    Sec. IIB relies on Refs [70], [72], [74], [80] to identify hardness parameters; these are external theorems, not derived here.
  • standard math Bounded thickness implies bounded treewidth, and bounded treewidth implies bounded density in UD graphs.
    Sec. IIB; used to establish the hierarchical nesting of hardness parameters.
  • domain assumption The triangular-lattice native embedding faithfully represents the intended UD graph.
    Sec. IIIA and App. D1; the mapping assumes next-nearest-neighbor interactions at 3.7% of nearest-neighbor interaction are negligible.
  • domain assumption CPLEX deterministic ticks are a valid metric for classical solving difficulty and CPLEX is a representative classical solver.
    Sec. IIIA; all classical runtime claims are based on CPLEX ticks and a single off-the-shelf solver.
  • ad hoc to paper The annealing schedule optimized on N=20 graphs transfers to larger graphs and to weighted instances.
    App. D2; schedule optimized on N=20 instances is applied unchanged to N up to 80 and to weighted problems.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors." pith.science (2026). https://pith.science/paper/NJM4JD2X

@misc{pith2026250204291,
  author       = {Pith},
  title        = {Pith review of: Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NJM4JD2X}},
  note         = {Machine review of arXiv:2502.04291}
}
read the original abstract

The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.

Figures

Figures reproduced from arXiv: 2502.04291 by the authors.

Figure 1
Figure 1. FIG. 1. Overview of the paper. We investigate the hardness of the MIS problem on natively embeddable graphs. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Treewidth [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: (b). This figure shows how the quality of the solu￾tion improves when the worst cost sampled bitstrings are discarded more and more. The simulations (solid lines) approach rapidly zero, despite the case N = 80 where the quality of the solution plateaus even when keepin…
Figure 5
Figure 5. Figure 5: FIG. 5 [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models

    quant-ph 2026-08 conditional novelty 6.0 of 10

    For shallow QAOA on maximum independent set, loss landscape variance increases with system size instead of vanishing, contradicting dynamical Lie algebra predictions.

  2. Quantum-Informed Portfolio Selection: An End-to-End Pipeline Validated on Trapped-Ion Hardware with Real Market Data

    quant-ph 2026-07 conditional novelty 6.0 of 10

    qReduMIS, using QAOA frozen-node signals plus classical reductions, solves real market MIS portfolio instances up to 225 assets on Helios with far better success and TTS scaling than standalone QAOA.

  3. A Framework for Quantum Advantage

    quant-ph 2025-06 conditional novelty 4.0 of 10

    A framework defining quantum advantage as verifiable plus classically superior, with a conclusion that random circuit sampling is not yet a satisfactory path.

  4. Strategic Plan for Neutral Atom Quantum Computation

    quant-ph 2026-07 conditional novelty 3.0 of 10

    If qubit-count growth (~1.8x/yr) and gate-error reduction (~0.62x/yr) continue, neutral-atom quantum computers could reach practical quantum advantage within a decade, this roadmap projects.

Reference graph

Works this paper leans on

125 extracted references · 35 canonical work pages · cited by 4 Pith papers

  1. [38]

    Hardness of the maximum-independent- set problem on unit-disk graphs and prospects for quan- tum speedups

    Ruben S Andrist, Martin JA Schuetz, Pierre Minssen, Romina Yalovetzky, Shouvanik Chakrabarti, Dylan Herman, NirajKumar, GrantSalton, RuslanShaydulin, Yue Sun, et al. Hardness of the maximum-independent- set problem on unit-disk graphs and prospects for quan- tum speedups. Physical Review Research, 5(4):043277,

  2. [1]

    Applications of combinatorial optimization

    Vangelis Th Paschos. Applications of combinatorial optimization. John Wiley & Sons, 2014. doi: 10.1002/9781118600283

    work page doi:10.1002/9781118600283 2014

  3. [2]

    Combinatorial optimization in telecommunications

    Mauricio GC Resende. Combinatorial optimization in telecommunications. Optimization and industry: new frontiers, pages 59–112, 2003. doi:10.1007/978-1-4613- 0233-9_4

    doi:10.1007/978-1-4613- 2003

  4. [3]

    Real- time scheduling optimization considering the unex- pected events in home health care

    Gang Du, Luyao Zheng, and Xiaoling Ouyang. Real- time scheduling optimization considering the unex- pected events in home health care. Journal of Combinatorial Optimization, 37:196–220, 2019. doi: 10.1007/s10878-017-0220-3

    work page doi:10.1007/s10878-017-0220-3 2019

  5. [4]

    Mathematical mod- eling and optimization of industrial problems

    M Montaz Ali, Aderemi O Adewumi, Nachamada Blamah, and Olabisi Falowo. Mathematical mod- eling and optimization of industrial problems. Journal of Applied Mathematics, 2015, 2015. doi: 10.1155/2015/438471

    work page doi:10.1155/2015/438471 2015

  6. [5]

    Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev., 41:303–332, 1995. URLhttps: //api.semanticscholar.org/CorpusID:2337707

    1995

  7. [6]

    A quantum approximate optimization algo- rithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gut- mann. A quantum approximate optimization algo- rithm. arXiv preprint arXiv:1411.4028, 2014. doi: 10.1103/physreva.111.012427

    arXiv 2014

  8. [7]

    Quantum optimization: Po- tential, challenges, and the path forward.arXivpreprint arXiv:2312.02279, 2023

    Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J Egger, Bruce G Elmegreen, et al. Quantum optimization: Po- tential, challenges, and the path forward.arXivpreprint arXiv:2312.02279, 2023

    arXiv 2023

Show all 125 references
  1. [8]

    On the emerging potential of quantum anneal- ing hardware for combinatorial optimization

    Byron Tasseff, Tameem Albash, Zachary Morrell, Marc Vuffray, Andrey Y Lokhov, Sidhant Misra, and Carleton Coffrin. On the emerging potential of quantum anneal- ing hardware for combinatorial optimization. Journal of Heuristics, 30(5):325–358, 2024. doi:10.1007/s10732- 024-09530-5

    2024 doi

  2. [9]

    Quantum phases of matter on a 256-atom programmable quantum simulator

    Sepehr Ebadi, Tout T Wang, Harry Levine, Alexan- der Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, Hannes Pichler, Wen Wei Ho, et al. Quantum phases of matter on a 256-atom programmable quantum simulator. Nature, 595(7866): 227–232, 2021. doi:10.103...

    2021 doi

  3. [10]

    Graph algorithms with neutral atom quantum processors

    Constantin Dalyac, Lucas Leclerc, Louis Vignoli, Mehdi Djellabi, Wesley da Silva Coelho, Bruno Ximenez, Alexandre Dareau, Davide Dreon, VIncent E Elfv- ing, Adrien Signoles, et al. Graph algorithms with neutral atom quantum processors. arXiv preprint arXiv:2403.11931, 2024. do...

    2024 arXiv

  4. [11]

    Qualifying quantum ap- proaches for hard industrial optimization problems

    Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron, and Margarita Veshchezerova. Qualifying quantum ap- proaches for hard industrial optimization problems. a case study in the field of smart-charging of electric ve- hicles. EPJ Q...

    2021 doi

  5. [12]

    Find- ing the maximum independent sets of platonic graphs using rydberg atoms

    Andrew Byun, Minhyuk Kim, and Jaewook Ahn. Find- ing the maximum independent sets of platonic graphs using rydberg atoms. PRX Quantum, 3(3):030305,

  6. [13]

    Im- plementing transferable annealing protocols for combi- natorial optimisation on neutral atom quantum proces- sors: a case study on smart-charging of electric vehicles,

    Lucas Leclerc, Constantin Dalyac, Pascale Bendotti, Rodolphe Griset, Joseph Mikael, and Loïc Henriet. Im- plementing transferable annealing protocols for combi- natorial optimisation on neutral atom quantum proces- sors: a case study on smart-charging of electric vehicles,

  7. [14]

    Ising formulations of many np problems

    Andrew Lucas. Ising formulations of many np problems. Frontiers in physics, 2:5, 2014. doi: 10.3389/fphy.2014.00005

    2014

  8. [15]

    Quantum optimiza- tion for maximum independent set using rydberg atom arrays

    Hannes Pichler, Sheng-Tao Wang, Leo Zhou, Soon- won Choi, and Mikhail D Lukin. Quantum optimiza- tion for maximum independent set using rydberg atom arrays. arXiv preprint arXiv:1808.10816, 2018. doi: 10.26226/m.6275705c66d5dcf63a3115ad

    2018 arXiv

  9. [16]

    Dipole blockade and quantum infor- mation processing in mesoscopic atomic ensembles

    Mikhail D Lukin, Michael Fleischhauer, Robin Cote, LuMing Duan, Dieter Jaksch, J Ignacio Cirac, and Peter Zoller. Dipole blockade and quantum infor- mation processing in mesoscopic atomic ensembles. Physical review letters, 87(3):037901, 2001. doi: 12 10.1103/physrevlett.87.037901

    2001 doi

  10. [17]

    Many- body physics with individually controlled rydberg atoms

    Antoine Browaeys and Thierry Lahaye. Many- body physics with individually controlled rydberg atoms. Nature Physics, 16(2):132–142, 2020. doi: 10.1038/s41567-019-0733-z

    2020 doi

  11. [18]

    Quantum information with rydberg atoms

    Mark Saffman, Thad G Walker, and Klaus Mølmer. Quantum information with rydberg atoms. Reviews of modern physics, 82(3):2313–2363, 2010. doi: 10.1117/12.2519368

    2010 doi

  12. [19]

    Observation of rydberg blockade between two atoms.Nature Physics, 5(2):110–114, 2009

    E Urban, Todd A Johnson, T Henage, L Isenhower, DD Yavuz, TG Walker, and M Saffman. Observation of rydberg blockade between two atoms.Nature Physics, 5(2):110–114, 2009. doi:10.1038/nphys1178

    2009 doi

  13. [20]

    Tunable two-dimensional ar- rays of single rydberg atoms for realizing quantum ising models

    Henning Labuhn, Daniel Barredo, Sylvain Ravets, Syl- vain De Léséleuc, Tommaso Macrì, Thierry Lahaye, and Antoine Browaeys. Tunable two-dimensional ar- rays of single rydberg atoms for realizing quantum ising models. Nature, 534(7609):667–670, 2016. doi: 10.1038/nature18274

    2016 doi

  14. [21]

    A unit-disk graph is defined by the positions of nodes, where an edge exists between two nodes if the distance between them is less than a constant r, typically set tor = 1

    Note1. A unit-disk graph is defined by the positions of nodes, where an edge exists between two nodes if the distance between them is less than a constant r, typically set tor = 1

  15. [22]

    Rydberg quantum wires for maximum independent set problems.Nature Physics, 18(7):755–759, 2022

    Minhyuk Kim, Kangheun Kim, Jaeyong Hwang, Eun- Gook Moon, and Jaewook Ahn. Rydberg quantum wires for maximum independent set problems.Nature Physics, 18(7):755–759, 2022. doi:10.1038/s41567-022- 01629-5

    2022 doi

  16. [23]

    Quan- tum simulation of ising spins on platonic graphs.arXiv preprint arXiv:2203.01541, 2022

    Andrew Byun, Minhyuk Kim, and Jaewook Ahn. Quan- tum simulation of ising spins on platonic graphs.arXiv preprint arXiv:2203.01541, 2022. doi:10.1016/0550- 3213(94)90033-7

    2022 arXiv

  17. [24]

    Exploring the impact of graph locality for the resolution of the maximum-independent-set problem with neutral atom devices

    Constantin Dalyac, Louis-Paul Henry, Minhyuk Kim, Jaewook Ahn, and Loïc Henriet. Exploring the impact of graph locality for the resolution of the maximum-independent-set problem with neutral atom devices. Physical Review A, 108(5):052423, 2023. doi: 10.1103/physreva.108.052423

    2023 doi

  18. [25]

    Quantum optimization with arbitrary connectivity us- ing rydberg atom arrays.PRX Quantum, 4(1):010316,

    Minh-Thi Nguyen, Jin-Guo Liu, Jonathan Wurtz, Mikhail D Lukin, Sheng-Tao Wang, and Hannes Pichler. Quantum optimization with arbitrary connectivity us- ing rydberg atom arrays.PRX Quantum, 4(1):010316,

  19. [26]

    Rydberg-blockade-based parity quantum optimization

    Martin Lanthaler, Clemens Dlaska, Kilian Ender, and Wolfgang Lechner. Rydberg-blockade-based parity quantum optimization. Physical Review Letters, 130 (22):220601, 2023. doi:10.1103/physrevlett.130.220601

    2023 doi

  20. [27]

    Rydberg-atom graphs for quadratic un- constrained binary optimization problems

    Andrew Byun, Junwoo Jung, Kangheun Kim, Min- hyuk Kim, Seokho Jeong, Heejeong Jeong, and Jae- wook Ahn. Rydberg-atom graphs for quadratic un- constrained binary optimization problems. Advanced Quantum Technologies, 7(8):2300398, 2024. doi: 10.1002/qute.202300398

    2024 doi

  21. [28]

    Quantum programming of the satisfiability problem with rydberg atom graphs

    Seokho Jeong, Minhyuk Kim, Minki Hhan, JuYoung Park, and Jaewook Ahn. Quantum programming of the satisfiability problem with rydberg atom graphs. Physical Review Research, 5(4):043037, 2023. doi: 10.1103/physrevresearch.5.043037

    2023 doi

  22. [29]

    Quantum annealing: A new method for minimizing multidimensional functions

    Aleta Berk Finnila, Maria A Gomez, C Sebenik, Cather- ine Stenson, and Jimmie D Doll. Quantum annealing: A new method for minimizing multidimensional functions. Chemical physics letters, 219(5-6):343–348, 1994

    1994

  23. [30]

    Quantum annealinginthetransverseisingmodel

    Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealinginthetransverseisingmodel. PhysicalReview E, 58(5):5355, 1998

    1998

  24. [31]

    Quantum computation by adiabatic evolution

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. arXiv preprint quant-ph/0001106, 2000

    2000 arXiv

  25. [32]

    Theory of quantum annealing of an ising spin glass.Science, 295(5564):2427–2430, 2002

    Giuseppe E Santoro, Roman Martonák, Erio Tosatti, and Roberto Car. Theory of quantum annealing of an ising spin glass.Science, 295(5564):2427–2430, 2002

    2002

  26. [33]

    A quantum approximate optimization algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gut- mann. A quantum approximate optimization algorithm. ArXiv:1411.4028, art. arXiv:1411.4028, 11 2014. doi: 10.48550/ARXIV.1411.4028

    2014 doi arXiv

  27. [34]

    A review on quantum approximate optimization algorithm and its variants

    Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao- Hui Chou, Rui-Hao Li, Komal Pandya, and Alessan- dro Summer. A review on quantum approximate optimization algorithm and its variants. Physics Reports, 1068:1–66, 6 2024. ISSN 0370-1573. doi: 10.1016/j.physrep.2024.03.002

    2024 doi

  28. [35]

    Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices.Phys.Rev. X, 10: 021067, 6 2020. doi:10.1103/PhysRevX.10.021067

    2020 doi

  29. [36]

    Quantum optimization of maximum independent set using rydberg atom arrays.Science, 376(6598):1209– 1215, 2022

    Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, J-G Liu, Rhine Samajdar, et al. Quantum optimization of maximum independent set using rydberg atom arrays.Science, 376(6598):1209– 1215, 2022. doi:10.1126...

    2022 doi

  30. [37]

    Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization

    Benjamin F Schiffer, Dominik S Wild, Nishad Maskara, Madelyn Cain, Mikhail D Lukin, and Rhine Sama- jdar. Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization. Physical Review Research, 6(1):013271, 2024. doi: 10.1103/physrevresearch.6.013271

    2024 doi

  31. [39]

    Efficient subgraph-based sam- pling of ising-type models with frustration

    Alex Selby. Efficient subgraph-based sam- pling of ising-type models with frustration. arXiv preprint arXiv:1409.3934, 2014. doi: 10.1103/physrevb.63.224401

    2014 arXiv

  32. [40]

    Salvatore Mandra, Zheng Zhu, Wenlong Wang, Ale- jandro Perdomo-Ortiz, and Helmut G Katzgraber. Strengths and weaknesses of weak-strong cluster prob- lems: A detailed overview of state-of-the-art classical heuristics versus quantum approaches.Physical Review A, 94(2):022337, 20...

    2016 doi

  33. [41]

    Demonstration of a scaling advantage for a quantum annealer over simu- lated annealing

    Tameem Albash and Daniel A Lidar. Demonstration of a scaling advantage for a quantum annealer over simu- lated annealing. Physical Review X, 8(3):031016, 2018. doi:10.1103/physrevx.8.031016

    2018 doi

  34. [42]

    doi:10.1103/physrevresearch.5.043277

    doi

  35. [43]

    How many qubits are needed for quantum computational supremacy? Quantum, 4:264, 2020

    Alexander M Dalzell, Aram W Harrow, Dax Enshan Koh, and Rolando L La Placa. How many qubits are needed for quantum computational supremacy? Quantum, 4:264, 2020. doi:10.22331/q-2020-05-11-264. 13

    2020 doi

  36. [44]

    Seeking quantum speedup through spin glasses: The good, the bad, and the ugly

    Helmut G Katzgraber, Firas Hamze, Zheng Zhu, An- drew J Ochoa, and Humberto Munoz-Bauza. Seeking quantum speedup through spin glasses: The good, the bad, and the ugly. Physical Review X, 5(3):031026,

  37. [45]

    Probing for quantum speedup in spin-glass problems with planted solutions

    Itay Hen, Joshua Job, Tameem Albash, Troels F Røn- now, Matthias Troyer, and Daniel A Lidar. Probing for quantum speedup in spin-glass problems with planted solutions. Physical Review A, 92(4):042325, 2015. doi: 10.1103/physreva.92.042325

    2015 doi

  38. [46]

    Defining and detecting quantum speedup

    Troels F Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V Isakov, David Wecker, John M Mar- tinis, Daniel A Lidar, and Matthias Troyer. Defining and detecting quantum speedup. science, 345(6195): 420–424, 2014. doi:10.1126/science.1252319

    2014 doi

  39. [47]

    V24.1: User’s Manual for CPLEX

    IBM ILOG CPLEX. V24.1: User’s Manual for CPLEX. International Business Machines Corpora- tion, 2024. URLhttps://www.ibm.com/products/ilog- cplex-optimization-studio

    2024

  40. [48]

    Maximumindependentsetforinterval graphs and trees in space efficient models

    Binay K Bhattacharya, Minati De, Subhas C Nandy, andSasankaRoy. Maximumindependentsetforinterval graphs and trees in space efficient models. InCCCG,

  41. [49]

    freeman San Francisco, 1979

    Michael R Garey and David S Johnson.Computers and intractability, volume 174. freeman San Francisco, 1979. doi:10.1007/978-1-4612-0515-9_1

    1979 doi

  42. [50]

    A replica analysis of the travelling salesman problem

    Marc Mézard and Giorgio Parisi. A replica analysis of the travelling salesman problem. Journal de physique, 47(8):1285–1296, 1986. doi: 10.1051/jphys:019860047080128500

    1986 doi

  43. [51]

    Best-case per- formance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabil- ities

    Zheng Zhu, Andrew J Ochoa, Stefan Schnabel, Firas Hamze, and Helmut G Katzgraber. Best-case per- formance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabil- ities. Physical Review A, 93(1):012317, 2016. doi: 10.1103/physreva.93.012317

    2016 doi

  44. [52]

    Determining computational complexity from characteristic ‘phase transitions’

    Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, and Lidror Troyansky. Determining computational complexity from characteristic ‘phase transitions’. Nature, 400(6740):133–137, 1999. doi: 10.1038/22055

    1999 doi

  45. [53]

    Gibbs states and the set of solutions of random con- straint satisfaction problems

    Florent Krzakała, Andrea Montanari, Federico Ricci- Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random con- straint satisfaction problems. Proceedings of the National Academy of Sciences, 104(25):10318–10323,

  46. [54]

    Algo- rithmic barriers from phase transitions

    Dimitris Achlioptas and Amin Coja-Oghlan. Algo- rithmic barriers from phase transitions. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 793–802. IEEE, 2008. doi: 10.1109/focs.2008.11

    2008 doi

  47. [55]

    On in- dependent sets in random graphs.Random Structures & Algorithms, 47(3):436–486, 2015

    Amin Coja-Oghlan and Charilaos Efthymiou. On in- dependent sets in random graphs.Random Structures & Algorithms, 47(3):436–486, 2015. doi:10.1007/978-0- 387-30162-4_187

    2015 doi

  48. [56]

    Phase transitions in combinatorial optimization problems: basics, algorithms and statistical mechanics

    Alexander K Hartmann and Martin Weigt. Phase transitions in combinatorial optimization problems: basics, algorithms and statistical mechanics. John Wi- ley & Sons, 2006. doi:10.1016/s0304-3975(01)00149-9

    2006 doi

  49. [57]

    Application of statistical mechanics to np-complete problems in combinatorial optimisation

    Yaotian Fu and Philip W Anderson. Application of statistical mechanics to np-complete problems in combinatorial optimisation. Journal of Physics A: Mathematical and General, 19(9):1605, 1986. doi: 10.1142/9789812799371_0037

    1986 doi

  50. [58]

    Frozen development in graph coloring.Theoretical computer science, 265(1-2): 227–264, 2001

    Joseph Culberson and Ian Gent. Frozen development in graph coloring.Theoretical computer science, 265(1-2): 227–264, 2001. doi:10.1016/s0304-3975(01)00164-5

    2001 doi

  51. [59]

    A new look at the easy-hard-easy pattern of combinatorial search dif- ficulty

    Dorothy L Mammen and Tad Hogg. A new look at the easy-hard-easy pattern of combinatorial search dif- ficulty. Journal of Artificial Intelligence Research, 7: 47–66, 1997. doi:10.1613/jair.370

    1997 doi

  52. [60]

    Systematic generation of very hard cases for graph 3-colorability

    Romulus Dan Vlasie. Systematic generation of very hard cases for graph 3-colorability. In Proceedings of 7th IEEE International Conference on Tools with Artificial Intelligence, pages 114–119. IEEE, 1995. doi: 10.1109/tai.1995.479412

    1995

  53. [61]

    The very particular structure of the very hard instances

    Dan R Vlasie. The very particular structure of the very hard instances. In Proceedings of the thirteenth national conference on Artificial intelligence-Volume 1, pages 266–270, 1996. doi:10.1016/j.dam.2006.07.015

    1996 doi

  54. [62]

    Hajós and ore constructions for digraphs

    Jørgen Bang-Jensen, Thomas Bellitto, Michael Stiebitz, and Thomas Schweser. Hajós and ore constructions for digraphs. arXiv preprint arXiv:1908.04096, 2019. doi: 10.37236/8942

    1908 arXiv

  55. [63]

    La Sapienza

    Gianmaria Leo. Solving hard instances of maximum stable set problem by equitable partitions. PhD thesis, Università degli Studi di Roma" La Sapienza", 2013

    2013

  56. [64]

    The sat phase transition

    Ian P Gent and Toby Walsh. The sat phase transition. In ECAI, volume 94, pages 105–109. PITMAN, 1994. doi:10.1007/bf02917402

    1994 doi

  57. [65]

    Clique benchmark instances (web site), 1992

    DIMACS. Clique benchmark instances (web site), 1992. URL http://cs.hbg.psu.edu/txn131/clique.html. Ac- cessed: 2024-07-26

    1992

  58. [66]

    Practical engineering of hard spin-glass in- stances

    Jeffrey Marshall, Victor Martin-Mayor, and Itay Hen. Practical engineering of hard spin-glass in- stances. Physical review A, 94(1):012320, 2016. doi: 10.1103/physreva.94.012320

    2016 doi

  59. [67]

    Quantum speedup by quantum annealing

    Rolando D Somma, Daniel Nagaj, and Mária Kiefer- ová. Quantum speedup by quantum annealing. Physical review letters, 109(5):050501, 2012. doi: 10.1103/physrevlett.109.050501

    2012 doi

  60. [68]

    The potential of quantum annealing for rapid solution structure identification.Constraints, 26 (1):1–25, 2021

    Yuchen Pang, Carleton Coffrin, Andrey Y Lokhov, and Marc Vuffray. The potential of quantum annealing for rapid solution structure identification.Constraints, 26 (1):1–25, 2021. doi:10.1007/s10601-020-09315-0

    2021 doi

  61. [69]

    A scalable readout system for a su- perconducting adiabatic quantum optimization system

    AJ Berkley, MW Johnson, P Bunyk, R Harris, J Jo- hansson, T Lanting, E Ladizinsky, E Tolkacheva, MHS Amin, and G Rose. A scalable readout system for a su- perconducting adiabatic quantum optimization system. Superconductor ScienceandTechnology, 23(10):105014,

  62. [70]

    Approximation algorithms for unit disk graphs

    Erik Jan van Leeuwen. Approximation algorithms for unit disk graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 351–361. Springer, 2005. doi:10.1007/11604686_31

    2005 doi

  63. [71]

    Neil J. A. Sloane. Challenge problems: Indepen- dent sets in graphs. URLhttps://oeis.org/A265032/ a265032.html. Accessed: 2024-07-26

    2024

  64. [72]

    Ap- plications of a planar separator theorem

    Richard J Lipton and Robert Endre Tarjan. Ap- plications of a planar separator theorem. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 162–170. IEEE, 1977. doi: 10.1137/0209046

    1977 doi

  65. [73]

    A framework for eth-tight algorithms and lower bounds in geometric intersection graphs

    Mark de Berg, Hans L Bodlaender, Sándor Kisfaludi- Bak, Dániel Marx, and Tom C van der Zanden. A framework for eth-tight algorithms and lower bounds in geometric intersection graphs. In Proceedings 14 of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 574–58...

    2018

  66. [74]

    An object is said to be α-fat if the ratio be- tween its circumscribed radius and inscribed radius is at most α

    Note2. An object is said to be α-fat if the ratio be- tween its circumscribed radius and inscribed radius is at most α. Intuitively, an α-fat object cannot be ex- cessively elongated or thin. A set of objects is said to be similarly-sized if the ratio between the diameters of ...

  67. [75]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. ISBN 978-3-319-21274-6. doi:10.1007/978-3-319-21275-3. URLhttps://doi.org/ 10.1007/978-3-319-21275-3

    2015 doi

  68. [76]

    van Leeuwen

    E.J. van Leeuwen. Optimization Problems on Mobile Ad Hoc Networks – Algorithms for Disk Graphs. PhD thesis, Master’s Thesis INF/SCR-04-32, Inst. of Infor- mation and Computing Sciences, Utrecht Univ., 2004

    2004

  69. [77]

    Clique is hard to approximate within n 1- varepsilon

    Johan Håstad. Clique is hard to approximate within n 1- varepsilon. Acta Math., 182(1):105–142, 1999. doi: 10.1007/bf02392825

    1999 doi

  70. [78]

    Approxima- tionschemesforcoveringandpackingproblemsinimage processing and vlsi

    Dorit S Hochbaum and Wolfgang Maass. Approxima- tionschemesforcoveringandpackingproblemsinimage processing and vlsi. Journal of the ACM (JACM), 32 (1):130–136, 1985. doi:10.1145/2455.214106

    1985

  71. [79]

    Linear time algorithms for np-hard problems restricted to partial k- trees

    Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for np-hard problems restricted to partial k- trees. Discrete applied mathematics, 23(1):11–24, 1989. doi:10.1016/0166-218x(89)90031-0

    1989 doi

  72. [80]

    Optimization and approximation on systems of geometric objects

    Erik Jan van Leeuwen et al. Optimization and approximation on systems of geometric objects. Uni- versiteit van Amsterdam [Host], 2009. doi:10.1007/978- 1-4471-0495-7_26

    2009 doi

  73. [81]

    to appear

    Pierre Cazals et al. to appear. doi: 10.7767/9783205201731

    doi

  74. [82]

    Antiferromagnetism

    GH0038 Wannier. Antiferromagnetism. the triangular ising net. Physical Review, 79(2):357, 1950

    1950

  75. [83]

    Impact-parameter selective rydberg atom collision by optical tweez- ers

    Hansub Hwang, Sunhwa Hwang, Jaewook Ahn, Shuhei Yoshida, and Joachim Burgdorfer. Impact-parameter selective rydberg atom collision by optical tweez- ers. arXiv preprint arXiv:2412.06225, 2024. doi: 10.1016/s0065-2539(08)60109-2

    2024 arXiv

  76. [84]

    Ex- ploring network structure, dynamics, and function using networkx

    Aric Hagberg, Pieter J Swart, and Daniel A Schult. Ex- ploring network structure, dynamics, and function using networkx. 2008. doi:10.25080/tcwv9851

    2008 doi

  77. [85]

    Branch-and- bound methods: A survey.Operations research, 14(4): 699–719, 1966

    Eugene L Lawler and David E Wood. Branch-and- bound methods: A survey.Operations research, 14(4): 699–719, 1966. doi:10.1287/opre.14.4.699

    1966 doi

  78. [86]

    Syn- thetic three-dimensional atomic structures assembled atom by atom

    Daniel Barredo, Vincent Lienhard, Sylvain De Lese- leuc, Thierry Lahaye, and Antoine Browaeys. Syn- thetic three-dimensional atomic structures assembled atom by atom. Nature, 561(7721):79–82, 2018. doi: 10.1038/s41586-018-0450-2

    2018 doi

  79. [87]

    Eptas and subexponential algorithm for maximum clique on disk and unit ball graphs

    Marthe Bonamy, Édouard Bonnet, Nicolas Bous- quet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora, and Stéphan Thomassé. Eptas and subexponential algorithm for maximum clique on disk and unit ball graphs. Journal of the ACM (JACM), 68(2):1–38...

    2021 doi

  80. [88]

    Quantum computing with neu- tral atoms.Quantum, 4:327, 2020

    Loïc Henriet, Lucas Beguin, Adrien Signoles, Thierry Lahaye, Antoine Browaeys, Georges-Olivier Reymond, and Christophe Jurczak. Quantum computing with neu- tral atoms.Quantum, 4:327, 2020. doi:10.22331/q-2020- 09-21-327

    2020 doi

  81. [89]

    Morgado and S

    M. Morgado and S. Whitlock. Quantum simula- tion and computing with Rydberg-interacting qubits. AVS Quantum Science, 3(2):023501, 6 2021. doi: 10.1116/5.0036562

    2021 doi

  82. [90]

    Bé guin, A

    L. Bé guin, A. Vernier, R. Chicireanu, T. La- haye, and A. Browaeys. Direct measurement of the van der waals interaction between two rydberg atoms. Phys. Rev. Lett., 110(26), 6 2013. doi: 10.1103/physrevlett.110.263201

    2013 doi

  83. [91]

    Šibalić, J.D

    N. Šibalić, J.D. Pritchard, C.S. Adams, and K.J. Weatherill. ARC: An open-source library for calcu- lating properties of alkali rydberg atoms. Computer Physics Communications, 220:319–331, 11 2017. doi: 10.1016/j.cpc.2017.06.015

    2017 doi

  84. [92]

    pasqal- io/emulators: v1.2.4, 2024

    Anton Quelle, Pablo Le Hénaff, Mauro Mendiza- bal, Stefano Grava, Elie Merhej, Mauro Mendizábal, Aleksander Wennersteen, and David Teller. pasqal- io/emulators: v1.2.4, 2024

    2024

  85. [93]

    Half-minute- scale atomic coherence and high relative stability in a tweezer clock

    Aaron W Young, William J Eckner, William R Milner, Dhruv Kedar, Matthew A Norcia, Eric Oelker, Nathan Schine, Jun Ye, and Adam M Kaufman. Half-minute- scale atomic coherence and high relative stability in a tweezer clock. Nature, 588(7838):408–413, 2020. doi: https://doi.org/1...

    2020 doi

  86. [94]

    Continuous operation of large- scale atom arrays in optical lattices, 2024

    Flavien Gyger, Maximilian Ammenwerth, Renhao Tao, Hendrik Timme, et al. Continuous operation of large- scale atom arrays in optical lattices, 2024

    2024

  87. [95]

    Nogrette, H

    F. Nogrette, H. Labuhn, S. Ravets, D. Barredo, L. B ’eguin, A. Vernier, T. Lahaye, and A. Browaeys. Single- atom trapping in holographic 2d arrays of microtraps with arbitrary geometries. Phys. Rev. X, 4:021034, 5

  88. [96]

    doi:10.1103/PhysRevX.4.021034

    doi

  89. [97]

    Advances in cryogenic avalanche detectors

    A Buzulutskov. Advances in cryogenic avalanche detectors. Journal of Instrumentation, 7(02): C02025–C02025, 2012. ISSN 1748-0221. doi: 10.1088/1748-0221/7/02/c02025

    2012 doi

  90. [98]

    A tweezer array with 6100 highly coherent atomic qubits

    Hannah J Manetsch, Gyohei Nomura, Elie Bataille, Kon H Leung, Xudong Lv, and Manuel Endres. A tweezer array with 6100 highly coherent atomic qubits. arXiv preprint arXiv:2403.12021, 2024

    2024 arXiv

  91. [99]

    Scaling advantage in approximate optimization with quantum annealing

    Humberto Munoz Bauza and Daniel A Lidar. Scaling advantage in approximate optimization with quantum annealing. arXiv preprint arXiv:2401.07184, 2024

    2024 arXiv

  92. [100]

    Microwave engineering of programmable xxz hamiltoni- ans in arrays of rydberg atoms.PRX Quantum, 3(2): 020303, 2022

    Pascal Scholl, Hannah J Williams, Guillaume Bornet, Florian Wallner, Daniel Barredo, L Henriet, Adrien Sig- noles, Clément Hainaut, Titus Franz, S Geier, et al. Microwave engineering of programmable xxz hamiltoni- ans in arrays of rydberg atoms.PRX Quantum, 3(2): 020303, 2022....

    2022

  93. [101]

    Three- dimensional rearrangement of single atoms using ac- tively controlled optical microtraps.Optics express, 24 (9):9816–9825, 2016

    Woojun Lee, Hyosub Kim, and Jaewook Ahn. Three- dimensional rearrangement of single atoms using ac- tively controlled optical microtraps.Optics express, 24 (9):9816–9825, 2016. 15

    2016

  94. [102]

    A quantum processor based on coherent transport of entangled atom arrays

    Dolev Bluvstein, Harry Levine, Giulia Semeghini, Tout T Wang, Sepehr Ebadi, Marcin Kalinowski, Alexander Keesling, Nishad Maskara, Hannes Pichler, Markus Greiner, et al. A quantum processor based on coherent transport of entangled atom arrays. Nature, 604(7906):451–456, 2022

    2022

  95. [103]

    Mitigation of readout noise in near-term quan- tum devices by classical post-processing based on detec- tor tomography.Quantum, 4:257, 2020

    Filip B Maciejewski, Zoltán Zimborás, and Michał Osz- maniec. Mitigation of readout noise in near-term quan- tum devices by classical post-processing based on detec- tor tomography.Quantum, 4:257, 2020. doi:10.22331/q- 2020-04-24-257. URL https://quantum-journal.org/ papers/q-...

    2020 doi

  96. [104]

    Efficient algorithms to solve atom reconfiguration problems

    Barry Cimring, Remy El Sabeh, Marc Bacvanski, Stephanie Maaz, et al. Efficient algorithms to solve atom reconfiguration problems. i. redistribution- reconfiguration algorithm. Phys. Rev. A, 108(2), 2023. ISSN 2469-9934. doi:10.1103/physreva.108.023107

    2023 doi

  97. [105]

    Klinkhamer, Jan Hendrik Becher, Ralf Klemt, et al

    Andrea Bergschneider, Vincent M. Klinkhamer, Jan Hendrik Becher, Ralf Klemt, et al. Spin- resolved single-atom imaging of 6li in free space. Phys. Rev. A, 97(6), 2018. ISSN 2469-9934. doi: 10.1103/physreva.97.063613

    2018 doi

  98. [106]

    On an annihilation number conjecture

    Vadim E Levit and Eugen Mandrescu. On an annihilation number conjecture. arXiv preprint arXiv:1811.04722, 2018. doi:10.26493/1855- 3974.1950.8bd

    2018 arXiv

  99. [107]

    Graphs with equal independence and annihilation numbers.the electronic journal of combinatorics, pages P180–P180, 2011

    Craig E Larson and Ryan Pepper. Graphs with equal independence and annihilation numbers.the electronic journal of combinatorics, pages P180–P180, 2011. doi: 10.37236/667

    2011 doi

  100. [108]

    Survey of algorithms on maximum clique problem

    Krishna Kumar Singh and Ajeet Kumar Pandey. Survey of algorithms on maximum clique problem. International Advanced Research Journal in Science, Engineering and Technology, 2(2):18–20, 2015. doi: 10.17148/iarjset.2015.2203. 16 Appendix A: Maximum Independent Set problem formula...

    2015

  101. [113]

    Bounds for the independence number of a graph

    William Willis. Bounds for the independence number of a graph. Master thesis, Virginia Commonwealth Uni- versity, 2011

    2011

  102. [114]

    The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks.IEEE Journal on Selected Areas in Communications, 22(6): 1069–1079, 2004

    Hari Balakrishnan, Christopher L Barrett, VS Anil Ku- mar, Madhav V Marathe, and Shripad Thite. The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks.IEEE Journal on Selected Areas in Communications, 22(6): 1069–1079, 2004. ...

    2004

  103. [118]

    IV we, so called, native instances of the neutral atoms quantum platforms with different system sizesN and densities ρ considered

    Generation of the native instances In Sec. IV we, so called, native instances of the neutral atoms quantum platforms with different system sizesN and densities ρ considered. To this end, we start from a selected pre-calibrated layout of the quantum platform, corresponding to a...

  104. [119]

    false negatives

    Annealing schedule As discussed in the main text, we employed quantum annealing for solving the MWIS problem. It entails preparing an initial state with high fidelity and evolving it adiabatically towards the state that encodes the target solution. In our case, this is obtaine...

    2000

  105. [120]

    • Nodes excluded from the matching are weighted based on their degree: w(v) = 0.1 × (deg(v) + 1), (F1) where deg(v) denotes the degree of nodev

    Matching-based weightingIn this method: • Nodes included in the matching receive a weight of 1. • Nodes excluded from the matching are weighted based on their degree: w(v) = 0.1 × (deg(v) + 1), (F1) where deg(v) denotes the degree of nodev. The objective here is to introduce s...

  106. [121]

    Unlike classical matching, where each node belongs to at most one matched edge, 2-distance matching ensures that matched edges are not adjacent

    2-distancematching-basedweighting Themaximum2-distancematchingproblem[105]extendstheclassical matching problem by enforcing a stricter adjacency constraint. Unlike classical matching, where each node belongs to at most one matched edge, 2-distance matching ensures that matched...

  107. [122]

    • Other nodes receive: w(v) = 1000 × (deg(v) + 1)

    Degree-based weightingIn this method: • Nodes with the minimum degree receive a weight of 0.1. • Other nodes receive: w(v) = 1000 × (deg(v) + 1). (F2)

  108. [123]

    In this weighting scheme, nodes belonging to the annihilation set receive a high weight of1000, while all other nodes are assigned a small weight of0.1

    Annihilation-based weightingThe annihilation number [106, 107] is the largest integerk such that: kX i=1 deg(vi) ≤ |E|, (F3) where deg(vi) denotes the degree of nodevi (i.e., the number of edges incident tovi), and|E| is the total number of edges in the graph. In this weightin...

  109. [124]

    Its ILP formulation is: Maximize X i∈V xi Subject to xi + xj ≤ 1 ∀(i, j) /∈ E, xi ∈ {0, 1} ∀i ∈ V

    Maximum clique-based weightingThe maximum clique problem [108] seeks to identify the largest complete subgraph, where every pair of nodes is connected by an edge. Its ILP formulation is: Maximize X i∈V xi Subject to xi + xj ≤ 1 ∀(i, j) /∈ E, xi ∈ {0, 1} ∀i ∈ V. In this method,...

  110. [125]

    It is defined as: CC(v) = n − 1P u∈V d(v, u) , (F4) where: – d(v, u) is the shortest path distance between nodesv and u

    Graph centrality-based weighting • Closeness centralityThe closeness centrality of a nodev quantifies how close it is to all other nodes in the graph, based on shortest path distances. It is defined as: CC(v) = n − 1P u∈V d(v, u) , (F4) where: – d(v, u) is the shortest path di...

  111. [2007]

    doi:10.1073/pnas.0703685104

    doi

  112. [2010]

    doi:10.1088/0953-2048/23/10/105014

    doi

  113. [2014]

    doi:10.2139/ssrn.1968428

    doi

  114. [2015]

    doi:10.1103/physrevx.5.031026

    doi

  115. [2022]

    doi:10.1103/prxquantum.3.030305

    doi

  116. [2023]

    doi:10.1103/prxquantum.4.010316

    doi

  117. [2024]

    URL https://arxiv.org/abs/2411.16656

    arXiv

Pith tools

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