loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
First Joint IEEE/IFIP Symposium on Theoretical Aspects of Software Engineering (TASE '07)
A Formal Derivation of Grover?s Quantum Search Algorithm
Shanghai, China
June 06-June 08
ISBN: 0-7695-2856-2
Paolo Zuliani, Oxford University
In this paper we aim at applying established formal methods techniques to a recent software area: quantum programming. In particular, we aim at providing a stepwise derivation of Grover?s quantum search algorithm. Our work shows that, in principle, traditional software engineering techniques such as specification and refinement can be applied to quantum programs. We have chosen Grover?s algorithm as an example because it is one of the two main quantum algorithms. The algorithm can find with high probability an element in an unordered array of length L in just O(pL) steps (while any classical probabilistic algorithm needs (L) steps). The derivation starts from a rigorous probabilistic specification of the search problem, then we stepwise refine that specification via standard refinement laws and quantum laws, until we arrive at a quantum program. The final program will thus be correct by construction.
Citation:
Paolo Zuliani, "A Formal Derivation of Grover?s Quantum Search Algorithm," tase, pp.67-74, First Joint IEEE/IFIP Symposium on Theoretical Aspects of Software Engineering (TASE '07), 2007
Usage of this product signifies your acceptance of the Terms of Use.