Proof rules for the correctness of quantum programs

Publication Type:
Journal Article
Citation:
Theoretical Computer Science, 2007, 386 (1-2), pp. 151 - 166
Issue Date:
2007-10-28
Metrics:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2008004827.pdf319.2 kB
Adobe PDF
We apply the notion of quantum predicate proposed by D'Hondt and Panangaden to analyze a simple language fragment which may describe the quantum part of a future quantum computer in Knill's architecture. The notion of weakest liberal precondition semantics, introduced by Dijkstra for classical deterministic programs and by McIver and Morgan for probabilistic programs, is generalized to our quantum programs. To help reasoning about the correctness of quantum programs, we extend the proof rules presented by Morgan for classical probabilistic loops to quantum loops. These rules are shown to be complete in the sense that any correct assertion about the quantum loops can be proved using them. Some illustrative examples are also given to demonstrate the practicality of our proof rules. © 2007 Elsevier Ltd. All rights reserved.
Please use this identifier to cite or link to this item: