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 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