The Quantum Turing Machine Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Modeling of computational value, reasoning of computation or evaluation of memory block all can be summarize as Automata or partly related to it. To emphasis more on Automata, approaching the memory either on a single stack or a empty stake can have a variety of difference. The topic discussed as per this report is Turing machines, mainly on Quantum Turing Machines.

Based on 'A Computable Odyssey', notes and materials by James Harland, he explained briefly that a Turing Machine is a theoretical device which comprehends memory using a infinite strip of tape. Invented by Alan Turing in the 1936, a Turing Machines can adapt to calculate logic of computer algorithms and hence explains what function goes on inside the CPU of a computer. Thought Turing Machine is a theoretical representation of the practical computing technology, its representation helps scientist and programmers understand the limits of a mechanical computation.

With this similar principle, making a Turing Machine to simulate other Turing Machines are called universal Turing Machine or UTM in short. These theories proposed by Alonzo Church who later on further proceed with the principle to be a Quantum Turing Machine with his computability-theory of Church-Turing thesis. Using the theoretical explanation, Quantum Turing Machines are presented via the Quantum Computers.

With the principle of Turing Machines applied to the generation of Quantum Computers, the complexity of bigger problems can be solved without worrying on how big a problem or how complex the algorithm is. Combination of Turing Machines also can be done without worrying about the possibility of getting a higher rate of errors, spilt or merge of solutions.

In this assignment, we're going to stress on two abstract topics from the Quantum Turing Machine, explaining the basics of Quantum Computers and how it works with the Turing Machines AND looking into further aspect on how Transition Matrices are used to go about problems or algorithms involved in a Quantum Turing Machine.


Being scientifically proven of solving way larger complex algorithms compared to classical computers, Quantum computers are fundamentally different. Due to the physics of quantum information mainly relates to the physics of possibility. Normal or classical computer memories to exists at a given time and space are a constraint as a simple list of zeros ( '0' ) or ( '1' ). Comparing both, in a single quantum memory, there can exists many combinations, such as possible lists of ( '1' ) and even zeros ( '0' ) can all exist simultaneously. The complexities make a complete means of a quantum search through these large states made of multiple possibilities.

To begin with, rather than focusing on the large systems, we will go in-depth of quantum information through a description of the smallest quantum systems, which is responsible as a whole for the performance by a Quantum Turing Machine to process a heavy and complex workload and in general why Quantum Computers are way more powerful.

Bits are a regular term used by every computer users these days, and are equivalent to the atom in matter of our everyday life. Bits on the hand are 'atoms' for computers, being the simplest possible units of information. Just as how an atom in a matter reacts to certain condition, bits responds in one way although having both ways. Measuring a normal bit, will result in one or two possible outcomes at most. Now comparing qubits and bits, it seems as if there are no difference in both, since both only gives the same answer, but the difference is in the possible questions proposed instead of the possible answers that can be acquired. The difference lies in the power to comprehend questions and apprehend them separately. For classical/normal bits, only a individual or single measurement is limited at one time, hence only a single question can be asked. For example : "Is this bit a one or a zero"? (Sounds familiar?). Qubit on the upper hand only one of two answers can be given but can be asked many different questions even though for each particular questions can only be answered once.

The complete description system can also be called as a System's State; a identically state are said to be of a same state if every system in a particular state behaves identically too. Classical/Normal bits, therefore, are always in one of the two states, "one" or "zero".

Knowing how state works for a quantum Turing Machine, we now look into how bits and qubits function differently in a state. Using the example of a 3D movie, notice that the 3D glasses that are given contains a red and blue side on each side. This is acquired by the rays of light from the movies, also known as photons (small unit of light), hitting on the glasses at a certain angle creating a 3D image to appear. But knowing this principle, how does each side of the lens differentiate which photon enters the red or blue lens? Simple Turing machine works in a way which only accepts one 'photon' and gives out the output, not knowing whether its right or wrong.

