Qafny: Quantum Program Verification Through Type-guided Classical Separation Logic

TitleQafny: Quantum Program Verification Through Type-guided Classical Separation Logic
Publication TypeJournal Article
Year of Publication2023
AuthorsLi, L, Zhu, M, Cleaveland, R, Lee, Y, Chang, L, Wu, X
Date Published7/12/2023

Formal verification has been proven instrumental to ensure that quantum programs implement their specifications but often requires a significant investment of time and labor. To address this challenge, we present Qafny, an automated proof system designed for verifying quantum programs. At its core, Qafny uses a type-guided quantum proof system that translates quantum operations to classical array operations. By modeling these operations as proof rules within a classical separation logic framework, Qafny provides automated support for the reasoning process that would otherwise be tedious and time-consuming. We prove the soundness and completeness of our proof system and implement a prototype compiler that transforms Qafny programs both into the Dafny programming language and into executable quantum circuits. Using Qafny, we demonstrate how to efficiently verify prominent quantum algorithms, including quantum-walk algorithms, Grover's search algorithm, and Shor's factoring algorithm, with significantly reduced human efforts.