Home > Issue_04 > The Essence of Quantum Computing

The Essence of Quantum Computing

6. The universal quantum computer

 

In his classic 1985 paper titled ‘Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer’81, David Deutsch described how a computer might run using the strange rules of quantum mechanics and why such a computer would differ fundamentally from ordinary computers. In fact, Deutsch showed that it is possible to construct reversible quantum gates for any classically computable function and suggested that quantum superposition might allow quantum evolution to perform many classical computations in parallel. Deutsch’s paper described the first true quantum Turing machine (QTM). In QTM, read, write, and shift operations were all accomplished by quantum mechanical interactions and whose “tape” could exist in states that were highly non-classical. For example, it could simultaneously encode many inputs to a problem on the tape and perform a calculation on all the inputs at the same time (quantum parallelism). In 1997, Samuel Bernstein and Umesh Vazirani82 showed that it is possible to conceive of a universal quantum Turing machine. In such a construction we must assume a sufficient supply of bits that correspond to the tape of a Turing machine. The QTM is sufficiently simple and at the same time universal to prove various theorems about quantum computation.

The universal quantum computer can perfectly simulate the UTM82. In addition, it can simulate various physical systems, real and theoretical, which are beyond the scope of the UTM. In quantum computers, we manipulate its global state at all times even when our intention is to manipulate a specific part of it, even as small as a qubit.

It is not yet clear if an equivalent of the Church-Turing Thesis exists for quantum computers. In 1985, David Deutsch provided a physical version of the Church-Turing Thesis: “Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means”. He then generalized the Thesis to “every computation, which can be realized physically, can be executed using a quantum Turing machine.”84 Deutsch has played a pioneering role in bringing quantum computing into the mainstream of computing.

To me quantum computation is a new and deeper and better way to understand the laws of physics, and hence understanding physical reality as a whole. — David Deutsch

The most important application of quantum computing in the future is likely to be a computer simulation of quantum systems, because that’s an application where we know for sure that quantum systems in general cannot be efficiently simulated on a classical computer. — David Deutsch

We do not know if quantum computers are inherently more powerful than classical computers partly because we are unsure how the quantum and the classical worlds are separated. For example, are there resources, truly unavailable in a classical world, being utilized in a quantum computation? It may eventually turn out that quantum computers are only as powerful as classical computers: that any problem which can be efficiently solved on a quantum computer can also be efficiently solved on a classical computer. It all depends on how clever we are in designing algorithms and the nature of algorithms permitted by the axiomatic systems we use in designing them. Also, there are issues of computability (i.e., which computational problems computers can or cannot solve), and issues of complexity (how efficiently computers can solve the problems they can). The fact that a computer can solve a particular kind of problem, in principle, does not mean that it can be done in practice for such obvious reasons that the running time of the computer is too long or the memory requirements are enormous, and so on.

7. Operands and operators in quantum mechanics

 

In physics, the notion of space is intimately related to distribution of matter; two material objects cannot occupy the same space at the same time. The notion of time comes from change. Without detectable change there is no need for the notion of time. In mathematics there are two basic entities: operands (nouns) and operators (verbs). For an operand (noun) to change its value it needs to be operated on (verbed). Operands have space-like property in that they can move to a new value. Operators have time-like property because they bring about change. Operators may also show space-like properties as when describing the gradient of a distribution of operands. In natural languages too, we find certain nouns also used as verbs and vice versa. In quantum mechanics, operators serve as surrogates for certain operands, hence commutability of operators plays such an important role in measurement. Here are a few such operators:


[81] Deutsch (1985).
[82] Bernstein & Vazirani (1997).
[83] Deutsch (1985).
[84] Deutsch (1985).

Pages ( 9 of 13 ): « Previous1 ... 78 9 1011 ... 13Next »

Leave a Comment:

Your email address will not be published. Required fields are marked *