pith. sign in

arxiv: 2410.14955 · v2 · submitted 2024-10-19 · 🪐 quant-ph

Quantum imaginary time evolution and UD-MIS problem

Victor A. Penas , Marcelo Losada , Pedro W. Lamberti This is my paper

Pith reviewed 2026-05-23 19:20 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum imaginary time evolutionunit-disk maximum independent setfailure probabilityquantum optimizationqubit graph instancesnumerical simulations
0
0 comments X

The pith

Quantum imaginary time evolution solves unit-disk maximum independent set instances on 6-10 qubit graphs with low failure probability that decreases with shots.

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

The paper applies a quantum imaginary time evolution procedure to the unit-disk maximum independent set problem. Simulations on 6, 8 and 10 qubit graph instances show the failure probability stays relatively small and drops rapidly as the number of shots grows. A theoretical upper bound on failure probability is also derived. A sympathetic reader would care because this offers a concrete quantum route to a combinatorial optimization task that appears in network design and resource allocation, using only standard measurement shots rather than complex error correction.

Core claim

A procedure based on quantum imaginary time evolution can be applied to solve the unit-disk maximum independent set problem. Numerical simulations on 6, 8 and 10-qubit graph instances establish that the failure probability remains relatively small and decreases rapidly with the number of shots, while a theoretical upper bound on the failure probability of the procedure can be obtained.

What carries the argument

Quantum imaginary time evolution procedure adapted to encode unit-disk maximum independent set instances on qubit graphs.

If this is right

  • The procedure produces relatively small failure probabilities on the tested 6-10 qubit UD-MIS instances.
  • Failure probability decreases rapidly as the number of shots is increased.
  • A theoretical upper bound on failure probability exists for the procedure.
  • The approach works for unit-disk graphs encoded directly into the qubit register.

Where Pith is reading between the lines

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

  • The observed scaling with shot count implies that hardware runs could reach high success rates using only moderate numbers of circuit executions.
  • The derived bound supplies a tool for estimating reliability before running larger instances.
  • Similar encodings could let the same evolution method address other graph-based constraint problems without changing the core algorithm.

Load-bearing premise

The quantum imaginary time evolution procedure can be directly applied to unit-disk maximum independent set instances encoded on 6-10 qubit graphs such that the reported failure probabilities and bound hold.

What would settle it

Performing the procedure on a 6-qubit unit-disk maximum independent set instance and measuring a failure probability that fails to decrease with added shots or exceeds the stated theoretical upper bound would falsify the central findings.

Figures

Figures reproduced from arXiv: 2410.14955 by Marcelo Losada, Pedro W. Lamberti, Victor A. Penas.

