Pith. sign in

REVIEW 2 major objections 5 minor 44 references

Encoding Circuit Satisfiability in Rydberg Atom Arrays

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

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

Pith's one-line read Circuit-SAT maps straight to Rydberg atoms, cutting atom cost 22-fold.

desk verdict A genuinely new gate-level compiler from Circuit-SAT to weighted king-subgraph MWIS, with a proved composition theorem and exact ground-state verification on three sizes; the genuine soft spots are missing code/data and an unvalidated hard-blockade assumption in the annealing simulation. read the letter →

arxiv 2608.12938 v1 pith:Z4RMXL7Z submitted 2026-08-13 quant-ph

Haotian Ji , Zhangjie Qin , Zheng An , Bowen Yan , Daoheng Niu , Kunzhe Dai , Jingkai Fang , Dongyang Cao
show 1 more author
Jiangyu Cui
This is my paper · ORCID
classification quant-ph
keywords Circuit-SATRydbergatomarraysmaximumweightindependentsetkingsubgraphgadgetencodingVLSIplacementandroutingquantumannealingcombinationalequivalencechecking
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

This paper tries to establish that Boolean circuit satisfiability can be encoded natively on a Rydberg atom array without the usual intermediate step of a conjunctive normal form formula. The proposed compilation, CAMERA, replaces each logic gate with a small weighted king-subgraph gadget, routes wires with a VLSI-style placement and routing compiler, and proves that the maximum-weight independent sets of the resulting graph project exactly onto the rows of the circuit truth table. The atom-count payoff is large: across random circuits of three to eight gates the direct encoding uses, on average, $22.4 \pm 1.8$ times fewer atoms than the CNF-mediated route, and exact ground-state checks on an 85-atom full adder and a 165-atom two-bit multiplier reproduce their complete truth tables. If the construction holds up, Rydberg arrays become reconfigurable logic blocks that can decide a Circuit-SAT instance with one weighted independent-set optimization on a branched graph.

What carries the argument

The load-bearing object is the weighted king-subgraph gadget: a small cluster of atoms with weights in $\{1,2\}$ whose maximum-weight independent sets realize the truth table of a Boolean primitive. The library contains AND, OR, NOT, XOR gates plus fan-out, crossing, and variable-length wire gadgets, all found by an automated exhaustive search and certified minimal within the searched class. Composition happens through clean pin amalgamation, meaning identified pins sum their weights and no unintended edges are introduced; Theorem 1 shows this preserves the truth relation exactly. The branching primitive, which pins a bit by deleting either the vertex to force 0 or its closed neighborhood to force 1, is the operation that turns the graph into a SAT decider. A placement-and-routing compiler using history-based rerouting and simulated annealing on a king grid produces blockade-valid layouts while keeping every atom weight in $\{1,2\}$, so only two local detuning values are needed.

What would settle it

Compile a known satisfiable and a known unsatisfiable circuit, branch the output port, and run exact classical MWIS on both the full and branched graphs: if any maximum-weight independent set of the full graph projects to a row outside the circuit truth table, or if satisfiable instances fail to satisfy $W^{\star} - W_{\mathrm{br}} = w_O$ while unsatisfiable instances satisfy it, Theorem 1 falls. A hardware test would measure the final-state weight distribution after the 4$\mu$s pulse on the 30-atom layout and check whether the most probable weight is $W^{\star}=23$ for the full graph and $W_{\mathrm{br}}=22$ for the branched graph; a systematic shortfall would indicate residual interactions or detuning errors beyond the hard-blockade model.

Watch

Extended reading notes

Core claim

