Modern microprocessors have to be designed with quantum mechanics in mind in order to ensure that they function correctly. In essence they use quantum effects to ensure that their classical computations are upheld. What no current processor does is to fully exploit quantum effects. Recently, it took 1,600 computers communicating over the Internet 8 months to solve the factorisation of a 129-digit number. Should it be possible to build a microprocessor which fully exploits quantum mechanics then it may be possible to carry out such factorisations in remarkably less time. The RSA algorithm, a widely used encryption system, is safe only if such factorisations cannot be performed quickly.
This report details a successful attempt to build a quantum circuit simulator. The project was undertaken as part of a final year assessment for a MEng degree in Computing at Imperial College, London. The simulator can accurately simulate circuits that are far more complex than anything that is expected to be built within the next few years.
The simulator runs on an IBM compatible PC running Windows NT or Windows 95. It takes an input in the form of a mathematical description of a circuit and then simulates it. It appears that this report is the first report on an attempt to build a quantum circuit simulator and the simulator itself may well be the first one to be publicly released. Due to this I have had to invent a number of algorithms for use in simulating the circuits. These algorithms are documented with the main body of this report.
Quantum computation appears to be inherently exponential in space and time to simulate on a classical machine and so the field of quantum circuit simulation is rich in possible heuristics that may reduce the resource requirements. I have made a start on researching such heuristics and the results are documented within.
This report also attempts to explain the behaviour of quantum computation and why it allows the possibility of exponential speed-ups over classical machine to the lay person. Later sections of the report document my design and implementation of the simulator in roughly chronological order and my thoughts on modern design processes. This may be of some interest to computing professionals.
I would like to thank Iain Stewart for introducing me to the field of quantum computation in the first place, suggesting an excellent project idea and then explaining the basics of the field in such clear terms. I would also like to thank my project supervisor, Steve Vickers, for his help and guidance throughout the course of the project. The works of P W Shor, David Deutsch and many others have provided the central research material for this project. Without their constant research in to this exciting field projects such as this would not be possible.
Back to Jon Marshall's Quantum Pages
This web page (c) 2000 Jon Marshall. Last updated 3rd June 2000