A Brief History of Universal Quantum Computing Models

• 1973, Charles H. Bennett proved the existence of reversible universal Turing machines. IBMJ. Res. Dev. 17:525

• 1980, Paul Benioff proved that reversible computing can be achieved based on quantum mechanics (via Hamiltonian-evolution models). J. Statist. Phys. 22:563, and a few papers in 1982. He also studied quantum Turing machines years later. Fortsch.Phys. 46:423 (1998)

• 1982, Richard P. Feynman envisaged quantum computers that can be universal and more efficient than classical computers to simulate quantum physics. Int. J. Theor. Phys. 21:467, also Found. Phys. 16:507 (1986)

• 1985, David Deutsch proved the existence of universal quantum Turing machines. Proc. Roy. Soc. 400:97. He also introduced the quantum circuit model. Proc. Roy. Soc. 425:73 (1989)

• 1993, Ethan Bernstein and Umesh Vazirani constructed universal quantum Turing machines, studied BQP (bounded-error polynomial) class, showed that quantum computing is digital. First in STOC, later on SIAM J. Comput. 26, 1411 (1997)

• 1993, Andrew Chi-Chih Yao proved that quantum Turing machines and quantum circuits are equivalent models, also defined quantum communication complexity. FOCS

• 1995, A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter studied universal gate set. PRA 52:3457

• 1995, John Watrous proved that one-dimensional quantum cellular automata (QCA) is universal by simulating quantum Turing machines. FOCS. A more rigorous definition of QCA is by B. Schumacher and R. F. Werner in 2004, Reversible quantum cellular automata, arXiv:quant-ph/0405174

• 1997, Michael A. Nielsen and Isaac L. Chuang studied stored-program quantum computing and the no-programming theorem, PRL 79:321. This poses a problem that is resolved only lately.

• 1997, Alexei Yu Kitaev developed the model of topological quantum computing by anyons, Annals Phys. 303:2 (2003), see also Commun. Math. Phys. 227:587 (2002)

• 1998, Edward Farhi and Sam Gutmann studied quantum walk algorithm, PRA 58:915, the complete proof of universality of quantum walk is by Andrew M. Childs, David Gosset, and Zak Webb, Science 339:791 (2013)

• 1999, Daniel Gottesman and Isaac L. Chuang developed quantum gate teleportation and Clifford hierarchy, Nature 402:390

• 1999, Paolo Zanardi, Mario Rasetti, and others developed holonomic/geometric quantum computing, Phys.Lett. A 264:94

• 2000, Sergey Bravyi and Alexei Yu Kitaev developed fermionic quantum computing, Annals Phys. 298:210 (2002)

• 2000, Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser proposed quantum computation by adiabatic evolution, arXiv:quant-ph/0001106, the universality (by state generation) is proved later by Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, FOCS, (2004)

• 2001, Robert Raussendorf and Hans J. Briegel developed the measurement-based quantum computing, PRL 86:5188

• 2001, autonamous Hamiltonian computing by Ari Mizel, M. W. Mitchell, and Marvin L. Cohen, PRA 63:040302

• 2002, Hamiltonian QCA-like models by Simon C. Benjamin, PRL 88:017904, and also Xingxiang Zhou, Zheng-Wei Zhou, Guang-Can Guo, and Marc J. Feldman, PRL 89:197903, quantum state transfer by Sougato Bose, PRL 91:207901 (2003)

• 2002, Claude Crepeau, Daniel Gottesman, and Adam Smith studied secure muti-party quantum computation, STOC

• 2004, Simon Perdrix and Philippe Jorrand, Measurement-based quantum Turing machines and their universality, arXiv:quant-ph/0404146

• 2004, Johan Åberg, Subspace preservation, subspace locality, and gluing of completely positive maps, Ann. Phys. 313:326

• 2005, Sergey Bravyi and Alexei Yu Kitaev, Universal quantum computation with ideal clifford gates and noisy ancillas, PRA 71:022316

• 2006, Gui-Lu Long, General quantum interference principle and duality computer, Commun. Theor. Phys. 45:825, also see Int. J. Theor. Phys. 50:1305 (2011)

• 2006, Timothy P. Spiller, Kae Nemoto, Samuel L. Braunstein, William J. Munro, Peter van Loock, and Gerard J. Milburn, Quantum computation by communication, New J. Phys. 8:30

• 2007, Dominik Janzing, Spin-1/2 particles moving on a two-dimensional lattice with nearest-neighbor interactions can realize an autonomous quantum computer, PRA 75:012307

• 2008, K. G. H. Vollbrecht and J. I. Cirac, Quantum simulators, continuous-time automata, and translationally invariant systems, PRL 100:010501

• 2008, G. Chiribella, G. M. D’Ariano, and P. Perinotti, Quantum circuit architecture, PRL 101:060401, see also PRA 88:022318 (2013)

• 2008, Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, Quantum random access memory, PRL 100:160501

