|
ScienceWeek
COMPUTER SCIENCE: RANDOM OPERATORS AND QUANTUM INFORMATION
The following points are made by J. Emerson et al (Science 2003 302:2098):
1) Random numbers are a fundamental component of classical information theory, with practical applications including stochastic estimation, system identification, and cryptographic protocols. For example, in the important case of Monte Carlo simulation, sequences of random numbers permit an unbiased statistical estimation of quantities that are impractical to evaluate by exact methods.
2) It is now clear that quantum theory provides a more general framework for information theory, one that offers important advantages over classical methods of computation and communication (1). In the quantum information paradigm, the basic elements are quantum state vectors [describing the possible states of the quantum bits (qubits)] and unitary operators (describing the desired transformations); information is encoded in a quantum state, and the computational algorithm, or communication protocol, is implemented via a sequence of unitary operators acting on that quantum state.
3) Quantum analogs of random numbers (i.e., random unitary operators and random quantum states) provide an equally useful and fundamental component to this emerging theory of quantum information. In the case of quantum communication, random quantum states are known to saturate the classical communication capacity of a noisy quantum channel (2). Moreover, sets of randomizing unitary operators enable the superdense coding of arbitrary quantum states (3) and lead to a decrease in the classical communication cost (in bits) for remote state preparation (4). Random unitary operators also allow the construction of more efficient data-hiding schemes and provide a means to reduce the key length required for the (approximate) encryption of quantum states (5). In the case of quantum processing, random unitary operators enable methods for characterizing the coherent control over large quantum devices serving as prototype quantum computers.
4) Identification of the dominant noise sources for a quantum device is an essential first step toward the realization of fault-tolerant quantum computation on that device. Unfortunately, a complete characterization of the noise via process tomography cannot be carried out for a large quantum processor because the number of experiments (and the amount of data) grows exponentially with the number of qubits. Moreover, the distribution and strength of these noise operators will generally depend on the target transformation. However, when the target transformation is a random unitary operator, key measurable signatures of noise and decoherence -- such as the rate of fidelity decay and the rate of purity loss -- become independent of the target transformation and depend only on the intrinsic properties of the noise. As a result, the implementation of random unitary operators on a quantum processor enables stochastic methods for estimating unwanted noise sources on prototype quantum processors.
5) In summary: In close analogy to the fundamental role of random numbers in classical information theory, random operators are a basic component of quantum information theory. Unfortunately, the implementation of random unitary operators on a quantum processor is exponentially hard. The authors introduce a method for generating pseudo-random unitary operators that can reproduce those statistical properties of random unitary operators most relevant to quantum information tasks. This method requires exponentially fewer resources, and hence enables the practical application of random unitary operators in quantum communication and information processing protocols. Using a nuclear magnetic resonance quantum processor, the authors were able to realize pseudo-random unitary operators that reproduce the expected random distribution of matrix elements.
References (abridged):
1. M. Nielsen, I. Chuang, Quantum Computation and Quantum Information (Cambridge Univ. Press, Cambridge, 2001)
2. S. Lloyd, Phys. Rev. A 55, 1613 (1997)
3. A. Harrow, P. Hayden, D. Leung, available at http://arxiv.org/abs/quant-ph/0307221
4. C. H. Bennett, P. Hayden, D. Leung, P. W. Shor, A. Winter, available at http://arxiv.org/abs/quant-ph/0307100
5. P. Hayden, D. Leung, P. W. Shor, A. Winter, available at http://arxiv.org/abs/quant-ph/0307104
Science http://www.sciencemag.org
--------------------------------
QUANTUM DOTS AND QUANTUM COMPUTERS
The following points are made by A. Zrenner et al (Nature 2002 418:597):
1) Physicists are actively seeking to transfer the weird phenomena of the quantum world from their laboratories to the real world. In particular, the prospect of quantum-information processing has attracted considerable attention for its potential to improve the speed and reliability of data handling(1). Information would be encoded in "quantum bits", and the search is on for a physical system that could form a reliable, controllable quantum bit.
2) In contrast to classical bits, which can be in either state 0 or state 1, quantum bits exist as a combination (a linear superposition) of two quantum logic states, represented as "0" and "1". In a quantum computer, the quantum bits first have to be controlled individually in order to initialize the quantum register in which information is stored. Then a controllable interaction between the quantum bits must be established so that the quantum states become entangled. It is this "entanglement" that is the key to a quantum computer's power: in effect, a rigid coupling is introduced between the quantum bits, which can then no longer be considered individually but are affected simultaneously by a calculational operation. It is thanks to this capacity for parallel processing that a quantum computer should be able to perform calculations much faster than a classical computer.
3) The original proposals for quantum computers were based on atomic systems(1), such as atoms held in traps, where the quantum bit is formed by two energy levels between which an atomic electron can make transitions. Now that semiconductor quantum dots have been synthesized, it opens up the possibility of mimicking these approaches in a solid-state environment. Quantum dots, tiny clusters of semiconductor material, are often called "artificial atoms", because the charge carriers in these systems (electrons or holes) can only occupy a restricted set of energy levels, just like the electrons in an atom. In fact, quantum dots offer a variety of two-level systems, based on charge or spin (or both). One such two-level system is a coupled electron-hole pair -- an exciton. The absence (equivalent to the state "0") and presence (state "1") of an exciton in a semiconductor quantum dot could represent the two levels of a quantum bit.(2-5)
References:
1. Bouwmeester, D., Ekert, A. & Zeilinger, A. (eds) The Physics of Quantum Information (Springer, Berlin, 2000).
2. Zrenner, A. et al. Nature 418, 612-614 (2002).
3. Stievater, T. H. et al. Phys. Rev. Lett. 87, 133603 (2000).
4. Kamada, H. et al. Phys. Rev. Lett. 87, 246401 (2001).
5. Htoon, H. et al. Phys. Rev. Lett. 88, 087401 (2002).
Nature http://www.nature.com/nature
--------------------------------
SHOR'S ALGORITHM AND QUANTUM COMPUTATION
In 1982, the quantum physicist Richard Feynman (1918-1988) published an article titled, "Simulating Physics with Computers". In this speculative piece, Feynman suggested harnessing the weird ambivalence of quantum-mechanical superposition of states of particles like electrons to compute at a pace that would far exceed the fastest possible conventional computer.
The phenomenon upon which a quantum computer rests is the ability of a quantum system, say an atom or a single photon, to be in more than one quantum state at the same time, that is, a superposition of states. So, for instance, the spin of a photon can be in both the up and down states simultaneously. If we represent these two states by 0 and 1, respectively, then calculations on the superposition act on both values at once. Thus, a quantum computer containing (n) photons or atoms in superposed states could do a calculation on 2^(n) numbers simultaneously -- a degree of parallelism that is inconceivable for everyday, classical computers.
There are a couple of drawbacks to this rosy picture, however. The first is that the process of quantum-mechanical measurement limits (via the Heisenberg Uncertainty Principle) the amount of information that can be extracted from a quantum computer. The second is that quantum superpositions are delicate, fragile things; any contact with the environment sets off the process of decoherence, which collapses the superposition to just one of the many possible states the quantum object can occupy. This collapse, of course, eliminates entirely the advantage of using a quantum, rather than classical, computer.
A good question to ask is, Why bother trying to build such a gadget as a quantum computer? Until rather recently, there was no convincing evidence to support the idea that a quantum machine could compute anything that could not be done equally well with a classical computer. But in 1992, Peter Shor of AT&T Bell Laboratories published a quantum-mechanical algorithm for factoring large numbers into their prime components that showed the superiority of using quantum computers over their classical counterparts. Factoring large numbers is a task of not only theoretical, but practical, importance in cryptography, which resulted in Shor's work getting a lot of attention. In all known classical factoring algorithms, the amount of time needed to find the prime factors of a number grows as an exponential function of the size of the number (this factor is approximately exp(L^(1/3)), where L is the length of the number in question). Shor's quantum algorithm requires a time proportional to L^(2), a polynomial growth in L. This is a dramatic reduction over the classical methods when L becomes large. So dramatic, in fact, that it transforms factoring from a computationally "hard" to a computationally "easy" problem.
The question surrounding the feasibility of Shor's method in practice (leaving aside the not entirely simple question of actually constructing a quantum machine) is whether the exponentially fast collapse of the superposition of states when exposed to the environment would swamp the exponential increase in computing speed for the factorization scheme. Careful estimates by Shor, Woijcech Zurek, and others have shown that quantum computation can still be useful in factoring as long as a sufficiently low decoherence rate can be maintained. Basically, these results rely on Shor's discovery of quantum analogs of the error-correcting codes used in conventional computers. The standard schemes for error correction cannot be used in the quantum case because they involve actually reading the state of the computer as the computation unfolds and creating redundant states to get any erroneous calculation back on track. The difficulty in the quantum situation is that information disappears in a quantum system as soon as you look at it.
The trick to creating an error-correcting scheme for the quantum computer is to encode the state of a single quantum bit as a combination of states in a multiple-bit system. In other words, Shor spreads the information in a single bit across nine such bits. In this way, the original quantum information is preserved even if an error occurs in one of these nine bits. Seth Lloyd of MIT, one of the pioneers in the quantum-computation game, states that the existence of such error-correcting codes came as "quite a surprise. Before Shor came up with this idea, nobody thought it was possible." One problem, however, noted by Lloyd, is that error correction, being a computation all its own, runs the same risk of making mistakes as in the original computation. At the moment, nobody has any good idea of how to address this "second-order" difficulty in quantum computation.
Adapted from: Paradigms Regained: A Further Exploration of the Mysteries of Modern Science. John L. Casti. Perennial 2000, p.254. The author is a professor of mathematics at the Technical University of Vienna (AT). More information at: http://www.amazon.com/exec/obidos/ASIN/0380731711/scienceweek
ScienceWeek http://scienceweek.com
|