This project grew out of a Special Session on Logic and the Foundations of Physics at the 2010 North American Annual Meeting of the Association for Symbolic Logic. Many of the session's lecturers investigated the role of algebraic structures in the context of the foundations of quantum physics, especially in quantum information and computation. In addition to this session, attendees heard tutorial lectures on quantum computing (given by Bob Coecke, University of Oxford) and an invited lecture on intuitionistic quantum logic (by Klaas Landsman, Radboud University, Nijmegen). The talks were so well-received by conference participants that we felt a volume of collected works on this subject would be a valuable addition to the literature.

The articles in this volume by mathematicians, philosophers, and scientists address foundational issues and fundamental abstract structures arising in highly active areas of theoretical, mathematical, and even experimental physics relevant to quantum information and quantum computation. We hope that the present collection advances this worthwhile program of scientific and mathematical progress.

We would like to thank the authors that contributed to this volume, and the ASL and Cambridge University Press for publishing it. This project was partially supported by the George Washington University Centers & Institutes Facilitating Fund Grant and by the University of San Francisco Faculty Development Fund. Many thanks also to Bryan Fregoso (a University of San Francisco student) for his invaluable assistance in assembling this volume.

Introduction. Compact closed categories were first introduced by Kelly [19] in early 1970's. Some thirty years later they found applications in quantum mechanics [1], whereby the vector space foundations of quantum mechanics were recasted in a higher order language and quantum protocols such as teleportation found succinct conceptual proofs. Compact closed categories are complete with regard to a pictorial calculus [19, 35]; this calculus is used to depict and reason about information flows in entangled quantum states modeled in tensor spaces, the phenomena that were considered to be mysteries of quantum mechanics and the Achilles heel of quantum logic [4]. The pictorial calculus revealed the multi-linear algebraic level needed for proving quantum information protocols and simplified the reasoning thereof to a great extent, by hiding the underlying additive vector space structure.

Most quantum protocols rely on classical, as well as quantum, data flow. In the work of [1], this classical data flow was modeled using bi-products defined over a compact closed category. However, the pictorial calculus could not extend well to bi-products, and their categorical axiomatization was not as clear as the built-in monoidal tensor of the category.

In the last two decades, the scientific community has witnessed a surge in activity, interesting results, and notable progress in our conceptual understanding of computing and information based on the laws of quantum theory. One of the significant aspects of these developments has been an integration of several fields of inquiry that not long ago appeared to be evolving, more or less, along narrow disciplinary paths without any major overlap with each other. In the resulting body of work, investigators have revealed a deeper connection among the ideas and techniques of (apparently) disparate fields. As is evident from the title of this volume, logic, mathematics, physics, computer science and information theory are intricately involved in this fascinating story. The inquisitive reader might focus, perhaps, on the marriage of the most unlikely and intriguing fields of quantum theory and logic and ask: Why quantum logic?

By many, “logic” is deemed to be panacea for faulty intuition. It is often associated with the rules of correct thinking and decision-making, but not necessarily in its most sublime role as a deep intellectual subject underlying the validity of mathematical structures and worthy of investigation and discovery in its own right. Indeed, within the realm of the classical theories of nature, one may encounter situations that defy comprehension, should one hold to the intuition developed through experiencing familiar macroscopic scenarios in our routine impressions of natural phenomena.

One such example is a statement within the special theory of relativity that the speed of light is the same in all inertial frames. It certainly defies the common intuition regarding the observation of velocities of familiar objects in relative motion. One might be tempted to dismiss it as contrary to observation. However, while analyzing natural phenomena for objects moving close to the speed of light and, therefore, unfamiliar in the range of velocities we are normally accustomed to, logical deductions based on the postulates of the special relativity theory lead to the correct predictions of experimental observations.

There exists an undeniable interconnection between the deepest theories of nature and mathematical reasoning, famously stated by Eugene Wigner as the unreasonable efficacy of mathematics in physical theories.