• 2008, Sergey Bravyi, David P. DiVincenzo, Daniel Loss, and Barbara M. Terhal, Quantum Simulation of Many-Body Hamiltonians Using Perturbation Theory with Bounded-Strength Interactions, PRL 101, 070503

• 2009, Frank Verstraete, Michael M. Wolf, and J. Ignacio Cirac, Quantum computation and quantum-state engineering driven by dissipation, Nat. Phys. 5:633

• 2009, Bryan Eastin and Emanuel Knill, Restrictions on transversal encoded quantum gate sets, PRL 102:110502

• 2009, Kaveh Khodjasteh and Lorenza Viola, Dynamically Error-Corrected Gates for Universal Quantum Computation, PRL 102:080501

• 2009, Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi, Universal blind quantum computation, FOCS

• 2010, Stephen P. Jordan, Permutational quantum computing, Quant. Infor. Comput. 10:470

• 2010, Daniel Nagaj, Fast universal quantum computation with railroad-switch local hamiltonians, J. Math. Phys. 51:062201

• 2010, Janet Anders and coauthors, Ancilla-driven universal quantum computation, PRA 82:020301

• 2012, Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland, Surface codes: Towards practical large-scale quantum computation, PRA 86:032324

• 2012, G. Paz-Silva, A. Rezakhani, J. Dominy, and D. Lidar, Zeno effect for quantum computation and control, PRL 108:080501

• 2013, Adam Paetznick and Ben W. Reichardt, Universal fault-tolerant quantum computation with only transversal gates and error correction, PRL 111:090505

• 2013, Daniel Gottesman, Fault-Tolerant Quantum Computation with Constant Overhead, arXiv:1310.2984

• 2013, M. Van den Nest, Universal quantum computation with little entanglement, PRL 110:060504

• 2014, Mateus Araújo, Adrien Feix, Fabio Costa, and Časlav Brukner, Quantum circuits cannot control unknown operations, New J. Phys. 16:093026

• 2015, Sagar Vijay, Timothy H. Hsieh, and Liang Fu, Majorana Fermion Surface Code for Universal Quantum Computation, PRX 5:041038

• 2016, Seth Lloyd and Barbara Terhal, Adiabatic and Hamiltonian computing on a 2d lattice with simple two-qubit interactions, New J. Phys. 18:023042

• 2016, J. Marshall, L. Venuti, and P. Zanardi, Modular quantum-information processing by dissipation, PRA 94:052339

• 2017, A. Mantri, T. Demarie, N. Menicucci, and J. Fitzsimons, Flow ambiguity: A path towards classically driven blind quantum computation PRX 7:031004

• 2017, J. Ikonen, J. Salmilehto, and M. Möttönen, Energy-efficient quantum computing, npj Quantum Information

• 2018, Toby Cubitt, Ashley Montanaro, Stephen Piddock, Universal quantum Hamiltonians, Proc. Natl. Acad. Sci. 115:9497

• 2018, Urmila Mahadev, Classical verification of quantum computations, arXiv:1804.01082v2

• 2019, Abel Molina and John Watrous, Revisiting the simulation of quantum Turing machines by quantum circuits, Proc. Roy. Soc. 475:20180767

• 2020, Qisheng Wang and Mingsheng Ying, Quantum random access stored-program machines, arXiv:2003.03514

• 2020, Yuxiang Yang, Renato Renner, Giulio Chiribella, Optimal universal programming of unitary gates, PRL 125:210501

• 2020, Dong-Sheng Wang, A local model of quantum Turing machines, Quant. Infor. Comput. 20:0213; A comparative study of universal quantum computing models: towards a physical unification, Quantum Engineering. 2021;e85; A prototype of quantum von Neumann architecture, Commun. Theor. Phys. 74:095103

• 2020, Adrian Parra-Rodriguez and coauthors creat a Hamiltonian-based digital-analog quantum computation, PRA 101:022305

• 2021, Sara Bartolucci and coauthors, Fusion-based quantum computation, arXiv:2101.09310

• 2021, Giulio Chiribella, Yuxiang Yang, and Renato Renner, Fundamental Energy Requirement of Reversible Quantum Operations, Phys. Rev. X 11:021014

• 2021, Zuzana Gavorová, Matan Seidel, and Yonathan Touati, Topological obstructions to implementing quantum if-clause, arXiv:2011.10031v2

• 2023, Dong-Sheng Wang, a unification/classification of universal computing models from resource theory, Commun. Theor. Phys. 75 125101

• 2023, Kyrylo Simonov and coauthors show that quantum SWICTH with indefinite causal order is universal, arXiv:2311.13654

• 2024, Philip A. LeMaitre and coauthors show that relativistic motions enables universal quantum computing, arXiv:2411.00105

ALSO SEE Complexity Zoo, Quantum Algorithm Zoo, Entropy Zoo, Error Correction Zoo

PLEASE LET ME KNOW IF IMPORTANT PROGRESS WAS NOT LISTED HERE.