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 1980's,
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.
@ 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].
@ 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)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)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 qp/07 [short];
Yanofsky a0708;
Duplij & Shapoval a0712-in.
Implementations > s.a. black holes.
* History: 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,
truncated sho with NMR-type; 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].
* Status: 2007, Intel
Corporation's Bourianoff estimates that we're at least 50 years away
from a true quantum computer.
* Problem: Fragility
of quantum states wrt decoherence (spontaneous radiation, vibrations, can't
make a measurement before it's done!), need error correction
technique.
* Approaches: NMR-type
(each qubit is the spin of a H or C atom in an external magnetic field); Ion
trap-type (1998, 5 ions trapped); Photons
(trapped between mirrors); Other (e.g., states of P impurities in Si).
@ Overview: Gershenfeld & Chuang SA(98)jun [with molecules]; DiVincenzo
FdP(00)qp.
@ 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: Preskill PT(99)jun; 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].
@ Topological,
with anyons: Collins
SA(06)apr; Das Sarma et al PT(06)jul;
Brennen & Pachos PRS(08)-a0704 [intro].
@ Related topics: Moore & Nilsson qp/98, qp/98 [parallel];
Hemaspaandra et
al
qp/99 [speed];
Trugenberger PRL(01)qp/00 [memory];
Karafyllidis PLA(03)
[cellular
architecture];
Mitchell qp/05 [geometric
phase-based]; news pw(07)nov [qubit based on Berry's phase].
Algorithms, Applications > s.a. computation [universe
as computer]; game
theory; integration;
knot invariants.
* 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 qp/97/EL
[experiment]; Lo & Chau Sci(99)qp/98;
Pawlowski & Czachor qp/04 [security
and interpretations]; > s.a. quantum info.
@ Factoring: 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;
Richter NJP(07)qp/06 [random
walk]; > 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)
[algorithm]; Montanaro qp/07 [search
of partially ordered sets].
@ 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. causality
violations; Lambda Calculus; 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, a0802; Duwell PhSc(07).
@ 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 jun 2008