QGAME

Quantum Gate And Measurement Emulator

(a quantum computer simulator)

Lee Spector (lspector@hampshire.edu)
School of Cognitive Science
Hampshire College






Introduction

QGAME (Quantum Gate And Measurement Emulator) is a system, that allows a user to run quantum computing algorithms on an ordinary digital computer. Because quantum computers have complexity advantages over classical computers, any classical emulator will necessarily be less efficient than the quantum computer that it is emulating. QGAME nonetheless allows the user to find out what outputs the quantum program would produce, and with what probabilities (since quantum computation is in general not deterministic).

QGAME is based on the "quantum gate array" model of quantum computation, in which quantum "gates" (represented as square matrices) are applied to a register of qubits (via tensor product formation and matrix multiplication). QGAME always starts with all qubits having the value zero (in the state |00...0>), applies a sequence of gates, and returns values about the resulting state. Measurement gates cause the system to branch, following one execution path (with the appropriate quantum state collapse) for each possible value. Final measurements are made across the end-states of all of the resulting branches.

Two versions of QGAME are currently available, the original Common Lisp implementation and a new C++ library (QGAME++), written by Manuel Nickschas. A few features vary between the implementations, but the core concepts and interface syntax are consistent. The C++ library is also included in distributions of Jon Klein's Breve simulation environment.

The QGAME graphical user interface (GUI), pictured above, is a quick hack for the Common Lisp version of QGAME, intended to allow people with no knowledge of Lisp to experiment with QGAME. It uses Macintosh Common Lisp (MCL) interface code and will work only under MacOS with MCL. Not all features of QGAME are available from the GUI. One uses the GUI by typing (or pasting) a program into the "QGAME Program" dialog and clicking on the "Run" button. The amplitudes can be monitored during the run and the probabilities of finding the system in any given state at the end of the computation are printed in the "Listener" window at the end of the run. Note that the Common Lisp implement of QGAME itself is platform independent (it will run on any platform for which a Common Lisp environment is available); only the GUI requires Macintosh Common Lisp.


Documentation

The most detailed description of QGAME, and of its use for automatic quantum computer programming (using the genetic programming technique), is in the book:

Spector, L. 2004. Automatic Quantum Computer Programming: A Genetic Programming Approach. Boston, MA: Kluwer Academic Publishers. (Cover and links, PDF brochure with mail/fax order form, description and online order form)

Additional version-specific documentation is included with the software downloads, either in source code comments or in separate files. For the C++ version (QGAME++), detailed documentation is also available in the QGAME++ HTML Documentation (which is also contained in the QGAME++ download, in HTML, LaTeX, and XML formats).

Related Publications


Code

QGAME++ source code in C++, including documentation (by Manuel Nickschas): qgame-0.4.1.tar.gz.

The Breve simulation environment, which includes the C++ version of QGAME: see http://www.spiderland.org/breve.

QGAME source code in Common Lisp: qgame.lisp.

Additional Common Lisp code to implement MATRIX-GATE forms, gate compression, and unitarity checks: gate-compression.lisp.

QGAME graphical user interface source code (requires Macintosh Common Lisp, updated as of December 2002 for MCL 5 under Mac OS X): qgame-gui.lisp.



Acknowledgments

This project has received support from an NSF Director's Award for Distinguished Teaching Scholars (to Spector), from NSF grant EIA-0216344, and from the Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory, Air Force Materiel Command, USAF, under agreement number F30502-00-2-0611 (for the project "Multi-type, Self-adaptive Genetic Programming for Complex Applications").