Structuring General and Complete Quantum Computations in Haskell: The Arrows Approach
Abstract
In this thesis we argue that a realistic model for quantum computations should be general with respect to measurements, and complete with respect to the information flow between the quantum and classical worlds. We thus structure general and complete quantum programming in Haskell using well known constructions from classical semantics and programming languages, like monads and arrows. The result connects “generic” and “complete” quantum features to well-founded semantics constructions and programming languages.References
Aharonov, D., Kitaev, A., and Nisan, N. (1998). Quantum circuits with mixed states. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 20–30. New York: ACM Press.
Altenkirch, T. and Reus, B. (1999). Monadic presentations of lambda terms using generalized inductive types. In Proc. Computer Science Logic.
Bell, J. S. (1987). On the Einstein-Podolsky-Rosen paradox. In [?], pages 14–21. Cambridge University Press.
Danos, V., Hondt, E. D.., Kashefi, E., and Panangaden, P. (2005). Distributed measurement-based quantum computation. In Selinger, P., editor, Proceedings of the 3rd International Workshop on Quantum Programming Languages, Electronic Notes in Theoretical Computer Science, Chicago, USA. [S.l.] Elsevier Science.
Gay, S. J. and Nagarajan, R. (2005). Communicating quantum processes. In Proceedings of the 32nd ACM Symposium on Principles of Programming Languages.
Hughes, J. (2000). Generalising monads to arrows. Science of Computer Programming, 37:67–111.
Jones, S. P., Hughes, J., Augustsson, L., Barton, D., Boutel, B., Burton, W., Fasel, J., Hammond, K., Hinze, R., Hudak, P., Johnsson, T., Jones, M., Launchbury, J., Meijer, E., Peterson, J., Reid, A., Runciman, C., and Wadler, P. (1999). Haskell 98: A Non-strict, Purely Functional Language. [link].
Moggi, E. (1989). Computational lambda-calculus and monads. In Proceedings of the Fourth Annual Symposium on Logic in computer science, pages 14–23. IEEE Press.
Nielsen, M. A. and Chuang, I. L. (2000). Quantum Computation and Quantum Information. Cambridge University Press.
Raussendorf, R., Browne, D., and Briegel, H. (2003). Measurement-based quantum computation with cluster states. Phys. Rev., A 68 (2003).
Sabry, A. (2003). Modeling quantum computing in Haskell. In Proceedings of the ACM SIGPLAN workshop on Haskell, pages 39–49. ACM Press.
Unruh, D. (2005). Quantum programs with classical output streams. Electronic Notes in Theoretical Computer Science. 3rd International Workshop on Quantum Programming Languages, to be published.
Vizzotto, J. K., Altenkirch, T., and Sabry, A. (2006a). Structuring quantum effects: Superoperators as arrows. Journal of Mathematical Structures in Computer Science: special issue in quantum programming languages, 16:453–468.
Vizzotto, J. K., Costa, A. C. R., and Sabry, A. (2006b). Quantum arrows in haskell. In Proc. 4th International Workshop on Quantum Programming Languages, Oxford. to appear in Electronic Notes in Theoretical Computer Science (ENTCS).
Altenkirch, T. and Reus, B. (1999). Monadic presentations of lambda terms using generalized inductive types. In Proc. Computer Science Logic.
Bell, J. S. (1987). On the Einstein-Podolsky-Rosen paradox. In [?], pages 14–21. Cambridge University Press.
Danos, V., Hondt, E. D.., Kashefi, E., and Panangaden, P. (2005). Distributed measurement-based quantum computation. In Selinger, P., editor, Proceedings of the 3rd International Workshop on Quantum Programming Languages, Electronic Notes in Theoretical Computer Science, Chicago, USA. [S.l.] Elsevier Science.
Gay, S. J. and Nagarajan, R. (2005). Communicating quantum processes. In Proceedings of the 32nd ACM Symposium on Principles of Programming Languages.
Hughes, J. (2000). Generalising monads to arrows. Science of Computer Programming, 37:67–111.
Jones, S. P., Hughes, J., Augustsson, L., Barton, D., Boutel, B., Burton, W., Fasel, J., Hammond, K., Hinze, R., Hudak, P., Johnsson, T., Jones, M., Launchbury, J., Meijer, E., Peterson, J., Reid, A., Runciman, C., and Wadler, P. (1999). Haskell 98: A Non-strict, Purely Functional Language. [link].
Moggi, E. (1989). Computational lambda-calculus and monads. In Proceedings of the Fourth Annual Symposium on Logic in computer science, pages 14–23. IEEE Press.
Nielsen, M. A. and Chuang, I. L. (2000). Quantum Computation and Quantum Information. Cambridge University Press.
Raussendorf, R., Browne, D., and Briegel, H. (2003). Measurement-based quantum computation with cluster states. Phys. Rev., A 68 (2003).
Sabry, A. (2003). Modeling quantum computing in Haskell. In Proceedings of the ACM SIGPLAN workshop on Haskell, pages 39–49. ACM Press.
Unruh, D. (2005). Quantum programs with classical output streams. Electronic Notes in Theoretical Computer Science. 3rd International Workshop on Quantum Programming Languages, to be published.
Vizzotto, J. K., Altenkirch, T., and Sabry, A. (2006a). Structuring quantum effects: Superoperators as arrows. Journal of Mathematical Structures in Computer Science: special issue in quantum programming languages, 16:453–468.
Vizzotto, J. K., Costa, A. C. R., and Sabry, A. (2006b). Quantum arrows in haskell. In Proc. 4th International Workshop on Quantum Programming Languages, Oxford. to appear in Electronic Notes in Theoretical Computer Science (ENTCS).
Published
2007-06-30
How to Cite
VIZZOTTO, Juliana Kaizer; COSTA, Antônio Carlos da Rocha; SABRY, Amr.
Structuring General and Complete Quantum Computations in Haskell: The Arrows Approach. In: THESIS AND DISSERTATION CONTEST (CTD), 20. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 1990-1997.
ISSN 2763-8820.
