Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Symposium on System Security, Safety, and Reliability (ISSSR)

Formal Verification of Quantum Arithmetic Circuits in Maude

Naoto Sato, Tsubasa Takagi

Published May 1, 2026• 0 citations
Publisher

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.

DOI
10.1109/isssr69973.2026.00019

Related papers

Symbolic model checking quantum circuits in Maude

Canh Minh Do, Kazuhiro Ogata

This article presents a symbolic approach to model checking quantum circuits using a set of laws from quantum mechanics and basic matrix operations with Dirac notation. We use Maude, a high-level specification/programming language based on rewriting logic, to implement our symbolic approach. As case studies, we use the approach to formally specify several quantum communication protocols in the early work of quantum communication and formally verify their correctness: Superdense Coding, Quantum Teleportation, Quantum Secret Sharing, Entanglement Swapping, Quantum Gate Teleportation, Two Mirror-image Teleportation, and Quantum Network Coding. We demonstrate that our approach/implementation can be a first step toward a general framework to formally specify and verify quantum circuits in Maude. The proposed way to formally specify a quantum circuit makes it possible to describe the quantum circuit in Maude such that the formal specification can be regarded as a series of quantum gate/measurement applications. Once a quantum circuit has been formally specified in the proposed way together with an initial state and a desired property expressed in linear temporal logic (LTL), the proposed model checking technique utilizes a built-in Maude LTL model checker to automatically conduct formal verification that the quantum circuit enjoys the property starting from the initial state.

PeerJ Computer Science•Jun 20, 2024•13 citations

Formal Specification and Verification of Quantum Computing Algorithms

Jincheng Zhang

The verification of quantum computing algorithms presents a significant hurdle due to the probabilistic nature of quantum mechanics and the complex entanglement inherent in quantum computations. This paper proposes a novel approach to address this challenge by developing a formal language and a corresponding verification tool tailored explicitly for quantum algorithm specification and verification. The system leverages concepts from quantum information theory and formal methods to provide a rigorous framework for ensuring the correctness of quantum algorithms. We introduce a new formalism that allows for precise description of quantum circuits and their operations, combined with automated theorem proving techniques to systematically verify the algorithm's behavior against a given specification. The key innovation lies in the ability to reason about quantum states and measurements within a formal setting, enabling a more comprehensive understanding and validation of these algorithms. This work lays the foundation for increased confidence in the development and deployment of quantum computing technologies.

•Sep 2, 2026•0 citations

Formal Verification of Quantum Circuit Optimization Algorithms

Jincheng Zhang

Quantum circuit optimization is crucial for realizing the full potential of quantum computing. However, the inherent complexity of quantum circuits and the potential for errors introduce significant challenges in ensuring the correctness and efficiency of optimization algorithms. This paper proposes a novel approach to formally verify quantum circuit optimization algorithms. We translate these algorithms into formal specification languages and leverage model checking and theorem proving techniques to rigorously demonstrate that the algorithms meet their intended objectives – primarily minimizing circuit complexity – without introducing unintended side effects. The core contribution lies in applying formal verification methodologies to this largely unexplored area, offering a path towards building trust and confidence in quantum optimization strategies. The presented framework provides a systematic method for ensuring the reliability of quantum circuits, a critical step towards practical quantum computation. The verification process relies on defining the desired behavior as a set of logical properties and then employing automated tools to check whether the optimized circuit satisfies these properties. This approach addresses the fundamental need for rigorous assurance in quantum systems, moving beyond empirical validation and towards mathematically proven correctness.

•Sep 5, 2026•0 citations

Symbolic Model Checking Quantum Circuits in Maude

Canh Minh Do, Kazuhiro Ogata

This paper presents a symbolic approach to model checking quantum circuits by using a set of laws from quantum mechanics and basic matrix operations with Dirac notation.We use Maude, a high-level specification/programming language based on rewriting logic, to implement our symbolic approach.As a case study, we use the approach to formally specify and verify the correctness of the quantum teleportation protocol, which is an important quantum communication protocol in the early work of quantum communications.Moreover, our implementation can be used as a general framework to formally specify and verify quantum circuits in Maude in an effortless way, where only an initial quantum state and a sequence of actions describing how a quantum circuit works in a simple way are required.

Proceedings/Proceedings of the ... International Conference on Software Engineering and Knowledge Engineering•Jul 1, 2023•8 citations

Formal Verification of Quantum Circuit Compilation using Symbolic Execution

Jincheng Zhang

Quantum circuit compilation is a crucial step in translating high-level quantum algorithms into executable quantum circuits on specific hardware. The complexity and potential for errors within this process necessitate rigorous verification methods. This paper proposes a novel approach leveraging symbolic execution to formally verify quantum circuit compilation. We represent quantum circuits and compilation steps as a symbolic program, enabling the exploration of all possible compilation paths. By incorporating quantum gate fidelities and noise models into the symbolic execution engine, we can identify potential errors in the compilation logic, providing a robust and systematic way to ensure the correctness of the compilation process. The core claim is that symbolic execution can be extended to formally verify the correctness of quantum circuit compilation processes. This work addresses a critical need in quantum computing, offering a new technique for building trust and reliability into quantum software.

•Aug 28, 2026•0 citations

A Review of Formal Methods in Quantum-Circuit Verification

Arun Govindankutty

