Qubiter
Copyright(c)19982007 R.R. Tucci. All rights reserved
News:

Sept 24, 2002: Qubiter is now covered by a US Patent. See "Compiler
for a Quantum Computer", US Patent
6,456,994
(The USPTO made many typing errors when transcribing this document;
they even mistyped the title.
Here is an Errata.
Here is a scan of the official Certificate
of Correction).

Dec
10, 2002: our grant proposal goes down in flames. Grant Proposal
submitted to ARO (Army Research Office) to continue Qubiter research is rejected.
Here is the Project Description section of
the losing proposal.
Here is
the website of Prof. Steven J. Leon, with whom I had the honor of writing
this proposal.

Sept 22, 2004: Applied for a REISSUE PATENT
of US Patent
6,456,994
Some typo fixes and clarification of the claims. Reissue
Patent
RE41,900

June 15, 2007: Updated Qubiter 1.1 to 1.11. Main difference is that
Qubiter 1.11 includes XCode2.4 project file for MacOS X.
What is Qubiter?
Qubiter 1.11 is a free computer program pertaining to quantum computers (QC)
and quantum Bayesian (QB) nets.
Currently, Qubiter is available only as pure C++ source code, without a graphical
user interface.
In its current version 1.11, Qubiter takes as input an arbitrary unitary
matrix, and returns as output an equivalent sequence of elementary operations
(QC operations like controllednots and qubit rotations). Such sequences
are often represented graphically by qubit circuits.
Future versions of Qubiter will take an arbitrary QB net as input, and return
an equivalent sequence of elementary operations. We also plan to add further
optimizations and some quantum error correction.
Some papers that will help you understand Qubiter:
Qubiter is brought to you courtesy of the Artiste company, makers of Quantum
Fog. If you want to contribute to Qubiter, please contact us at
What is the connection between Quantum Fog and Qubiter?
In classical computation, code is usually written in a high level language
(such as C++), which, for the most part, does not mention bits. Then a compiler
of some sort reduces the high level language to bit level instructions.
Quantum Fog is a tool for writing QC programs in
a high level visual language, and then simulating the resulting programs.
Quantum Fog can also feed this high level language to Qubiter. (The high
level language uses decision diagrams called quantum Bayesian networks, which
are discussed elsewhere in this website). Qubiter is a tool that translates
this high level language to qubit level instructions which can then be fed
to a QC. Hence we call Quantum Fog a quantum computer simulator and
Qubiter a quantum compiler. Quantum Fog differs from other QC simulators
presently available in that it is not a "bit level" simulator.
Where can I find Qubiter?
You may download Qubiter 1.11 source code by pressing
here.(about 90 K).
Comments about Qubiter1.11 Distribution:
Qubiter 1.11 is fairly crudea pure C++ program with no GUI. It's
just a research tool, so don't expect too much. The Qubiter 1.11 distribution
includes an XCode 2.4 project file. Qubiter is linked to the Clapack
library.
XCode is an application (Integrated Development Environment) produced
by Apple Inc. It provides an interface for the gcc (GNU) compiler. XCode
is available for free at the Apple website.
Clapack is a library of linear algebra subroutines. It was produced
by translating the Fortran library called Lapack into C via a tool called
f2c. Clapack is available for free at
www.netlib.org. Clapack is automatically
included (as the vecLib Framework) in the standard installation of MacOS
X .
Since Qubiter 1.11 is pure C++, you don't need XCode, or even Mac OS X to
use it: you can run Qubiter on any platform for which you have a C++ compiler.
However, if you don't use XCode, you will have to write your own makefile
or project file. Furthermore, if you do not use MacOS X, you will have to
install the Clapack library in your computer, if it isn't installed already,
as it is in Macs.
General Linear Algebra Software:

Netlib The mother lode. A giant repository
of Linear Algebra software, including Lapack and Clapack.

Matlab /
Octave. Matlab is an excellent
commercial program made by The Mathworks, but it is very costly for
nonacademics. Octave is an excellent GPL program that clones most of Matlab's
Linear Algebra subroutines.
Octave/Matlab Quantum Compiling Software:
CS Decomposition Corner:
Qubiter applies recursively a technique from Linear Algebra called the CS
Decomposition (CS = Cosine Sine). The CS decomposition is very closely
related to the Generalized Singular Value Decomposition (GSVD). To perform
the CS decomposition, Qubiter calls subroutines from Clapack, a free software
package available at Netlib. The
Matlab software package (sold by The
Mathworks) also contains subroutines that can do the CS decomposition.
Here are some authors of papers and/or software dealing with the CS
decomposition:
Related Papers:

"Elementary Gates for Quantum Computation", by a cast of thousands (Barenco
et al)
quantph/9503016

"Reducing Quantum Computations to Elementary Unitary Operations'' by G. Cybenko
[Comp. in Sci. and Engin., March/April 2001, pp. 2732]
pdf . This
pedagogical paper reviews Barenco et al algorithm

"How to Compile A Quantum Bayesian Net", by R. R. Tucci,
quantph/9805016

"A Rudimentary Quantum Compiler (2cnd Ed.)", by R.R. Tucci,
quantph/9902062

"A Practical Method of Constructing Quantum Combinational Logic Circuits"
by JaeSeung Lee, Yongwook Chung, Jaehyun Kim, Soonchil Lee,
quantph/9911053

