quantum-computing

Quantum Circuit Optimization by Graph Coloring

Quantum Science and Technology (arXiv overlay)

20 min read

0 likes

⚡ Quantum Brief

Researchers Hochang Lee, Kyung Chul Jeong, and Panjin Kim demonstrated that optimizing quantum circuits with commuting gates can be reduced to a graph vertex coloring problem, where gates become vertices and non-parallelizable operations form edges. Their method transforms circuit depth minimization into a graph problem, enabling the use of existing vertex coloring algorithms as optimization backends, bypassing the need for quantum-specific solutions. Numerical experiments validated the approach, showing measurable improvements in circuit depth for arithmetic operations like finite field multiplication and QFT-based addition. The technique leverages decades of graph theory research, offering a practical pathway to integrate mature optimization tools into quantum software stacks like Qiskit and PennyLane. Two established graph coloring solvers were tested, proving effective in reducing circuit depth, with potential applications in cryptography and quantum algorithm acceleration.

Quantum Circuit Optimization by Graph Coloring

Summarize this article with:

AbstractThis work shows that minimizing the depth of a quantum circuit composed of commuting operations reduces to a vertex coloring problem on an appropriately constructed graph, where gates correspond to vertices and edges encode non-parallelizability. The reduction leads to algorithms for circuit optimization by adopting any vertex coloring solver as an optimization backend. The approach is validated by numerical experiments as well as applications to known quantum circuits, including finite field multiplication and QFT-based addition.Featured image: A quantum circuit of commuting gates (CZ and CCZ) is reduced to a graph-coloring instance. After solving the coloring problem, the solution is mapped back to an optimized circuit.Popular summaryOptimizing logic circuits is an active area of research in the quantum computing community. While the topic has roots in computational questions—such as how small a circuit can be—it is also practically relevant: a handful of these algorithms are already integrated into real-world software stacks such as Qiskit and PennyLane. Building on this line of work, it is shown that a certain class of quantum circuits, referred to here as commuting circuits, can be reduced to the vertex coloring problem on a graph. This reduction immediately suggests optimizing commuting circuits not as a circuit problem but as a graph problem, where a long-standing literature offers tools that may translate into practical improvements. Two well-known graph coloring solvers are evaluated, demonstrating the effectiveness of the approach. These findings are used to improve previously known quantum circuits for arithmetic operations.► BibTeX data@article{Lee2026quantumcircuit, doi = {10.22331/q-2026-02-06-1996}, url = {https://doi.org/10.22331/q-2026-02-06-1996}, title = {Quantum {C}ircuit {O}ptimization by {G}raph {C}oloring}, author = {Lee, Hochang and Jeong, Kyung Chul and Kim, Panjin}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1996}, month = feb, year = {2026} }► References [1] Dan Shepherd and Michael J. Bremner. ``Temporally unstructured quantum computation''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1413–1439 (2009). https://doi.org/10.1098/rspa.2008.0443 [2] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. ``Achieving quantum supremacy with sparse and noisy commuting quantum computations''. Quantum 1, 8 (2017). https://doi.org/10.22331/q-2017-04-25-8 [3] Sergey Bravyi and Mikhail Vyalyi. ``Commutative version of the local Hamiltonian problem and common eigenspace problem''. Quantum Info. Comput. 5, 187–215 (2005). https://doi.org/10.26421/qic5.3-2 [4] A.Yu. Kitaev. ``Fault-tolerant quantum computation by anyons''. Annals of Physics 303, 2–30 (2003). https://doi.org/10.1016/S0003-4916(02)00018-0 [5] Dmitri Maslov, Jimson Mathew, Donny Cheung, and Dhiraj K. Pradhan. ``An $O(m^2)$-depth quantum algorithm for the elliptic curve discrete logarithm problem over $GF(2^m)$''. Quantum Info. Comput. 9, 610–621 (2009). https://doi.org/10.26421/qic9.7-8-4 [6] Thomas G. Draper. ``Addition on a quantum computer'' (2000). arXiv:quant-ph/0008033. arXiv:quant-ph/0008033 [7] Mehdi Saeedi and Igor L. Markov. ``Synthesis and optimization of reversible circuits—a survey''. ACM Comput. Surv. 45 (2013). https://doi.org/10.1145/2431211.2431220 [8] Yunseong Nam, Neil J Ross, Yuan Su, Andrew M Childs, and Dmitri Maslov. ``Automated optimization of large quantum circuits with continuous parameters''. npj Quantum Information 4, 23 (2018). https://doi.org/10.1038/s41534-018-0072-4 [9] J-H Bae, Paul M Alsing, Doyeol Ahn, and Warner A Miller. ``Quantum circuit optimization using quantum Karnaugh map''. Scientific reports 10, 15651 (2020). https://doi.org/10.1038/s41598-020-72469-7 [10] Zhenyu Huang and Siwei Sun. ``Synthesizing quantum circuits of AES with lower T-depth and less qubits''.

In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022. Pages 614–644. Cham (2022).

Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-22969-5_21 [11] Matthew Amy, Dmitri Maslov, and Michele Mosca. ``Polynomial-time T-depth optimization of Clifford+T circuits via matroid partitioning''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 1476–1489 (2014). https://doi.org/10.1109/TCAD.2014.2341953 [12] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''.

Cambridge University Press. (2010). https://doi.org/10.1017/CBO9780511976667 [13] Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov. ``Clifford circuit optimization with templates and symbolic Pauli gates''. Quantum 5, 580 (2021). https://doi.org/10.22331/q-2021-11-16-580 [14] John Adrian Bondy and Uppaluri Siva Ramachandra Murty. ``Graph theory''.

Springer Publishing Company, Incorporated. (2008). https://doi.org/10.1007/978-1-84628-970-5 [15] Valentine Kabanets and Jin-Yi Cai. ``Circuit minimization problem''. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. Page 73–79. STOC '00New York, NY, USA (2000). Association for Computing Machinery. https://doi.org/10.1145/335305.335314 [16] Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael Saks. ``Minimizing disjunctive normal form formulas and $AC^0$ circuits given a truth table''. SIAM Journal on Computing 38, 63–84 (2008). https://doi.org/10.1137/060664537 [17] S Hirahara, I Oliveira, and R Santhanam. ``NP-hardness of minimum circuit size problem for OR-AND-MOD circuits''. In 33rd Computational Complexity Conference (CCC 2018). Volume 102 of Leibniz International Proceedings in Informatics, pages 5:1–5:31. Schloss Dagstuhl (2018). https://doi.org/10.4230/LIPIcs.CCC.2018.5 [18] Rahul Ilango, Bruno Loff, and Igor C. Oliveira. ``NP-hardness of circuit minimization for multi-output functions''.

In Shubhangi Saraf, editor, 35th Computational Complexity Conference (CCC 2020). Volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:36. Dagstuhl, Germany (2020). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CCC.2020.22 [19] Shuichi Hirahara. ``NP-hardness of learning programs and partial MCSP''. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Pages 968–979. (2022). https://doi.org/10.1109/FOCS54457.2022.00095 [20] Kunihiro Wasa, Shin Nishio, Koki Suetsugu, Michael Hanks, Ashley Stephens, Yu Yokoi, and Kae Nemoto. ``Hardness of braided quantum circuit optimization in the surface code''. IEEE Transactions on Quantum Engineering 4, 1–7 (2023). https://doi.org/10.1109/TQE.2023.3251358 [21] John van de Wetering and Matt Amy. ``Optimising quantum circuits is generally hard'' (2024). arXiv:2310.05958. arXiv:2310.05958 [22] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018). https://doi.org/10.22331/q-2018-08-06-79 [23] Matthew Amy, Dmitri Maslov, and Michele Mosca. ``Polynomial-time T-depth optimization of Clifford+T circuits via matroid partitioning''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 1476–1489 (2014). https://doi.org/10.1109/TCAD.2014.2341953 [24] D. Maslov, C. Young, D.M. Miller, and G.W. Dueck. ``Quantum circuit simplification using templates''. In Design, Automation and Test in Europe. Pages 1208–1213 Vol. 2. (2005). https://doi.org/10.1109/DATE.2005.249 [25] Mathias Soeken, Robert Wille, Gerhard W. Dueck, and Rolf Drechsler. ``Window optimization of reversible and quantum circuits''. In 13th IEEE Symposium on Design and Diagnostics of Electronic Circuits and Systems. Pages 341–345. (2010). https://doi.org/10.1109/DDECS.2010.5491754 [26] Robert Wille, Lucas Berent, Tobias Forster, Jagatheesan Kunasaikaran, Kevin Mato, Tom Peham, Nils Quetschlich, Damian Rovara, Aaron Sander, Ludwig Schmid, Daniel Schönberger, Yannick Stade, and Lukas Burgholzer. ``The MQT handbook : A summary of design automation tools and software for quantum computing''. In 2024 IEEE International Conference on Quantum Software (QSW). Pages 1–8. (2024). https://doi.org/10.1109/QSW62656.2024.00013 [27] Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. ``Quantum computing with Qiskit'' (2024). arXiv:2405.08810. arXiv:2405.08810 [28] Dmitri Maslov and Ben Zindorf. ``Depth optimization of CZ, CNOT, and Clifford circuits''. IEEE Transactions on Quantum Engineering 3, 1–8 (2022). https://doi.org/10.1109/TQE.2022.3180900 [29] Brittanney Amento, Martin Rötteler, and Rainer Steinwandt. ``Quantum binary field inversion: improved circuit depth via choice of basis representation''. Quantum Info. Comput. 13, 116–134 (2013). https://doi.org/10.26421/qic13.1-2-7 [30] Rebekah Herrman, James Ostrowski, Travis S. Humble, and George Siopsis. ``Lower bounds on circuit depth of the quantum approximate optimization algorithm''.

Quantum Information Processing 20, 59 (2021). https://doi.org/10.1007/s11128-021-03001-7 [31] Claude Berge. ``Hypergraphs: combinatorics of finite sets''. Volume 45. Elsevier. (1984). https://doi.org/10.1016/s0924-6509(08)x7007-2 [32] Andrew Jena, Scott Genin, and Michele Mosca. ``Pauli partitioning with respect to gate sets'' (2019). arXiv:1907.07859. arXiv:1907.07859 [33] Vladyslav Verteletskyi, Tzu-Ching Yen, and Artur F. Izmaylov. ``Measurement optimization in the variational quantum eigensolver using a minimum clique cover''. The Journal of Chemical Physics 152, 124114 (2020). https://doi.org/10.1063/1.5141458 [34] Ikko Hamamura and Takashi Imamichi. ``Efficient evaluation of quantum observables using entangled measurements''. npj Quantum Information 6, 56 (2020). https://doi.org/10.1038/s41534-020-0284-2 [35] Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, and Frederic T. Chong. ``$O(N^3)$ measurement cost for variational quantum eigensolver on molecular hamiltonians''. IEEE Transactions on Quantum Engineering 1, 1–24 (2020). https://doi.org/10.1109/TQE.2020.3035814 [36] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature Communications 5, 4213 (2014). https://doi.org/10.1038/ncomms5213 [37] Muhammad Asaduzzaman, Raghav G. Jha, and Bharath Sambasivam. ``Sachdev-Ye-Kitaev model on a noisy quantum computer''. Phys. Rev. D 109, 105002 (2024). https://doi.org/10.1103/PhysRevD.109.105002 [38] D. J. A. Welsh and M. B. Powell. ``An upper bound for the chromatic number of a graph and its application to timetabling problems''.

The Computer Journal 10, 85–86 (1967). https://doi.org/10.1093/comjnl/10.1.85 [39] Daniel Brélaz. ``New methods to color the vertices of a graph''. Commun. ACM 22, 251–256 (1979). https://doi.org/10.1145/359094.359101 [40] Frank Thomson Leighton. ``A graph coloring algorithm for large scheduling problems''. Journal of research of the national bureau of standards 84, 489–506 (1979). https://doi.org/10.6028/jres.084.024 [41] Hussein Al-Omari and Khair Eddin Sabri. ``New graph coloring algorithms''. American Journal of Mathematics and Statistics 2, 739–741 (2006). https://doi.org/10.3844/jmssp.2006.439.441 [42] Murat Aslan and Nurdan Akhan Baykan. ``A performance comparison of graph coloring algorithms''. International Journal of Intelligent Systems and Applications in Engineering 4, 1–7 (2016). https://doi.org/10.18201/ijisae.273053 [43] Isabelle Devarenne, Hakim Mabed, and Alexandre Caminada. ``Intelligent neighborhood exploration in local search heuristics''. In 2006 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06). Pages 144–150. (2006). https://doi.org/10.1109/ICTAI.2006.68 [44] J. Randall Brown. ``Chromatic scheduling and the chromatic number problem''. Management Science 19, 456–463 (1972). https://doi.org/10.1287/mnsc.19.4.456 [45] Michał Karoński, Edward R Scheinerman, and Karen B Singer-Cohen. ``On random intersection graphs: The subgraph problem''. Combinatorics, Probability and Computing 8, 131–159 (1999). https://doi.org/10.1017/S0963548398003459 [46] Michael Behrisch, Anusch Taraz, and Michael Ueckerdt. ``Coloring random intersection graphs and complex Networks''. SIAM Journal on Discrete Mathematics 23, 288–299 (2009). https://doi.org/10.1137/050647153 [47] Valentas Kurauskas and Katarzyna Rybarczyk. ``On the chromatic index of random uniform hypergraphs''. SIAM Journal on Discrete Mathematics 29, 541–558 (2015). https://doi.org/10.1137/130942292 [48] Katarzyna Rybarczyk. ``The chromatic number of random intersection graphs''.

Discussiones Mathematicae Graph Theory 37, 465–476 (2017). https://doi.org/10.7151/dmgt.1955 [49] Brittanney Amento, Martin Rötteler, and Rainer Steinwandt. ``Efficient quantum circuits for binary elliptic curve arithmetic: reducing T-gate complexity''. Quantum Info. Comput. 13, 631–644 (2013). https://doi.org/10.26421/qic13.7-8-5 [50] Martin Rötteler and Rainer Steinwandt. ``A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth $O(\log^2 n)$''. Quantum Info. Comput. 14, 888–900 (2014). https://doi.org/10.26421/QIC14.9-10-11 [51] Shane Kepley and Rainer Steinwandt. ``Quantum circuits for $\mathbb{F}_{2^{n}}$-multiplication with subquadratic gate count''.

Quantum Information Processing 14, 2373–2386 (2015). https://doi.org/10.1007/s11128-015-0993-1 [52] Iggy Van Hoof. ``Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count''. Quantum Info. Comput. 20, 721–735 (2020). https://doi.org/10.26421/qic20.9-10-1 [53] Qing-bin Luo, Guo-wu Yang, Xiao-yu Li, and Qiang Li. ``Quantum reversible circuits for $\mathrm{GF}(2^{8})$ multiplicative inverse''. EPJ Quantum Technology 9, 24 (2022). https://doi.org/10.1140/epjqt/s40507-022-00144-z [54] Mashiyat Zaman, Kotaro Tanahashi, and Shu Tanaka. ``PyQUBO: python library for mapping combinatorial optimization problems to QUBO form''. IEEE Transactions on Computers 71, 838–850 (2022). https://doi.org/10.1109/tc.2021.3063618 [55] Lidia Ruiz-Perez and Juan Carlos Garcia-Escartin. ``Quantum arithmetic with the quantum Fourier transform''.

Quantum Information Processing 16, 152 (2017). https://doi.org/10.1007/s11128-017-1603-1 [56] B. Bollobás. ``The chromatic number of random graphs''. Combinatorica 8, 49–55 (1988). https://doi.org/10.1007/BF02122551 [57] Christof Zalka. ``Grover's quantum searching algorithm is optimal''. Phys. Rev. A 60, 2746–2751 (1999). https://doi.org/10.1103/PhysRevA.60.2746 [58] Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, and Jialin Zhang. ``Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis''. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Page 213–229. SODA '20USA (2020). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975994.13 [59] M. Grötschel, L. Lovász, and A. Schrijver. ``Polynomial algorithms for perfect graphs''. In C. Berge and V. Chvátal, editors, Topics on Perfect Graphs. Volume 88 of North-Holland Mathematics Studies, pages 325–356. North-Holland (1984). https://doi.org/10.1016/S0304-0208(08)72943-8Cited byCould not fetch Crossref cited-by data during last attempt 2026-02-06 13:05:01: Could not fetch cited-by data for 10.22331/q-2026-02-06-1996 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-02-06 13:05:02: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractThis work shows that minimizing the depth of a quantum circuit composed of commuting operations reduces to a vertex coloring problem on an appropriately constructed graph, where gates correspond to vertices and edges encode non-parallelizability. The reduction leads to algorithms for circuit optimization by adopting any vertex coloring solver as an optimization backend. The approach is validated by numerical experiments as well as applications to known quantum circuits, including finite field multiplication and QFT-based addition.Featured image: A quantum circuit of commuting gates (CZ and CCZ) is reduced to a graph-coloring instance. After solving the coloring problem, the solution is mapped back to an optimized circuit.Popular summaryOptimizing logic circuits is an active area of research in the quantum computing community. While the topic has roots in computational questions—such as how small a circuit can be—it is also practically relevant: a handful of these algorithms are already integrated into real-world software stacks such as Qiskit and PennyLane. Building on this line of work, it is shown that a certain class of quantum circuits, referred to here as commuting circuits, can be reduced to the vertex coloring problem on a graph. This reduction immediately suggests optimizing commuting circuits not as a circuit problem but as a graph problem, where a long-standing literature offers tools that may translate into practical improvements. Two well-known graph coloring solvers are evaluated, demonstrating the effectiveness of the approach. These findings are used to improve previously known quantum circuits for arithmetic operations.► BibTeX data@article{Lee2026quantumcircuit, doi = {10.22331/q-2026-02-06-1996}, url = {https://doi.org/10.22331/q-2026-02-06-1996}, title = {Quantum {C}ircuit {O}ptimization by {G}raph {C}oloring}, author = {Lee, Hochang and Jeong, Kyung Chul and Kim, Panjin}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1996}, month = feb, year = {2026} }► References [1] Dan Shepherd and Michael J. Bremner. ``Temporally unstructured quantum computation''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1413–1439 (2009). https://doi.org/10.1098/rspa.2008.0443 [2] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. ``Achieving quantum supremacy with sparse and noisy commuting quantum computations''. Quantum 1, 8 (2017). https://doi.org/10.22331/q-2017-04-25-8 [3] Sergey Bravyi and Mikhail Vyalyi. ``Commutative version of the local Hamiltonian problem and common eigenspace problem''. Quantum Info. Comput. 5, 187–215 (2005). https://doi.org/10.26421/qic5.3-2 [4] A.Yu. Kitaev. ``Fault-tolerant quantum computation by anyons''. Annals of Physics 303, 2–30 (2003). https://doi.org/10.1016/S0003-4916(02)00018-0 [5] Dmitri Maslov, Jimson Mathew, Donny Cheung, and Dhiraj K. Pradhan. ``An $O(m^2)$-depth quantum algorithm for the elliptic curve discrete logarithm problem over $GF(2^m)$''. Quantum Info. Comput. 9, 610–621 (2009). https://doi.org/10.26421/qic9.7-8-4 [6] Thomas G. Draper. ``Addition on a quantum computer'' (2000). arXiv:quant-ph/0008033. arXiv:quant-ph/0008033 [7] Mehdi Saeedi and Igor L. Markov. ``Synthesis and optimization of reversible circuits—a survey''. ACM Comput. Surv. 45 (2013). https://doi.org/10.1145/2431211.2431220 [8] Yunseong Nam, Neil J Ross, Yuan Su, Andrew M Childs, and Dmitri Maslov. ``Automated optimization of large quantum circuits with continuous parameters''. npj Quantum Information 4, 23 (2018). https://doi.org/10.1038/s41534-018-0072-4 [9] J-H Bae, Paul M Alsing, Doyeol Ahn, and Warner A Miller. ``Quantum circuit optimization using quantum Karnaugh map''. Scientific reports 10, 15651 (2020). https://doi.org/10.1038/s41598-020-72469-7 [10] Zhenyu Huang and Siwei Sun. ``Synthesizing quantum circuits of AES with lower T-depth and less qubits''.

In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022. Pages 614–644. Cham (2022).

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed

Quantum Circuit Optimization by Graph Coloring

Tags

Source Information