The physics and the logic of quantum-ish logic. In 1932 John von Neumann formalized Quantum Mechanics in his book “Mathematische Grundlagen der Quantenmechanik”. This was effectively the official birth of the quantum mechanical formalism which until now, some 75 years later, has remained the same. Quantum theory underpins so many things in our daily lives including chemical industry, energy production and information technology, which arguably makes it the most technologically successful theory of physics ever.

However, in 1935, merely three years after the birth of his brainchild, von Neumann wrote in a letter to American mathematician Garrett Birkhoff: “I would like to make a confession which may seem immoral: I do not believe absolutely in Hilbert space no more.” (sic)—for more details see [73].

Soon thereafter they published a paper entitled “The Logic of Quantum Mechanics” [13]. Their ‘quantum logic’ was cast in order-theoretic terms, very much in the spirit of the then reigning algebraic view of logic, with the distributive law being replaced with a weaker (ortho)modular law.

This resulted in a research community of quantum logicians [68, 71, 47, 30]. However, despite von Neumann's reputation, and the large body of research that has been produced in the area, one does not find a trace of this activity neither in the mainstream physics, mathematics, nor logic literature. Hence, 75 years later one may want to conclude that this activity was a failure.

What went wrong?

The mathematics of it. Let us consider the raison d'être for the Hilbert space formalism.

Introduction. Hidden variables are extra variables added to the model of an experiment to explain correlations in the outcomes. Here is a simple example. Alice's and Bob's computers have been prepared with the same password. We know that the password is either p2s4w6r8 or 1a3s5o7d, but we do not know which it is. If Alice now types in p2s4w6r8 and this unlocks her computer, we immediately know what will happen when Bob types in one or other of the two passwords. The two outcomes—when Alice types a password and Bob types a password—are perfectly correlated. Clearly, it would be wrong to conclude that, when Alice types a password on her machine, this somehow causes Bob's machine to acquire the same password. The correlation is purely informational: It is our state of knowledge that changes, not Bob's computer. Formally, we can consider an r.v. (random variable) X for Alice's password, an r.v. Y for Bob's password, and an extra r.v. Z. The r.v. Z takes the value z1 or z2 according as the two machines were prepared with the first or the second password. Then, even though X and Y will be perfectly correlated, they will also be independent (trivially so), conditional on the value of Z. In this sense, the extra r.v. Z explains the correlation.

Introduction. There is a fascinating interplay and overlap between recursion theory and descriptive set theory. A particularly beautiful source of such interaction has been Martin's conjecture on Turing invariant functions. This longstanding open problem in recursion theory has connected to many problems in descriptive set theory, particularly in the theory of countable Borel equivalence relations.

In this paper, we shall give an overview of some work that has been done on Martin's conjecture, and applications that it has had in descriptive set theory. We will present a long unpublished result of Slaman and Steel that arithmetic equivalence is a universal countable Borel equivalence relation. This theorem has interesting corollaries for the theory of universal countable Borel equivalence relations in general. We end with some open problems, and directions for future research.

Martin's conjecture. Martin's conjecture on Turing invariant functions is one of the oldest and deepest open problems on the global structure of the Turing degrees. Inspired by Sacks’ question on the existence of a degree-invariant solution to Post's problem [Sac66], Martin made a sweeping conjecture that says in essence, the only nontrivial definable Turing invariant functions are the Turing jump and its iterates through the transfinite.

Our basic references for descriptive set theory and effective descriptive set theory are the books of Kechris [Kec95] and Sacks [Sac90]. Let ≤T be Turing reducibility on the Cantor space ω2, and let ≡T be Turing equivalence. Given x ∈ω2, let x′ be the Turing jump of x. The Turing degree of a real x∈ω2 is the ≡T equivalence class of x. A Turing invariant function is a function such that for all reals x, y ∈ ω2, if x ≡T y, then f(x) ≡T f(y). The Turing invariant functions are those which induce functions on the Turing degrees.

With the axiom of choice, we can construct many pathological Turing invariant functions. Martin's conjecture is set in the context of ZF+DC+AD, where AD is the axiom of determinacy. We assume ZF+DC+AD for the rest of this section. The results we will discuss all “localize” so that the assumption of AD essentially amounts to studying definable functions assuming definable determinacy, for instance, Borel functions using Borel determinacy.