Quantum Computers A Simple Example

In this contribution to Non-standard computation we review the most important ideas about quantum Turing machines, quantum complexity theory, the Feynman idea, and concepts for the realization of quantum computers. 

As a simple example of a quantum computer, the quantum realization of a universal, reversible gate is described in Sect. 5.2. 

In Sect. 5.3 the concept of a universal, reversible Turing machine is introduced and it is shown that any irreversible Turing machine can be efficiently simulated on the reversible one. This implies that reversible Turing machines can solve problems about as fast, and with about the same memory requirements, as usual irreversible computers. 

How to obtain a quantum Turing machine from a classical reversible Turing machine is outlined in Sect. 5.4. 

Up to this point, we do not tackle the subject of quantum complexity theory. Questions such as whether there is an advantage in using quantum computers for special tasks (for example factoring integers) are not in the foreground. However, since interesting results have recently emerged on this subject we will review the main ideas in Sect. 5.5. 

---