The QGame++ System

0.4.1

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 QGAME, which was developed in Common Lisp by Lee Spector (lspector@hampshire.edu). The QGAME homepage can be found at http://hampshire.edu/lspector/qgame.html . For performance reasons, a C++ version of QGAME seemed to be useful, which is why QGame++ was developed. Both QGAME and QGame++ were developed for use in conjunction with a genetic programming system, to allow for the evolution of new quantum algorithms, but can be useful for testing quantum algorithms regardless of their origin.

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.

Most interesting quantum algorithms involve calling an "oracle" or "black box" function of which one is trying to determine some property. QGame++ supports only boolean oracles (that is, with single qubit output), but it allows the user to specify any such oracle and to indicate the desired system output for each specified oracle. Oracles are implemented in the standard way, by applying a (unitary) quantum "NOT" gate on the output qubit wherever the oracle's truth table indicates a "1".

More extensive documentation concerning quantum programs and the quantum gate array model, as well as general information concerning the QGAME system and its uses in genetic programming can be found in Lee Spector's soon-to-appear book:

Spector, Lee. (2004). Automatic Quantum Computer Programming: A Genetic Programming Approach. Kluwer Academic Publishers.

The QGame++ Library

The core of the QGame++ system is libqgame++, a shared library that can be used from other programs. The functions and data structures it provides can be made available by including the file qgame++.h. This documentation should be sufficient to show you how to use libqgame++ in your own programs.

The qgame Command-Line Client

qgame is a simple command-line client that allows you to access the functionality provided by libqgame++ from the command line. It reads a QGAME program from the command line or STDIN and runs it either in evaluation mode (where the program is run several times on different test cases and in the end some statistical data is produced) or simply executes it once (outputting the list of resulting quantum systems in the end, including their respective probabilities and register contents). The evaluation mode effectively runs QSys::testProgram() provided by libqgame++, and is equivalent to the TEST-QUANTUM-PROGRAM function in the Lisp version of the QGAME system.

qgame parses text files containing QGAME programs in the syntax defined by Lee Spector as described in the QGAME Language Description, or in the book on automatic quantum programming cited above. Use 'qgame --help' or 'man qgame' for acceptable command line options.

You might also want to look in the qgame code to see how libqgame++ is used, which should help you getting started with your own libqgame++ project. Note that the focus of this project has been to provide a robust libqgame++ library that can be used in client applications, not to provide a polished command-line interface. The qgame command-line interface provided here serves as a simple demonstration of the use of the libqgame++ library, and may also be useful as-is, but it is fairly simple and has not been extensively documented.

Requirements and Installation

QGame++ should run on any system supporting the current C++ standard. It has been developed on a Linux system using current versions of gcc 3.x, automake and related tools, and most testing was done on Linux, too. However, there have been successes using MacOS X, and it probably will even run on Windows (although I can't help you with compilation and installation there).

Installation instructions can be found in INSTALL. If you are familiar with the standard autoconf/automake style of configuration and installation, you probably won't need to look there at all and can just go ahead using './configure', 'make' and 'make install' as usual. This will install libqgame++, its header files, the command line client and a man page for qgame in the standard locations on your system.

Some Important Remarks

QGame++ is still work in progress, and in an early beta stage. Although it is believed to work correctly, it has not been tested extensively so far. Also I expect the interfaces and QGAME syntax to change in later versions, because the integration in Lee Spector's genetic programming system PushGP (http://hampshire.edu/lspector/push.html) will quite possibly lead to modifications of the current version. So, even though QGame++ is already quite usable in its current state, be warned that there is no guarantee that later versions might break compatibility.

If you find any bugs or problems in this program, or if you want to discuss new features or modifications to existing features, feel free to send a message to qgame-devel@nickschas.de. I would also like to hear from you if you successfully use QGame++ in a project. In general, any comment is welcomed.

The QGame++ system is licensed under the GPL, and you can find the licensing conditions implied by the GPL in the file COPYING supplied with the source code. There is no warranty; not even for merchantibility or fitness for a particular purpose.

Acknowledgements

As mentioned above, QGame++ is based on Lee Spector's Lisp version QGAME, and even though naturally the C++ code is very different from the Lisp code and I used a different approach to implement most things, this work was heavily inspired by QGAME. In addition, planned as a faster replacement for QGAME, the syntax used and features that have been implemented come straight from QGAME, as do parts of this documentation. Thanks and credits therefore go to Lee Spector, whose homepage at http://hampshire.edu/lspector you should not miss.

This work was also funded by Lee, who therefore helped me survive in a foreign country ;-), and gave me the opportunity to be involved in research in the U.S., in spite of the numerous difficulties arising from my status as an exchange student. Many thanks for that.

-- Manuel Nickschas <qgame-devel@nickschas.de>
Amherst, Massachusetts
March 2004

---