Quantum computing exploits the principles of quantum mechanics to perform computation. Information is stored in qubits and processed with a sequence of quantum gates arranged as circuits. Verifying the correctness of quantum circuits is becoming essential as hardware scales in qubit count and architectural complexity. Traditional testing and naive simulation do not scale and quickly become computationally infeasible because the state space grows exponentially. This creates a strong need for more powerful and scalable verification techniques. Formal methods offer a viable solution by providing mathematically rigorous and scalable verification techniques that address these scalability challenges through abstraction, symbolic reasoning, and probabilistic guarantees. This study examines how formal methods are applied to quantum-circuit verification. Specifically, four families of formal techniques: barrier certificates, abstract interpretation, model checking, and theorem proving are examined, along with the theoretical foundations and practical applications of these techniques. Finally, the study highlights open challenges and identifies promising directions for future research. An extensive set of references is included to support further study and exploration.

Electronics•Mar 9, 2026•5 citations
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.
This article presents a symbolic approach to model checking quantum circuits using a set of laws from quantum mechanics and basic matrix operations with Dirac notation. We use Maude, a high-level specification/programming language based on rewriting logic, to implement our symbolic approach. As case studies, we use the approach to formally specify several quantum communication protocols in the early work of quantum communication and formally verify their correctness: Superdense Coding, Quantum Teleportation, Quantum Secret Sharing, Entanglement Swapping, Quantum Gate Teleportation, Two Mirror-image Teleportation, and Quantum Network Coding. We demonstrate that our approach/implementation can be a first step toward a general framework to formally specify and verify quantum circuits in Maude. The proposed way to formally specify a quantum circuit makes it possible to describe the quantum circuit in Maude such that the formal specification can be regarded as a series of quantum gate/measurement applications. Once a quantum circuit has been formally specified in the proposed way together with an initial state and a desired property expressed in linear temporal logic (LTL), the proposed model checking technique utilizes a built-in Maude LTL model checker to automatically conduct formal verification that the quantum circuit enjoys the property starting from the initial state.
The verification of quantum computing algorithms presents a significant hurdle due to the probabilistic nature of quantum mechanics and the complex entanglement inherent in quantum computations. This paper proposes a novel approach to address this challenge by developing a formal language and a corresponding verification tool tailored explicitly for quantum algorithm specification and verification. The system leverages concepts from quantum information theory and formal methods to provide a rigorous framework for ensuring the correctness of quantum algorithms. We introduce a new formalism that allows for precise description of quantum circuits and their operations, combined with automated theorem proving techniques to systematically verify the algorithm's behavior against a given specification. The key innovation lies in the ability to reason about quantum states and measurements within a formal setting, enabling a more comprehensive understanding and validation of these algorithms. This work lays the foundation for increased confidence in the development and deployment of quantum computing technologies.
Quantum circuit optimization is crucial for realizing the full potential of quantum computing. However, the inherent complexity of quantum circuits and the potential for errors introduce significant challenges in ensuring the correctness and efficiency of optimization algorithms. This paper proposes a novel approach to formally verify quantum circuit optimization algorithms. We translate these algorithms into formal specification languages and leverage model checking and theorem proving techniques to rigorously demonstrate that the algorithms meet their intended objectives – primarily minimizing circuit complexity – without introducing unintended side effects. The core contribution lies in applying formal verification methodologies to this largely unexplored area, offering a path towards building trust and confidence in quantum optimization strategies. The presented framework provides a systematic method for ensuring the reliability of quantum circuits, a critical step towards practical quantum computation. The verification process relies on defining the desired behavior as a set of logical properties and then employing automated tools to check whether the optimized circuit satisfies these properties. This approach addresses the fundamental need for rigorous assurance in quantum systems, moving beyond empirical validation and towards mathematically proven correctness.
This paper presents a symbolic approach to model checking quantum circuits by using a set of laws from quantum mechanics and basic matrix operations with Dirac notation.We use Maude, a high-level specification/programming language based on rewriting logic, to implement our symbolic approach.As a case study, we use the approach to formally specify and verify the correctness of the quantum teleportation protocol, which is an important quantum communication protocol in the early work of quantum communications.Moreover, our implementation can be used as a general framework to formally specify and verify quantum circuits in Maude in an effortless way, where only an initial quantum state and a sequence of actions describing how a quantum circuit works in a simple way are required.
Quantum circuit compilation is a crucial step in translating high-level quantum algorithms into executable quantum circuits on specific hardware. The complexity and potential for errors within this process necessitate rigorous verification methods. This paper proposes a novel approach leveraging symbolic execution to formally verify quantum circuit compilation. We represent quantum circuits and compilation steps as a symbolic program, enabling the exploration of all possible compilation paths. By incorporating quantum gate fidelities and noise models into the symbolic execution engine, we can identify potential errors in the compilation logic, providing a robust and systematic way to ensure the correctness of the compilation process. The core claim is that symbolic execution can be extended to formally verify the correctness of quantum circuit compilation processes. This work addresses a critical need in quantum computing, offering a new technique for building trust and reliability into quantum software.
Quantum computing exploits the principles of quantum mechanics to perform computation. Information is stored in qubits and processed with a sequence of quantum gates arranged as circuits. Verifying the correctness of quantum circuits is becoming essential as hardware scales in qubit count and architectural complexity. Traditional testing and naive simulation do not scale and quickly become computationally infeasible because the state space grows exponentially. This creates a strong need for more powerful and scalable verification techniques. Formal methods offer a viable solution by providing mathematically rigorous and scalable verification techniques that address these scalability challenges through abstraction, symbolic reasoning, and probabilistic guarantees. This study examines how formal methods are applied to quantum-circuit verification. Specifically, four families of formal techniques: barrier certificates, abstract interpretation, model checking, and theorem proving are examined, along with the theoretical foundations and practical applications of these techniques. Finally, the study highlights open challenges and identifies promising directions for future research. An extensive set of references is included to support further study and exploration.