The paper's central claim is that the MWIS manifold of the compiled weighted king subgraph is the truth table of the circuit: port projections of the maximum-weight independent sets are exactly the rows $(x, F_C(x))$ of the circuit (Eq. 4), and the optimal weight is the sum of the constituent gadget optima. Deciding satisfiability then reduces to one branching operation: deleting the output port and the atoms it blockades, solving the MWIS on the reduced graph, and comparing the branched optimum $W_{\mathrm{br}}$ with the reference $W^{\star}$; the instance is satisfiable exactly when $W^{\star} - W_{\mathrm{br}} = w_O$ (Eq. 5), in which case the input-port occupations of the branched optimum spell a satisfying assignment, while a strict deficit certifies unsatisfiability. The same compiled graph evaluates the circuit forward when input ports are pinned instead, and mixed pinning answers general constraint queries. The authors verify the equivalence exactly through exhaustive enumeration on the 30-atom three-gate circuit, the 85-atom full adder, and the 165-atom two-bit multiplier, and they report that a closed-system tensor-network simulation of a 4$\mu$s annealing protocol reaches the MWIS manifold in 58.0% of projective samples on the three-gate instance.

Load-bearing premise

The hardware must operate in the hard-blockade limit, where atoms within a fixed radius interact strongly and all farther pairs do not interact at all; any residual interaction beyond that radius, or any deviation in the local detunings, breaks the exact equality between the array's ground state and the compiled graph's maximum-weight independent set.

Editorial extensions

If this is right

  • Circuit-SAT instances of a few gates fit comfortably on current Rydberg arrays: the three-gate circuit, full adder, and two-bit multiplier compile to 30, 85, and 165 atoms, versus 1257, 2563, and 5060 atoms through the CNF chain.
  • A single compiled layout can be reused for several tasks at runtime: pinning the inputs evaluates the circuit, pinning the output inverts it and extracts a witness, and pinning a mixed subset of ports poses general constraint queries, all without re-layout.
  • The output-branching test gives an exact UNSAT certificate only when $W_{\mathrm{br}}$ is a proven optimum; with analog hardware samples, persistent failure to reach the satisfiable reference weight is the operational signature of unsatisfiability.
  • For typical structured feed-forward circuits the atom cost grows nearly linearly with gate count, while the worst case remains quadratic with a much smaller constant than the CNF baseline.
  • A 4$\mu$s annealing pulse on the compiled three-gate instance reaches the exact ground-state manifold in 58.0% of 1000 projective samples, and 54.6% on the branched certificate graph, indicating the encoded optima are dynamically accessible under a hardware-compatible schedule.

Reading between the lines

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

  • An extension the authors leave implicit: the same exhaustive gadget search could be run for NAND, NOR, XNOR, or multi-input gates, potentially shrinking circuits that currently require several composed library gates and reducing routing overhead further.
  • The near-linear atom scaling for structured feed-forward circuits suggests that circuits with dozens of gates could be compiled onto near-term arrays; whether annealing dynamics still concentrate on the MWIS manifold at that size is an open empirical question the paper does not resolve.
  • Because the branching criterion is exact only for certified optima, a practical hardware protocol would collect many shots and compare the full weight histogram against $W^{\star}$ and $W_{\mathrm{br}}$, turning the equality test into a statistical check rather than a single-sample certificate.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper introduces CAMERA, a compiler that maps gate-level Boolean circuits to maximum-weight independent set (MWIS) problems on king-subgraph geometries suitable for Rydberg atom arrays. Each logic gate and routing primitive is represented by a small weighted gadget, and gadgets are composed through clean pin amalgamations. The main theorems state that the port projections of the MWIS manifold of the compiled graph coincide with the circuit truth table (Eq. 4), and that branching the output port gives a satisfiability criterion based on comparing the branched optimum with the reference weight (Eq. 5). The authors validate the construction by exact ground-state enumeration of a 30-atom three-gate circuit, an 85-atom full adder, and a 165-atom two-bit multiplier; benchmark atom counts against a CNF-mediated encoding; and simulate a 4-microsecond annealing protocol for the 30-atom instance.

