Abstract
We demonstrate a new unification of probability with standard computation in which a nonzero chance of disaster is treated as disaster. Laws and a Galois connection with the more traditional probabilistic model are provided. Reversibility in the probabilistic guarded-command language is discussed. Finally the formalism is applied to unify quantum computation and cryptography within the probabilistic method.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. In: Proc. IEEE Conference on Computers, Systems and Signal processing, Bangalore, pp. 175–179 (1984)
Bennett, C.H., Brassard, G., Robert, J.-M.: Privacy amplification by public discussion. SIAM Journal of Computing 17(2), 210–229 (1988)
Bennett, C.H.: Quantum cryptography using any two nonorthogonal states. Physical Review Letters 68(21), 3121–3124 (1992)
Butler, M.J., Hartel, P.: Reasoning about Grover’s quantum search algorithm using probabilistic wp. ACM Transactions on Programming Languages and Systems 21(3), 417–430 (1999)
Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of 28th ACM STOC, pp. 212–219 (1996)
Gruska, J.: Quantum Computing. Advanced Topics in Computer Science. McGraw-Hill International, UK (1999)
Harel, D.: Algorithmics: The Spirit of Computing, 2nd edn. Addison Wesley, Reading (1992)
He, J., Seidel, K., McIver, A.K.: Probabilistic models for the guarded command language. Science of Computer Programming 28, 171–192 (1997)
Hehner, E.R.: Probabilistic predicative programming. In: Kozen, D. (ed.) MPC 2004. LNCS, vol. 3125, pp. 169–185. Springer, Heidelberg (2004)
Hoare, C.A.R., He, J.: Unifying Theories of Programming. Prentice Hall, Englewood Cliffs (1998)
Landauer, R.: Irreversibility and heat generated in the computing process. IBM Journal of Research and Development 5 (1961)
McIver, A.K., Morgan, C.C.: Abstraction, Refinement and Proof for Probabilistic Systems. Springer Monographs in Computer Science (2005)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Sanders, J.W., Zuliani, P.: Quantum Programming. In: Backhouse, R., Oliveira, J.N. (eds.) MPC 2000. LNCS, vol. 1837, pp. 80–99. Springer, Heidelberg (2000)
Stoddart, W.J., Zeyda, F., Lynas, R.: A design-based model of reversible computation. In: Dunne, S., Stoddart, B. (eds.) UTP 2006. LNCS, vol. 4010, pp. 63–83. Springer, Heidelberg (2006)
Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299(5886), 802–803 (1982)
Zuliani, P.: Logical reversibility. IBM Journal of Research and Development 45(6), 807–818 (2001)
Zuliani, P.: Compiling Quantum Programs. Acta Informatica 41(7-8), 435–474 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
He, J., Sanders, J.W. (2006). Unifying Probability. In: Dunne, S., Stoddart, B. (eds) Unifying Theories of Programming. UTP 2006. Lecture Notes in Computer Science, vol 4010. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11768173_11
Download citation
DOI: https://doi.org/10.1007/11768173_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34750-7
Online ISBN: 978-3-540-34752-1
eBook Packages: Computer ScienceComputer Science (R0)