Quantum Computers  

In General > s.a. computation; grassmann manifolds; Lambda Calculus; logic; quantum chaos; quantum information; time; Turing Machine.
* Idea: A computer which can be in a superposition of quantum states.
* Motivation: It would allow faster computation in some cases, like factoring large numbers (used in cryptography), search and optimisation, simulation of quantum systems, and solution of large systems of linear equations.
* Precursors: 1961, Landauer, dissipation and irreversible operations; 1973, Bennett, reversible dissipationless computation.
* History: Early 1980s, Ideas pioneered by P Benioff, R Feynman, and others; 1989, Deutsch, universal three-qubit quantum logic gate; 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; 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; Stolze & Suter 08; Benenti et al 04, 07 [and III]; Stenholm & Suominen 05; Harrow ACM(12)-a1501 [motivation].
@ Quantum speedup: Castagnoli & Finkelstein PRS(01); Castagnoli a0906/Nat, a0910, Cuffaro PhD(13)-a1304 [reason]; Howard et al Nat(14)jun-a1401 [contextuality as a critical resource]; > s.a. quantum state evolution [speed].
@ Other theory: Deutsch PRS(89); Unruh PRA(95)ht/94 [coherence]; Jozsa in(97)qp; issue PRS(98)#1969; issue PTRS(98)#1743; Gudder IJTP(00); Anders et al FP(08) [as a form of phase transition]; Castagnoli IJTP(08); Pérez-Delgado & Kok PRA(11)-a0906 [criteria], PRA(11); Horsman & Munro a0908-conf [hybrid quantum-classical computation]; Chiribella et al PRA(13)-a0912 [without fixed causal structure]; Venegas-Andraca MSCS(10)-a1103 [conceptual]; Preskill a1203-conf [the entanglement frontier]; Van Meter FP(14) [outlook]; Loveridge et al PRS(15)-a1408 [topos logic as a quantum computational resource].
@ Books: Berman et al 98; Macchiavello et al ed-01; Le Bellac 06; Geroch 09; Rieffel & Polak 11 [r PT(12)feb]; Steeb & Hardy 11 [problems and solutions]; Perry 12 [readable].
@ Intros, reviews: Barenco CP(96)qp; Brassard qp/96-proc; Di Vincenzo cm/96-in; Bennett et al qp/97-in; Preskill PRS(98)qp/97 [assessment]; Steane RPP(98)qp/97; Aharonov ARCP-qp/98; Rieffel & Polak ACM-qp/98; Scarani AJP(98)nov-qp; Vedral & Plenio PQE(98)qp; Zalka qp/98; Lomonaco qp/00-ln; Knill & Nielsen qp/00-en; Ekert et al qp/00-ln, IJMPA(01); Greenland CP(01); Arrighi qp/03; Zalka qp/03-ln; Chatterjee qp/03; Eisert & Wolf qp/04-ch; Rosinger qp/04-ln; Gerjuoy AJP(05)qp/04; Bub qp/05-ch; Benenti & Strini QB(07)qp [short]; Yanofsky a0708; Duplij & Shapoval a0712-conf; Ladd et al Nat(10)-a1009; Burell a1210 [using cavity QED concepts]; Dyakonov a1212-conf [rev]; Wiebe a1401 [and foundations of physics]; Montanaro a1511 [short survey]; Biswas et al a1704 [NASA perspective]; Castagnoli a1710 [the seminal Deutsch algorithm]; Calude & Calude a1712; Landsberg a1801 [for mathematicians].
@ Intros for computer scientists: Mermin AJP(03)jan-qp/02; Nannicini a1708.

