Quantum Circuit Optimization by Graph Coloring

Hochang Lee, Kyung Chul Jeong, Panjin Kim · 2025

Read Quantum Circuit Optimization by Graph Coloring by Hochang Lee, Kyung Chul Jeong, Panjin Kim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-14447.txt.

Description

Hochang Lee, Kyung Chul Jeong, and Panjin Kim link two hard problems in a short 2025 paper. The first is shortening quantum circuits, whose depth drives errors on real hardware. The second is coloring the points of a graph so that linked points never share a color.

The authors show that for circuits built from gates that can swap order, finding the shallowest layout is exactly a coloring task. Gates become graph points, and edges join gates that cannot run side by side. Any good coloring tool can then serve as the circuit optimizer. Tests on known circuits, including arithmetic blocks used in quantum algorithms, confirm the approach. The trick lets quantum engineers borrow decades of graph research.

Catalog record

CREATORHochang Lee, Kyung Chul Jeong, Panjin Kim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-14447

Browse the full library · About the Tower of Babel