The study of undecidability in problems arising from physics has experienced a renewed interest, mainly in connection with quantum information problems. The goal of this review is to survey this recent development. After a historical introduction, we first explain the necessary results about undecidability in mathematics and computer science. Then we briefly review the first results about undecidability in physics which emerged mostly in the 80s and early 90s. Finally, we focus on the most recent contributions, which we divide in two main categories: many body systems and quantum information problems.
The study of undecidability in problems arising from physics has experienced a renewed interest, mainly in connection with quantum information problems. The goal of this review is to survey this recent development. After a historical introduction, we first explain the necessary results about undecidability in mathematics and computer science. Then we briefly review the first results about undecidability in physics which emerged mostly in the 80s and early 90s. Finally, we focus on the most recent contributions, which we divide in two main categories: many body systems and quantum information problems.
Over the past several decades, quantum information science has emerged to seek answers to the question: can we gain some advantage by storing, transmitting and processing information encoded in systems that exhibit unique quantum properties? Today it is understood that the answer is yes, and many research groups around the world are working towards the highly ambitious technological goal of building a quantum computer, which would dramatically improve computational power for particular tasks. A number of physical systems, spanning much of modern physics, are being developed for quantum computation. However, it remains unclear which technology, if any, will ultimately prove successful. Here we describe the latest developments for each of the leading approaches and explain the major challenges for the future. This review outlines the principles of operation of quantum computers and their elements. The theory of ideal computers that do not interact with the environment and are immune to quantum decohering processes is presented. Decohering processes in quantum computers are investigated. The review considers methods for correcting quantum computing errors arising from the decoherence of the state of the quantum computer, as well as possible methods for the suppression of the decohering processes. A brief enumeration of proposed quantum computer realizations concludes the review.
Quantum measurement problem is a long-standing problem at the heart of the foundations of modern physics and nascent technology, such as quantum technology. The last forty years brought a renowned interest in this problem with an emphasis on the new foundations of quantum theory and unpredicted formulation of some new quantum disciplines, such as the open quantum systems theory and the quantum information and computation science. A state of the art of the problem of measurement is shortly presented, including a brief historical view, with a review of the authors' original contributions.
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
This article aims to provide an introductory survey on quantum random walks.Starting from a physical effect to illustrate the main ideas we will introduce quantum random walks, review some of their properties and outline their striking differences to classical walks.We will touch upon both physical effects and computer science applications, introducing some of the main concepts and language of present day quantum information science in this context.We will mention recent developments in this new area and outline some open questions. God does not play dice.
This article aims to provide an introductory survey on quantum random walks. Starting from a physical effect to illustrate the main ideas we will introduce quantum random walks, review some of their properties and outline their striking differences to classical walks. We will touch upon both physical effects and computer science applications, introducing some of the main concepts and language of present day quantum information science in this context. We will mention recent developments in this new area and outline some open questions. 1. Overview Ever since the discovery of quantum mechanics people have been puzzled by the counter-intuitive character of the laws of nature. Over time we have learned to accept more and more effects that are unimaginable in a classical Newtonian world. Modern technology exploits quantum effects both to our benefit and detriment—among the memorable examples we should cite laser technology and not omit the atomic bomb. In recent years interest in quantum information theory has been generated by the prospect of employing its laws to design devices of surprising power [1]. New ideas include quantum cryptography [2, 3] and quantum computation. In 1994 Shor [4] discovered a quantum algorithm to factor numbers efficiently (that is in time that grows only polynomically with the length of the number to be factored). This has unleashed a wave of activity across a broad range of disciplines: physics, computer science, mathematics and engineering. This fruitful axis of research has uncovered many new effects that are strikingly different from their classical counterparts, both from the physical point of view as well as from a computer science and communication theory perspective. Over time these communities have gained a greater understanding of the concepts and notions of the other. The idea that information cannot be separated from
Geometric and topological methods play an increasingly important role in quantum information science and quantum computation. Beyond the conventional Hilbert space formalism, a variety of mathematical frameworks, including group representations, mapping class groups, modular tensor categories, and character varieties, have been proposed to describe quantum states and quantum gates in a structurally robust manner. This review surveys the development of topological and geometric approaches to quantum information, with particular emphasis on representations of fundamental groups into SL(2,C), their associated character varieties, and the algebraic surfaces arising from trace coordinates, such as Fricke and Cayley cubic surfaces. These structures provide a geometric encoding of quantum degrees of freedom and offer alternative perspectives on topological quantum computing beyond anyon-based models. We also examine connections with integrable systems and isomonodromic deformations, where Painlevé equations and monodromy data supply a dynamical viewpoint on quantum state evolution. A critical comparison is provided with other geometric and topological approaches to quantum information, including geometric quantum mechanics, information geometry, tensor network geometry, and category-theoretic formulations. By synthesising results from topology, algebraic geometry, and mathematical physics, this review aims to clarify the conceptual landscape of topological quantum information geometry and to identify open problems and emerging directions in the field.