Figure 1
Figure 1. Figure 1: FIG. 1. Examples of UD-MIS graphs consisting of 6 (a), 8 (b) and 10 (c) qubits. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Error and fidelity results for the 6-qubit graph instance of Fig. 1a for different domains. (a) and (c) depict plots of [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Failure probability for 6-qubit graph (Fig 1a). (a) [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Failure probability ( [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. (a) and (b) show normalized histograms of obtained eigenvalues for 6-qubit graphs, with number of shots [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Error and fidelity results for the 8-qubit graph instance of Fig. 1b for different domains. (a) and (c) depict plots [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. Failure probability for 8-qubit graph (Fig 1b). (a) [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. Failure probability ( [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9. (a) and (b) show normalized histograms of obtained eigenvalues for 8-qubit graphs, with number of shots [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FIG. 10. Error and fidelity results for the 10-qubit graph instance of Fig. 1c for different domains. (a) and (c) depict plots [PITH_FULL_IMAGE:figures/full_fig_p016_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: FIG. 11. Failure probability for 10-qubit graph (Fig 1c). (a) [PITH_FULL_IMAGE:figures/full_fig_p016_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: FIG. 12. Failure probability ( [PITH_FULL_IMAGE:figures/full_fig_p017_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: FIG. 13. (a) and (b) show normalized histograms of obtained eigenvalues for 6-qubit graphs, with number of shots [PITH_FULL_IMAGE:figures/full_fig_p017_13.png] view at source ↗
read the original abstract

In this work we apply a procedure based on the quantum imaginary time evolution method to solve the unit-disk maximum independent set problem. Numerical simulations were performed for instances of 6, 8 and 10-qubits graphs. We have found that the failure probability of the procedure is relatively small and rapidly decreases with the number of shots. In addition, a theoretical upper bound for the failure probability of the procedure was obtained.

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.

Referee Report

2 major / 0 minor

Summary. The manuscript applies a quantum imaginary time evolution (QITE) procedure to solve unit-disk maximum independent set (UD-MIS) instances. It reports numerical simulations on 6-, 8-, and 10-qubit graphs in which the failure probability is relatively small and decreases rapidly with the number of shots, together with a theoretical upper bound on that failure probability.

Significance. If the numerical results and bound are reproducible, the work provides a concrete demonstration that QITE can be mapped to the UD-MIS penalty Hamiltonian on small graphs and yields shot-scalable success rates. The existence of an analytic bound is a positive feature that could guide further analysis. Because the system sizes remain classically simulable, the immediate impact on quantum advantage is modest, but the approach is a useful proof-of-concept for imaginary-time methods in combinatorial optimization.

major comments (2)
  1. [Abstract] Abstract: the central numerical claims (failure probabilities for 6/8/10-qubit instances and their scaling with shots) are stated without any description of the graph instances chosen, the explicit penalty Hamiltonian, the QITE implementation details (time-step size, Trotterization or approximation scheme, number of steps), the success criterion for an independent set, or the statistical procedure used to estimate failure probability from finite shots. These omissions make the reported probabilities and their shot dependence impossible to verify from the given text.
  2. [Abstract] Abstract: the theoretical upper bound on failure probability is asserted but no derivation, assumptions, or proof outline is supplied. Because the bound is presented as an independent theoretical result supporting the numerical findings, its derivation steps are load-bearing and must be provided.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback on the abstract. We agree that additional details are needed for reproducibility and will revise the abstract (and, where appropriate, the main text) to address both points. Below we respond to each major comment.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central numerical claims (failure probabilities for 6/8/10-qubit instances and their scaling with shots) are stated without any description of the graph instances chosen, the explicit penalty Hamiltonian, the QITE implementation details (time-step size, Trotterization or approximation scheme, number of steps), the success criterion for an independent set, or the statistical procedure used to estimate failure probability from finite shots. These omissions make the reported probabilities and their shot dependence impossible to verify from the given text.

    Authors: We agree that the abstract is too concise and omits information required to verify the numerical results. In the revised manuscript we will expand the abstract to include: (i) the specific families of 6-, 8- and 10-qubit unit-disk graphs considered, (ii) the explicit form of the penalty Hamiltonian used to encode the UD-MIS objective, (iii) the QITE parameters (imaginary-time step size, total number of steps, and whether a first-order Trotter or other approximation is applied), (iv) the success criterion (a measured bit-string is counted as successful only if it encodes a valid maximum independent set), and (v) the statistical procedure (failure probability is estimated from the fraction of shots that fail the success criterion, with binomial confidence intervals). These additions will make the reported probabilities and their shot scaling directly verifiable from the abstract. revision: yes

  2. Referee: [Abstract] Abstract: the theoretical upper bound on failure probability is asserted but no derivation, assumptions, or proof outline is supplied. Because the bound is presented as an independent theoretical result supporting the numerical findings, its derivation steps are load-bearing and must be provided.

    Authors: The derivation of the upper bound appears in the main text, but we accept that the abstract provides no outline of its assumptions or proof strategy. In the revision we will append a single sentence to the abstract that states the key assumptions (the QITE evolution projects onto the ground-state manifold of the penalty Hamiltonian with a gap that grows with the penalty strength, and the measurement is performed after a fixed imaginary time) and sketches the proof (the failure probability is bounded by the norm of the component of the evolved state orthogonal to the ground subspace, which is controlled by the imaginary-time propagator). If the main-text derivation is judged insufficiently detailed, we will also expand that section. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper applies standard QITE to UD-MIS instances on 6-10 qubit graphs, reports empirical failure probabilities from direct simulation, and states a theoretical upper bound on failure probability. No equations reduce a claimed prediction or bound to a fitted parameter defined from the same data; no self-citation is invoked as the sole justification for a uniqueness or ansatz step; the mapping and measurement statistics are standard and externally verifiable. The central results remain independent of the reported numerics.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; full manuscript would be required to audit them.

pith-pipeline@v0.9.0 · 5587 in / 1068 out tokens · 38755 ms · 2026-05-23T19:20:20.194951+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

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

53 extracted references · 53 canonical work pages

  1. [1]

    0⟩, where H⊗N is the Hadamard gate acting on each qubit

    We start with an initial state |ψ0⟩ = H⊗N |0 . . .0⟩, where H⊗N is the Hadamard gate acting on each qubit. In terms of the eigenvectors basis of H, the initial state has the form |ψ0⟩ = 1√ d Pd−1 i=0 |Ei⟩

    work page

  2. [2]

    Then, we apply the QITE operator up to a time tmax: |ψ0⟩ → | ϕqite tmax ⟩ = QH(τ, nmax, D)|ψ0⟩, (11) where tmax, τ, and D should be chosen according to the particular problem, and nmax = tmax/τ

    work page

  3. [3]

    We register the M outputs Eim, with 1 ≤ m ≤ M

    We measure |ϕqite t ⟩ M times (M number of shots) in the computational basis, with M << d . We register the M outputs Eim, with 1 ≤ m ≤ M. 4

    work page

  4. [4]

    Independent Sets

    Finally, with a classical computer, we choose from the M outputs Eim the one with less energy. The general idea of the method is the following. When applying QITE operator Q H(τ, nmax, D) to the initial state |ψ0⟩, as nmax grows, it is expected to obtain a superposition of eigenstates of H with higher probabilities for the eigenstates with the smallest ei...

    work page

  5. [5]

    It should be noted that for all iterations we have ε(t) ≤ √ 2, satisfying hypothesis of Thm. 2. For a better comparison, we have plotted the fidelity between both states in Fig. 2c. Fig. 2d shows convergence of QITE state to |ψite tmax ⟩ as the domain dimension and the number of iterations increase. Regarding the chosen domains, we find that DB performs b...

    work page

  6. [6]

    As in the case of 6-qubit graphs, we obtained that DB performs better than DA in matching the ITE state for large number of iterations

    Results for 8-qubits graphs In this section we present the results for random graphs of 8 qubits. As in the case of 6-qubit graphs, we obtained that DB performs better than DA in matching the ITE state for large number of iterations. However,DA performs well enough in terms of the failure probability. Again, we obtained that the failure probability decrea...

    work page

  7. [7]

    In this case we only consider 10 random graphs due to the numerical complexity of the calculations

    Results for 10-qubits graphs In this section we show the results for random graphs of 10 qubits. In this case we only consider 10 random graphs due to the numerical complexity of the calculations. As in the other cases, DA performs well enough in terms of the failure probability, but DB performs better than DA in matching the ITE state for large number of...

    work page

  8. [8]

    A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem,

    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,” Science, vol. 292, p. 472–475, Apr. 2001

    work page 2001

  9. [9]

    Colloquium: Quantum annealing and analog quantum computation,

    A. Das and B. K. Chakrabarti, “Colloquium: Quantum annealing and analog quantum computation,” Reviews of Modern Physics, vol. 80, p. 1061–1081, Sept. 2008

    work page 2008

  10. [10]

    A quantum approximate optimization algorithm,

    E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” 2014

    work page 2014

  11. [11]

    A variational eigenvalue solver on a photonic quantum processor,

    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 Communications, vol. 5, July 2014

    work page 2014

  12. [12]

    Variational quantum algorithms,

    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 algorithms,” Nature Reviews Physics, vol. 3, p. 625–644, Aug. 2021

    work page 2021

  13. [13]

    The variational quantum eigensolver: A review of methods and best practices,

    J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, I. Rungger, G. H. Booth, and J. Tennyson, “The variational quantum eigensolver: A review of methods and best practices,” Physics Reports, vol. 986, p. 1–128, Nov. 2022

    work page 2022

  14. [14]

    Barren plateaus in quantum neural network training landscapes,

    J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, “Barren plateaus in quantum neural network training landscapes,” Nature Communications, vol. 9, Nov. 2018

    work page 2018

  15. [15]

    Variational ansatz-based quantum simulation of imaginary time evolution,

    S. McArdle, T. Jones, S. Endo, Y. Li, S. C. Benjamin, and X. Yuan, “Variational ansatz-based quantum simulation of imaginary time evolution,” npj Quantum Information , vol. 5, Sept. 2019

    work page 2019

  16. [16]

    Making trotters sprint: A variational imaginary time ansatz for quantum many-body systems,

    M. J. S. Beach, R. G. Melko, T. Grover, and T. H. Hsieh, “Making trotters sprint: A variational imaginary time ansatz for quantum many-body systems,” Physical Review B, vol. 100, Sept. 2019

    work page 2019

  17. [17]

    Cooling with imaginary time,

    P. J. Love, “Cooling with imaginary time,” Nature Physics, vol. 16, p. 130–131, Feb. 2020

    work page 2020

  18. [18]

    Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution,

    M. Motta, C. Sun, A. T. K. Tan, M. J. O’Rourke, E. Ye, A. J. Minnich, F. G. S. L. Brand˜ ao, and G. K.-L. Chan, “Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution,” Nature Physics, vol. 16, p. 205–210, Nov. 2019

    work page 2019

  19. [19]

    Implementation of quantum imaginary-time evolution method on nisq devices by introducing nonlocal approximation,

    H. Nishi, T. Kosugi, and Y.-i. Matsushita, “Implementation of quantum imaginary-time evolution method on nisq devices by introducing nonlocal approximation,” npj Quantum Information , vol. 7, June 2021

    work page 2021

  20. [20]

    Leveraging randomized compiling for the quantum imaginary-time-evolution algorithm,

    J.-L. Ville, A. Morvan, A. Hashim, R. K. Naik, M. Lu, B. Mitchell, J.-M. Kreikebaum, K. P. O’Brien, J. J. Wallman, I. Hincks, J. Emerson, E. Smith, E. Younis, C. Iancu, D. I. Santiago, and I. Siddiqi, “Leveraging randomized compiling for the quantum imaginary-time-evolution algorithm,” Physical Review Research, vol. 4, Aug. 2022

    work page 2022

  21. [21]

    Quantum imaginary time evolution steered by reinforcement learning,

    C. Cao, Z. An, S.-Y. Hou, D. L. Zhou, and B. Zeng, “Quantum imaginary time evolution steered by reinforcement learning,” Communications Physics, vol. 5, Mar. 2022

    work page 2022

  22. [22]

    Real- and imaginary-time evolution with compressed quantum circuits,

    S.-H. Lin, R. Dilip, A. G. Green, A. Smith, and F. Pollmann, “Real- and imaginary-time evolution with compressed quantum circuits,” PRX Quantum, vol. 2, p. 010342, Mar 2021

    work page 2021

  23. [23]

    Quantum simulations of molecular systems with intrinsic atomic orbitals,

    S. Barison, D. E. Galli, and M. Motta, “Quantum simulations of molecular systems with intrinsic atomic orbitals,” Physical Review A, vol. 106, Aug. 2022

    work page 2022

  24. [24]

    Practical quantum computation of chemical and nuclear energy levels using quantum imaginary time evolution and lanczos algorithms,

    K. Yeter-Aydeniz, R. C. Pooser, and G. Siopsis, “Practical quantum computation of chemical and nuclear energy levels using quantum imaginary time evolution and lanczos algorithms,” npj Quantum Inf , vol. 6, p. 63, July 2020

    work page 2020

  25. [25]

    Digital quantum simulation of open quantum systems using quantum imaginary–time evolution,

    H. Kamakari, S.-N. Sun, M. Motta, and A. J. Minnich, “Digital quantum simulation of open quantum systems using quantum imaginary–time evolution,” PRX Quantum, vol. 3, Feb. 2022

    work page 2022

  26. [26]

    Solving maxcut with quantum imaginary time evolution,

    R. Alam, G. Siopsis, R. Herrman, J. Ostrowski, P. Lotshaw, and T. Humble, “Solving maxcut with quantum imaginary time evolution,” Quantum Inf Process, vol. 22, p. 281, Jul 2023

    work page 2023

  27. [27]

    Combinatorial optimization with quantum imaginary time evolution,

    N. M. Bauer, R. Alam, G. Siopsis, and J. Ostrowski, “Combinatorial optimization with quantum imaginary time evolution,” Phys. Rev. A , vol. 109, p. 052430, May 2024

    work page 2024

  28. [28]

    Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices,

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, “Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices,” Physical Review X, vol. 10, June 2020

    work page 2020

  29. [29]

    Lower bounds on circuit depth of the quantum approximate optimization algorithm,

    J. Ostrowski, R. Herrman, T. S. Humble, and G. Siopsis, “Lower bounds on circuit depth of the quantum approximate optimization algorithm,” 2020

    work page 2020

  30. [30]

    Classical symmetries and the quantum approximate optimization algorithm,

    R. Shaydulin, S. Hadfield, T. Hogg, and I. Safro, “Classical symmetries and the quantum approximate optimization algorithm,” Quantum Information Processing, vol. 20, Oct. 2021

    work page 2021

  31. [31]

    Classical variational simulation of the quantum approximate optimization algorithm,

    M. Medvidovi´ c and G. Carleo, “Classical variational simulation of the quantum approximate optimization algorithm,”npj Quantum Information, vol. 7, June 2021

    work page 2021

  32. [32]

    Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer,

    L. Zhu, H. L. Tang, G. S. Barron, F. A. Calderon-Vargas, N. J. Mayhall, E. Barnes, and S. E. Economou, “Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer,” Phys. Rev. Res., vol. 4, p. 033029, Jul 2022

    work page 2022

  33. [33]

    Multi-angle quantum approximate optimization algorithm,

    R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis, “Multi-angle quantum approximate optimization algorithm,” Scientific Reports, vol. 12, p. 6781, Apr 2022

    work page 2022

  34. [34]

    Qaoa for max-cut requires hundreds of qubits for quantum speed-up,

    G. G. Guerreschi and A. Y. Matsuura, “Qaoa for max-cut requires hundreds of qubits for quantum speed-up,” Scientific Reports, vol. 9, May 2019

    work page 2019

  35. [35]

    Unsupervised machine learning on a hybrid quantum computer,

    J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. S. Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, C. A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, R. S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, B. R. Johnson, M. Reagor, M...

    work page 2017

  36. [36]

    Quantum optimization for maximum independent set using rydberg atom arrays,

    H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, “Quantum optimization for maximum independent set using rydberg atom arrays,” 2018

    work page 2018

  37. [37]

    Robustness to spontaneous emission of a variational quantum algorithm,

    L. Henriet, “Robustness to spontaneous emission of a variational quantum algorithm,” Physical Review A , vol. 101, Jan. 2020

    work page 2020

  38. [38]

    Quantum optimization of maximum independent set using rydberg atom arrays,

    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 independent set using rydberg atom arrays,” Scienc...

    work page 2022

  39. [39]

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

    R. S. Andrist, M. J. A. Schuetz, P. Minssen, R. Yalovetzky, S. Chakrabarti, D. Herman, N. Kumar, G. Salton, R. Shaydulin, Y. Sun, M. Pistoia, and H. G. Katzgraber, “Hardness of the maximum-independent-set problem on unit-disk graphs and prospects for quantum speedups,” Phys. Rev. Res., vol. 5, p. 043277, Dec 2023

    work page 2023

  40. [40]

    Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm,

    D. Lykov, J. Wurtz, C. Poole, M. Saffman, T. Noel, and Y. Alexeev, “Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm,” npj Quantum Information , vol. 9, July 2023

    work page 2023

  41. [41]

    Approximating maximum independent set on rydberg atom arrays using local detun- ings,

    H. Yeo, H. E. Kim, and K. Jeong, “Approximating maximum independent set on rydberg atom arrays using local detun- ings,” 2024

    work page 2024

  42. [42]

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

    C. Dalyac, L.-P. Henry, M. Kim, J. Ahn, and L. Henriet, “Exploring the impact of graph locality for the resolution of the maximum- independent-set problem with neutral atom devices,” Phys. Rev. A , vol. 108, p. 052423, Nov 2023

    work page 2023

  43. [43]

    Quantum computing with neutral atoms,

    L. Henriet, L. Beguin, A. Signoles, T. Lahaye, A. Browaeys, G.-O. Reymond, and C. Jurczak, “Quantum computing with neutral atoms,” Quantum, vol. 4, p. 327, Sept. 2020

    work page 2020

  44. [44]

    Quantum computing with rydberg atom graphs,

    M. Kim, J. Ahn, Y. Song, J. Moon, and H. Jeong, “Quantum computing with rydberg atom graphs,” Journal of the Korean Physical Society, vol. 82, pp. 827–840, May 2023

    work page 2023

  45. [45]

    Tunable two-dimensional arrays of single rydberg atoms for realizing quantum ising models,

    H. Labuhn, D. Barredo, S. Ravets, S. de L´ es´ eleuc, T. Macr` ı, T. Lahaye, and A. Browaeys, “Tunable two-dimensional arrays of single rydberg atoms for realizing quantum ising models,” Nature, vol. 534, p. 667–670, June 2016

    work page 2016

  46. [46]

    Synthetic three-dimensional atomic structures assembled atom by atom,

    D. Barredo, V. Lienhard, S. de L´ es´ eleuc, T. Lahaye, and A. Browaeys, “Synthetic three-dimensional atomic structures assembled atom by atom,” Nature, vol. 561, p. 79–82, Sept. 2018

    work page 2018

  47. [47]

    Solving optimization problems with rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks,

    M. F. Serret, B. Marchand, and T. Ayral, “Solving optimization problems with rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks,” Physical Review A , vol. 102, Nov. 2020

    work page 2020

  48. [48]

    Hromkoviˇ c,Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approxima- tion, and Heuristics

    J. Hromkoviˇ c,Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approxima- tion, and Heuristics . Springer Berlin, Heidelberg, 2004

    work page 2004

  49. [49]

    Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs,

    T. Matsui, “Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs,” in Discrete and Computational Geometry (J. Akiyama, M. Kano, and M. Urabe, eds.), (Berlin, Heidelberg), pp. 194–200, Springer Berlin Heidelberg, 2000

    work page 2000

  50. [50]

    Efficient independent set approximation in unit disk graphs,

    G. K. Das, G. D. da Fonseca, and R. K. Jallu, “Efficient independent set approximation in unit disk graphs,” Discrete Applied Mathematics, vol. 280, pp. 63–70, 2020. Algorithms and Discrete Applied Mathematics (CALDAM 2016)

    work page 2020

  51. [51]

    Approximation algorithms for unit disk graphs,

    E. J. van Leeuwen, “Approximation algorithms for unit disk graphs,” in Graph-Theoretic Concepts in Computer Science (D. Kratsch, ed.), (Berlin, Heidelberg), pp. 351–361, Springer Berlin Heidelberg, 2005

    work page 2005

  52. [52]

    Shifting coresets: Obtaining linear-time approxi- mations for unit disk graphs and other geometric intersection graphs,

    G. D. da Fonseca, V. G. a. Pereira de S´ a, and C. M. H. de Figueiredo, “Shifting coresets: Obtaining linear-time approxi- mations for unit disk graphs and other geometric intersection graphs,” International Journal of Computational Geometry & Applications, vol. 27, no. 04, pp. 255–276, 2017

    work page 2017

  53. [53]

    A robust ptas for maximum weight independent sets in unit disk graphs,

    T. Nieberg, J. Hurink, and W. Kern, “A robust ptas for maximum weight independent sets in unit disk graphs,” in Graph-Theoretic Concepts in Computer Science (J. Hromkoviˇ c, M. Nagl, and B. Westfechtel, eds.), (Berlin, Heidelberg), pp. 214–221, Springer Berlin Heidelberg, 2005

    work page 2005