[Paleopsych] Bart D'Hooghe and Jaroslaw Pykacz: Quantum Mechanics and Computation

[Premise Checker]

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