QDD is a C++ library which provides a relatively intuitive set of quantum computing constructs within the context of the C++ programming environment. QDD is unique in that the its emulation of quantum computing is based upon a Binary Decision Diagram (BDD) representation of the quantum state. This is in contrast to the complex number representation used by QCL and Open QuBit. Quantum Fog is another quantum system simulation package developed by the Artiste company. Quantum Fog is similar to QCL and Open QuBit in that it provides an exact simulation of quantum behavior, but it differs in that it uses Bayesian Nets to represent the quantum state. Bayesian Nets are used in Quantum Fog because of their expressivness and because they are considered a natural vehicle for working with the conditional probabilities typically encountered in entangled quantum states. Where Bayesian Nets are a natural vehicle for effectively expressing conditional probabilities, BDDs are a natural vehicle for effectively describing boolean functions. The use of BDDs to model the underlying quantum state allows QDD to model relatively large quantum states and provides a relatively high degree of performance. In the reference implementation of Shor's factoring algorithm provided with the QDD library, SHORNUF, QDD can factor a 16 bit number in approximately 8 minutes on a P200 with 64M of RAM. However, the use of a BDD representation also restricts QDD to operating as a "digital" quantum computer. QCL and Open QuBit, in contrast, support an "analog" computer model. Although the BDD representation used by QDD provides a relatively high degree of scalability and performance nearly linear in the size of the state representation, the size of the underlying representation is still exponential in the number of quantum bits used and therefore QDD still cannot be used to efficiently factor very large numbers. Nonetheless, it is hoped that, by releasing the source code for QDD, others will be inspired to consider other optimizations to the library that might lead to new or better techniques for modeling quantum computation.
The QDD library and the program SHORNUF are free software licensed under the GPL.
I make no claims at this point about the portability of this code. I have compiled it on my home RedHat 8.0 Linux system.
The best I can do at this point is a couple of small, commented excerpts from the SHORNUF program that illustrate some high points of using QDD to implement quantum operations.
Beyond that, the code is the documentation. I may ultimately publish a short paper on how BDDs are used by QDD to represent quantum states. However, in the absence of overwhelming demand, I will first work on trying to find better graphical representations for quantum states (Now, that would be something!). For an excellent overview of mixing classical and quantum computing concepts, see the QCL documentation by Bernhard Oemer.
My ultimate goal for QDD is to use it to factor RSA challenge problems. However, given the current capabilities of QDD, this would really be quite an accomplishment!
My primary focus in the coming months (years?) will be on the fundamental representation used by QDD. It is only through breakthroughs in this area that QDD can ever hope to take on RSA challenge problems. In keeping with this philosophy, my future work will involve :
Aside from these tasks, there are lots of software engineering types of things that could be done to it (better naming conventions, more consistent interface, etc). However, since I am not a software engineer, these things will have to wait.
If you would be interested in helping me to improve QDD in any way (theory, coding, documentation, permanent home page, etc), feel free to let me know. Of course QDD is open source software, so you are free to improve or extend it on your own in any way you see fit as long as the result remains free.
The BDD package used by (and distributed with) QDD is the BuDDy package by Jorn Lind-Nielsen .
The seminal paper on BDDs was written by Randy Bryant . His paper on *BMDs also looks very promising for this application.
The quantum algorithms used in SHORNUF are taken almost directly from those distributed with QCL, by Bernhard Oemer.
Of course, Shor's factorization algorithm came to us courtesy of Peter Shor.
Thanks to John Cowles from the University of Wyoming for his assistance in understanding quantum factorization, the properties of mod, and the super-cool modular inverse function.
The Open QuBit project.
Computing with a cup of coffee : Bulk Spin