From the Academy

Quantum computing
Shu-Shen Li*†, Gui-Lu Long‡§¶, Feng-Shan Bai储, Song-Lin Feng*, and Hou-Zhi Zheng*
*National Laboratory for Superlattices and Microstructures, Institute of Semiconductors, Chinese Academy of Sciences, P.O. Box 912, Beijing 100083, China;
Departments of ‡Physics and 储Mathematics, Tsinghua University, Beijing 100084, China; §Key Laboratory for Quantum Information and Measurements,
Ministry of Education, Beijing 100084, China; and ¶Center for Atomic, Molecular, and Nanosciences, Tsinghua University,
Beijing 100084, China

Quantum computing is a quickly growing research field. This article introduces the basic concepts of quantum computing, recent
developments in quantum searching, and decoherence in a possible quantum dot realization.

Q uantum computing combines computer science with quan-

tum mechanics and it is a fast-growing research field (1). In
1982, Feynman (2) pointed out that to simulate a quantum
one problem: the probability of finding the marked state may
never be exactly 1. To overcome this difficulty, one has to
generalize the standard Grover algorithm by replacing phase
system, the computer has to be working quantum mechanically, inversions by rotations of smaller angles so that the search step
or one needs a quantum computer (QC). The first proposal for can be made smaller. We uncovered that the generalized algo-
practical implementation of a QC was presented in 1993. The rithm which uses only a smaller phase rotation of the marked
elementary unit of quantum information in a QC is the quantum state alone was wrong (5). Furthermore, if both phase inversions
bit (qubit). A single qubit can be envisaged as a two-state system are modified, then the two-phase rotations must satisfy a phase-
such as a spin-half, a two-level atom. The potential power of a matching requirement (6). By using homomorphism between su
QC is based on the ability of quantum systems to be in super- (2) and so (3) groups, we give a simple picture of the phase-
position of its basic states. All of these numbers represented by matching requirement and the quantities in the generalized
the basic states can be manipulated simultaneously. Thus, a QC quantum search algorithm (7). We have experimentally imple-
has enormous quantum parallelism. mented the phase-matching requirement in a 2-qubit system by
To perform quantum computations, one should have the using the NMR quantum computation technique (8, 9).
following basic conditions: (i) a two-level system (兩0⬎ and 兩1⬎)
as a qubit, (ii) the ability to prepare the qubit in a given state, say Dephasing Rate in a Quantum Dot (QD) Qubit
兩0⬎, (iii) the capability of measuring each qubit, (iv) construction A workable QC should contain thousands of qubits. A QC of
of basic gate operations such as conditional logic gate (the such size is probably more likely to be built by solid state
control-not gate), and (v) sufficient long decoherence time. It is technologies such as semiconductor nanostructures or QDs. The
very important for a QC to be well isolated from any environ- ground and first excited states of an electron in a QD may be
mental interaction because they destroy the superposition of used as 兩0⬎ and 兩1⬎ of a qubit. An electromagnetic pulse can be
states. Furthermore, one has to use quantum error corrections, applied to manipulate the states of an electron qubit. To perform

FROM THE
ACADEMY
which have been invented in recent years. a quantum control-not manipulation, one may apply a static
Several schemes, such as trapped ions, quantum optical sys- electric field to a gate near the QD.
tems, nuclear and electron spins, and superconductor Josephson Two major obstacles have to be overcome, however, before
junctions, have been proposed for embodying quantum compu- QDs can become the triumphant technology in building a QC.
tation in recent years. First, one should be able to fabricate high-quality regularly
spaced uniform semiconductor QDs. Today, by using the Stran-
Quantum Searching and Phase Matching
ski-Krastanov growth mode, fabricating self-assembled high-
For a long time, QC research has been the luxury of just a few quality InAs兾GaAs QDs may not be very difficult by various
academic elite in the world, that is, until 1994 when Shor (3) types of modern epitaxy technologies, such as molecular-beam
invented his famous prime factorization algorithm. Shor showed epitaxy. However, the growth of regularly spaced, uniform
in a concrete example that a QC could do much better than a self-assembled QDs for a QC purpose still remains a severe
classical computer. More importantly, the difficulty in factoring challenge. The second key issue is how to prolong decoherence
a large number is the basis of the Rivest–Shamir–Adleman time in semiconductor QDs when there exist enormous degrees
(RSA) public key encryption scheme that is widely used today. of freedom that quickly dephase the systems.
Through Shor’s algorithm, the QC has suddenly become a real In a recent study, we concentrated on the latter point by
possible threat, and this algorithm has sparked worldwide inter- elucidating that a static electric field may efficiently reduce the
ests in the QC. Shor’s algorithm is applicable only to a specific dephasing rate or prolong decoherence time in a QD. In our
problem. Grover’s algorithm (4), however, devised in 1996, is model, we assumed a large energy difference between 兩0⬎ and
another that is applicable to many problems. Grover’s quantum 兩1⬎ so that we could neglect the acoustic- and optic-phonon
search algorithm solves the problem of unsorted database scatterings. We took into account only the dominant decoher-
searching. Finding a marked state from an unsorted database ence coming from the vacuum fluctuation. We assumed the InAs
requires N兾2 searches for a classical computer. Grover’s algo-
rithm finds a marked item in only 公N steps where N is the size
of the database. Grover’s algorithm has many applications such This paper is a summary of a session presented at the third annual Chinese–American
as deciphering the digital encryption scheme (DES) encryption Frontiers of Science symposium, held October 20 –22, 2000, at the Arnold and Mabel
scheme optimization. Beckman Center of the National Academies of Science and Engineering in Irvine, CA.
The standard Grover algorithm achieves quadratic speedup Abbreviations: QC, quantum computer; QD, quantum dot; qubit, quantum bit.
over classical searching algorithms. This algorithm suffers from †To whom reprint requests should be addressed. E-mail: sslee@red.semi.ac.cn.

