Designing and Implementing Small Quantum Circuits and Algorithms

It appears, in principle, that the laws of quantum mechan-ics allow a quantum computer to solve certain mathemati-cal problems more rapidly than can be done using a classi-cal computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementa-tion of relatively simple quantum algorithms using current experimental techniques. This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit cur-rent schemes for implementing a quantum computer. Sec-ondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical com-putation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model