[Joint CQSE & NCTS Seminar] Exponential Quantum Speedup in Boolean Matching for Reversible Logic Circuits
Title: [Joint CQSE & NCTS Seminar] Exponential Quantum Speedup in Boolean Matching for Reversible Logic Circuits
Speaker: Prof. Jie-Hong Roland Jiang (National Taiwan University)
Time: 2025/09/19 (Fri.) 14:20-16:20
Place: Rm. 104, Chin-Pao Yang Lecture Hall, Department of Physics/CCMS, NTU
Online: https://nationaltaiwanuniversity-zbh.my.webex.com/nationaltaiwanuniversity-zbh.my/j.php?MTID=m35c57ceb3c91fd5af3ca30d927e989a1
Abstract
Boolean matching is an important problem in logic synthesis and verification for electronic design automation. Despite being well-studied for conventional Boolean circuits, its treatment for reversible logic circuits remains largely, if not completely, missing. This work provides the first such study. Given two (black-box) reversible logic circuits that are promised to be matchable, we check their equivalences under various input/output negation and permutation conditions, subject to the availability/unavailability of their inverse circuits. Notably, among other results, we show that the equivalence up to input negation and permutation is solvable in quantum polynomial time, while its classical complexity is exponential. This result is arguably the first demonstration of quantum exponential speedup in solving design automation problems. Also, as a negative result, we show that the equivalence up to both input and output negations is not solvable in quantum polynomial time unless UNIQUE-SAT is, which is unlikely. This work paves the theoretical foundation of Boolean matching reversible circuits for potential applications, e.g., in quantum circuit synthesis.(Joint work with Tian-Fu Chen)
Reference:
Tian-Fu Chen and Jie-Hong Roland Jiang. 2024. Boolean Matching Reversible Circuits: Algorithm and Complexity. In Proceedings of the 61st ACM/IEEE Design Automation Conference (DAC '24). Association for Computing Machinery, New York, NY, USA, Article 18, 1–6. https://doi.org/10.1145/3649329.3657312
Biography
Professor Jie-Hong R. Jiang received his B.S. and M.S. degrees in Electronics Engineering from National Chiao Tung University, Hsinchu, Taiwan, in 1996 and 1998, respectively, and his Ph.D. in Electrical Engineering and Computer Sciences from the University of California, Berkeley, in 2004. He is currently a Professor in the Department of Electrical Engineering and the Graduate Institute of Electronics Engineering at National Taiwan University (NTU). His research interests include logic synthesis, formal verification, electronic design automation (EDA), and computation models of biological and physical systems.
