Quantum Turing Automata: Computational Power of The

Download as pdf or txt
Download as pdf or txt
You are on page 1of 6

Computational Power of the

Quantum Turing Automata


Sina Jafarpour, Mohammad Ghodsi, Keyvan Sadri, Zuheir Montazeri

Abstract
Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially
bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of
the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on
the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics
and investigate the domain of this novel definition for computation. The main object is to show the domain of
these Computation machines and the new definition of Algorithms using these automata.
In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all
the fundamental concepts required for the next chapters. In section two we describe various classes of classical
complexity automata. In next chapter we introduce quantum complexity featuring Quantum Turing Machines
and discuss its relationship to classical complexity. Section four presents a relationship between Quantum
complexity classes based on the quantum Turing machines and Quantum oracles, and their relationship with
corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in
problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe
the field to be headed, and what might reasonably be expected in the future.

Keywords
Quantum, Computation, Complexity, Turing machine, Oracle, Computability, Grover algorithm

This, in combination with Gödel theorem, came as a bit


1. Introduction of a surprise to mathematicians. On the other hand, it
merely demonstrated what the greatest mathematicians
Early in the 20th century Gödel, Church and Turing always knew and practiced, namely that mathematics is
proposed 3 different models of computation: an art. Also, that some of the best mathematics is
• general recursive functions of Gödel constructed by broadening a particular theory that is an
• lambda expressions object of some assertion and attacking the problem from a
• the Turing machine higher level. For example, algebraic problems can often
Somewhat later it turned out that they were very much be tackled with a surprising efficacy by rolling out the
the same. But later still, towards the end of the 20th apparatus of complex analysis.
century, it turned out that certain physical assumptions,
which may not necessarily correspond to how certain The original Turing machine was deterministic (DTM):
computations can be done, were smuggled into all three the head would be always in a single state, which would
models. In particular quantum computation, the subject of uniquely determine which direction it would go into and
this lecture, is not modeled correctly by any of the above. how far. There is a variant of the Turing machine, which
But there are even some aspects of classical computation, is not deterministic. The head may be in a state, which
which are not adequately accounted for by the Turing gives the machine certain choices as to the direction and
machine and equivalent models, e.g., the thermodynamics length of the next traverse. The choices are then made by
of computation. throwing dice and possibly applying some weights to the
outcome. A machine like that is called a probabilistic
The Turing machine was invented by Alan Turing in Turing machine (PTM), and it turns out that it is more
order to address Hilbert's Entscheidungsproblem. It is powerful than the deterministic Turing machine in the
sufficiently simple so that various mathematical theorems sense that anything computable with DTM is also
can be proven about it. In particular by using this model computable with PTM and usually faster.
Turing was able to show that the Entscheidungsproblem
must be answered in negative, i.e., there is no mechanical But both PTM and DTM are based on classical physics:
procedure, in general, which can be used to decide a the states of the tape and of the head are always readable
theoremhood of an arbitrary statement in mathematics. and writable, data can be always copied, and everything
is uniquely defined. As a result, the definition of human however, that the constant 1/3 is arbitrary. Any constant
computation is deeply affected by the environment we are value in the range (0, 0.5) gives an equivalent definition
living in. The main question is that on the grounds that of the class BPP, since repeated executions of the
the human brain is not environmental dependent and also probabilistic machine M on x can bring the probability of
new sorts of abstract environments have been innovated, correct behavior arbitrarily close to 1.
is there a way to define the computation in a more
abstract form? It is clear that P ⊆ BPP, since a deterministic algorithm
that runs in polynomial time, is like a probabilistic
2. Classical Complexity Classes algorithm that runs in polynomial time with an error
probability of 0, which is less than 1/3. It is still an open
2.1. The Class P question whether P ⊂ BPP or P = BPP, though currently
there exist problems which are known to lie in BPP but
The set of all languages that can be computed in not known to lie in P, such as the problem of finding
polynomial time on a deterministic Turing machine is square roots modulo a prime number. It is also an open
called the class P. Familiar examples of problems in P question whether BPP ⊆ NP or NP ⊆ BPP.
include sorting a list of elements, computing the