Significance. If the encoding and the physical mapping hold, this is a useful and well-structured reduction: it preserves circuit topology, uses only two detuning values, yields a parameter-free reference weight, and reduces atom overhead substantially relative to the CNF route. The paper's strengths are the composition-theoretic proofs in the Supplemental Material, the exact exhaustive verification of all compiled instances against their complete truth tables, and the explicit unit-weight gaps that exclude incorrect port projections. The main limitations are that the placement-and-routing compiler is heuristic, the physical correspondence to Rydberg hardware is asserted only in the hard-blockade limit, and the annealing simulation does not specify whether residual van der Waals interactions were included. These issues are local and addressable, but they affect the strength of the practical claims.

major comments (2)
  1. [Sec. III C; Algorithms S2-S3] The paper's practical claim requires the Rydberg ground state to be exactly the MWIS of the compiled king graph, but this correspondence is established only in the hard-blockade limit. The compiled instances have a unit weight gap between correct and incorrect port projections (Supplemental Tables S2 and S4), while the physical Hamiltonian retains a van der Waals tail V_ij = C6/d^6 for all pairs. Residual interactions beyond the nominal blockade radius can shift energies by an amount comparable to one weight unit when the nearest-neighbor interaction is chosen large enough to enforce blockade, so they can in principle select a spurious port projection and break Eq. (4) on real hardware. The tensor-network annealing simulation of Sec. IV D does not state whether the simulated Hamiltonian included the full C6 tail or truncated interactions at the blockade radius; if it truncated, the 58% success rate gives no evidence about residual-tail robustness, and if it included the tail, a single 30-atom instance is too narrow a test. I ask the authors to simulate the three compiled instances with the full interaction tail, report the resulting gap between the correct and spurious manifolds, and either quantify the robustness of the encoding or restrict the hardware-facing claims accordingly.
  2. [Sec. III C; Algorithms S2-S3] Theorem 1 is conditional on the compiler producing a layout that satisfies the clean edge condition, but the placement-and-routing pipeline of Sec. III C is a heuristic search (simulated annealing, A* routing, PathFinder rerouting, and greedy descent) with no termination or completeness guarantee. The paper presents CAMERA as an automatic route from a gate-level netlist to a blockade-valid layout, so the absence of any characterization of compilation success is load-bearing for the claimed generality. Please add either a completeness/termination result for a suitable class of circuits, or an explicit statement that the compiler is heuristic together with empirical success statistics on a larger set of netlists.
minor comments (5)
  1. [Sec. III C] The sentence 'The clean edge condition of Sec.S4' contains a broken cross-reference; it should refer to Definition S4 or Section SI of the Supplemental Material.
  2. [Fig. 1 caption] The phrase 'combinational equivalence checking by amiter' should read 'by a miter'.
  3. [Sec. IV A] The two quadratic fits are based on only six median values each, and the text itself notes that the gadget medians are nearly as consistent with linear growth; the coefficient comparison (2.29 versus 51.1) should be presented as an empirical description of the sampled window rather than as a structural scaling law.
  4. [Sec. IV D] The tensor-network simulation should report its numerical parameters, including bond dimension, time step, and truncation error, and should state explicitly whether the full van der Waals tail was included in the simulated Hamiltonian.
  5. [Supplemental Secs. SVI-SVII] The exact enumeration of the 85- and 165-atom graphs by a column-transfer dynamic program is mentioned but not described; please provide the method details or release the code so that the reported counts and gap values can be reproduced.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central derivation is a proved composition theorem over independently verified gadget contracts, with no fitted parameter renamed as a prediction.

full rationale

