**An Overview**

The idea of quantum computers, i.e., a computer that encodes and manipulates information in quantum states, and exploits the quantum mechanical effects, such as superposition and entanglement, was originally proposed by Benioff [1] and Feynman [2]. In his paper in 1982 [2], Feynman envisaged a universal quantum computer and conjectured that such a machine will be capable of simulating generic quantum systems, a task which is intractable on classical computers. An efficient simulation of quantum systems would have a wide range of applications in the study of many-body systems, from quantum chemistry to high energy physics and condensed matter. For instance, a universal quantum simulator can be used to test the properties of a molecule before synthesizing it in the lab, which can have revolutionary impacts, e.g., on drug design. Feynman’s conjecture was proved to be correct in 1996 by Seth Lloyd [3].

The idea of quantum computers attracted an enormous amount of attention when in 1994 Peter Shor discovered an efficient algorithm for factoring large numbers using a quantum computer, a task for which there is no known efficient classical algorithm [4]. Then, researchers realized that quantum computers can be useful for solving problems which apparently have nothing to do with quantum systems. For instance, in 1996 Lov Grover came up with an efficient quantum algorithm for search in an unsorted database [5].

Another reason that motivates researchers in academia and industry to work on quantum computers is the observation that approximately in every two years the number of transistors in a dense integrated circuit is increased by a factor of two, also known as Moore’s law. This means that soon, in a decade or two, transistors will be at a size where the quantum mechanical effects are not negligible, and this can be a big obstacle for the progress of the classical computers. Hence, many companies such as Google, IBM, Intel and Microsoft have decided to make huge investments on both theoretical and experimental research on quantum computers.

Shor’s landmark discovery also clarified that quantum computers can be a threat for the security of current cryptographic systems: the computational hardness of problems such as factoring is at the heart of the modern public key cryptographic systems that are currently in use, for instance, for protecting email and banking communications. Therefore, a quantum computer can easily break these codes. Fortunately, quantum mechanics itself provides a solution to this challenge. In 1984, inspired by the previous work of Wiesner on quantum money, Gill Brassard and Charles Bennett introduced a quantum key distribution protocol [6]. Unlike current classical cryptographic systems, quantum key distribution does not rely on any computational assumption and its security is a direct consequence of the Heisenberg uncertainty principle. Hence, it promises an absolute, information theoretic security.

Another active area of research in quantum information science is quantum metrology [7], which is a set of techniques and methods for making high-resolution measurements of physical parameters. Quantum metrology techniques are already in use in some of the most precise clocks in the world, such as the quantum logic clock at the National Institute of Standards and Technology (NIST) [8]. Also, they are used at the heart of the Laser Interferometer Gravitational-Wave Observatory (LIGO) experiment [9], which recently announced the first observation of gravitational waves.

In addition to these technological applications, the insights and techniques developed in quantum information theory have found many applications in other fields of physics. For instance, applying these techniques to the field of many-body systems, researchers in quantum information theory have made significant contributions in topics such as area law [10, 11], tensor networks [12, 13], topological order [14 16], classification of phases [17, 18], many-body localization [19] and efficient (classical) algorithms for finding the ground states of local Hamiltonians [20].

Another intriguing example is the recent proposal on applications of quantum error correction in the context of string theory and black holes. The theory of quantum error correction studies techniques for protecting quantum information against noise and decoherence [21]. The very fact that, despite the no cloning theorem [22] and the continuous nature of quantum information, error correction is still possible is an astonishing discovery, which guarantees quantum computation can be done reliably at the presence of noise and decoherence. In an interesting twist, recently it has been argued that the theory of quantum error correction and the properties of quantum error correcting codes may also explain the emergence of bulk locality in AdS/CFT correspondence [23, 24]. Currently, many top researchers in both string and quantum information communities are studying this proposal.

**References:**

[1] P. Benioff, Phys. Rev. Lett. 48 , 1581 (1982).

[2] R. P. Feynman, International journal of theoretical physics 21 , 467 (1982).

[3] S. Lloyd, Science 273 , 1073 (1996).

[4] P. W. Shor, in Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on (IEEE, 1994), pp. 124–134.

[5] L. K. Grover, Physical Review Letters 79 , 325 (1997).

[6] C. H. Bennett, in International Conference on Computer System and Signal Processing, IEEE, 1984 (1984), pp. 175–179.

[7] V. Giovannetti, S. Lloyd, and L. Maccone, Nature Photonics 5 , 222 (2011).

[8] C. Chou, D. Hume, J. Koelemeij, D. Wineland, and T. Rosenband, Physical Review Letters 104 , 070802 (2010).

[9] U. L. Andersen, Nature Photonics 7 , 589 (2013).

[10] M. M. Wolf, F. Verstraete, M. B. Hastings, and J. I. Cirac, Physical review letters 100 , 070502 (2008).

[11] J. Eisert, M. Cramer, and M. B. Plenio, Reviews of Modern Physics 82 , 277 (2010).

[12] G. Vidal, Physical review letters 99 , 220405 (2007).

[13] G. Vidal, Physical review letters 101 , 110501 (2008).

[14] A. Kitaev and J. Preskill, Physical review letters 96 , 110404 (2006).

[15] A. Y. Kitaev, Annals of Physics 303 , 2 (2003).

[16] C. Nayak, S. H. Simon, A. Stern, M. Freedman, and S. D. Sarma, Reviews of Modern Physics 80 , 1083 (2008).

[17] N. Schuch, D. Pérez-García, and I. Cirac, Physical review B 84 , 165139 (2011).

[18] X. Chen, Z.-C. Gu, and X.-G. Wen, Physical review B 83 , 035107 (2011).

[19] J. Goold, C. Gogolin, S. Clark, J. Eisert, A. Scardicchio, and A. Silva, Physical Review B 92 , 180202 (2015).

[20] Z. Landau, U. Vazirani, and T. Vidick, in Proceedings of the 5th conference on Innovations in theoretical computer science (ACM, 2014), pp. 301–302.

[21] D. Lidar and T. Brun, eds., Quantum Error Correction (Cambridge University Press, Cambride, UK, 2013).

[22] W. K. Wootters and W. H. Zurek, Nature 299 , 802 (1982).

[23] A. Almheiri, X. Dong, and D. Harlow, arXiv preprint arXiv:1411.7041 (2014).

[24] F. Pastawski, B. Yoshida, D. Harlow, and J. Preskill, arXiv preprint arXiv:1503.06237 (2015).