[Paleopsych] Bart D'Hooghe and Jaroslaw Pykacz: Quantum Mechanics and Computation
Premise Checker
checker at panix.com
Sun Sep 11 22:20:33 UTC 2005
Bart D'Hooghe and Jaroslaw Pykacz: Quantum Mechanics and Computation
Foundations of Science (2004) 9: 387-404
[Sorry about my inability to reproduce the equations. I can supply the PDF next
week. This is a terribly important article. It argues that quantum computing
can potentially become far more powerful than any mannter of parallel
processing done with classical computers.]
ABSTRACT. In quantum computation non classical features such as superposition
states and entanglement are used to solve problems in new ways, impossible on
classical digital computers. We illustrate by Deutsch algorithm how a quantum
computer can use superposition states to outperform any classical computer. We
comment on the view of a quantum computer as a massive parallel computer and
recall Amdahl's law for a classical parallel computer. We argue that the view
on quantum computation as a massive parallel computation disregards the
presence of entanglement in a general quantum computation and the non classical
way in which parallel results are combined to obtain the final output.
KEY WORDS: quantum computation, parallel computers
1. INTRODUCTION
The theory of quantum computation has its roots in the year 1982 when Feynman
(1982, 1986) pointed out that a simulation of a quantum system on a classical
computer requires a number of resources (in time and space) exponentially
increasing with the size of the system. Indeed, a composite quantum system is
described in the tensor product of the Hilbert spaces used to represent the
subsystems such that the number of basis vectors increases exponentially with
the number of subsystems. However, a simulation performed on a genuine quantum
system will not suffer from this exponential overhead due to its intrinsic
quantum nature. Deutsch extended the ideas of Feynman by defining the Quantum
Turing Machine (Deutsch, 1985) as a universal computation device based on the
rules of quantum mechanics. The analogue of the classical Shannon bit is the
qubit, i.e., a bi-stable state quantum system (photon, spin 1/2 particle, ...)
which is mathematically represented in a two-dimensional complex Hilbert space.
If the register of a
Postdoctoral Fellow of the Fund for Scientific Research-Flanders (Belgium).
quantum computer contains N qubits, then according to the rules of quantum
mechanics the state of the register is represented in the tensor product of N
two-dimensional Hilbert spaces, one for each qubit. The running of the quantum
computer corresponds to a unitary evolution of the state of the quantum
register, after which a final measurement is made to read the output. It is
possible to show that a quantum computer is a universal computation device,
i.e., any computation that can be performed on a classical computer can also be
performed on a quantum computer.
The paper of Feynman already suggests that a quantum computer can perform
certain computational tasks faster than any classical computer can, e.g. the
simulation of a quantum system. Deutsch and Simon discovered problems the
solving of which on a classical computer is impossible (Deutsch, 1986; Deutsch
and Jozsa, 1992; Simon, 1994), but which can be solved on a quantum computer
running a quantum algorithm. Although very important from a theoretical point
of view, one could still consider these examples as rather academic and without
any practical meaning. This changed as the quantum algorithms of Simon and
Deutsch inspired other quantum algorithms which could solve
interesting problems, such as Shor's factoring algorithm (Shor, 1994) and
Grover's database search algorithm (Grover, 1996). These new quantum algorithms
showed that building a quantum computer would not only be important from an
information-theoretical point of view, but also for practical applications.
Shor's factoring algorithm can factor integers in a time polynomial in the size
of the input such that this algorithm could break a commonly used cryptography
system, namely the RSA encryption method which relies on the computational
hardness to factor a number into its primes (Rivest, Shamir and Adleman, 1978).
Grover's search algorithm can search a database in a time proportional to the
square root of the size of the database, in contrast with a classical computer
requiring an average search time linearly depending on the size of the
database. Despite the fact that the physical implementation of a quantum
computer still encounters great technical difficulties, already some
preliminary results have been obtained by building quantum computers with a
limited number of qubits, demonstrating the validity of some of the most
important quantum algorithms, e.g., Shor's factoring algorithm was run on an
NMR quantum computer (Vandersypen et al., 2001) to factor the number 15 in its
primes 3 and 5. The question to what extent a quantum computer can solve
certain problems faster than classical computers is the topic of the theory of
quantum information and complexity, e.g., Bernstein and Vazirani (1993).
In this paper we focus on the presence of genuine quantum features, such as
quantum superposition and entanglement, in a quantum computation. In the first
section we give a brief overview of the basics of quantum computation. We
recall the notion of a qubit as the unit of information as the quantum
counterpart of the classical Shannon bit. Already for a quantum computer
containing a few qubits it is possible to study some simple quantum algorithms,
and we analyze to what extent the presence of quantum superposition states is
necessary in order to obtain a computational speed up compared to a classical
computer. As a specific example, we discuss Deutsch problem. We show that the
phase of the state vector of the quantum register is not totally irrelevant,
but contains information about the evaluated function value. In the third
section, we comment on the view on quantum computation as a massive parallel
computation. We recall Amdahl's law for classical parallel computers which
defines an upper bound in the possible speed up using a parallel computer.
Next, we study to what extent this law is applicable in the realm of quantum
computers and discuss the validity of the interpretation of a quantum
computation as a massive parallel computation.
2. HOW A QUANTUM COMPUTER WORKS
2.1. Computation is a Physical Process
In this paper we follow a physical view on computation since any actual
computation is always performed by some real physical system. The input is
encoded by a suitably chosen initial state of the register of the computer,
after which a processor induces changes of the state of the register according
to some algorithm till the final state of the register is obtained and the
algorithm stops. The reading of the output of the computational process
corresponds with measuring the final state of the register. In this framework
(computers as physical devices with a state evolution described by the
algorithm) classical and quantum computers can be studied on the same footing,
namely as physical devices with a certain set of possible accessible states and
state evolutions induced by running the algorithm. Depending on the nature of
the accessible states and possible state evolutions, the physical device which
runs the computation is then called either a quantum computer or a classical
computer.
Classical computers are characterized by a register that is a set of bi-stable
classical physical systems (switches, wires, magnets, etc.) able to store
binary units (bits) of information: '0' or '1', called the 'classical Shannon
bits'. The processor forces a transition of the initial state of the register
to the final state according to an algorithm which obeys the laws of classical
physics. Therefore, a classical N- bit register can be in only one of its
possible 2N states at a time and a classical processor forces its transition to
another such state, which is described mathematically as the action of Boolean
functions on bit strings. Quantum computers on the other hand have registers
which are sets of bi-stable quantum physical systems (two-level atoms, spin-1/2
particles, photons in orthogonal polarization states, etc.) able to store
quantum binary units (qubits) of information. The state of each qubit is
represented by a vector in a two-dimensional complex Hilbert space. It can be a
superposition of two orthogonal states |0> and |1>which form a 'computational
basis' of this Hilbert
10 space such that |0>=and |1>= and which may be
01 thought of as representing 'classical' values '0' and '1'. Using Dirac
notation, we denote the state of a qubit |q>as:
|q>=c0 |0>+c1 |1>,c0,c1 .C, |c0|2 +|c1|2 =1
A quantum N-qubit register can be not only in any of the 2N 'classical' states:
|0>=|00 ...0>,|1>=|00 ...1>,...,|2N -1>= |11 ...1>, but also in any
superposition state |.>: 2N-12N-1 |.>= ci |i>,c0,...c2N-1 .C, |ci|2 =1 i=0 i=0
The processor forces a transition of the initial state of the register to the
final state according to the laws of quantum mechanics, which is described
mathematically as the action of unitary transformations on the (superposition)
state |.>of the quantum register. Therefore, a quantum processor can in a
single run perform a unitary transformation simultaneously on each 'classical'
state |i>that is in the superposition state |.>. Hence, running a single
quantum processor on this superposition state of classical inputs could be
interpreted as the running of a huge family of parallel processors, which is
the essence of the famous 'quantum parallelism', a view on quantum computation
on which we comment in more detail in the last section of this paper. If, in
order to read the output, a measurement is
performed on the quantum register in a final state .f :2N-12N-1 |.f>= di
|i>,d0,...d2N-1 .C, |di|2 =1, i=0 i=0
the state of the register collapses into one of its 'classical” states |i>with
probability |di|2. A 'good' quantum algorithm often uses superposition in the
input state and a well-chosen unitary evolution such that the output state of
the quantum register has a very large probability to be the 'classical' state
corresponding to the correct solution of the problem.
For instance, in Grover's database search problem one has to find in a database
an entry for which a certain proposition holds. For each input, an oracle can
be called to tell whether the proposition holds or not. Starting from a
superposition of all the classical states as the initial state of the quantum
register, running Grover's algorithm transforms this initial state into a state
in which the component corresponding to the entry with the searched property
has maximal amplitude. In some cases a quantum computation can even yield the
correct outcome with certitude, e.g., for Deutsch problem and Grover's quantum
search on a database with two entries. In general, a quantum computation only
gives the correct outcome with a certain probability because the final
measurement is probabilistic. However, verifying a 'candidate solution'
obtained by a quantum computation is often computational easy, and by repeating
the quantum computation a number of times one can increase the probability of
obtaining the correct outcome arbitrarily close to unity.
It should be remarked that quantum information is of an entirely different
nature than classical information. This not only follows from the presence of
superposition states and entanglement in the quantum register, but also from
the no-cloning theorem discovered by Dieks (1982) and Wootters and Zurek
(1982), which implies that the state of the quantum register cannot be copied
without destroying the original state. Amongst others, this implies that a
quantum computation is a very delicate process. It is also one of the reasons
why it is so difficult to build a quantum computer with a large number of
qubits, since decoherence naturally arising in a quantum computation can not be
countered by copying the state of the quantum register a number of times to
compensate decoherence effects by redundancy. To solve decoherence problems
special error correcting techniques have been developed, e.g., Calderbank and
Shor (1996).
2.2. Unitary Evolutions of the Quantum Register by Quantum Gates
During quantum computation, the state of a quantum register changes by unitary
transformation. Since the set of possible unitary transformations of an N qubit
system is infinite, in principle an infinite number of possible state
evolutions could be considered for the quantum register. However, universal
sets of m-qubit gates have been found, such that any unitary transformation for
the N qubit register can be decomposed in a succession of unitary gates working
on only a limited number (m) of qubits. Actually, already a two qubit gate
together with the single qubit phase operations form a universal set of gates
(DiVincenzo, 1995), i.e., any quantum circuit can be implemented up to
arbitrary precision using these gates. This not only makes it much easier to
grasp the running of a quantum computer in terms of the two qubit and single
qubit phase operations, but also suggests that some of the characteristic
features of a quantum computer can already be demonstrated by two qubit
algorithms.
As we have already mentioned in the introduction, any classical computer can be
simulated by a quantum computer. This means that any classical gate can be
simulated in a quantum computation using a number of universal quantum gates.
On the other hand, there are quantum gates without any classical analogue,
e.g., the phase gates which act on the phase of a qubit (there is even no
classical analogue for the phase of a qubit, since the classical Shannon bit
can only have value '0' or '1' and does not have a phase), or the 'square root
of NOT'.
As an illustration we briefly present some of the well-known quantum gates, see
e.g., Nielsen and Chuang (2000) for more. Since quantum gates correspond to
unitary transformations, they are completely defined by the matrix
representation in a(n arbitrary chosen) basis of the tensor product Hilbert
space in which the state vector of the quantum register is represented, i.e.,
the computational basis.
The Hadamard transformation acts on a single qubit and transforms a 'classical'
state (|0 . or |1>) into a superposition state. Its matrix representation is
given by:
1 11 H =v 21 -1 such that H|0>= |0>v+|1. and H |1>= |0>v-|1. . Also H-1 = H,
22 so the inverse of the Hadamard gate is the Hadamard gate itself:
H |0>v+|1. =|0. and H |0>v-|1>=|1. . Another single qubit gate is the
22 phase shift gate. Using Pauli matrices:
01 0 -i 10 sx = ,sy = ,sz = 10 i 00 -1
the phase shift gates are given by:
cos .i sin .cos . sin . ei. 0i.sx = i.sy = i.sz =,e ,e -i.i sin . cos . - sin .
cos . 0 e
The quantum analogue of the classical NOT gate is the quantum NOT gate which
inverts the value of a qubit: NOT |0>=|1. , NOT |1>=|0 . with matrix
representation given by: 01 NOT = 10
The 'square root of NOT' is a quantum gate which has no classical analogue:
v 1 - ii 11 + i 1 -i NOT == 21 i 2 -i 1 vv
andis suchthat NOT NOT = NOT.
The Controlled NOT gate (CNOT) is a two qubit gate which induces a NOT on the
'target' qubit when the 'control' qubit has value 1. If for a two qubit state
|a,b. the qubit a denotes the control bit and the qubit b the target bit, the
action of CNOT is defined as CNOT |a,b>=|a,b . a>, with . addition modulo 2,
and the matrix representation of CNOT is given by: .. 1000 .. 0100 ..CNOT = .
0001 . 0010
Together with the phase operations acting on a single qubit, the CNOT gate
forms a universal set of gates (Barenco et al., 1995), such that any unitary
transformation can be expressed in terms of these universal gates. Actually,
any two qubit gate inducing entanglement between the two qubits in the quantum
register, together with the single qubit phase operations, forms a universal
set of gates (Dodd et al., 2001; Bremner et al., 2002).
3. A QUANTUM ALGORITHM USING TWO QUBITS
3.1. Deutsch Problem
Let us consider the following formulation of Deutsch problem (Deutsch, 1986;
Deutsch and Jozsa, 1992). Given a {0,1}-valued function f defined on a
two-point domain, for simplicity let it also be {0,1}, determine with a single
call of the black box (which calculates the function f and will be called
'oracle') whether the function f is constant or balanced. Clearly, this problem
cannot be solved on a classical computer, since a classical computation
requires the value of f to be calculated in both points, after which the two
values can be compared to determine whether the function f is balanced or not.
However, this problem can be solved by a quantum computer. Let a quantum
register containing two qubits be prepared in the input state .0:
.0 =|0>v + |1>.|0>v - |1>=|00>+|10>-|01>-|11 .
22 2
We assume the existence of an oracle represented by a unitary transformation Uf
such that calling the oracle transforms an input state |xy . into the state Uf
|xy>=|x( y . f (x)) . with . being the addition modulo 2. Applying this
transformation to the state .0 we obtain:
|0f(0)>+|1f(1)> - 0f(0) - 1f(1) Uf (.0) = 2 with f (i) = f (i) . 1. After Uf a
Hadamard transformation is performed on the first qubit. Let us consider the
two possibilities, namely f constant or balanced.
If f is constant, f(0) = f(1) , and the state of the two qubit quantum register
can be rewritten as ( H . 1) Uf (.0) = ( H . 1) |0f(0)>+|1f(0)> -
0f(0) - 1f(0) 2 |0>+|1>|f(0)> - f(0) = ( H . 1) v . v 22 =|0> . |f(0)>v - f(0)
2 such that if the function f is constant the first qubit is |0>.
• If f is balanced, f(1) = f(0) . 1 = f(0), f(1) = f(1) . 1 = f(0), and the
state of the quantum register can be rewritten as: ( H . 1) Uf (.0) = ( H . 1)
|0f(0)> + 1f(0) - 0f(0) -|1f(0) . 2 |0>-|1>|f(0)> - f(0) = ( H . 1) v . v 22
=|1> . |f(0)>v - f(0)
2 such that if the function f is balanced the first qubit is |1>.
Therefore, in a quantum computation with one call of the oracle the problem
whether f is constant or balanced is solved by measuring the state of the first
qubit: if the first qubit is 0 the function f is constant, if the first qubit
is 1 the function f is balanced. It looks as if the quantum computer can
calculate both values f(0) and f(1) parallelly and compare them simultaneously.
However, the quantum computater cannot answer a question about the actual value
of f(0)or f(1). If the function f is constant, we still do not know whether ( f
(0), f (1) ) =(0,0) or ( f (0), f (1) ) =(1,1) . Similarly, if f is balanced we
still have two possibilities, either ( f (0), f (1) ) =(0,1) or ( f (0), f (1)
) =(1,0) . As we show in next subsection, the knowledge about the actual values
f(0)and f(1) is encoded in the phase of the state vector of the quantum
register.
3.2. What about the Phase?
Let us note that |f(0)>-f(0) =(-1)f(0)(|0>-|1>).The state of the quantum
register can be transformed into a 'classical state' (i.e., the qubits assume
only values zero or one) by applying a Hadamard gate on the second qubit. In
the case that f is constant, the state .fc of the quantum register is given by:
.c =(1 .H)( H .1)Uf (.0) =(1 .H) |0>.|f(0)>v-f(0) f 2 =(1 .H) |0>.(-1)f(0)
|0>v-|1>=(-1)f(0) |0>.|1 . 2
Analogously, if f is balanced, the state .fb is given by:
.b =(1 .H)( H .1)Uf (.0)=(-1)f(0)|1>.|1> f
In both cases, reading the first qubit yields the answer to the problem of
Deutsch. If we could measure the phase of the final state vector of the two
qubit register, we could also answer the question about the actual value of
f(0) . Indeed: if f(0) =0, then (-1)f(0) = 1 and no phase shift occurs. If on
the other hand f(0) =1, then (-1)f(0) =-1 which corresponds with a phase shift
of p, since eip =-1. Further, knowing the value of the first qubit, i.e.,
knowing whether the function f is constant or balanced, we could immediately
obtain the value of f(1) as either f(1) = f(0),or f(1) = f(0) . 1.Hence in both
cases, f being constant or balanced, knowledge about the phase of the state
vector of the register and the value of the first qubit would determine the
value of f(0)and f(1).This shows that in the quantum computation solving
Deutsch problem knowledge about the actual value of f(0)has been absorbed into
the state vector of the quantum register. Therefore, after a single call of the
oracle, the state vector of the quantum register contains information about the
function values in both points. Nevertheless, since it is not possible to
measure the absolute phase of a state vector, no knowledge about the function
value f(0)(and consequently f(1)) can be obtained by application of this
algorithm.
3.3. Product States in Deutsch Algorithm
Let us rewrite some of the expressions in Deutsch algorithm applied to function
defined on two points only, to show that in each step of the computation the
state of the quantum register is a product state (see Arvind, 2001). Clearly,
the initial state is a product state (of superposition states for each qubit).
Since |f(1)> -
f(1) = (-1)f(1)(|0>-|1>), after calling the oracle, the state of the quantum
register is given by: |0f(0)>+|1f(1)> - 0f(0) - 1f(1) Uf (.0) = 2 . . . . . . f
(0) f (1) |0> . |f(0)> - +|1> . |f(1)> - = 2 |0> . (-1)f(0)(|0>-|1>)+|1> .
(-1)f(1)(|0>-|1> ) = 2 (-1)f(0)|0> + (-1)f(1)|1>|0>-|1 . = v . v 22
which is again a product state. Since the Hadamard gate acts on a single qubit,
it can not entangle the qubits such that after applying the two Hadamard gates
as described in the previous subsection we obtain again a product state, either
(-1)f(0)|0>.|1 . if f is constant, or (-1)f(0)|1>.|1 . if f is balanced.
Therefore, during this Deutsch algorithm the state of the quantum register can
always be written as a product state. Hence this quantum algorithm does not use
quantum entanglement, but rather exploits the possibility of the individual
qubits to be in a superposition state, such that the state of the register is a
product of superposition states. Since this Deutsch algorithm does not use
entanglement, it could be run on a classical optical system making use of
interference between optical signals, such that a 'classical qubit' is encoded
in the polarization of a (classical) light beam (Arvind, 2001). On the other
hand, two qubit quantum algorithms exist which do require the use of quantum
entanglement (Arvind and Mukunda, 2000) such that the absence of entanglement
in Deutsch two qubit algorithm is not typical for two qubit quantum
computation. Moreover, it has been shown (Arvind, 2001) that the Deutsch Jozsa
algorithm for three or more qubits involves entangled states, such that its
implementation using these 'classical qubits' becomes impossible.
Although in a general quantum algorithm entangled states are used, a classical
digital computer has no access to the superposition states used by any Deutsch
algorithm such that Deutsch problem still can be considered as a good example
of quantum computation outperforming classical bivalued computation. Another
example of computation 'outperforming' classical (single processor) computation
is parallel computation. In the next section, we discuss the maximal speed-up
possible for classical parallel computers and comment on the intuitive view of
quantum computation as a massive parallel computation.
4. INTERPRETATION OF QUANTUM COMPUTATION AS A PARALLEL COMPUTATION
4.1. Amdahl's Law for Classical Parallel Computation
The main idea behind parallel computing is to divide the computational work
among a number of processors, whose combined effort will perform a task faster
than a single processor. Amdahl (1967) realized that the speed-up which can be
obtained by making a computation parallel has an upper bound, such that adding
more parallel processors does not result in a further speed-up of the
computation. Ideally, dividing the work among k processors will decrease the
computation time by a factor k 1 . However, in general not all work can be
performed parallel, and the computation contains a serial part. Let T (k) be
the time needed to perform the calculation by k parallel processors, and T(1)
the time needed for a single processor. The speed-up S (k) is defined as the
ratio of T(1) and T (k): T(1) S (k) = T (k)
Let us split the computation into a serial part S and a parallel part P which
can be divided among the parallel processors. The speed up S (k) using k
parallel processors is given by:
T(1) Ts +Tp S (k) = = T (k) Ts +Tkp
which shows that even for k .8the speed up has an upper bound given by: Ts +Tp
Tp S(8 ) ==1 + Ts Ts
Clearly, the serial part of the computation puts an upper bound to the possible
speed-up using a parallel computer. In practice, the situation is even worse,
since this formula does not take into account the extra work needed to divide
the parallel part of the computation between the parallel processors, nor the
extra time needed to transport the data between the processors and combine them
to obtain the final output. Nevertheless, this expression already gives some
idea of the feasibility and the amount of possible speed-up using a parallel
computer. This expression is known as Amdahl's Law (Amdahl, 1967) and yields
the maximal possible speed-up using a parallel computer.
4.2. Quantum Computation as a Massive Parallel Computation?
In this section we analyze some of the main differences between a quantum
computer and a classical parallel computer. Let us first explain in what sense
a quantum computation could be interpreted as a parallel computation. Let us
consider the case that for each classical state of the register a computation
has to be performed (e.g., the value of a function) and that each computation
takes a time tc independent of the input. On a classical computer with N bits
there are 2N classical states such that this calculation would take a time
2Ntc, which increases exponentially with N, the number of bits. A quantum
computer can perform this calculation in a single run applying a unitary
transformation to the superposition of the classical states in the input. Let
tq be the time necessary to run the quantum algorithm. To obtain a parallel
computer which is as fast as a quantum computer, a speed-up of S (k) = 2Ntc/tq
is needed. In the maximal parallel situation and if tq ˜ tc, k = 2N parallel
processors are necessary, since according to Amdahl's law the speed-up is given
by:
. T(1) Ts + Tp 0 + TpSk = 2N =
. = = = 2N T 2N Ts + 2TNp 0 + 2TNp
which shows that under these assumptions the calculation on a parallel computer
with 2N processors is as fast as on a quantum computer. In this sense, a
quantum computer is as powerful as a parallel computer with as many parallel
processors as there are classical input states.
However, this view on quantum computation as a massive parallel computation is
not completely correct. First of all, in order to obtain quantum speed-up in a
general quantum computation unitary gates have to be used which entangle the
qubits (Jozsa and Linden, 2002). Therefore, a classical state of the register
(which is a product state) is in general transformed by the quantum gates into
an entangled state, i.e., a non-classical state. In a real classical parallel
computation, classical states are always mapped into other classical states,
with Boolean functions describing the action of the classical gates. In a
quantum computation, classical states are mapped onto entangled states, with
unitary transformations describing the action of the quantum gates. Hence the
view on a quantum computer as processing each classical input separately in a
massive parallel computation is invalid because now the classical states become
entangled.
Secondly, in a classical parallel computation the 'parallel results' are
classical states of the parallel registers, and the final output is obtained by
combining the results in a classical way, i.e., using classical (deterministic)
logic. In a quantum computation, the 'parallel results' are state vectors which
need to be combined in a quantum way, namely by superposition in which the
phase of the superposed state vectors is important.
Finally, a more philosophical remark. In a classical parallel computation all
parallel results are 'actual', i.e., the state of each parallel register can be
measured without disturbing the computation. In a quantum computation the final
state of the quantum register (before the measurement to read the output) is in
general a superposition of classical states. If one performs a measurement to
obtain the output of the quantum computation, one can only observe the register
in a classical state with a certain probability. In this sense, the
superposition state itself is never 'actualized' in a measurement. Due to the
no-cloning theorem, this 'potential' status is irreducible. A fortiori, the
quantum 'parallel results', i.e., the state vectors in the superposition, can
also only be considered 'potential' and 'intermediate parallel results' cannot
be measured without disturbing the quantum computation.
Taking into account these important differences between a quantum computation
and a classical parallel computation, we argue that a quantum computation
should not be viewed as a kind of massive parallel computation in the classical
sense (and obeying Amdahl's law), but really should be regarded as a new kind
of computation, on a physical device with non classical features such as
superposition states and entanglement.
5. CONCLUSIONS
A quantum computer which has access to non classical states can allow a
computational speed-up impossible on a classical computer. For example, using
product states of superposition states of the individual qubits, Deutsch
problem can be solved with a single call of the oracle on a quantum computer.
We showed that the state vector of the quantum register contains
complete information about the function values in both points, i.e., the phase
of the state vector is not irrelevant.
In general, a quantum computation also uses entangled (i.e., non product)
states. This lead us to argue against the view on a quantum computer as a
massive parallel computer because of the presence of entanglement in a general
quantum computation and the crucial difference between the ways in which
classical and quantum information is handled, e.g. the no-cloning theorem
forbids storing intermediate results without disturbing the quantum
computation. Also, the output of a classical parallel computation is obtained
by combining the parallel results using classical logic. In a quantum
computation the parallel results are state vectors which are combined in a
quantum way, namely by superposition in which the phase is important.
A classical digital parallel computer has no access to superposition states
which are used by the quantum algorithm to solve Deutsch problem with a
single call of the oracle. No matter how many parallel processors a classical
computer contains, it can not solve the problem making only a single call to
the oracle. This illustrates the fact that quantum computers are a totally new
kind of computers which are more powerful than classical parallel computers,
even if these have as many parallel processors as there are classical states in
the quantum register. In a sense, a quantum computer should be regarded not as
a massive parallel but rather as a superposing and entangling parallel
computer.
ACKNOWLEDGMENTS
Part of this paper was prepared during the joint Polish-Flemish Research
Project 007/R97/R98 and the financial support provided within this Project is
gratefully acknowledged. Bart D'Hooghe is a Postdoctoral Fellow of the Fund for
Scientific Research -Flanders (Belgium).
REFERENCES
Amdahl, G.M.: 1967, Validity of the Single-Processor Approach to Achieving
Large-Scale Computing Capabilities. AFIPS Conference Proceedings, Spring
Joint Computing Conference (Atlantic City, N.J., Apr. 18-20). Reston, VA: AFIPS
Press, 30, 483-485.
Arvind: 2001, Quantum Entanglement and Quantum Computational Algorithms.
Pramana Jr. of Physics 56: 357-365; available as e-print: quant-ph/0012116.
Arvind and N. Mukunda: 2000, A Two-qubit Algorithm Involving Quantum
Entanglement. e-print: quant-ph/0006069.
Barenco, A., D. Deutsch, A. Ekert and R. Jozsa: 1995, Conditional Quantum
Dynamics and Logic Gates. Phys.Rev.Lett. 74: 4083-4086, e-print:
quantph/9503017.
Bernstein, E. and U. Vazirani: 1993, Quantum Complexity Theory. Proc. 25th
ACM Symp. on Theory of Computating, 11-20.
Bremner, M.J., C.M. Dawson, J.L. Dodd, A. Gilchrist, A.W. Harrow, D. Mortimer,
M.A. Nielsen and T.J. Osborne: 2002, A Practical Scheme for Quantum Computation
with Any Two-qubit Entangling Gate. Phys. Rev. Lett. 89: 247902; e-print:
quant-ph/0207072. Calderbank, A.R. and P.W. Shor: 1996, Good Quantum
Error-Correcting Codes Exist. Phys. Rev. A 54(2): 1098-1106.
Deutsch, D.: 1985, Quantum Theory, the Church-Turing Principle, and the
Universal Quantum Computer. Proc. Roy. Soc. London A400: 97.
Deutsch, D.: 1986, Three Connections between Everett's Interpretation and
Experiment. In R. Penrose and C.J. Isham (eds.), Quantum Concepts in Space
and Time. Oxford: Clarendon Press, 215-225.
Deutsch, D. and R. Jozsa: 1992, Rapid Solutions of Problems by Quantum
Computation. Proc. Roy. Soc. Lond. A 439: 553-558.
Dieks, D.: 1982, Communication by EPR Devices. Phys. Lett. A 92: 271.
DiVincenzo, D.P.: 1995, Two-bit Gates are Universal for Quantum Computation.
Phys. Rev. A 51: 1015-1022.
Dodd, J.L., M.A. Nielsen, M.J. Bremner and R.T. Thew: 2001, Universal Quantum
Computation and Simulation Using Any Entangling Hamiltonian and Local
Unitaries. e-print: quant-ph/0106064.
Feynman, R.: 1982, Simulating Physics with Computers. Int. J. Theor. Phys. 21:
467-488.
Feynman, R.: 1986, Quantum Mechanical Computers. Found. Phys. 16: 507.
Grover, L.K.: 1996, A Fast Quantum Mechanical Algorithm for Database Search.
Proceedings of the 28th Annual ACM Symposium on Computing, 212.
Jozsa, R. and N. Linden: 2002, On the Role of Entanglement in Quantum
Computational Speed-up. e-print: quant-ph/0201143.
Nielsen, M.A. and I.L. Chuang: 2000, Quantum Computation and Quantum
Information. Cambridge: University Press.
Rivest, R.L., A. Shamir and L.M. Adleman: 1978, A Method for Obtaining Digital
Signatures and Public-Key Cryptosystems. Communications of the ACM 21 2:
120-126.
Shor, P.W.: 1994, Algorithms for quantum Computation, Discrete Logarithms and
Factoring. Proc. 35th Annual symposium on Foundations of Computer Science, IEEE
Computer Society Press, Los Alamitos, CA, 124.
Simon, D.: 1994, On the Power of Quantum Computation. In FOCS'94, 116-123.
Journal version available at SIAM J. Comp., 1997, 26(5): 1474-1483.
Vandersypen, L.M.K., M. Steffen, G. Breyta, C.S. Yannoni, M.H. Sherwood and
I.L. Chuang: 2001, Experimental Realization of Shor's Quantum Factoring
Algorithm Using Nuclear Magnetic Resonance. Nature 414: 883-887. Wootters, W.K.
and W.H. Zurek: 1982, A Single Quantum Cannot be Cloned. Nature 299: 982-983.
Departement Wiskunde Bart D'Hooghe Vrije Universiteit Brussel Pleinlaan 2
1050 Brussel Belgium E-mail: bdhooghe at vub.ac.be
Instytut Matematyki Jaroslaw Pykacz Uniwersytet Gda´nski Wita Stwosza 57
80-952 Gda´nsk Poland E-mail: pykacz at delta.math.univ.gda.pl
More information about the paleopsych
mailing list