Metraipolis › archive › dc_f768e2ee960e

Graph-Aware Exact Branch-and-Bound with Device Profiles for Static Qubit Allocation — arXiv:2608.04058

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.04058
License (as archived): CC0-1.0
Archived: 2026-10-31T12:01:39.169Z
SHA-256 of the archived text: 5978575298d4b68ff3db6d28d264e3c4c9b7dba6916a69e228fe257972d6ccd5
Stable URL of this page: https://metraipolis.com/documento/dc_f768e2ee960e

How to cite

Graph-Aware Exact Branch-and-Bound with Device Profiles for Static Qubit Allocation — arXiv:2608.04058 — arXiv (en), https://arxiv.org/abs/2608.04058 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f768e2ee960e (Metraipolis archive dc_f768e2ee960e, sha256 5978575298d4b68ff3db6d28d264e3c4c9b7dba6916a69e228fe257972d6ccd5)

BibTeX

@misc{dcf768e2ee960e,
  title = {Graph-Aware Exact Branch-and-Bound with Device Profiles for Static Qubit Allocation — arXiv:2608.04058},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.04058},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f768e2ee960e; sha256 5978575298d4b68ff3db6d28d264e3c4c9b7dba6916a69e228fe257972d6ccd5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04058. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Static qubit allocation maps a circuit's logical qubits to a sparse physical device while minimising an interaction-weighted physical-distance cost function, yielding a rectangular quadratic assignment problem. Existing work combines strong lower bounds with distributed branch-and-bound. We integrate graph-aware exact reductions with an engineering bundle for a lightweight assignment-bound path: unavoidable assigned-cost filtering, incrementally maintained root-orbit and prefix-stabilizer symmetry pruning, conditioned parent-LAP screening, and circuit-independent physical device profiles. On 21 relatively easy Melbourne instances and six Boeblingen instances completed by the GLB baseline, the final single-thread configuration provides geometric-mean speedups of 2.98x and 13.27x, respectively. With 60 threads on one shared-memory server, all instances in the final Boeblingen--Cairo experiment are certified optimal within half an hour, excluding one-time device-artifact construction. These results show that graph-aware node processing and engineering the search process substantially reduce the resources required for exact allocation.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-08-06 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2608.04058 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T11:50:18.149Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).