Space-Efficient Quantum Computer Simulator
and Applications in Computational Physics

M. P. Frank1, Uwe Meyer-Baese1, Irinel Chiorescu2,
Liviu Oniciuc1, and Robert van Engelen3
1Dept. of Electrical & Computer Eng., FAMU-FSU College of Engineering
2National High Magnetic Field Laboratory and Dept. of Physics, Florida State University
3Dept. of Computer Science, Florida State University

 

In this project, guided by Prof. Uwe Meyer-Baese, we are developing several versions of a quantum computer simulator with low memory requirements, and investigating whether it might be useful for applications including:

  1. Desktop-scale simulations of quantum-mechanical physical systems for which conventional numerical modeling techniques would require too much memory (i.e. supercomputer-scale) to be affordable for the average researcher or student.
  2. Simulations of arbitrary moderately-sized quantum circuits for educational purposes (e.g. in course assignments for a course on quantum information processing).

Project History

(Look up date): Computational complexity theorists characterize generalized space-time tradeoffs for computations having wide dataflow graphs.

ca. 1942:  Richard Feynman invents the path-integral formulation of quantum mechanics, showing that computing quantum amplitudes does not require carrying out time-evolution of a state vector.

ca. 1952:  David Bohm shows that, to model quantum statistics, it is sufficient to update a classical state under the influence of local amplitudes.

ca. 1993:  Quantum complexity theorists show constructively that BQP is a subset of PSPACE, i.e. that space-efficient simulation of quantum computers is possible.

ca. 2002:  Dr. Frank (then at UF) describes a particular optimized algorithm for space-efficient simulation of quantum computers in his lecture notes and talk slides.

2004:  Dr. Frank moves from UF to FSU.

Fall 2006-Feb. 2007:  Under PI Meyer-Baese and co-PI Irinel Chiorescu of NHMFL, we apply to FSU CRC for a planning grant to develop an FPGA-based version of the simulator.  The grant is subsequently awarded.

May 2007-Aug. 2008:  Frank is away from FSU.

Fall 2008: Frank returns and rejoins the project as a postdoctoral associate.  The first early prototype version of the simulator is developed in C++.  Two conference papers are submitted (to SPIE and ACMSE) describing the preliminary work.  Another funding proposal (to NSF) to continue the FPGA development and investigate applications is written & submitted w. an additional co-PI, Robert van Engelen of the FSU CS dept.

Spring 2009: The ACMSE and SPIE conference papers are being completed and presentations are being given.

Project Materials

The following project-related materials are currently available online through this page:

 

  1. Notes for QC simulator – v2.1 (Includes documentation & examples of input file formats.)

 

  1. SEQCSim executable (ver. 0.8, release, Windows XP, 32-bit)

 

  1. ZIP file of some sample input data files – expand in parent directory of .exe directory

 

  1. Final preprint (v. 1.01) of paper, “Space-Efficient Simulations of Quantum Computers,” to appear in ACMSE 2009.

 

  1. Submitted manuscript (v. 0.5.1) of paper, “A space-efficient quantum computer simulator suitable for high-speed FPGA implementation,” to appear in SPIE QIC VII 2009.

 

  1. ZIP file of QFT adders, (2-15) bits.  These input files were used to obtain the empirical data in the preceding paper.

 

  1. Final version (v2) of PowerPoint presentation (here’s a PDF version) presented at ACMSE 2009.

 

  1. Source code version 0.8, now publicly released under GNU GPLv3.  Here are ZIP (1.2MB) and RAR (728K) archives.  The file tree is presently structured as a Visual Studio solution.  It compiles and runs successfully under Microsoft Visual C++ 2008 Express (which is free), but it does not use any Microsoft-specific libraries, only the ANSI C++ STL and TR1 extensions.  So it should be fairly easy to port it to other platforms.  If you try it on other platforms or make changes, we would appreciate hearing from you about your experiences.  Contact michael.patrick.frank@gmail.com.  At some point, we will upload the source code to SourceForge or GitHub for version management, but in the meantime, just use the archive links above. 

 

  1. A more recent presentation, derived from the one we presented at SPIE 2009:  Michael P. Frank, “Space-Efficient Quantum Computer Simulators,” invited talk presented at the Laboratory for Physical Sciences at College Park, MD (revised version of SPIE 2009 talk), Mar. 14, 2012.  PDF of talk slides.