maximum flow between two points in a network of pipes,
and finding the shortest path between two points in a
graph. 2.4. The Class PSPACE
The class PSPACE is the set of decision problems that
can be solved by a Turing machine using a polynomial
2.2. The Class NP amount of tape, given an unlimited amount of time.
Analogously, EXPSPACE is the set of decision problems
Definition of NP is that it contains all languages that are that can be solved by a Turing machine using an
verifiable in polynomial time on a deterministic machine. exponential amount of tape, given an unlimited amount of
This means that given an input and a certificate of the time. It is clear that BPP ⊆ PSPACE, since a polynomial
input’s membership in a language, a machine can check if time machine can only using a polynomial amount of
the certificate is valid in polynomial time. For example, tape. It’s an open question whether this inclusion is strict,
in determining whether a number k is composite, one of
though it is generally believed that BPP ⊆ PSPACE. It
the factors of k could be used as the certificate. A
machine could then determine the validity of the has been proven that NP ⊆ PSPACE, and that PSPACE
certificate by dividing k by it and checking that the ⊆ EXPSPACE.
remainder is 0.
3. Quantum Abstract Machine
Since a deterministic Turing machine is just a specific
The quantum analog to a Boolean circuit that operates on
type of nondeterministic machine, P ⊆ NP. Perhaps the
n bits is a quantum circuit that operates on n Qubits. A
most famous open question in computer science is Qubit, like a classical bit, can be either 0 or 1, but unlike
whether or not the classes P and NP are equivalent. Does a classical bit, can also be in a normalized superposition
nondeterminism increase the power of a Turing machine, of these states. The state of n Qubits, then is a normalized
to the point where we can quickly solve problems that we vector in N = 2n-dimensional Hilbert space In the same
otherwise could not? Although it may appear “obvious” way a boolean circuit is built from NAND gates, a
that these two classes are not equivalent, given that a quantum circuit is built from universal gates, represented
nondeterministic machine can perform parallel by unitary N × N matrices, that can be composed to
computation, no one has been able to prove this produce any unitary N × N matrix. The result of applying
distinction. a gate is the product of its matrix and the vector
representing the state being operated on. One additional
2.3. The Class BPP operation on a quantum state is measurement, which
A language L is in the complexity class BPP (Bounded- probabilistically determines a physical property of the
Error Probabilistic Polynomial-Time), if there exists a state, and simultaneously removes elements of the initial
probabilistic Turing machine, M, that runs in polynomial superposition that are inconsistent with the result of the
time such that: measurement.*

1. if xψis in L, then Mψaccepts xψwith probability ← 3.1. Quantum Turing Machines
2/3 A mathematical theory of computation that is based on
2..if x is not in L, then M accepts x with probability < 1/3 quantum physics is bound to be different. As you move
 from classical physics to quantum physics there is a
In other words, BPP is the class of decidable problems
solvable by a probabilistic Turing machine in polynomial
*
time with an error probability of at most 1/3. Note, We have assumed that the reader has the rudimentary familiarity with
the Quantum Computation and Quantum Algorithms, [1],[2].
qualitative change in concepts that has profound
ramifications.

In the quantum Turing machine read, write, and shift


