International Symposium on System Security, Safety, and Reliability (ISSSR)
Formal Verification of Quantum Arithmetic Circuits in Maude
Naoto Sato, Tsubasa Takagi
Abstract
Quantum arithmetic circuits are fundamental components of many quantum algorithms, including Shor's algorithm. However, ensuring their correctness is challenging because circuit behavior becomes increasingly complex as the number of qubits grows, making exhaustive classical simulation intractable. Subtle design errors may compromise the reliability of entire algorithms. To address this challenge, we present a systematic approach to the formal verification of quantum arithmetic circuits using Maude, a rewriting logic framework suited for algebraic specification and reasoning about complex systems. In our approach, quantum gates and circuits are formally specified as rewrite rules in Maude, enabling a rigorous analysis of their behavior for all possible inputs. Using this framework, we formally verify the correctness of the fundamental quantum arithmetic circuits used in Shor's algorithm, including modular multiplication and modular exponentiation. Our results demonstrate that algebraic specification provides a practical foundation for verifying quantum arithmetic circuits. This work contributes to the development of reliable quantum software and strengthens confidence in arithmetic-intensive quantum algorithms, including the HHL algorithm.