Algorithms, Applications > s.a. computation; game theory.
* Shor's algorithm: A algorithm, proposed in 1994, which can potentially factor large integers in a time proportional to L2 for an L-digit number, a fraction of the exp{L1/3} time needed for the best digital computers; 2001, It 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; Pawłowski & Czachor qp/04 [security and interpretations]; > s.a. quantum information.
@ Factoring: Shor in(94); Lomonaco qp/00; Mermin PT(07)apr; Dattani & Bryans a1411 [factorization of 44929 with 4 qubits].
@ Algorithms: Abrams & Lloyd; Jozsa PRS(98)qp/97-proc; Czachor APS(98)qp [non-linear]; Hogg et al IJMPC(99)qp/98 [tools]; Ohya & Volovich qp/99 [for NP problems]; Shor qp/00-ln [intro]; Hunziker et al qp/03 [quantum learning]; Hodges qp/05 [re classically unsolvable problems]; Rosinger qp/06 [comments]; Furrow qp/06-conf; Richter NJP(07)qp/06 [random walk]; Mosca a0808-en [survey]; Harrow et al PRL(09)-a0811, Harrow a1501-en [systems of linear equations]; Abbott NatC(12)-a0910-proc [Deustch-Jozsa problem]; Mosca & Smith a1001-ch; Childs & van Dam RMP(10) [rev]; Yung et al PRA(10)-a1005 [simulating a thermal state]; Patel pn-a1102 [database search algorithm]; > s.a. computation; random processes [random numbers]; Fowler et al PRA(12)-a1208 [surface codes, intro]; Zeng a1512-PhD [abstract structure]; > s.a. 3-manifolds; integration theory; knot invariants; ramsey theory; Triangulations.
@ Programming languages: Blaha qp/02; Mlnařík a0708; Green et al ACM(13)-a1304-proc, LNCS(13)-a1304 [Quipper].
@ Searching: Chuang et al PRL(98) + pn(98)apr [experiment]; Lomonaco qp/00-ln; Grover AJP(01)jul [algorithm]; Montanaro QIC(09)qp/07 [search of partially ordered sets]; Dohotaru & Hoyer QIC(09)-a0810 [lower bound].
@ Application to classical evolution: Meyer qp/01 [solving classical evolutions]; Georgeot & Shepelyansky qp/03 [chaotic evolution]; Margolus a1109 [quantum emulation of classical dynamics]; Bogdanov & Bogdanova a1412-conf [Lorenz and Rössler strange attractors].
@ Other physics problems: Somaroo et al PRL(99) + pn(99)jul [simulating another quantum system]; > s.a. computational physics [quantum simulation]; lattice field theories [energy spectrum for lattice fermions]; lattice gauge theories; quantum gravity; SU(2); topological field theories; Wavelets.

Special Topics > s.a. implementations [including counterfactual computation, topological quantum computing]; quantum measurements; spin models.
@ And complexity: Svozil ht/94; Fortnow qp/00-talk; Aharonov & Naveh qp/02-ln [quantum NP].
@ Limits: Pati et al qp/02; Gambini et al in(06)qp/05 [from quantum gravity].
@ Other views and theoretical aspects: Castagnoli & Monti qp/98-conf [and particle statistics]; Rudiak-Gould qp/06 [sum-over-histories view]; Roser MS-a1012 [and pilot-wave theory]; Ohzeki a1204-in [and statistical mechanics].
@ Universal quantum computer: Deutsch PRS(85); Yu Shi PLA(02)qp/99; Raussendorf PRA(05)qp/04 [quantum cellular automaton]; > s.a. computation.
@ Other topics: Jozsa qp/98-proc [quantum effects]; Lloyd & Braunstein PRL(99)qp/98 [continuous variables]; Obenland & Despain qp/98-conf [simulation]; Viola et al JPA(01) [physical qubits]; Fujii qp/01 [holonomic]; Aerts & Czachor JPA(07) [quantum-like computing]; Sanders LNCS(13)-a1307 [universal quantum simulators]; Delfosse et al PRX(15) [with rebits, using contextuality and Wigner function negativity as computational resources]; Adlam & Kent IJQI(15) [deterministic relativistic quantum bit commitment]; > s.a. quantum information [including storage].

In Generalized Theories > s.a. interference [with higher-order interference]; probability in physics [generalised probabilistic theories].
@ Many-worlds view: Hewitt-Horsman qp/02, FP(09)-a0802; Duwell PhSc(07)dec; Cuffaro SHPMP(12) [against].
@ And quantum gravity: Hardy qp/06-proc [quantum gravity computer];
Mielczarek a1803-GRF.
@ 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]; Stannett QIC-a1103-in.

"Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical." – R. Feynman.

main pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 15 may 2018