A quantum Turing Machine on the other hand, does not work that way. Quantum Turing Machine uses the concept of circular polarization, where taking the 3D movie example again, each lens from the 3D glasses will be prompt with 'With the incoming photon, which is exactly right-circularly polarized and which is left-circularly polarized?' each time a photons hits on the lens. Using this, each state of a Turing Machine can ask different questions such as, "Which of the polarization is exactly horizontal or vertical?", "Which of the polarization is diagonal or anti-diagonal?", "Which of the polarization right-circularly or left-circularly polarized?" all to give out one output.

Using this example, Alan Turing proposed a qubit model by explaining the representation of qubits on a state via points on a sphere through a series of questions as follow.

Which of the polarization is horizontal or vertical?

Which of the polarization is diagonal or anti-diagonal?

Which of the polarization is right-circularly or left-circularly polarized?

Representation Model of Qubits by Alan Turing

*All diagrams are shown on Appendix (page )

In *Figure 1 : It shows that placing the point on the red axis, it indicates whether a particular photon will be measure horizontal, vertical or a combination of the two.

In *Figure 2 : The single point plotted can read two questions at the same time and give an answer. Adding a third blue axis represents the last question. As a whole :

Red : Horizontal or Vertical

Green : Diagonal or AntiDiagonal

Blue : Right or Left

In *Figure 3 : Labelling six single-qubit states on the single-qubit sphere,

In *Figure 4 : Applying the six points, each represents a state that have a 100% chance of being transmitted through a polarizer hence 100% of being measure in a particular quantum state. This is because every single point can corresponds to a single line that passes through the center of the sphere.

In *Figure 5 : Drawing a new line perpendicular to the measurement axis and passing through the point corresponding to the quantum state, it divides the measurement axis into 2 segments whose lengths corresponds to the probability of the 2 possible measurement results.

Applying this, the measurements will appear to be random for a change state of a qubit.

How then is it possible to apply this model by changing qubits without having random results? The rotations are defined by a single axis, just like measurements. Instead of projecting all possible states into 2 possible outcomes, they rotate all states on an axis. The points on the axis of rotations only will be unaffected, thus leaving out the unwanted qubits states to changed not affecting the measured ones.

In *Figure 6 : We can now summarize the important characteristics of single qubits :

All single-qubit states correspond to a point on or inside a sphere.

Every axis corresponds to a single quantum measurement, and every measurement changes the state of the qubit to match the result of the measurement.

Qubits can be changed by rotating them around an axis.

In *Figure 7 : Because quantum bits can be single electrons, ions or photons, all of which can be accidentally measured using a single stray atom, this gives room for a high chance of decoherence. One of the many reasons why 100-qubit quantum computer has not yet been built.


Abstract Machine

Quantum Turing Machine also known as Universal Quantum Computer or in short as QTM is an abstract machine. The properties of being abstract allows it to be model the effect of a usage of a quantum computer. Quantum algorithms can be represented as a particular quantum Turing machine which is known as quantum computation.

Classical and probabilistic Turing Machines are the main definition of Quantum Turing Machine, a probabilistic Turing machine as well, its framework is based on transition matrices which comes in many forms. Base, CD, CD-MF, SP , SP-CD, SP-CD-MF and Oracle are one of the few set of control flow constraints defined in abstract machines models used to analyze the machines for parallelism under ideal conditions.

The constraint flows are as follow :

BASE : Until the preceding branch in the trace is completely resolved, the instruction cannot be executed. This shows that the branch instructions should be executed in order, one time per cycle.

CD : Until the control dependence branches are completed, the instruction cannot be executed. Similarly, the branch instructions are executed in order, one per cycle, to avoid the ability to perform multiple flows of control simultaneously.

CD -MF : Until the control dependence branches are completed, the instruction cannot be executed. The branches can be executed in parallel and not necessary to be in ordered, the branches can be in multiple flow.

SP : Until the control dependence mispredicted branches are completed, the instruction cannot be executed. The branch instruction that are controlled have to wait for all preceding mispredicted branches.

SP-CD : Until the control dependence mispredicted branches are completed, the instruction cannot be executed. Similarly, the branch instruction that are controlled have to wait for all preceding mispredicted branches, this time however not just the ones it is control dependent on.

SP-CD-MP : Until the control dependence mispredicted branches are completed, the instruction cannot be executed. No additional constraints are added on these branches.

