Encoding Circuit Satisfiability in Rydberg Atom Arrays

Haotian Ji, Zhangjie Qin, Zheng An, Bowen Yan, Daoheng Niu, Kunzhe Dai, Jingkai Fang, Dongyang Cao, Jiangyu Cui

arXivarxiv/2608.12938Aug 13, 2026quant-phscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2608.12938
curl -X POST /api/v1/records/arxiv/2608.12938/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.12938/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'