operations are all accomplished by quantum interactions.
The tape itself exists in a quantum state as does the head.
In particular in place of the Turing cell on the tape, that
could hold either 0 or 1, in quantum Turing machine there
is a Qubit, which can hold a quantum superposition of 0
and 1. The quantum Turing machine can encode many
inputs to a problem simultaneously, and then it can
perform calculations on all the inputs at the same time.
This is called quantum parallelism. The tape of the
quantum Turing machine can be drawn as shown in Fig.1
Which each arrowed circle stands for a Qubit.
Fig.1 Quantum Turing Machine
The machine evolves in many different directions
simultaneously. After some time t its state is a
superposition of all states that can be reached from the 3.3. Quantum Computability
initial condition in that time. This model, like the
Bennet showed that any classical circuit can be converted
classical Turing machine was sufficiently simple and at
into an equivalent reversible circuit, and further that this
the same time universal to prove various theorems about
conversion can be done efficiently. Thus, we see
quantum computation. In 1990 Christopher Moore from
immediately that a quantum computer is at least as
Cornell University showed that a single classical particle
powerful as a classical computer. To demonstrate that a
moving in a three-dimensional potential well made of a
quantum computer is no more powerful than a classical
finite number of parabolic mirrors is equivalent to a
computer we present a classical Turing machine that
Turing machine, and hence is capable of universal
simulates an arbitrary quantum circuit. The quantum
computation.
gates of the circuit are given, suitably encoded, as input
to the Turing machine as N × N matrices, along with the
3.2. Formal Definition of Quantum Turing measurements made on the circuit, in the order of
Machine application. In addition, the states of the Turing machine
A quantum Turing machine is defined as a triple (Q, ∑, δ ) contain all the information necessary about the physical
where Q is a finite set of states that includes a start and properties of each of the quantum basis states. The
machine also receives an encoding of the N-dimensional
final state, ∑ is the tape alphabet and includes the blank initial state in its input. The machine then applies each
letter ‘#’, and δ is a transition functionψ quantum gate to the current state by doing a matrix
δ : Q*∑ → C Q*∑ * D
where D = {L,R} is the direction in multiplication.
which the tape head moves. The set C is all complex
numbers whose kth bit can be computed in time One detail that may not be immediately obvious is the
polynomial in k. The configuration of the quantum manner in which our simulation should handle
machine is a superposition of configurations, where a measurement, since measurement appears to rely entirely
configuration is an element of ∑ z *Q * Z the first member on the physical properties of the system and true
of which corresponds to the tape contents, the second the “randomness.” It turns out, however, that a non-
deterministic Turing machine will still compute correctly
state, and the last the tape head position. The function δ Providing some computation path succeeds. Therefore we
must be unitary. A quantum machine halts when its state appeal to nondeterminism and let our Turing machine
is a superposition of only those configurations that are in decide the outcome of the measurement
the final state. The output of the machine is the nondeterministically, and then use the information it
corresponding superposition of the tape contents. For a knows about each of the quantum basis states to delete
decider, the output contains a 0 in the start cell if it inconsistent elements. Finally, it renormalizes the
rejects, 1 if it accepts. The probability that the decider resulting vector. Thus the Turing machine can simulate
accepts is the total amplitude of accepting configurations each of the operations of a quantum circuit, and therefore
in its output superposition. compute anything that can be computed on a quantum
circuit.
4. Complexity of Quantum Turing than that. For example it can generate truly random
numbers, something that classical Turing machines
machines cannot do.
Having proven that a quantum computer can compute
exactly the same set of languages as a classical computer, Despite this evidence as to the power of quantum
we now examine quantum complexity. computation, the above results do not appear to break any
major ground in terms of computational complexity. That
4.1. The Class BQP is, although they suggest that quantum computation is at
The quantum analog to BPP is the class BQP. This least somewhat more powerful than classical
consists of all languages for which a quantum machine computation, they do not lend any real insight as to
gives the right answer at least 2 3 of the time. It is known whether it will allow us to compute NP-complete
that BPP ⊆ BQP, since anything that can be computed problems. However, in the following sections we will
demonstrate that class NP can never be solved in less
on a classical machine can be computed on a quantum
than p2n time.
machine with little overhead. However, it is not known
whether or not this containment is strict. While there are
problems such as factoring and computing a discrete log 4.3. Oracle Quantum Turing machine
that are in BQP but not known to be in BPP, no one has Consider SAT, the prototypical example of an NP-
actually proven that these problems are not in BPP. It is complete problem. An instance of this problem consists
currently known that BQP sits between BPP and of a Boolean function f (x1, . . . ,xn) = c1 ^ . . . ^ cm the
PSPACE in the complexity hierarchy. Thus BQP contains SAT problem asks you to determine whether there exists
all of P and BPP, and potentially some problems in NP a satisfying assignment that is, an input (a1, . . . ,an) such
but probably none that are NP-complete, and perhaps that f (a1, . . . ,an) = 1. UNIQUE-SAT is a variant of SAT
some problems in PSPACE that are not in NP. The latter that poses the same problem with the restriction that f
two postulations, however, have not been proven. must have zero or one satisfying assignments, but no
more. As it turns out, there is a randomized reduction
from SAT to UNIQUE-SAT; thus, the two problems are
4.2. Relationship between NP and BQP equally hard. We will use the black box model when
considering this problem. In this model, we know that
Although nothing universal has been proven about the
either f ≡ 0 or there exists exactly one a such that f (a)
relationship between the relative speeds of quantum and
= 1, where a is chosen uniformly at random. That is, f is
classical computation, several such relativized† results
treated as a black box; we can make queries to f, but we
have made progress that suggests the direction that future
have no access to the Boolean formula itself.
work will eventually go. The first results discovered
Equivalently we can represent f by a table of N = 2n
appeared to suggest that quantum computation was
entries where either none or exactly one entry is 1. Ideally
significantly faster than classical computation. Among
we want a quantum algorithm that solves this problem in
these was the discovery by Deutsch, Jozsa, Berthiaume,
time O(poly(n)).
and Brassard, of oracles under which problems could be
found for which a quantum machine computed the
Can a quantum computer solve this problem by going
answer with certainty in polynomial time, whereas
into a superposition of all exponentially many possible
requiring a probabilistic classical machine to solve the
truth assignments? To answer this question precisely, let
same problem with certainty required exponential time
us define the black box query model:
for some inputs. Note, however, that relative to the same
oracle, these problems were in BPP, indicating that only
Here’s the problem: You are given a Boolean
the requirement of certainty pushed the problem across
function f : {1, . . . ,N} → {0,1}, and are promised that
theexponential time barrier.
for exactly one a ∈ {1, . . . ,N}, f (a) = 1. Think of this as
a table of size N, where exactly one element has value 1,
Bernstein and Vazirani showed that there exist oracles
and all the others are 0. Since we assume f can be
under which there exist problems that are in BQP but not
computed classically in polynomial time, we can also
BPP, which is now taken as some of the earliest evidence
compute it in superposition:
that QTMs are more powerful than probabilistic Turing
Machines. Building upon this, Simon proved the stronger
result that there exists an oracle relative to which BQP ∑x
α x x〉 0〉 → ∑
x
α x x 〉 f ( x )〉

