Category: Computation Models and Computational Complexity

We now come to the issues that make computer scientists look to the quan- tum paradigm for answering some of their questions on efficient algorithms. Efficiency is quantified in terms of how the resources used for the compu- tation scale with the number of input bits n. Typically, polynomial scaling is termed “efficient” while exponential…

In the early 1970s, this line of thinking prompted Bennett to come up with ways to beat the Landauer limit: by introducing reversible computation. The gates we have studied so far, such as AND and XOR, are intrinsically irreversible since they are two-one functions. An n → m function can, however, be implemented reversibly if…

We are studying classical gates to help us develop quantum gates. Quantum gates are unitary. This means they are reversible: they can be “run backward”. More practically, the meaning is that the inputs can be deduced from the outputs. Most classical gates however, are irreversible, and cannot as such be extended to quantum gates. For…

It is well known that AND, NOT and OR form a universal set of gates. Consider for example the case n = 1. We have four distinct functions imple- mented as in Table 6.2. TABLE 6.2: The four 1-bit functions. Function Action Form Gate f 1 : 0 → 0 1 → 0 f(x) =…

Classical computation using binary variables works on Boolean logic, and implementation of basic logical operations are done through logic gates that are well known. We will revise their behaviour and notation and express their action as matrix operators. We will think of a computation as effected by a circuit evaluating some Boolean function whose input…

For a long time historically, computation was a matter of actually solving, or finding algorithms to solve, various mathematical problems using mechan- ical or other algorithms. It was only in the early twentieth century that the process of computation was modelled in mathematical terms, largely in the works of Alan Turing, Alonso Church, Kurt G¨odel,…

Now that we have the laws for qubits, we need to develop a system for meaning- fully manipulating them. Much of the current paradigm for quantum comput- ing is motivated by classical computation theory, especially the circuit model for computation. In this chapter, we will briefly overview the classical model of Boolean circuit theory, and…