Modeling quantum computing in Haskell

ABSTRACT

The paper develops a model of quantum computing from the perspective of functional programming. The model explains the fundamental ideas of quantum computing at a level of abstraction that is familiar to functional programmers. The model also illustrates some of the inherent difficulties in interpreting quantum mechanics and highlights the differences between quantum computing and traditional (functional or otherwise) computing models.

REFERENCES

• 1: Henry G. Baker, NREVERSAL of Fortune - The Thermodynamics of Garbage Collection, Proceedings of the International Workshop on Memory Management, p.507-524, September 17-19, 1992
• 2: J. S. Bell. On the Einstein-Podolsky-Rosen paradox. In {3}, pages 14--21. Cambridge University Press, 1987.
• 3: J. S. Bell. Speakable and Unspeakable in Quantum Mechanics. Cambridge University Press, 1987.
• 4: C. H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17(6):525--532, Nov. 1973.
• 5: Harry Buhrman , John Tromp , Paul M. B. Vitányi, Time and Space Bounds for Reversible Simulation, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.1017-1027, July 08-12, 2001
• 6: J. G. Cramer. The transactional interpretation of quantum mechanics. Modern Physics, 58:647--688, 1986.
• 7: D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Roy. Soc. London, Ser. A, 400:97--117, 1985.
• 8: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 9: A. Einstein, B. Podolsky, and N. Rosen. Can quantum-mechanical description of physical reality be considered complete? Phys. Rev., 47:777--780, 1935.
• 10: H. Everett, III. "Relative state" formulation of quantum mechanics. Reviews of Modern Physics, 29:454, 1957.
• 11: Michael P. Frank , Thomas F. Knight, Jr., Reversibility for efficient computing, 1999
• 12: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 13: R. Hinze. Haskell does it with class. Slides of a talk given at the Generic Haskell meeting, May 2001.
• 14: K. Kagawa. Mutable data structures and composable references in a pure functional language. In State in Programming Languages (SIPL'95), pages 79--94, Jan. 1995.
• 15: Jerzy Karczmarczuk, Structure and interpretation of quantum mechanics: a functional framework, Proceedings of the 2003 ACM SIGPLAN workshop on Haskell, p.50-61, August 28-28, 2003, Uppsala, Sweden [doi>10.1145/871895.871901]
• 16: L. H. Kauffman. Quantum Topology and Quantum Computing, chapter IV of {18}. American Mathematical Society, 2002.
• 17: Werner E. Kluge, A Reversible SE(M)CD Machine, Selected Papers from the 11th International Workshop on Implementation of Functional Languages, p.95-113, September 07-10, 1999
• 18: S. J. Lomonaco, Jr., editor. Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium, volume 58 of Proceedings of Symposia in Applied Mathematics. American Mathematical Society, Mar. 2002.
• 19: S. J. Lomonaco, Jr. A Rosetta Stone for Quantum Mechanics with an Introduction to Quantum Computation, chapter I of {18}. American Mathematical Society, 2002.
• 20: Conor McBride, Faking it Simulating dependent types in Haskell, Journal of Functional Programming, v.12 n.5, p.375-392, July 2002 [doi>10.1017/S0956796802004355]
• 21: S.-C. Mu and R. Bird. Functional quantum programming. In Second Asian Workshop on Programming Languages and Systems, KAIST, Korea, Dec. 2001.
• 22: B. Omer. A procedural formalism for quantum computing. Master's thesis, Department of Theoretical Physics, Technical University of Vienna, 1998.
• 23: An introduction to quantum computing for non-physicists, ACM Computing Surveys (CSUR), v.32 n.3, p.300-335, Sept. 2000 [doi>10.1145/367701.367709]
• 24: P. Selinger. Towards a quantum programming language. Unpublished, 2002.
• 25: Tim Sheard , Simon Peyton Jones, Template meta-programming for Haskell, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.1-16, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581691]
• 26: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 27: J. Skibinski. Collection of Haskell modules. Available at http://web.archive.org/web/20010415043244/www.numeric-quest.com/haskell/index.html, Initialized: 1998-09-18, last modified: 2001-04-02.
• 28: J. Skibinski. Haskell simulator of quantum computer. Available at http://web.archive.org/web/20010630025035/www.numeric-quest.com/haskell/QuantumComputer.html, Initialized: 2001-05-02, last modified: 2001-05-05.
• 29: A. Steane. Quantum computing. Reports on Progress in Physics, 61:117--173, 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Languages, Theory

Keywords:
Haskell, adaptor, entanglement, quantum computing, qubit, virtual value