cannot even be simulated by a probabilistic Turing Another way we can implement f is put the answer
Machine allowed to run for an exponential number of register in superposition:
steps Quantum Turing machine can be used to simulate
the classical Turing machine and the probabilistic Turing
machine too. But quantum Turing machine can do more


A case can be determined to be true but there is no efficient algorithm
for it
 0 〉 − 1〉   x 〉 f ( x )〉 − x 〉 f ( x )〉 
 
∑ α x 〉   →
 ∑ α
 
Lemma: Φ t 〉 − ωt 〉 = E0 〉 + ... + Et −1 〉
x x
 2  2
x x
 
 f ( x )〉 − f ( x ) 〉   0 〉 − 1〉 
∑ x〉 ∑ x 〉 (− 1 )  
x
= α = α  
x
 2  x
2
x
  x   Proof: Consider two runs of the algorithm A, which differ
only on the t-th step. The first run queries the function f
Now, we might as well assume f is a black box or oracle. on the first t steps and queries g for the remaining T −t
All we need to do is design an algorithm that finds a: steps; the second run queries f on the first t −1 steps and
f (a) = 1 g for the remaining T −t +1 steps. After the first t −1
steps, both runs are in state Φ t 〉 . On the t-th step, one
For the purposes of this discussion, we want to separate
the quantum algorithm itself from the function f. We run queries f and the other queries g. The outputs of these
assume that the quantum algorithm is infinitely powerful queries differ only on the amplitude of the two basis
and focus instead on the number of queries it must make vectors z〉 0〉 and z〉1〉 , so overall the output vectors
to f. All queries to f occur in superposition; that is, a differ by at most 2α z,t . Thus, at the end of the t-th step,