The paper's central claims are Theorem 1 (Eq. 4), that the MWIS port projections of the compiled king subgraph equal the circuit truth table, and Theorem 2 (Eq. 5), that the output-branching weight difference decides satisfiability. Both are proved in the Supplemental Material from the gadget contracts (Eq. S4), the clean-amalgamation composition rules (Definition S4), and the classical branching identity (Eq. 3). The gadget contracts themselves are not assumed as predictions: each AND, OR, XOR, NOT, crossing, and fan-out realization is verified by exhaustive enumeration of all maximal independent sets (Sec. SII), independently of the automated-search methodology cited as Ref. [28], which is not authored by the present paper's authors. The multi-gate instances (30-atom three-gate circuit, 85-atom full adder, 165-atom multiplier) are verified by exact ground-state enumeration against their complete truth tables, so the reported truth-table readouts are independent checks rather than quantities fitted to enforce those outcomes. The atom-count comparison against the CNF route is a benchmark measurement, not a prediction derived from the encoding. The hard-blockade assumption is a stated physical modeling idealization; it limits the practical claim but does not make the derivation circular, because the graph-theoretic theorems and their exact enumerations are valid on the compiled weighted king graphs regardless of the physical realization. No load-bearing self-citation, imported uniqueness theorem, or ansatz-smuggling-through-citation was found, and no 'prediction' reduces by construction to an input fit.

Assumptions & free parameters 7 free parameters · 4 assumptions · 0 invented entities

The construction rests on gadget weight vectors found by combinatorial search (free parameters) and on the hard-blockade and compiler-validation assumptions (axioms). No new physical entities are introduced.

free parameters (7)
  • AND gadget weights = (1,1,1,1,2,2)
    Selected by the automated integer-program search so the four maximal independent sets at weight 3 realize the AND truth table; minimality certified by exhaustive polyplet enumeration.
  • OR gadget weights = (1,1,1,1,1,2)
    Selected so the four maximal independent sets realize the OR truth table; certified minimal by exhaustive search.
  • XOR gadget weights = (1,1,1,2,2,2,2,2,2)
    Selected so the four maximal independent sets at weight 6 realize XOR with a unit gap; nine atoms certified minimal.
  • Crossing gadget weights = (1,1,1,1,2,2,2,2,2,2,2)
    Selected so the four maximal independent sets realize the crossing relation with a unit gap; eleven atoms certified minimal for genuine crossings.
  • Fan-out gadget weights = (1,1,1,2,1)
    Selected so the two maximal independent sets realize the equality relation on three pins; five atoms certified minimal under the binary weight alphabet.
  • Wire chain weights = endpoints 1, interiors 2
    Chosen so an odd-length chain realizes the equality relation with a unit gap; the parity rule is required by the composition theorem.
  • Annealing pulse parameters = Omega/2pi=2 MHz, Delta/2pi=7.6 MHz, 4 microsecond sweep
    Chosen to match existing Rydberg platforms for the simulation in Sec. IV D; not part of the encoding correctness claim.
assumptions (4)
  • domain assumption Hard-blockade limit: atoms closer than the blockade radius cannot be simultaneously excited and atoms farther apart have no interaction.
    Invoked in Sec. II B to identify the ground state of the driven array with the MWIS of the compiled king graph. Standard in Rydberg optimization but an idealization that fails in the presence of residual van der Waals interactions.
  • domain assumption The exhaustive polyplet enumeration and the integer-program gadget search are complete and correct.
    Used in Sec. SII to certify gadget minimality and to generate the weight vectors; the paper verifies the enumeration against the known polyomino census but does not provide formal machine-checked proofs.
  • domain assumption The compiler's validator correctly checks the clean edge condition and wire parity.
    Theorem 1 applies only to validated layouts; the paper does not prove the validator is sound, but the exact ground-state checks on compiled instances provide evidence.
  • standard math MWIS is NP-hard on unit disk graphs.
    Cited from Ref. [32] to argue that the geometric restriction to king subgraphs does not reduce expressive power.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Encoding Circuit Satisfiability in Rydberg Atom Arrays." pith.science (2026). https://pith.science/paper/Z4RMXL7Z

