Abstract
We show how to use a programming language for formally describing and reasoning about errors in quantum computation. The formalisation is based on the concept of performing the correct operation with probability at least p, and the erroneous one with probability at most 1 − p. We apply the concept to two examples: Bell’s inequalities and the Deutsch–Jozsa quantum algorithm. The former is a fundamental thought experiment aimed at showing that Quantum Mechanics is not “local and realist”, and it is used in quantum cryptography protocols. We study it assuming faulty measurements, and we derive hardware reliability conditions that must be satisfied in order for the experiment to support its conclusions. The latter is a quantum algorithm for efficiently solving a classification problem for Boolean functions. The algorithm solves the problem with no error, but when we introduce faulty operations it becomes a two-sided error algorithm. Reasoning is accomplished via standard programming laws and quantum laws.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aharonov D., Kitaev A., Nisan N.: Quantum circuits with mixed states. In: STOC ’98: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 20–30 (1998)
Altenkirch T., Grattage J.: A functional quantum programming language. In LICS ’05: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, pp. 249–258 (2005)
Aspect A., Graingier P., Roger G.: Experimental realization of EPR Gedankenexperiment: a new violation of Bell’s inequalities. Phys. Rev. Lett. 49, 91–94 (1982)
Bell J.S.: On the Einstein–Podolsky–Rosen paradox. Physics 1, 195–200 (1964)
Bennett C.H., Wiesner S.J.: Communication via one- and two-particle operators on Einstein–Podolsky–Rosen states. Phys. Rev. Lett. 69(20), 2881–2884 (1992)
Clauser J.F., Horne M.A., Shimony A., Holt R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880–884 (1969)
Deutsch D., Jozsa R.: Rapid solution of problems by quantum computation. Proc. R. Soc. London A439, 553–558 (1992)
Ekert A.K.: Quantum cryptography based on Bell’s theorem. Phys. Rev. Lett. 67(6), 661–663 (1991)
Fedrizzi A. et al.: High-fidelity transmission of entanglement over a high-loss freespace channel. Nat. Phys. 5, 389–392 (2009)
Gay S.J.: Quantum programming languages: survey and bibliography. Math. Struct. Comput. Sci. 16(4), 581–600 (2006)
He J., McIver A., Seidel K.: Probabilistic models for the guarded command language. Sci. Comput. Program. 28, 171–192 (1997)
Isham C.J.: Lectures on quantum theory. Imperial College Press, London (1997)
McIver A., Morgan C.C.: Abstraction, Refinement and Proof for Probabilistic Systems. Springer, Berlin (2005)
Morgan C.C., McIver A., Seidel K.: Probabilistic predicate transformers. ACM Trans. Program. Lang. Syst. 18(3), 325–353 (1996)
Nielsen M.A., Chuang I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Reed M., Simon B.: Methods of Mathematical Physics. I. Functional Analysis. Acamedic Press, Dublin (1972)
Sanders, J.W., Zuliani, P.: Quantum programming. In: MPC’00: Mathematics of Program Construction, Springer LNCS, vol. 1837, pp. 80–99 (2000)
Selinger P.: Towards a quantum programming language. Math. Struct. Comput. Sci. 14(4), 527–586 (2004)
Ursin R. et al.: Entanglement-based quantum communication over 144 km. Nat. Phys. 3, 481–486 (2007)
von Neumann J.: Mathematical Foundations of Quantum Mechanics. Princeton University Press, New Jersey (1955)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zuliani, P. Reasoning about faulty quantum programs. Acta Informatica 46, 403–432 (2009). https://doi.org/10.1007/s00236-009-0100-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00236-009-0100-0