single query on αx x〉 0〉 yields the output α x x〉 f (x)〉 .
x
the state of the first run is Φ t 〉 , whereas the state of the
second run is Φ t 〉 + Ft 〉 , where Ft ≤ 2α z ,t . Now if U is
Theorem: In the black box model, any quantum
the unitary transform describing the remaining T −t steps
algorithm for determining whether there exist x1, . . . ,xn
(of both runs), then the final state after T steps for the two
such That f (x1, . . . ,xn) = 1 must make Ω( N ) ) queries to
runs are U( Φ t 〉 ) and U( Φ t 〉 + Ft 〉 ), respectively. The
f.
latter state can be written as U( Φ t 〉 + Et 〉 ), where
Proof: Consider any quantum algorithm A for solving
Et 〉 = U ( Ft 〉 ) . Since unitary transformations preserve
this search problem. First do a test run of A on the
function f ≡ 0. Let T be the number of queries that A length, we know that Et ≤ 2α z ,t . Thus, the effect of
makes to f, and let α x ,t be the amplitude with which A switching the queried function only on the t-th step can
queries x at time t (that is, the query at time t is be described by an “error” E t in the final state of the
∑ α x〉 ) . x ,t algorithm, where Et ≤ 2α z ,t .
t

Now, define the query magnitude of x to be ∑αx,t . The


2

x
We can transform the run Af to Ag by a succession of T
expectation value of the query magnitude of x is changes of the kind described above. Overall, the
 2 T . difference between the final states of Af and Ag is
E ∑ α x, t  = ⇒ min  ∑ α  ≤ T 2

 t  N N
x
 t
x, t
 E0 〉 + ... + Et −1 〉 , where E t ≤ 2α z ,t .

Let z be the input at which this minimum occurs; then by Finally, it is useful to consider where this factor of N
the Cauchy-Schwarz inequality: comes from. In the worst case, we query z with amplitude
2
1 at each time step .The vectors that indicate the
  T2
 ∑ α x ,t  ≤ T ∑ α x ,t
2
=
 t  t N N
differences at each step could all be orthogonal, in which
Let Φt 〉 | be the states of A f Af after the t-th step. Now
case the total distance is the sum of the squares of each
run the algorithm A on the function g such that g(z) = 1 vector’s length, which is about N. However, if all vectors
and for all y ≠ z , g(y) = 0. Suppose the final state of Ag are in the same direction, the total distance is the sum of
the length of each vector, which is approximately N .
is ωt 〉 . By the lemma proven in follow:
Φ t 〉 − ω t 〉 = E 0 〉 + ... + Et −1 〉 |where | E t ≤ 2α z ,t .Using the
triangle inequality and the inequality proved above, we 5. Quantum Problem Solving
have: Now that we have come up with the idea of Quantum
2 . black box lets have a more practical look at the concept
Φ 〉 − ω 〉 ≤ ∑ E ≤ 2∑ α ≤ T
t t t x ,t
N t
of solving problems using Quantum Computers. The
unique features of a quantum computer pose the
This implies that the two states can be distinguished with following paradox: imagine that the computer is used to
probability at most prove automatically a mathematical theorem. Classical
 T  by any measurement. Thus any quantum computer programs that do just that exist and have
O  
 N delivered a number of genuine proofs of nontrivial
