Quantum UiB seminar: Quantum-Constrained Edge Coloring for Syndrome Compilation of Quantum Codes
How syndrome compilation for quantum codes can be formulated as a graph-coloring problem.
Syndrome extraction is the process of measuring quantum error-correcting checks to obtain the information needed for decoding. Performing these measurements with low-depth circuits can reduce the time and noise involved.
In this talk, we describe how syndrome compilation for quantum codes can be formulated as a graph-coloring problem. Each edge represents a two-qubit gate, and its color specifies when the gate is performed. Gates sharing a qubit must receive different colors, while additional quantum constraints ensure that the measurements occur in a valid order. With one ancilla per check, the minimum number of colors satisfying these constraints gives the minimum two-qubit circuit depth.
About the speaker
Hsuan-Yin Lin (external link) is a Senior Research Scientist at Simula UiB, Norway. His research aims to develop the information-theoretic foundations of trustworthy quantum and distributed learning systems, spanning information theory, quantum information, coding theory, and differential privacy. His current research focuses on quantum error correction, privacy-preserving learning, and finite-blocklength information theory. He serves as an Associate Editor for the IEEE Transactions on Communications and as the General Chair of the 2026 IEEE European School of Information Theory (ESIT).