Foundations of Science (2004) 9: 387–404
© Springer 2005
BART D’HOOGHE and JAROSLAW PYKACZ
QUANTUM MECHANICS AND COMPUTATION
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).
388
BART D’HOOGHE AND JAROSLAW PYKACZ
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
QUANTUM MECHANICS AND COMPUTATION
389
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
390
BART D’HOOGHE AND JAROSLAW PYKACZ
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 whichform a ‘computational basis’ of this Hilbert 1 0 space such that |0 = and |1 = and which may be 0 1 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 |ψ: |ψ =
N −1 2
i=0
ci |i , c0 , . . . c2N −1 ∈ C,
N −1 2
|ci |2 = 1
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
QUANTUM MECHANICS AND COMPUTATION
391
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 : |ψf =
N −1 2
i=0
di |i , d0 , . . . d2N −1 ∈ C,
N −1 2
|di |2 = 1,
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.
392
BART D’HOOGHE AND JAROSLAW PYKACZ
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
393
QUANTUM MECHANICS AND COMPUTATION
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 H =√ 2
1 1 1 −1
√ √ . Also H −1 = H, such that H |0 = |0+|1 and H |1 = |0−|1 2 2 so the inverse of the Hadamard gate is the Hadamard gate itself: √ √ = |0 and H |0−|1 = |1 . Another single qubit gate is the H |0+|1 2 2 phase shift gate. Using Pauli matrices:
σx =
0 1 1 0
, σy =
0 −i i 0
, σz =
1 0 0 −1
the phase shift gates are given by:
e
iθσx
cos θ i sin θ = i sin θ cos θ
, e
iθσy
cos θ sin θ = − sin θ cos θ
, e
iθσz
eiθ 0 = 0 e−iθ
The quantum analogue of the classical NOT gate is the quantum NOT gate which inverts the value of a qubit: N OT |0 = |1 , N OT |1 = |0 with matrix representation given by: N OT =
0 1 1 0
394
BART D’HOOGHE AND JAROSLAW PYKACZ
The ‘square root of NOT’ is a quantum gate which has no classical analogue: √ 1 + i 1 −i 1−i i 1 N OT = = 1 i −i 1 2 2 √ √ and is such that N OT N OT = N OT . 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 CN OT |a, b = |a, b ⊕ a, with ⊕ addition modulo 2, and the matrix representation of CNOT is given by: 1 0 0 0 0 1 0 0 CN OT = 0 0 0 1 0 0 1 0 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
QUANTUM MECHANICS AND COMPUTATION
395
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 =
|00 + |10 − |01 − |11 |0 + |1 |0 − |1 ⊗ √ = √ 2 2 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 |0f (0) + |1f (0) − 0f (0) − 1f (0) (H ⊗ 1) Uf (ψ0 ) = (H ⊗ 1) 2 |0 + |1 |f (0) − f (0) = (H ⊗ 1) √ ⊗ √ 2 2 |f (0) − f (0) √ = |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: |0f (0) + 1f (0) − 0f (0) − |1f (0) (H ⊗ 1) Uf (ψ0 ) = (H ⊗ 1) 2 |0 − |1 |f (0) − f (0) ⊗ √ √ = (H ⊗ 1) 2 2 |f (0) − f (0) = |1 ⊗ √ 2
such that if the function f is balanced the first qubit is |1.
396
BART D’HOOGHE AND JAROSLAW PYKACZ
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:
ψfc
|f (0) − f (0) = (1 ⊗ H ) (H ⊗ 1) Uf (ψ0 ) = (1 ⊗ H ) |0 ⊗ √ 2 |0 − |1 = (1 ⊗ H ) |0 ⊗ (−1)f (0) √ = (−1)f (0) |0 ⊗ |1 2
Analogously, if f is balanced, the state ψfb is given by: ψfb = (1 ⊗ H ) (H ⊗ 1) Uf (ψ0 ) = (−1)f (0) |1 ⊗ |1 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 π, since eiπ = −1. Further, knowing the value of the first qubit, i.e., knowing whether the function f is constant or
QUANTUM MECHANICS AND COMPUTATION
397
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 |0 ⊗ |f (0) − f (0) + |1 ⊗ |f (1) − f (1) = 2 |0 ⊗ (−1)f (0) (|0 − |1) + |1 ⊗ (−1)f (1) (|0 − |1) = 2 f (0) f (1) |0 − |1 |0 + (−1) |1 (−1) ⊗ √ = √ 2 2 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.
398
BART D’HOOGHE AND JAROSLAW PYKACZ
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
QUANTUM MECHANICS AND COMPUTATION
399
decrease the computation time by a factor k1 . 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): S (k) =
T (1) 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: S (k) =
Ts + Tp T (1) = T T (k) Ts + kp
which shows that even for k → ∞ the speed up has an upper bound given by: S (∞) =
Ts + Tp Tp =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
400
BART D’HOOGHE AND JAROSLAW PYKACZ
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 2N tc , 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) = 2N tc /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: Ts + Tp 0 + Tp T (1) S k = 2N = N = = = 2N T Tp p T 2 Ts + 2N 0 + 2N 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
QUANTUM MECHANICS AND COMPUTATION
401
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.
402
BART D’HOOGHE AND JAROSLAW PYKACZ
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.
QUANTUM MECHANICS AND COMPUTATION
403
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.
404
BART D’HOOGHE AND JAROSLAW PYKACZ
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 Vrije Universiteit Brussel Pleinlaan 2 1050 Brussel Belgium E-mail:
[email protected] Instytut Matematyki Uniwersytet Gda´nski Wita Stwosza 57 80-952 Gda´nsk Poland E-mail:
[email protected]
Bart D’Hooghe
Jaroslaw Pykacz