"Cartan Decomposition of SU(2^n), Constructive Controllability of Spin systems
and Universal Quantum Computing", by Navin Khaneja, Steffen Glaser,
quantph/0010100

"Clifford algebras, noncommutative tori and universal quantum computers",
by Alexander Yu. Vlasov,
quantph/0109010

"Efficient Discrete Approximations of Quantum Gates" by A. Harrow, B. Recht,
I. Chuang,
quantph/0111031

"A geometric theory of nonlocal twoqubit operations", by Jun Zhang, Jiri
Vala, K. Birgitta Whaley, Shankar Sastry,
quantph/0209120

"An Arbitrary Twoqubit Computation In 23 Elementary Gates" by S.S. Bullock,
I.L. Markov,
quantph/0211002

"A universal quantum circuit for twoqubit transformations with three CNOT
gates", by G. Vidal, C. M. Dawson,
quantph/0307177

"Compiling Quantum Circuits using the Palindrome Transform", by Alfred V.
Aho, Krysta M. Svore,
quantph/0311008

"Realization of a General ThreeQubit Quantum Gate" by Farrokh Vatan, Colin
P. Williams,
quantph/0401178

"Note on the Khaneja Glaser Decomposition",
by S.S. Bullock,
quantph/0403141

"Universal quantum computation", M. Mottonen,
J. Vartiainen, V. Bergholm, M. Salomaa,
quantph/0404089

"A Practical Topdown Approach to Quantum Circuit
Synthesis" by V.V.Shende, S.S.Bullock, I.L.Markov,
quantph/0406176

"Quantum circuit for a direct sum of twodimensional
unitary operators", by V. Bergholm, J. Vartiainen, M.Mottonen,
M. Salomaa,
quantph/0410066

"Qubiter Algorithm Modification, Expressing Unstructured
Unitary Matrices with Fewer CNOTs", by R.R. Tucci,
quantph/0411027

"Quantum Fast Fourier Transform Viewed as a Special
Case of Recursive Application of CosineSine Decomposition", by
R.R. Tucci,
quantph/0411097

"Quantum Compiling with Approximation of
Multiplexors", by R.R. Tucci,
quantph/0412072

"Decompositions of general quantum
gates", by M. Mottonen, J. J. Vartiainen,
quantph/0504100

"The SolovayKitaev algorithm", by
Christopher M. Dawson, Michael A. Nielsen,
quantph/0505030

"A constructive algorithm for the Cartan decomposition of SU(2^N)", by H.
N. Sa Earp, J. K. Pachos,
quantph/0505128

"An Introduction to Cartan's KAK Decomposition for
QC Programmers", by R.R.Tucci,
quantph/0507171

"Replacing Two ControlledU's with Two
CNOTs", by R.R.Tucci,
quantph/0509111

"A new algorithm for producing quantum circuits
using KAK decompositions", by Yumi Nakajima, Yasuhito Kawano,
Hiroshi Sekigawa,
quantph/0509196

"Synthesis of multiqudit Hybrid and dvalued Quantum Logic Circuits by
Decomposition", by Faisal Shah Khan, Marek Perkowski,
quantph/0511019

"Synthesis of Ternary Quantum Logic Circuits by Decomposition", by Faisal
Shah Khan, Marek Perkowski,
quantph/0511041

"Simplifying Quantum Circuits via Circuit Invariants
and Dressed NOTs", by R.R. Tucci,
quantph/0606061

"How to Compile Some NAND Formula
Evaluators", by R.R. Tucci,
arXiv:0706.0479

``How many CNOT gates does it take to generate a
threequbit state?", by M. Znidaric, O. Giraud, B. Georgeot,
arXiv:0711.4021

``Quantum CISC Compilation by Optimal Control and
Scalable Assembly of Complex Instruction Sets beyond TwoQubit
Gates", T.SchulteHerbruggen, A. Sporl, S.J. Glaser,
ArXiv:0712.3227
Caveat Emptor:
Scientists have a deep moral obligation to cite all important prior
art in their scientific papers. Some individuals have studiously
avoided citing the paper "A Rudimentary Quantum Compiler" in their
papers about quantum compilers, even though Qubiter preceded their work by
several years. I cite the work of these individuals in this web page, because
I choose not to sink to their level, but this should not be construed as
my endorsement of their character. I believe that honest competition
is highly beneficial to science, and I encourage it. But hiding prior
art is not honest competition. It is unethical, sleazy behavior that damages
the scientific community in many ways.
Other Groups That Have Worked in the Past on Quantum Compiling:
(in alphabetical order)

Berkeley Univ. (Zhang, Vala, Whaley)

Columbia Univ. (Krysta Svore)

Harvuhd (N.Khaneja, S. Glaser)

Helsinki Univ of Tech (HUT) (M. Mottonen (now at Berkeley), J. Vartiainen)

Jet Propulsion Lab (Colin P. Williams)

U Michigan (I. Markov)

MIT (Aram Harrow)

NIST (Paul E. Black, S.S. Bullock)
Quantum Compiling and
Simulation

NNT (Yumi Nakajima, Yasuhito Kawano,
Hiroshi Sekigawa)

Univ. of Queensland (GQC,
new)
[Home Page]