ORACLE : No constraints are proposed due to control of the branch flow.

**All constraints definitions are referred in reference section.

The ability to handle control flow is distinguished by each machine. More aggressive machines have less restrictive constraints. For example, observing the BASE machine control flow constraints is of the most severe, preventing the instructions from executing before any other preceding branches, without the uses of any of the three techniques. Thus comparing with the CD-MF machine, it doesn't require the properties of branch ordering constraint at the same time it may follow any amount of flow of control.

Illustration of the power of the difference in each abstract machine models, *Figure 1 (in appendix/Matrices), assuming there are no data dependencies. Each node in the graph consist of single instruction and followed by each node, contains the set of branch instructions which shows is control dependency. Thus an abstract machine works by branching instruction with edges to trace the control dependence relationship and by allowing it to execute all questions at one go.

*Figure 2 (in appendix/Matrices) shows the executions of the other machine models where the dependency due to the control flow as well as the instructions of the same leve represents the edges to be executed at the same time.

Stochastic Matrix

Quantum Turing Machine is related to probabilistic complexity of Turing machines, and thus transition matrices makes up the basis framework of the machines. Stochastic Matrix is one type of matrices used being capable of applying it to the quantum complexity, Andrey Markov, who is famous for the Markov Chain concept states that the conditional probability distribution such as the Stochastic Matrices enables the frame to withhold large complexity of workload.

Basic of Stochastic Matrix comes from a long line of the Markov Chain. The technique of generalized automata was a convenient instrument for the investigation of representability of problems. Via Quantum principles, the stochasticity can aid in the number of languages demonstrated, example being set of symmetric words and set of initial segments of an arbitraty fixed infinite binary sequence (unlike normal Turing machines which uses common basic binary sequence).

Knowing the basic of this principle, the stochastic matrix is divided into two parts :

A right stochastic matrix and ;

A left stochastic matrix.

Based on the Cat/Mouse example, I can explain the Matrix in a much more simpler version. Take for example a scenario exists :

State I: One cat in the first box, and one mouse in the third box: (1, 3)

State II: One cat in the first box,one mouse in the fifth box: (1, 5)

State III: One cat in the second box, one mouse in the fourth box: (2, 4)

State IV: One cat in the third box, one mouse in the fifth box: (3, 5)

State V: One cat ate the mouse and the game ended: F

Using a stochastic matrix, the states above can be represented by using this probability matrix :-

P = \begin{bmatrix} 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 1 & 0 & 0 \\ 1/4 & 1/4 & 0 & 1/4 & 1/4 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}.

defining from the probability matrice P=\left(\begin{matrix}p_{1,1}&p_{1,2}&\dots&p_{1,j}&\dots\\ p_{2,1}&p_{2,2}&\dots&p_{2,j}&\dots\\ \vdots&\vdots&\ddots&\vdots&\ddots\\ p_{i,1}&p_{i,2}&\dots&p_{i,j}&\dots\\ \vdots&\vdots&\ddots&\vdots&\ddots \end{matrix}\right)..

Hence, with the results above, assuming it's a long term process, π = (0,0,0,0,1). Noting that the cat will eventually catch the mouse.

Hence, applying the concept to the matrice, and by removing the fifth state :-

T=\begin{bmatrix} 0 & 0 & 1/2 & 0\\ 0 & 0 & 1 & 0\\ 1/4 & 1/4 & 0 & 1/4\\ 0 & 0 & 1/2 & 0\\ \end{bmatrix},

Hence, the expected mouse survival will be

E[K] = Ï„(I-T)-1 1= 4.5

Opening the brackets : -

E[K(K-1)…(K- n+1)] = n! τ(I-T)-nTn-11.

Through this equation, a graph of Number of time steps against Probability of Mouse Alive can be plotted roughly based on the matrice format.

This is to show that the stochastic matrix is used as a basic of Turing machines computability problems which and has and is being used as a theory section in the Quantum Engineering of Computer Science, the matrix enables scientist to further comprehends the probability of complex algorithm enabling engineers, scientist and even programmers to make use of the system to manage bigger problems.




Abstract Machine Types of Constraints