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:
- 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.
- 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:
- Notes for QC
simulator – v2.1 (Includes documentation & examples of input
file formats.)
- SEQCSim executable (ver. 0.8, release, Windows XP,
32-bit)
- ZIP file of some
sample input data files – expand in parent directory of .exe directory
- Final preprint
(v. 1.01) of paper, “Space-Efficient Simulations of Quantum Computers,” to
appear in ACMSE 2009.
- 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.
- ZIP
file of QFT adders, (2-15) bits. These input files were used to obtain the
empirical data in the preceding paper.
- Final
version (v2) of PowerPoint
presentation (here’s a PDF
version) presented at ACMSE 2009.
- 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.
- 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.