www.pnas.org兾cgi兾doi兾10.1073兾pnas.191373698 PNAS 兩 October 9, 2001 兩 vol. 98 兩 no. 21 兩 11847–11848

Fig. 1. The decoherence time as a function of the vertical static electric field (a) and the parallel static electric field (b) with the different QD heights: 4 nm (solid
lines), 5 nm (dotted lines), and 6 nm (dashed lines). The radius of the QD is taken as 5 nm.

self-assembled QDs to be a cylinder. We studied the dephasing the electric field until the strength of the electric field is lower
rate of an InAs single-electron QD embedded in GaAs, used for than 5 kV兾cm. The decoherence time then increases very fast as
the solid-state qubit. The effective masses of InAs and GaAs the electric field goes beyond 5 kV兾cm. The decoherence time
materials were 0.023 m0 and 0.067 m0, respectively, and the band may reach the order of magnitude of milliseconds under the 20
gaps of GaAs and InAs were 1.518 eV (1 eV ⫽ 1.602 ⫻ 10⫺19 J) kV兾cm static electric field for the QD with a 5-nm radius and a
and 0.418 eV, respectively. The conduction-band offset was 4-nm height.
assumed to be 70% of the band gap difference. The material The QC is charming, and the road to building one is long and
not straight. Technologies have to be developed further before
dielectric constant ␧ is equal to 12.25 ␧0 (10).
a realistic QC is built. However, there have been no known
Fig. 1 a and b shows the decoherence times as a function of the insurmountable obstacles blocking the way. The QC of the 21st
vertical and parallel static electric field, respectively, for the same century will surely unleash its tremendous power.
radius (5 nm) and 3 different heights: 4 nm (solid lines), 5 nm
(dotted lines), and 6 nm (dashed lines). From this figure, one can The National Natural Science Foundation of China is acknowledged for
find that the decoherence time does not sensitively depend on support.

1. Bennett, C. H. & DiVincenzo, D. P. (2000) Nature (London) 404, 247–255. 7. Long, G. L., Li, Y. S., Zhang, W. L. & Tu, C. C. (2000) Phys. Rev. A 61,
2. Feynman, R. (1982) Int. J. Theor. Phys. 21, 467–488. 42351–42355.
3. Shor, P. W. (1994) Proc. 36th Annual Symp. (Santa Fe, NM), Nov. 20–22. 8. Chuang, I. L., Vandersypen, L. M. K., Zhou, X. L., Leung, D. W. & Lloyd, S.
4. Grover, L. (1997) Phys. Rev. Lett. 79, 325–328. (1998) Nature (London) 393, 143–146.
5. Long, G. L., Zhang, W. L., Li, Y. S. & Niu, L. (1999) Theor. Phys. 32, 335–338. 9. Jones, J. A., Mosca, M. & Hansen, R. H. (1998) Nature (London) 393, 344–346.
6. Long, G. L., Li, Y. S., Zhang, W. L. & Niu, L. (1999) Phys. Lett. A 262, 27–34. 10. Li, S. S. & Xia, J. B. (1998) Phys. Rev. B 58, 3561–3564.

11848 兩 www.pnas.org兾cgi兾doi兾10.1073兾pnas.191373698 Li et al.