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; news cosmos(18)jul, Phys(19)oct [towards quantum supremacy].
@ II: Deutsch PW(92)jun; Haroche & Raimond PT(96)aug; Mermin 07; Stolze & Suter 08; Stenholm & Suominen 05; Harrow ACM(12)-a1501 [motivation]; Benenti et al 18 [and III]; Hughes et al a2004 [course for high school students]; Kasirajan 21; Espitia & Park a2105 [in scientific computing and cybersecurity].
@ Quantum speedup: Hemaspaandra et al qp/99; 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]; Raussendorf QIC-a1602 [cohomological framework]; Holik et al a1811 [quantum computational logics]; Trindade et al a2003 [in terms of algebraic spinors]; Svozil a2011-in [quantum computational states as vectors, classical ones as set elements].
@ 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]; Wootton et al a2012 [interactive textbook].
@ 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]; Dyakonov a1903-conf, Martonosi & Roetteler a1903 [status]; de Wolf a1907-ln; Jazaeri a1908; Alexeev et al a1912 [needs, opportunities, and challenges]; Catt & Hutter a2005; Bishnoi a2006 [book length]; Cuffaro a2103-ch [philosopher's perspective].
@ Intros for computer scientists: Mermin AJP(03)jan-qp/02; Nannicini a1708.

Algorithms > s.a. complexity; computation.
* Shor's algorithm: An algorithm, proposed in 1994, which can potentially factor large integers in a time proportional to L² for an L-digit number, a fraction of the exp{L^1/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 [4-qubit factorization of 44929]; Anschuetz et al a1808 [variational].
@ 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 nComm(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]; Fowler et al PRA(12)-a1208 [surface codes, intro]; Zeng a1512-PhD [abstract structure]; Hangleiter a2012-PhD [quantum sampling algorithms]; > s.a. 3-manifolds; computation; integration theory; knot invariants; ramsey theory; random processes [random numbers]; Triangulations.
@ Programming languages: Blaha qp/02; Mlnařík a0708; Green et al ACM(13)-a1304-proc, LNCS(13)-a1304 [Quipper].

Special Topics > s.a. implementations [including counterfactual computation, topological quantum computing, applications]; 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.
@ Quantum simulations: Obenland & Despain qp/98-conf; Sanders LNCS(13)-a1307 [universal quantum simulators]; Cohen et al a2003 [for lqg].
@ Other topics: Jozsa qp/98-proc [quantum effects]; Lloyd & Braunstein PRL(99)qp/98 [continuous variables]; Viola et al JPA(01) [physical qubits]; Fujii qp/01 [holonomic]; Aerts & Czachor JPA(07) [quantum-like computing]; 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]; Vourdas JPA(18)-a1810 [fermionic]; > 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; Vaid a1912 [quantum error correction in quantum gravity].
@ 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 page – abbreviations – journals – comments – other sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 31 may 2021