Quantum
Computers| Quantum
Computers |
In General > s.a. computation;
grassmann manifolds;
logic; quantum chaos; quantum
information; time.
* Idea: A computer which
can be in a superposition of quantum states.
* Motivation: Would allow
faster computation in some cases, like factoring large numbers
(cryptography).
* History: Early 1980s,
Ideas pioneered by P Benioff, R Feynman, and others; 1994,
A
concrete algorithm for factorization; 1999,
Kitaev,
definition and use of complexity class QMA, the quantum analog of the
class
NP.
* Qubit: A quantum system
that can be in (a superposition of) two states; > s.a. quantum
systems.
* And complexity: The quantum
analog of the class NP is Kitaev's complexity class QMA.
@ I: Lloyd SA(95)oct; Milburn 98; Grover ThSc(99)jul;
Aaronson SA(08)mar; Mermin 07 [r AS(08)];
Monroe & Lukin pw(08)aug
[rev]; Monroe & Wineland SA(08)aug; Bacon
pw(09)feb.
@ II: Deutsch PW(92)jun; Haroche & Raimond
PT(96)aug;
Mermin 07 [r: PT(08)mar];
Stolze & Suter 08.
@ Theory: Deutsch PRS(89);
Unruh ht/94 [coherence];
Jozsa in(97)qp;
issue PRS(98)#1969;
issue PTRS(98)#1743;
Gudder IJTP(00);
Castagnoli & Finkelstein
PRS(01)
[speed-up]; Anders et al FP(08)
[as a form of phase transition]; Castagnoli IJTP(08);
Castagnoli a0906/Nat
[reason for quantum speed]; Pérez-Delgado & Kok a0906 [criteria];
Horsman & Munro a0908-in [hybrid quantum-classical computation].
@ Intros, reviews: Barenco CP(96)qp;
Brassard qp/96-in;
Di Vincenzo cm/96-in;
Bennett et al qp/97-in;
Preskill PRS(98)qp/97 [assessment];
Steane RPP(98)qp/97;
Aharonov qp/98-in;
Rieffel & Polak qp/98-in;
Scarani AJP(98)nov-qp;
Vedral & Plenio PQE(98)qp;
Zalka qp/98;
Lomonaco
qp/00-ln;
Knill & Nielsen qp/00-in;
Ekert et al qp/00-ln,
IJMPA(01);
Greenland CP(01);
Macchiavello et al ed-01; Mermin AJP(03)jan-qp/02 [for
computer scientists]; Arrighi
qp/03;
Zalka qp/03-in;
Chatterjee qp/03;
Eisert & Wolf qp/04-in;
Rosinger
qp/04-ln;
Gerjuoy qp/04;
Bub qp/05-in;
Le Bellac 06; Steeb & Hardy 06 [problems
and solutions]; Benenti & Strini QB(07)qp [short];
Yanofsky a0708;
Duplij & Shapoval a0712-in.
Implementations > s.a. black holes.
* Issue: Efficient
fault-tolerant quantum computation requires error
probabilities for qubit manipulations below ~10–4,
but quantum
states are fragile wrt decoherence (spontaneous radiation, vibrations, can't
make a measurement before it's done!), and one needs error correction
techniques.
* 1995: A single
quantum logic gate has been made (but a useful computer would need thousands
of them).
* 1998: 3-bit memory.
* 1999: First simulation,
a truncated simple harmonic oscillator, with NMR-type (each qubit is the spin
of a H or C atom in an external B-field).
* 2002: Physical
realization of NOT operation –
or something analogous for qubits [@ De Martini et al Nat(02)oct].
* 2003: Two qubits entangled
in a solid-state device [@ Pashkin et al Nat(03)feb].
* 2007: Vancouver firm
claims to have developed commercially viable quantum computer [@ news
pw(07)feb],
but Intel
Corporation's Bourianoff estimates that we're at least 50 years away
from a true quantum computer.
* 2008: Useful quantum
computers are far beyond current
technology,
mainly because of the difficulties in maintaining coherence of
all the qubits.
* Approaches: NMR-type;
Josephson junctions (1997); Quantum dots (1998); Ion trap-type (1998, 5 ions
trapped);
Photons (trapped between mirrors); Geometric or holonomic quantum computation
(based on geometric phases); Other (e.g., states of P impurities in Si).
* Topological quantum
computation: A proposal that uses topological states
of matter whose quasiparticle excitations are neither bosons nor fermions,
but
particles
obeying non-Abelian braiding statistics known as non-Abelian anyons; Quantum
information is stored in states with multiple quasiparticles, which have a
topological
degeneracy, and the unitary gate operations necessary for quantum
computation are carried out by braiding quasiparticles and then measuring the
multiquasiparticle
states; It has emerged as a promising approach to constructing
a fault-tolerant quantum computer, because the non-local encoding of the quasiparticle
states makes them immune
to errors
caused by local perturbations; 2008, To date, the only such topological states
thought to have been found in nature are fractional quantum Hall states.
@ Overview: Gershenfeld & Chuang SA(98)jun
[with molecules]; DiVincenzo
FdP(00)qp;
Stoneham Phy(09) [future assessment].
@ Experiment: Monroe et al PRL(95);
Turchette et al PRL(95);
Bose et al PTRS(98)gq/97-in.
@ With entangled states: Wootters CM(02)qp/00 [qubit chains]; Jozsa & Linden
qp/02.
@ Errors: news pn(96)oct;
DiVincenzo & Loss cm/97-in;
Preskill PRS(98)qp/97, qp/97-in;
Cory et al PRL(98); & R
Laflamme.
@ Fault-tolerant: Kitaev AP(03)qp/97 [with anyons]; Preskill PT(99)jun;
Knill Nat(05)mar;
Gottesman qp/07 [rev].
@ Quantum networks: Elliott qp/04,
et al qp/05-in
[DARPA]; news pw(05)dec.
@ Optical: Kok a0705-ln; O'Brien Sci(07)-a0803 [rev].
@ Geometric phase:
Mitchell qp/05;
news pw(07)nov
[qubit based on Berry's phase]; Sjöqvist Phy(08).
@ Topological,
with anyons: Collins
SA(06)apr; Das Sarma et al PT(06)jul;
Brennen & Pachos PRS(08)-a0704 [intro];
Nayak et al RMP(08) [rev].
@ Related topics: Shnirman et al PRL(97)
[Josephson junctions]; Loss & DiVincenzo PRA(98)
[quantum dots]; Moore & Nilsson qp/98, qp/98 [parallel];
Hemaspaandra et
al
qp/99 [speed];
Trugenberger PRL(01)qp/00 [memory];
Karafyllidis PLA(03)
[cellular
architecture]; Häffner et al PRP(08)
[trapped ions]; Anders & Browne PRL(09)
[computational power of correlations].
Algorithms, Applications > s.a. computation [universe
as computer]; game
theory; integration;
knot invariants; random
processes [random
numbers].
* Shor's algorithm: A
quantum computer program which can potentially factor large numbers in a fraction
of the time needed for the world's currently
fastest
supercomputers; 2001, has factored the number 15.
@ Information, cryptography, security: Lo PRA(97)qp/96;
Ekert qp/97;
Zbinden et al EL-qp/97
[experiment]; Lo & Chau Sci(99)qp/98;
Pawlowski & Czachor qp/04 [security
and interpretations]; > s.a. quantum information.
@ Factoring: Shor in(94); Lomonaco qp/00;
Mermin PT(07)apr.
@ Algorithms: Abrams & Lloyd; Jozsa qp/97-in;
Czachor APS(98)qp [non-linear];
Hogg et al IJMPC(99)qp/98 [tools];
Ohya & Volovich qp/99 [for
NP problems]; Shor qp/00-in
[intro]; Hunziker et al
qp/03 [quantum
learning]; Hodges qp/05 [re
classically unsolvable problems]; Rosinger qp/06 [comments];
Furrow
qp/06-in;
Richter NJP(07)qp/06 [random
walk]; Mosca a0808-in
[survey]; Harrow et al PRL(09)-a0811 [solving
linear systems of equations]; Abbott a0910-in
[Deustch-Jozsa problem]; > s.a. computation [NP].
@ Programming languages: Blaha qp/02;
Mlnarik a0708.
@ Searching: Chuang et al PRL(98)
+ pn(98)apr
[experiment]; Lomonaco qp/00-ln;
Grover AJP(01)jul
[algorithm]; Montanaro qp/07 [search
of partially ordered sets]; Dohotaru & Hoyer a0810 [lower
bound].
@ Physics problems: Somaroo et al PRL(99)
+ pn(99)jul;
Meyer qp/01 [solving
classical evolutions]; Georgeot & Shepelyansky qp/03 [chaotic
evolution];
> s.a. quantum gravity; SU(2); topological
field theories.
Special Topics > s.a. Lambda
Calculus; measurement in quantum theory; spin
models; Turing Machine.
@ And complexity: Svozil ht/94;
Fortnow qp/00-in;
Aharonov & Naveh
qp/02 [quantum
NP].
@ Limits: Pati et al qp/02;
Gambini et al in(06)qp/05 [from
quantum gravity].
@ Many-worlds view: Hewitt-Horsman
qp/02,
FP(09)-a0802;
Duwell PhSc(07)dec.
@ With closed timelike curves: Deutsch PRD(91);
Brun FPL(03)gq/02;
Bacon PRA(04)qp/03;
Aaronson & Watrous PRS(09)-a0808 [equivalent
to classical].
@ Universal quantum computer: Deutsch PRS(85); Yu Shi PLA(02)qp/99;
Raussendorf qp/04 [quantum
cellular automaton].
@ Other topics: Castagnoli & Monti qp/98-in
[and particle statistics]; Jozsa
qp/98-in
[quantum effects]; Lloyd & Braunstein PRL(99)qp/98 [continuous
variables]; Obenland & Despain
qp/98-in
[simulation]; Viola et al JPA(01)
[physical qubits]; Fujii qp/01 [holonomic];
Rudiak-Gould qp/06 [sum-over-histories
view]; Hardy qp/06-in
[quantum gravity computer]; Hosten et al Nat(06)feb,
Vaidman PRL(07)
[counterfactual computation];
Aerts & Czachor JPA(07)
[quantum-like computing]; > s.a. quantum
information [including
storage].
main page – abbreviations – journals – comments – other
sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified
21 oct 2009