EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Reasoning about Parameterized Recursive Quantum Programs with Ancilla Data and Probabilistic Control

Dominique Unruh, Benoît Valiron, Mingsheng Ying

ACM Transactions on Computational Logic · 31.10.2026 · 27 (4) · 1-63

DOI: 10.1145/3815573 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 15.07.2026. Verfasst von Dominique Unruh und 2 weiteren Autor:innen. Die Arbeit nennt 88 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: ERC consolidator grant CerQuS, Estonian Centre of Excellence in IT, ERDF and by PUT team.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Most modern (classical) programming languages support recursion. Recursion has also been successfully applied to the design of several quantum algorithms and introduced in a couple of quantum programming languages. So, it can be expected that recursion will become one of the fundamental paradigms of quantum programming. In addition, ancilla quantum data, e.g., ancilla qubits, have been extensively employed in designing various quantum algorithms, especially in the design of quantum circuits, and are also included in the mainstream quantum programming languages. Several program logics have been developed for the verification of quantum While-programs. However, there are as yet no general methods for reasoning about general recursive procedures with parameter passing and ancilla data in quantum computing (with measurement). We fill the gap in this article by proposing a parameterized quantum assertion logic and, based on which, designing a Hoare logic for verifying parameterized recursive quantum programs with ancilla data and probabilistic control (induced by quantum measurement). The assertion logic is a unifying framework for defining various assertions of both classical (deterministic or probabilistic) and quantum programs. Besides proving partial and total correctness of the above quantum programs, the Hoare logic can be used to prove probabilistic correctness of these programs by reducing it to total correctness. Concretely, an axiomatic basis of reasoning with both approximate and exact probabilities is established grounded on the soundness and completeness theorem of the Hoare logic. In particular, two counterexamples for illustrating incompleteness of non-parameterized assertions in verifying recursive procedures, and, one counterexample for showing the failure of reasoning with exact probabilities based on partial correctness, are constructed. The effectiveness of our logic in verifying quantum programs with the above mechanisms is shown by three main examples—recursive quantum Markov chain (with probabilistic control), fixed-point Grover’s search, and recursive quantum Fourier sampling. What’s more, the successful verification of recursive quantum Fourier sampling illustrates that the Hoare logic has the potential in verifying more complicated programs, e.g., with data structure of arrays and functionality of quantum uncomputation (i.e., restoring the allocated quantum data to their original state before deallocation).

Förderung

  • ERC consolidator grant CerQuS
  • Estonian Centre of Excellence in IT
  • ERDF and by PUT team
  • European Union through the MSCA SE project QCOMICAL
  • French National Research Agency
  • EPIQ
  • OQULUS
  • HQI-Acquisition

Zitieren

APA

Unruh, D., Valiron, B., & Ying, M. (2026). Reasoning about Parameterized Recursive Quantum Programs with Ancilla Data and Probabilistic Control. ACM Transactions on Computational Logic, 27(4), 1-63. https://doi.org/10.1145/3815573

Vancouver

Unruh D, Valiron B, Ying M. Reasoning about Parameterized Recursive Quantum Programs with Ancilla Data and Probabilistic Control. ACM Transactions on Computational Logic. 2026;27(4):1-63. doi:10.1145/3815573

BibTeX
@article{Unruh2026,
  author = {Unruh, Dominique and Valiron, Benoît and Ying, Mingsheng},
  title = {Reasoning about Parameterized Recursive Quantum Programs with Ancilla Data and Probabilistic Control},
  journal = {ACM Transactions on Computational Logic},
  year = {2026},
  volume = {27},
  number = {4},
  pages = {1--63},
  doi = {10.1145/3815573}
}
Kostenlos starten →