@misc{pith2026260812938,
  author       = {Pith},
  title        = {Pith review of: Encoding Circuit Satisfiability in Rydberg Atom Arrays},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z4RMXL7Z}},
  note         = {Machine review of arXiv:2608.12938}
}
abstract

Rydberg atom arrays natively encode the maximum-weight independent set (MWIS) problem through the blockade mechanism, so the Boolean circuit satisfiability problem (Circuit-SAT) can be brought onto the platform once it is reduced to MWIS. The conventional encoding of Circuit-SAT in the Rydberg atom array proceeds through conjunctive normal form (CNF) and incurs a substantial atom overhead. We introduce CAMERA (Circuit-SAT Atom-efficient MWIS Encoding for Rydberg Arrays), a method that provides MWIS encodings of Circuit-SAT instances on the king subgraph geometry of the array. CAMERA represents each logic gate as a compact weighted gadget and assembles the gadgets with a placement and routing compiler inspired by very large scale integration (VLSI) design. On random multi-gate benchmarks, the direct encoding route lowers the atom cost relative to the CNF route by an average factor of $22.4 \pm 1.8$. To demonstrate that the encoding extends from individual weighted gadgets to multi-gate arithmetic blocks, we compile a full adder and a multiplier, verifying each against its complete truth table by exact classical ground state calculations. We further showcase solving a representative Circuit-SAT instance end-to-end, from gate level compilation through a closed-system tensor-network simulation of a hardware-compatible annealing protocol on the encoded 30-atom instance to readout of a satisfying assignment. These results establish a complete encoding and simulation workflow as a proof of principle, and a concrete route toward solving a broader family of combinatorial problems on Rydberg atom arrays.

Figures

Figures reproduced from arXiv: 2608.12938 by the authors.

