Quantum Parallelism

The ideas about quantum parallelism and quantum complexity theory that will be reviewed in the next section are based on machines that compute according to the switching scheme. That is, the overall Hamiltonian is time dependent. 

It has been shown by several authors that quantum computers may have an advantage over classical computers in the sense of complexity theory. That is, there are problems for which a quantum computer is faster by at least a factor O S) where S is the size of the memory (measured as the number of bits) necessary to code the input for the program. Only recently it has been shown that there may even be an exponential gap between the speed of a quantum computer and a classical Turing machine [9,10], 

In this section we review the most important ideas. 

All the approaches can be summarized under the keyword quantum parallelism. This term was introduced by Deutsch in [4], Generally speaking, quantum parallelism is a method to compute in parallel on a serial computer. The main idea is to prepare the initial state of a quantum computer as a superposition of n states where each state corresponds to the initial state of a classical, reversible Turing machine. Then it is in principle possible to perform n computations in parallel as will be explained below. Of course, eventually a measurement has to be performed in order to read out a final result. This will lead to a collapse of the wave function, discarding most of the information about the superimposed states. The problem is how to read out a result and thereby gain more information than is available in a state that corresponds to the final state of one classical machine. We will now be more specific. 

Consider a Turing computable function f(i) that maps the positive integers IN onto a subspace of IN. Then we know from the previous section that there is a quantum Turing machine based on a reversible, classical machine M on which this function can be evaluated. The overall computation of / is described by the unitary operator Uf which is the product of local, unitary transformations Ui. To abbreviate the notation, we will only consider the subspace of the input and output data of the quantum machine. Furthermore, we will write i) to denote a part of the memory in which the number i is stored. For example, using the binary number system, 

---

The principal difference between quantum and classical computation is the essentially continuous nature of quantum information, which results from the superposition principle. From this characteristic follow both the amazing computational power of quantum computer (known as quantum parallelism) as well as its great sensitivity to the environment. 

If prepared in a general superposition state, quantum registers consisting of N qubits can store 2 bits of information simultaneously, as compared to classical registers where only N bits of information are stored. However, not all the information contained in quantum memories can be accessed by physical measurements. Nevertheless, so-called quantum parallelism makes quantum computers very fast they can process quantum superpositions of many numbers in one computational step, where each computational step is a unitary transformation of quantum registers. To achieve this, a universal quantum computer should be able to perform an arbitrary unitary transformation on any superposition of states. 

This characteristic allows the circuit to compute in parallel, in what is called quantum parallelism. The problem is that when a measurement is performed, only one of the superposition states is obtained with a probability given by the coefficients of the linear combination. Then, quantum algorithms must take advantage (before performing the measurement) of global characteristics of the functions computed in parallel. 

In the trapped-ion system, the qubit levels are two electronic states of the trapped charged atom. Using superpositions, states in which the qubit is in 0 and 1, one can process all possible input states at once with a given algorithm (quantum parallelism). The only catch is that once the algorithm terminates, the answer must be read out. Similar to Schrddinger s cat, which, upon looking, is... 

A quantum parallel computation can be done by preparing the computer in the... 

Somehow the final state seems to hold n solutions /(i), i = 1,..., n. However, the computation has been done on a single computer and Uf has been applied only once. This is quantum parallelism. 

This is also true for more complex measurement operators as shown in [12]. Making use of quantum parallelism requires more sophisticated quantum computation schemes. For four special problems, such schemes have been suggested in [5], [8],. [9,10], and [11] respectively. 

We will now review the proof of the main result in [5] We show that the first problem can be solved linearly faster using quantum parallelism than by any classical means. 

In order to perform a quantum parallel computation we have to prepare the initial state... 

The transformation of the results f(i) from state vectors to phases is common to all algorithms that solve problems efficiently by quantum parallelism. 

In order to realize computers that make use of quantum parallelism or to implement the ideas of Feynman and Margolus it is necessary to load superpositions of 0-bit and 1-bit states onto the polymer. This can for instance be done by applying 7t/2-pulses to the molecule A at the front end of the polymer. The ground state 10) will then change to the state ( 0) — 11)). If a 7r-pulse of frequency uj q is applied at... 

Ediund A and Peskin U 1998 A parallel Green s operator for multidimensional quantum scattering calculations Int. J. Quantum Chem. 69 167... 

A term that is nearly synonymous with complex numbers or functions is their phase. The rising preoccupation with the wave function phase in the last few decades is beyond doubt, to the extent that the importance of phases has of late become comparable to that of the moduli. (We use Dirac s terminology [7], which writes a wave function by a set of coefficients, the amplitudes, each expressible in terms of its absolute value, its modulus, and its phase. ) There is a related growth of literatm e on interference effects, associated with Aharonov-Bohm and Berry phases [8-14], In parallel, one has witnessed in recent years a trend to construct selectively and to manipulate wave functions. The necessary techifiques to achieve these are also anchored in the phases of the wave function components. This bend is manifest in such diverse areas as coherent or squeezed states [15,16], elecbon bansport in mesoscopic systems [17], sculpting of Rydberg-atom wavepackets [18,19], repeated and nondemolition quantum measurements [20], wavepacket collapse [21], and quantum computations [22,23], Experimentally, the determination of phases frequently utilizes measurement of Ramsey fringes [24] or similar" methods [25]. 

The quantum efflciency of die inadiatioii of a hydrogen-chlorine mixture has the apparent value between 10" and 10 , but the coiTesponding value for the parallel bromine reaction is only about 10. Of course die real quantum efflciency can only reach the value of unity as an upper limit, and the large apparent value for the chlorine reaction indicates that once two chlorine atoms... 

---