Exact Diagonal Completion on Reachable Subspaces: Application to QAOA Placement

Abstract:Unused encoding states offer opportunities to simplify quantum circuits. For algorithms restricted to reachable subspaces, unspecified diagonal-operator entries can be optimized without changing ideal computation. We investigate exact diagonal completion for the quantum approximate optimization algorithm (QAOA) applied to placement, using permutation-preserving register swaps. We construct exact Manhattan-distance operators through weighted-$\ell_1$ optimization of Walsh coefficients and a sparse recurrence requiring $O(\sqrt{m})$ terms on balanced rectangles, avoiding $O(m^4)$ dense constraint storage. Across 160 geometries, weighted-$\ell_1$ completion reduces controlled-NOT (CX) counts relative to four alternative extensions in all 96 cases with unused binary codes under Gray-code synthesis. On an independently specified 60-case cohort, median reductions relative to virtual-coordinate extension are 28.0\%, 53.9\%, and 21.6\% at six, nine, and twelve sites. Under generic diagonal synthesis, reductions decrease to 10.9\%, 1.3\%, and 0.7\%, demonstrating compiler dependence. Additional ancillas reduce mixer serialization, but token circuits remain deeper than one-hot baselines. Ideal placement simulations show baseline-dependent solution quality, with classical search performing better. OpenROAD integration takes 72 QAOA and 216 classical placements across six RTL designs through clock-tree synthesis and global routing with zero overflow. Completion improves phase construction; no end-to-end advantage is established.

Quantum Physics (quant-ph); Hardware Architecture (cs.AR); Emerging Technologies (cs.ET)

arXiv:2609.38734 [quant-ph]

(or arXiv:2609.38734v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.38734 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.