Figure 1
Figure 1. FIG. 1. Overview of the encoding framework, from an electronic-design consistency check to a Rydberg native MWIS problem. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Atom cost of the conventional CNF route (red) and [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3. End-to-end compilation and solution of the multi-gate Circuit-SAT instance [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: FIG. 4. Detecting unsatisfiability from the compiled king subgraph, for the minimal unsatisfiable instance [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5. Compilation of multi gate arithmetic blocks into weighted king subgraphs by the automated pipeline. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 25 canonical work pages

  1. [1]

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

    work page 2022

  2. [2]

    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)

    2023

  3. [3]

    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

  4. [4]

    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]

    arXiv 2024

  5. [5]

    Bombieri, Z

    L. Bombieri, Z. Zeng, R. Tricarico, R. Lin, S. Notarni- cola, M. Cain, M. D. Lukin, and H. Pichler, Quantum adiabatic optimization with Rydberg arrays: Localiza- tion phenomena and encoding strategies, PRX Quantum 6, 020306 (2025)

    work page 2025

  6. [6]

    Pichler, S.-T

    H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Quantum optimization for maximum independent set using Rydberg atom arrays (2018), arXiv:1808.10816 [quant-ph]

    arXiv 2018

  7. [7]

    Saffman, T

    M. Saffman, T. G. Walker, and K. Mølmer, Quantum information with Rydberg atoms, Reviews of Modern Physics82, 2313 (2010)

    2010

  8. [8]

    Browaeys and T

    A. Browaeys and T. Lahaye, Many-body physics with individually controlled Rydberg atoms, Nature Physics 16, 132 (2020)

    2020

Show all 44 references
  1. [9]

    Bernien, S

    H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Om- ran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, V. Vuleti´ c, and M. D. Lukin, Probing many- body dynamics on a 51-atom quantum simulator, Nature 551, 579 (2017)

    2017

  2. [10]

    Ebadi, T

    S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Se- meghini, A. Omran, D. Bluvstein, R. Samajdar, H. Pich- ler, W. W. Ho, S. Choi, S. Sachdev, M. Greiner, V. Vuleti´ c, and M. D. Lukin, Quantum phases of matter on a 256-atom programmable quantum simulator, Nature 595, 227 (2021)

    2021

  3. [11]

    Scholl, M

    P. Scholl, M. Schuler, H. J. Williams, I. Cong, S. Tan, D. Barredo, S. Choi, H. Pichler, M. D. Lukin, and M. Aidelsburger, Quantum simulation of two- dimensional antiferromagnets with hundreds of Rydberg atoms, Nature595, 233 (2021)

    2021

  4. [12]

    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 en- tangled atom arrays, Nature604, 451 (2022)

    2022

  5. [13]

    Bluvstein, S

    D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, H. Pichler, S. Choi, and M. D. Lukin, Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2024)

    2024

  6. [14]

    H. J. Manetsch, G. Nomura, E. Bataille, K. H. Leung, X. Lv, and M. Endres, A tweezer array with 6100 highly coherent atomic qubits, Nature647, 60 (2025)

    2025

  7. [15]

    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, Qua...

    2022

  8. [16]

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

    2022

  9. [17]

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

    2024

  10. [18]

    A. M. Farouk, I. I. Beterov, P. Xu, and I. I. Ryabtsev, Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs us- ing Rydberg atoms, Phys. Rev. A110, 022442 (2024)

    2024

  11. [19]

    H. Yeo, H. E. Kim, and K. Jeong, Approximating maxi- mum independent set on Rydberg atom arrays using local detunings, Adv. Quantum Technol.8, 2400291 (2025)

    2025

  12. [20]

    M. Cain, S. Chattopadhyay, J.-G. Liu, R. Samajdar, H. Pichler, and M. D. Lukin, Quantum speedup for combinatorial optimization with flat energy landscapes (2023), arXiv:2306.13123 [quant-ph]

    2023 arXiv

  13. [21]

    R. S. Andrist, M. J. A. Schuetz, P. Minssen, R. Yalovet- zky, 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, Physica...

    2023

  14. [22]

    S. A. Cook, The complexity of theorem-proving proce- dures, inProceedings of the 3rd Annual ACM Symposium on Theory of Computing(ACM, 1971) pp. 151–158

    1971

  15. [23]

    R. M. Karp, Reducibility among combinatorial prob- lems, inComplexity of Computer Computations, edited by R. E. Miller, J. W. Thatcher, and J. D. Bohlinger (Springer, Boston, MA, 1972) pp. 85–103

    1972

  16. [24]

    Li, G.-H

    X.-W. Li, G.-H. Li, and M. Shao, Formal verification techniques based on boolean satisfiability problem, Jour- nal of Computer Science and Technology20, 38 (2005)

    2005

  17. [25]

    G. S. Tseitin, On the complexity of derivation in propo- sitional calculus, inAutomation of Reasoning: Classi- cal Papers in Computational Logic 1967–1970, edited by J. Siekmann and G. Wrightson (Springer, Berlin, Heidel- berg, 1983) pp. 466–483

    1967

  18. [26]

    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, Physical Review Research5, 043037 (2023)

    2023

  19. [27]

    Angkhanawin, A

    T. Angkhanawin, A. Deger, J. D. Pritchard, and C. S. Adams, Graph coloring via quantum optimization on a Rydberg-qudit atom array, Quantum Science and Tech- nology11, 025012 (2026)

    2026

  20. [28]

    Pan, H.-H

    X.-W. Pan, H.-H. Zhou, Y.-M. Lu, and J.-G. Liu, En- coding computationally hard problems in triangular Ry- dberg atom arrays (2025), arXiv:2510.25249 [quant-ph]

    2025

  21. [29]

    Jaksch, J

    D. Jaksch, J. I. Cirac, P. Zoller, S. L. Rolston, R. Cˆ ot´ e, and M. D. Lukin, Fast quantum gates for neutral atoms, Physical Review Letters85, 2208 (2000)

    2000

  22. [30]

    M. D. Lukin, M. Fleischhauer, R. Cote, L. M. Duan, D. Jaksch, J. I. Cirac, and P. Zoller, Dipole blockade and quantum information processing in mesoscopic atomic ensembles, Physical Review Letters87, 037901 (2001)

    2001

  23. [31]

    Levine, A

    H. Levine, A. Keesling, A. Omran, H. Bernien, S. Schwartz, A. S. Zibrov, M. Endres, M. Greiner, V. Vuleti´ c, and M. D. Lukin, High-fidelity control and entanglement of Rydberg-atom qubits, Physical Review Letters121, 123603 (2018)

    2018

  24. [32]

    B. N. Clark, C. J. Colbourn, and D. S. Johnson, Unit disk graphs, Discrete Mathematics86, 165 (1990). 13

    1990

  25. [33]

    R. E. Tarjan and A. E. Trojanowski, Finding a maxi- mum independent set, SIAM Journal on Computing6, 537 (1977)

    1977

  26. [34]

    F. V. Fomin and D. Kratsch,Exact Exponential Algo- rithms(Springer, Berlin, Heidelberg, 2010)

    2010

  27. [35]

    P. E. Hart, N. J. Nilsson, and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics 4, 100 (1968)

    1968

  28. [36]

    McMurchie and C

    L. McMurchie and C. Ebeling, PathFinder: A negotiation-based performance-driven router for FPGAs, inProceedings of the Third International ACM Sympo- sium on Field-Programmable Gate Arrays (FPGA ’95) (1995) pp. 111–117

    1995

  29. [37]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimiza- tion by simulated annealing, Science220, 671 (1983)

    1983

  30. [38]

    Metropolis, A

    N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, Equation of state calculations by fast computing machines, The Journal of Chemical Physics21, 1087 (1953)

    1953

  31. [39]

    Wurtz, A

    J. Wurtz, A. Bylinskii, B. Braverman, J. Amato-Grill, S. H. Cantu, F. Huber, A. Lukin, F. Liu, P. Wein- berg, J. Long, S.-T. Wang, N. Gemelke, and A. Keesling, Aquila: QuEra’s 256-qubit neutral-atom quantum com- puter (2023), arXiv:2306.11727 [quant-ph]

    2023 arXiv

  32. [40]

    Hutton,The Ruby interpreter, Research Report 72 (Chalmers University of Technology, G¨ oteborg, Sweden, 1993)

    G. Hutton,The Ruby interpreter, Research Report 72 (Chalmers University of Technology, G¨ oteborg, Sweden, 1993)

    1993

  33. [41]

    D. I. Spivak, The operad of wiring diagrams: formalizing a graphical language for databases, recursion, and plug- and-play circuits (2013), arXiv:1305.0297 [cs.DB]

    2013 arXiv

  34. [42]

    Encoding Circuit Satisfiability in Rydberg Atom Arrays

    A. B. Kahn, Topological sorting of large networks, Com- munications of the ACM5, 558 (1962). 14 Supplemental Material for “Encoding Circuit Satisfiability in Rydberg Atom Arrays” SI. COMPOSITION THEORY OF THE GADGET ENCODING This section develops the composition theory behind ...

    1962

  35. [43]

    Second, the weights must be equal: a scan over (w x,wy)∈{1,2,3} 2 confirms that the two rows tie exactly when wx =w y, and unit weights suffice, so NOT costs no weight-2 atom. Third, the gadget is trivially optimal in every metric of Table S1: two atoms is the minimum conceiva...

  36. [44]

    Its single deviation from the port budget is the pinp 1, which is king-adjacent to the three auxiliary atomsa,f,g

    The eleven-atom gadget is therefore the lightest genuine crossing and the only one compatible with the two-value weight alphabet of the library. Its single deviation from the port budget is the pinp 1, which is king-adjacent to the three auxiliary atomsa,f,g. G. Fan-out gadget...

Pith tools

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