Quantum Turing Automata: Computational Power of The
Quantum Turing Automata: Computational Power of The
Quantum Turing Automata: Computational Power of The
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
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
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.