Result Details

A Practical Specification Language for Automatic Quantum Program Verification

TSAI, W.; CHEN, Y.; LENGÁL, O. A Practical Specification Language for Automatic Quantum Program Verification. In Lecture Notes in Computer Science. Lecture Notes in Computer Science. CHAM: Springer Nature, 2026. p. 302-325. ISBN: 978-3-032-32536-5.
Type
conference paper
Language
English
Authors
Tsai Wei-Lun
Chen Yu-Fang
Lengál Ondřej, doc. Ing., Ph.D., DITS (FIT)
Abstract

Hoare-style verification provides a principled foundation for reasoning about the correctness of quantum programs, but existing approaches do not allow fully automatic verification. While automata-based verification scales well when specifications are given directly as automata, prior frameworks incur exponential blow-up when translating high-level set-based assertions into automata, which severely limits practicality. We introduce an extended set-based specification language and a specification-to-automata translation algorithm whose complexity is linear in the number of qubits, enabled by controlled automaton construction and qubit reordering. The resulting compact automata enable fully automatic Hoare-style verification of fixed-qubit quantum programs at previously infeasible scales, while substantially improving expressiveness without compromising efficiency.

Keywords

quantum circuits, specification, automata

Published
2026
Pages
302–325
Journal
Lecture Notes in Computer Science, vol. 16684, ISSN
Proceedings
Lecture Notes in Computer Science
Conference
38th International Conference on Computer Aided Verification - CAV 2026
ISBN
978-3-032-32536-5
Publisher
Springer Nature
Place
CHAM
DOI
UT WoS
001854511500015
EID Scopus
BibTeX
@inproceedings{BUT212541,
  author="{} and  {} and Ondřej {Lengál}",
  title="A Practical Specification Language for Automatic Quantum Program Verification",
  booktitle="Lecture Notes in Computer Science",
  year="2026",
  journal="Lecture Notes in Computer Science",
  volume="16684",
  pages="302--325",
  publisher="Springer Nature",
  address="CHAM",
  doi="10.1007/978-3-032-32537-2\{_}15",
  isbn="978-3-032-32536-5"
}
Projects
QUAK: Quantum Program Analysis using Automata Toolkit, GACR, Standardní projekty, GA25-18318S, 25-18318S, start: 2025-01-01, end: 2027-12-31, running
Reliable, Secure, and Intelligent Computer Systems - extension for 2026, BUT, Vnitřní projekty VUT, FIT-S-26-9011, start: 2026-03-01, end: 2027-02-28, running
Departments
Back to top