Martin Hebenstreit

This short article (which is in parts an excerpt from my Dissertation) is my personal attempt at briefly explaining the research field of Quantum Information Theory to a technologically interested non-expert in quantum physics.

Machines that calculate

For millennia, people have strived to build machines that assist them in information processing tasks. Let it be simple calculating tools such as the Abacus, or incredibly complex technologies such as modern computers and supercomputers. The development of transistors within the last few decades is sometimes said to have heralded a new period of human history, the Information Age. Based on semiconductor fabricated circuits, nowadays, computers perform operations at a rate in the GHz regime, operating at the limit of what is technologically possible. Needless to say, however, any information processing device must be bound to the laws of physics. On very small scales, physics are governed by the laws of quantum mechanics, leading to behaviors that are highly counter-intuitive to our daily life perception of the world. It has been noted that some of the phenomena of quantum physics, such as entanglement, may be taken advantage of for information processing tasks. For certain tasks, improvements over strategies based purely on classical physics are indeed expected. From an experimental side, this led to the desire of technologically isolating phenomena of quantum physics and from the theory side, to the emergence of Quantum Information Theory, a combination of the fields of (classical) information theory and quantum mechanics.

Where does quantum power come from?

As mentioned before, the laws of quantum mechanics differ vastly form our intuitive picture of nature. The basic information carrier within Quantum Information Theory is the qubit, which may, opposed to a classical bit, not only take the values 0 or 1, but, in fact, arbitrary superpositions thereof. More formally, the mathematical description of the state of a qubit is given by a normalized vector in a two-dimensional Hilbert space. According to the postulates of quantum mechanics, the state space of a joint quantum system, a quantum system that is composed of several individual constituents, is described by the tensor product of the state spaces describing the individual components. This leads to an exponential growth (in the number of constituents) of the size of the description of possible configurations of joint systems. This in stark contrast to when dealing with classical bits. In particular, the phenomenon of entangled states arises, in which (multipartite) quantum systems are correlated in ways that go beyond classical correlations. Moreover, measuring a quantum system always goes hand in hand with affecting the state of the system. A prominent consequence of these postulates is the no-cloning theorem, which—roughly speaking—states that it is impossible to copy quantum information perfectly. In the following, I will briefly mention two tasks, in which these laws may be exploited.

Quantum computation

Originally proposed as a method to use quantum systems in order to simulate quantum systems, the perspectives of quantum computation are nowadays much broader. Applications range from number theory over simulating condensed matter systems to applications in optimization problems. More concretely, the Shor algorithm allows solving the problem of integer factorization efficiently, a task for which—despite much effort spent—no efficient classical algorithm is known. Here, efficient refers to a simulation time measured in terms of elementary operations, that scales polynomially with the input size, i.e., the length of a binary sequence encoding the input. Considering optimization problems, recently it has for instance been shown that quantum algorithms allow to solve semi-definite programs more effectively. The computational power that a quantum computer has in addition over a classical architecture stems from the fact that the state of a quantum computer may be in a superposition of classical states, or in an entangled state. This is referred to as quantum parallelism. However, as a consequence of the way in which measurements affect the state of a system within quantum mechanics, in general it is not possible to read out the full state of a quantum computer (otherwise, quantum computers would be exceptionally more powerful, presumably). Nevertheless, within certain tasks the aforementioned superposition principle allows for an advantage even without having the possibility of reading out the full state. An advantage may be found within the aforementioned Shor algorithm for integer factorization. Prominent examples also include oracle-algorithms such as the Deutsch algorithm, the Deutsch-Jozsa algorithm, or the Grover search algorithm.

Quantum cryptography

Another major application within Quantum Information Theory is certainly cryptography. One of the most prominent cryptographic tasks is exchanging messages secretly, i.e., such that nobody except for the intended recipient may decipher the content of a message. It can be easily seen that this problem reduces to establishing a so-called secret key, a random bitstring that is only known to the two communicating partners. Common classical protocols for secure data transmission, such as RSA, are based on assumptions in computational complexity theory. In particular, these classical protocols rely on so-called trapdoor functions, which are functions that are easy to compute, but difficult to invert, unless extra information is provided. Several candidates for such functions exist. However, none of them does provably possess the desired properties (in fact, some of them are breakable with a quantum computer at hand). Quantum Information Theory is providing alternative solutions to the problem of secret key distribution. In contrast to the aforementioned classical protocols, these protocols do not rely on assumptions in computational complexity theory; the security is enforced by the laws of physics, instead.

Entanglement theory

Entanglement plays an important role in both of the aforementioned (and many more) tasks. Therefore, gaining an understanding of entanglement is highly desirable within Quantum Information Theory. It turns out that there is not merely a single kind of entanglement. In fact, there is a vast variety of different kinds of entanglement. The characterization of entanglement, qualitatively as well as quantitatively, is (especially considering multipartite systems) a highly nontrivial task and constitutes a research field on its own.

References and further reading

• M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information (Cambridge University Press, 2013).
• R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Quantum entanglement, Rev. Mod. Phys. 81, 865–942 (2009).
• A. Kitaev, A. Shen, M. Vyalyi, and M. Vyalyi, Classical and quantum computation, Graduate studies in mathematics (American Mathematical Society, 2002).
• E. Chitambar and G. Gour, Quantum resource theories, Rev. Mod. Phys. 91, 025001 (2019).
• W. Wootters and W. Zurek, A single quantum cannot be cloned, Nature 299, 802 (1982).
• C. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, Proceedings of IEEE International Conference on Computers, Systems and Signal Processing 175, 8 (1984).
• A. K. Ekert, Quantum cryptography based on Bell’s theorem, Phys. Rev. Lett. 67, 661–663 (1991).
• P. W. Shor and J. Preskill, Simple proof of security of the BB84 quantum key distribution protocol, Phys. Rev. Lett. 85, 441–444 (2000).
• E. Chitambar, D. Leung, L. Mancinska, M. Ozols, and A. Winter, Everything you always wanted to know about LOCC (but were afraid to ask), Communications in Mathematical Physics 328, 303–326 (2014).
• R. P. Feynman, Simulating physics with computers, International Journal of Theoretical Physics 21, 467–488 (1982).
• P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26, 1484 (1997).
• C. Pomerance, A tale of two sieves, Notices Amer. math. soc 43, 1473 (1996).
• F. G. S. L. Brandao and K. Svore, Quantum speed-ups for semidefinite programming, arXiv:1609.05537 [quant-ph] (2016).
• D. Deutsch and R. Penrose, Quantum theory, the Church-Turing principle and the universal quantum computer, Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400, 97 (1985).
• D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439, 553 (1992).
• R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 339 (1998).
• L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC ’96 (ACM, New York, NY, USA, 1996) pp. 212.
• E. Bernstein and U. Vazirani, Quantum complexity theory, SIAM Journal on Computing 26, 1411 (1997).