algorithm that distinguishes f from g with constant theorems. But in a quantum computer the details of the
probability of success must make Ω ( N ) queries. reasoning cannot be followed. An attempt to do that
converts the quantum computer into a classical computer. References
The situation is exactly the same as in the Feynman
[1] Zdzisaw Meglicki, "Introduction to Quantum
double-slit Gedankenexperiment The moment you insert Computing",http://beige.ucs.indiana.edu/M743/M743.pdf
an apparatus that can tell you which way the particle ,2005.
goes, the quantum interference image vanishes and you're [2] Riffel, Polak, "An Introduction to Quantum Computer for
left with a classical distribution and a classical trajectory. Non-Physicists", Palo laboratory,2004.
This led some authors, e.g., Williams and Clearwater to [3] Dasgupta, Papadimitriou ,and Vazirani, "Algorithms",
ponder a situation whereupon a quantum computer would http://www.cse.ucsd.edu/users/dasgupta/mcgrawhill,2006
be able to tell you if your theorem is true or false, but it [4] Steane, M., “A quantum computer only needs one
would not be possible to extract the proof. universe,” lanl e-print quant-ph/0003084, Mar.2003.
[5] Robinson, S., “Emerging insights on limitations of
quantum computing shape quest for fast algorithms,”
This may indeed be the case, but it does not imply that a SIAM News, vol. 36, no. 1, Jan./Feb. 2003.
classical proof of that theorem does not exist or that it [6] Fortnow, L., “One complexity theorist’s view of quantum
cannot be found. One can demonstrate easily that the computing,” Theoretical Computer Science, 292(3):597-
solution of the Schrödinger wave equation that describes 610, 2003.
the double-slit Gedankenexperiment represents a [7] Dam, W. V. “Quantum complexity theory,” SQuInT
congruence of classical trajectories. Whether there is a Retreat 2003, lecture, June 2003.
classical particle that follows those trajectories or not is [8] Bennet, C., “Logical reversibility of computation,” IBM
highly debatable. But this is a matter of interpretation. J.Res.Develop., Vol. 17, 1993, pp. 525-532.
From a strictly mathematical point of view a congruence [9] Bennet, C., Bernstein, E., Brassard, G., and Vazirani, U.,
of trajectories is there in the solution of the Schrödinger “Strengths and weaknesses of quantum computation,”
Special issue on Quantum Computation of the Siam
equation. Journal of Computing, Oct. 1999.
[10] Bernstein, E. and Vazirani, U., “Quantum complexity
Translating this result onto our quantum theorem prover theory,” Special issue on Quantum Computation of the
tells us that if we were able to somehow measure the Siam Journal of Computing, Oct. 1999.
whole wave function of the computer as it goes through [11] Berthiaume, A. and Brassard, G., “Oracle quantum
the proof, and it may be possible to do that by running the computing,” Journal of Modern Optics, vol. 41,no. 12,
job repetitively and measuring distributions, then it Dec. 1994, pp. 2521-2535.
should be possible to extract a ``classical trajectory'' from [12] Boyer, M., Brassard, G., Høyer, P., and Tapp, A., “Tight
that function that represents a classical proof of our bounds on quantum searching,” arXiv e-print quant-
ph/9605034, 1996.
theorem. The wave function will, in fact, deliver a whole [13] Grover, L., “A framework for fast quantum mechanical
congruence of proofs of numerous theorems, of which algorithms,” lanl e-print quant-ph/9711043, Nov. 1998.
ours will be but one. [14] Nielsen, M. and Chuang, I, Quantum Computation and
Quantum Information. Cambridge University Press, 2004.
5. Conclusion [15] Simon, D., “On the power of quantum computation,”
Proceedings of the 35th Annual IEEE Symposium on
Perhaps unsurprisingly, quantum complexity theory now Foundations of Computer Science, 1996, pp. 116-123.
faces many of the same big questions that have faced the [16] Sipser, M., Introduction to the Theory of Computation.
classical complexity community for many years. And PWS Publishing Company, 1997.
unfortunately there doesn’t appear to be a solution on the
horizon. Despite a great deal of effort by people hoping to
prove both sides of the issues, virtually nothing concrete
is known about the true power of quantum computation.
Since we are left then to sift through relativized results
that, at best offer mere glimpses at what might be the
larger picture, we choose to take a cautious position.
We believe that the present evidence suggests that the
realistic gains to be reaped from quantum computing
are going to be polynomial, and not exponential.
Nevertheless we acknowledge that a quadratic speedup in
processing time is significant, and as nano-production
continues to develop, we expect that practical
implementations of quantum computation will become a
reality. Initially the applications may be limited to
database systems and other specific applications that
require enormous problem sizes (with which to exploit
Grover’s algorithm), but we believe that in time other
examples of modest, but substantial, polynomial gains
will be discovered.

You might also like