BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Bob Coecke

Bob Coecke appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phmath.CTComputation and LanguageLogic in Computer ScienceArtificial Intelligencemath.QAmath-phmath.MPgr-qcInformation Theorymath.ITmath.LOmath.DSProgramming LanguagesComputational ComplexityFormal Languages and Automata TheoryInformation Retrievalmath.OAmath.PRSystems and Control

Catalog footprint

What is connected

59works
20topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

59 published item(s)

preprint2022arXiv

Language-independence of DisCoCirc's Text Circuits: English and Urdu

DisCoCirc is a newly proposed framework for representing the grammar and semantics of texts using compositional, generative circuits. While it constitutes a development of the Categorical Distributional Compositional (DisCoCat) framework, it exposes radically new features. In particular, [14] suggested that DisCoCirc goes some way toward eliminating grammatical differences between languages. In this paper we provide a sketch that this is indeed the case for restricted fragments of English and Urdu. We first develop DisCoCirc for a fragment of Urdu, as it was done for English in [14]. There is a simple translation from English grammar to Urdu grammar, and vice versa. We then show that differences in grammatical structure between English and Urdu - primarily relating to the ordering of words and phrases - vanish when passing to DisCoCirc circuits.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

DisCoPy: Monoidal Categories in Python

We introduce DisCoPy, an open source toolbox for computing with monoidal categories. The library provides an intuitive syntax for defining string diagrams and monoidal functors. Its modularity allows the efficient implementation of computational experiments in the various applications of category theory where diagrams have become a lingua franca. As an example, we used DisCoPy to perform natural language processing on quantum hardware for the first time.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Kindergarden quantum mechanics graduates (...or how I learned to stop gluing LEGO together and love the ZX-calculus)

This paper is a `spiritual child' of the 2005 lecture notes Kindergarten Quantum Mechanics, which showed how a simple, pictorial extension of Dirac notation allowed several quantum features to be easily expressed and derived, using language even a kindergartner can understand. Central to that approach was the use of pictures and pictorial transformation rules to understand and derive features of quantum theory and computation. However, this approach left many wondering `where's the beef?' In other words, was this new approach capable of producing new results, or was it simply an aesthetically pleasing way to restate stuff we already know? The aim of this sequel paper is to say `here's the beef!', and highlight some of the major results of the approach advocated in Kindergarten Quantum Mechanics, and how they are being applied to tackle practical problems on real quantum computers. We will focus mainly on what has become the Swiss army knife of the pictorial formalism: the ZX-calculus. First we look at some of the ideas behind the ZX-calculus, comparing and contrasting it with the usual quantum circuit formalism. We then survey results from the past 2 years falling into three categories: (1) completeness of the rules of the ZX-calculus, (2) state-of-the-art quantum circuit optimisation results in commercial and open-source quantum compilers relying on ZX, and (3) the use of ZX in translating real-world stuff like natural language into quantum circuits that can be run on today's (very limited) quantum hardware. We also take the title literally, and outline an ongoing experiment aiming to show that ZX-calculus enables children to do cutting-edge quantum computing stuff. If anything, this would truly confirm that `kindergarten quantum mechanics' wasn't just a joke.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Functorial evolution of quantum fields

We present a compositional algebraic framework to describe the evolution of quantum fields in discretised spacetimes. We show how familiar notions from Relativity and quantum causality can be recovered in a purely order-theoretic way from the causal order of events in spacetime, with no direct mention of analysis or topology. We formulate theory-independent notions of fields over causal orders in a compositional, functorial way. We draw a strong connection to Algebraic Quantum Field Theory (AQFT), using a sheaf-theoretical approach in our definition of spaces of states over regions of spacetime. We introduce notions of symmetry and cellular automata, which we show to subsume existing definitions of Quantum Cellular Automata (QCA) from previous literature. Given the extreme flexibility of our constructions, we propose that our framework be used as the starting point for new developments in AQFT, QCA and more generally Quantum Field Theory.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Meaning updating of density matrices

The DisCoCat model of natural language meaning assigns meaning to a sentence given: (i) the meanings of its words, and, (ii) its grammatical structure. The recently introduced DisCoCirc model extends this to text consisting of multiple sentences. While in DisCoCat all meanings are fixed, in DisCoCirc each sentence updates meanings of words. In this paper we explore different update mechanisms for DisCoCirc, in the case where meaning is encoded in density matrices---which come with several advantages as compared to vectors. Our starting point are two non-commutative update mechanisms, borrowing one from quantum foundations research, from Leifer and Spekkens. Unfortunately, neither of these satisfies any desirable algebraic properties, nor are internal to the meaning category. By passing to double density matrices we do get an elegant internal diagrammatic update mechanism. We also show that (commutative) spiders can be cast as an instance of the Leifer-Spekkens update mechanism. This result is of interest to quantum foundations, as it bridges the work in Categorical Quantum Mechanics (CQM) with that on conditional quantum states. Our work also underpins implementation of text-level natural language processing on quantum hardware (a.k.a. QNLP), for which exponential space-gain and quadratic speed-up have previously been identified.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Proceedings 16th International Conference on Quantum Physics and Logic

This volume contains the proceedings of the 16th International Conference on Quantum Physics and Logic (QPL 2017), which was held June 10-14, 2019. Quantum Physics and Logic is an annual conference that brings together researchers working on mathematical foundations of quantum physics, quantum computing, and related areas, with a focus on structural perspectives and the use of logical tools, ordered algebraic and category-theoretic structures, formal languages, semantical methods, and other computer science techniques applied to the study of physical behaviour in general. Work that applies structures and methods inspired by quantum theory to other fields (including computer science) is also welcome.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Mathematics of Text Structure

In previous work we gave a mathematical foundation, referred to as DisCoCat, for how words interact in a sentence in order to produce the meaning of that sentence. To do so, we exploited the perfect structural match of grammar and categories of meaning spaces. Here, we give a mathematical foundation, referred to as DisCoCirc, for how sentences interact in texts in order to produce the meaning of that text. First we revisit DisCoCat. While in DisCoCat all meanings are fixed as states (i.e. have no input), in DisCoCirc word meanings correspond to a type, or system, and the states of this system can evolve. Sentences are gates within a circuit which update the variable meanings of those words. Like in DisCoCat, word meanings can live in a variety of spaces e.g. propositional, vectorial, or cognitive. The compositional structure are string diagrams representing information flows, and an entire text yields a single string diagram in which word meanings lift to the meaning of an entire text. While the developments in this paper are independent of a physical embodiment (cf. classical vs. quantum computing), both the compositional formalism and suggested meaning model are highly quantum-inspired, and implementation on a quantum computer would come with a range of benefits. We also praise Jim Lambek for his role in mathematical linguistics in general, and the development of the DisCo program more specifically.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Categorical Quantum Mechanics I: Causal Quantum Processes

We derive the category-theoretic backbone of quantum theory from a process ontology. More specifically, we treat quantum theory as a theory of systems, processes and their interactions. In this first part of a three-part overview, we first present a general theory of diagrams, and in particular, of string diagrams. We discuss why diagrams are a very natural starting point for developing scientific theories. Then we define process theories, and define a very general notion of quantum type. We show how our process ontology enables us to assert causality, that is, compatibility of quantum theory and relativity theory, and we prove the no-signalling theorem. Other notable contributions include new, elegant derivations of the no-broadcasting theorem, unitarity of evolution, and Stinespring dilation, all for any 'quantum' type in a general class of process theories.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Categorical Quantum Mechanics II: Classical-Quantum Interaction

This is the second part of a three-part overview, in which we derive the category-theoretic backbone of quantum theory from a process ontology, treating quantum theory as a theory of systems, processes and their interactions. In this part we focus on classical-quantum interaction. Classical and quantum systems are treated as distinct types, of which the respective behavioural properties are specified in terms of processes and their compositions. In particular, classicality is witnessed by 'spiders' which fuse together whenever they connect. We define mixedness and show that pure processes are extremal in the space of all processes, and we define entanglement and show that quantum theory indeed exhibits entanglement. We discuss the classification of tripartite qubit entanglement and show that both the GHZ-state and the W-state come from spider-like families of processes, which differ only in how they behave when they are connected by two or more wires. We define measurements and provide fully-comprehensive descriptions of several quantum protocols involving classical data flow. Finally, we give a notion of 'genuine quantumness', from which special processes called 'phase spiders' arise, and get a first glimpse of quantum non-locality.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Compositional Distributional Cognition

We accommodate the Integrated Connectionist/Symbolic Architecture (ICS) of [32] within the categorical compositional semantics (CatCo) of [13], forming a model of categorical compositional cognition (CatCog). This resolves intrinsic problems with ICS such as the fact that representations inhabit an unbounded space and that sentences with differing tree structures cannot be directly compared. We do so in a way that makes the most of the grammatical structure available, in contrast to strategies like circular convolution. Using the CatCo model also allows us to make use of tools developed for CatCo such as the representation of ambiguity and logical reasoning via density matrices, structural meanings for words such as relative pronouns, and addressing over- and under-extension, all of which are present in cognitive processes. Moreover the CatCog framework is sufficiently flexible to allow for entirely different representations of meaning, such as conceptual spaces. Interestingly, since the CatCo model was largely inspired by categorical quantum mechanics, so is CatCog.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Dual Density Operators and Natural Language Meaning

Density operators allow for representing ambiguity about a vector representation, both in quantum theory and in distributional natural language meaning. Formally equivalently, they allow for discarding part of the description of a composite system, where we consider the discarded part to be the context. We introduce dual density operators, which allow for two independent notions of context. We demonstrate the use of dual density operators within a grammatical-compositional distributional framework for natural language meaning. We show that dual density operators can be used to simultaneously represent: (i) ambiguity about word meanings (e.g. queen as a person vs. queen as a band), and (ii) lexical entailment (e.g. tiger -> mammal). We provide a proof-of-concept example.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

From quantum foundations via natural language meaning to a theory of everything

In this paper we argue for a paradigmatic shift from `reductionism' to `togetherness'. In particular, we show how interaction between systems in quantum theory naturally carries over to modelling how word meanings interact in natural language. Since meaning in natural language, depending on the subject domain, encompasses discussions within any scientific discipline, we obtain a template for theories such as social interaction, animal behaviour, and many others.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Graded Entailment for Compositional Distributional Semantics

The categorical compositional distributional model of natural language provides a conceptually motivated procedure to compute the meaning of sentences, given grammatical structure and the meanings of its words. This approach has outperformed other models in mainstream empirical language processing tasks. However, until recently it has lacked the crucial feature of lexical entailment -- as do other distributional models of meaning. In this paper we solve the problem of entailment for categorical compositional distributional semantics. Taking advantage of the abstract categorical framework allows us to vary our choice of model. This enables the introduction of a notion of entailment, exploiting ideas from the categorical semantics of partial knowledge in quantum computation. The new model of language uses density matrices, on which we introduce a novel robust graded order capturing the entailment strength between concepts. This graded measure emerges from a general framework for approximate entailment, induced by any commutative monoid. Quantum logic embeds in our graded order. Our main theorem shows that entailment strength lifts compositionally to the sentence level, giving a lower bound on sentence entailment. We describe the essential properties of graded entailment such as continuity, and provide a procedure for calculating entailment strength.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Harmonic Grammar in a DisCo Model of Meaning

The model of cognition developed in (Smolensky and Legendre, 2006) seeks to unify two levels of description of the cognitive process: the connectionist and the symbolic. The theory developed brings together these two levels into the Integrated Connectionist/Symbolic Cognitive architecture (ICS). Clark and Pulman (2007) draw a parallel with semantics where meaning may be modelled on both distributional and symbolic levels, developed by Coecke et al, 2010 into the Distributional Compositional (DisCo) model of meaning. In the current work, we revisit Smolensky and Legendre (S&L)'s model. We describe the DisCo framework, summarise the key ideas in S&L's architecture, and describe how their description of harmony as a graded measure of grammaticality may be applied in the DisCo model.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Interacting Conceptual Spaces

We propose applying the categorical compositional scheme of [6] to conceptual space models of cognition. In order to do this we introduce the category of convex relations as a new setting for categorical compositional semantics, emphasizing the convex structure important to conceptual space applications. We show how conceptual spaces for composite types such as adjectives and verbs can be constructed. We illustrate this new model on detailed examples.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Process-theoretic characterisation of the Hermitian adjoint

We show that the physical principle "the adjoint associates to each state a `test' for that state" fully characterises the Hermitian adjoint for pure quantum theory, therefore providing the adjoint with operational meaning beyond its standard mathematical definition. Also, we show that for general process theories, which all admit a diagrammatic representation, this physical principle induces a reflection operation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Quantum Algorithms for Compositional Natural Language Processing

We propose a new application of quantum computing to the field of natural language processing. Ongoing work in this field attempts to incorporate grammatical structure into algorithms that compute meaning. In (Coecke, Sadrzadeh and Clark, 2010), the authors introduce such a model (the CSC model) based on tensor product composition. While this algorithm has many advantages, its implementation is hampered by the large classical computational resources that it requires. In this work we show how computational shortcomings of the CSC approach could be resolved using quantum computation (possibly in addition to existing techniques for dimension reduction). We address the value of quantum RAM (Giovannetti,2008) for this model and extend an algorithm from Wiebe, Braun and Lloyd (2012) into a quantum algorithm to categorize sentences in CSC. Our new algorithm demonstrates a quadratic speedup over classical methods under certain conditions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Compositional Explanation of the Pet Fish Phenomenon

The `pet fish' phenomenon is often cited as a paradigm example of the `non-compositionality' of human concept use. We show here how this phenomenon is naturally accommodated within a compositional distributional model of meaning. This model describes the meaning of a composite concept by accounting for interaction between its constituents via their grammatical roles. We give two illustrative examples to show how the qualitative phenomena are exhibited. We go on to apply the model to experimental data, and finally discuss extensions of the formalism.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Distributional Sentence Entailment Using Density Matrices

Categorical compositional distributional model of Coecke et al. (2010) suggests a way to combine grammatical composition of the formal, type logical models with the corpus based, empirical word representations of distributional semantics. This paper contributes to the project by expanding the model to also capture entailment relations. This is achieved by extending the representations of words from points in meaning space to density operators, which are probability distributions on the subspaces of the space. A symmetric measure of similarity and an asymmetric measure of entailment is defined, where lexical entailment is measured using von Neumann entropy, the quantum variant of Kullback-Leibler divergence. Lexical entailment, combined with the composition map on word representations, provides a method to obtain entailment relations on the level of sentences. Truth theoretic and corpus-based examples are provided.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Generalised Compositional Theories and Diagrammatic Reasoning

This chapter provides an introduction to the use of diagrammatic language, or perhaps more accurately, diagrammatic calculus, in quantum information and quantum foundations. We illustrate the use of diagrammatic calculus in one particular case, namely the study of complementarity and non-locality, two fundamental concepts of quantum theory whose relationship we explore in later part of this chapter. The diagrammatic calculus that we are concerned with here is not merely an illustrative tool, but it has both (i) a conceptual physical backbone, which allows it to act as a foundation for diverse physical theories, and (ii) a genuine mathematical underpinning, permitting one to relate it to standard mathematical structures.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Open System Categorical Quantum Semantics in Natural Language Processing

Originally inspired by categorical quantum mechanics (Abramsky and Coecke, LiCS'04), the categorical compositional distributional model of natural language meaning of Coecke, Sadrzadeh and Clark provides a conceptually motivated procedure to compute the meaning of a sentence, given its grammatical structure within a Lambek pregroup and a vectorial representation of the meaning of its parts. The predictions of this first model have outperformed that of other models in mainstream empirical language processing tasks on large scale data. Moreover, just like CQM allows for varying the model in which we interpret quantum axioms, one can also vary the model in which we interpret word meaning. In this paper we show that further developments in categorical quantum mechanics are relevant to natural language processing too. Firstly, Selinger's CPM-construction allows for explicitly taking into account lexical ambiguity and distinguishing between the two inherently different notions of homonymy and polysemy. In terms of the model in which we interpret word meaning, this means a passage from the vector space model to density matrices. Despite this change of model, standard empirical methods for comparing meanings can be easily adopted, which we demonstrate by a small-scale experiment on real-world data. This experiment moreover provides preliminary evidence of the validity of our proposed new model for word meaning. Secondly, commutative classical structures as well as their non-commutative counterparts that arise in the image of the CPM-construction allow for encoding relative pronouns, verbs and adjectives, and finally, iteration of the CPM-construction, something that has no counterpart in the quantum realm, enables one to accommodate both entailment and ambiguity.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A mathematical theory of resources

In many different fields of science, it is useful to characterize physical states and processes as resources. Chemistry, thermodynamics, Shannon's theory of communication channels, and the theory of quantum entanglement are prominent examples. Questions addressed by a theory of resources include: Which resources can be converted into which other ones? What is the rate at which arbitrarily many copies of one resource can be converted into arbitrarily many copies of another? Can a catalyst help in making an impossible transformation possible? How does one quantify the resource? Here, we propose a general mathematical definition of what constitutes a resource theory. We prove some general theorems about how resource theories can be constructed from theories of processes wherein there is a special class of processes that are implementable at no cost and which define the means by which the costly states and processes can be interconverted one to another. We outline how various existing resource theories fit into our framework. Our abstract characterization of resource theories is a first step in a larger project of identifying universal features and principles of resource theories. In this vein, we identify a few general results concerning resource convertibility.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Categories of Quantum and Classical Channels

We introduce a construction that turns a category of pure state spaces and operators into a category of observable algebras and superoperators. For example, it turns the category of finite-dimensional Hilbert spaces into the category of finite-dimensional C*-algebras and completely positive maps. In particular, the new category contains both quantum and classical channels, providing elegant abstract notions of preparation and measurement. We also consider nonstandard models, that can be used to investigate which notions from algebraic quantum information theory are operationally justifiable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Categories of Quantum and Classical Channels (extended abstract)

We introduce the CP*-construction on a dagger compact closed category as a generalisation of Selinger's CPM-construction. While the latter takes a dagger compact closed category and forms its category of "abstract matrix algebras" and completely positive maps, the CP*-construction forms its category of "abstract C*-algebras" and completely positive maps. This analogy is justified by the case of finite-dimensional Hilbert spaces, where the CP*-construction yields the category of finite-dimensional C*-algebras and completely positive maps. The CP*-construction fully embeds Selinger's CPM-construction in such a way that the objects in the image of the embedding can be thought of as "purely quantum" state spaces. It also embeds the category of classical stochastic maps, whose image consists of "purely classical" state spaces. By allowing classical and quantum data to coexist, this provides elegant abstract notions of preparation, measurement, and more general quantum channels.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Complete set of circuit equations for Stabilizer Quantum Mechanics

We find a sufficient set of equations between quantum circuits from which we can derive any other equation between stabilizer quantum circuits. To establish this result, we rely upon existing work on the completeness of the graphical ZX language for quantum processes. The complexity of the circuit equations, as opposed to the very intuitive reading of the much smaller number of ZX-equations, advocates the latter for performing computations with quantum circuits.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Proceedings of the 10th International Workshop on Quantum Physics and Logic

This volume contains the proceedings of the 10th International Workshop on Quantum Physics and Logic (QPL X), which was held July 17-19, 2013 at ICFO in Castelldefels (Barcelona), Spain. The goal of this workshop series is to bring together researchers working on mathematical foundations of quantum physics, quantum computing and spatio-temporal causal structures, and in particular those that use logical tools, ordered algebraic and category-theoretic structures, formal languages, semantic methods and other computer science methods for the study of physical behavior in general. Over the past few years, there has been growing activity in these foundational approaches, together with a renewed interest in the foundations of quantum theory, which complement the more mainstream research in quantum computation.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Proceedings of the 11th workshop on Quantum Physics and Logic

This volume contains the proceedings of the 11th International Workshop on Quantum Physics and Logic (QPL 2014), which was held from the 4th to the 6th of June, 2014, at Kyoto University, Japan. The goal of the QPL workshop series is to bring together researchers working on mathematical foundations of quantum physics, quantum computing and spatio-temporal causal structures, and in particular those that use logical tools, ordered algebraic and category-theoretic structures, formal languages, semantic methods and other computer science methods for the study of physical behavior in general. Over the past few years, there has been growing activity in these foundational approaches, together with a renewed interest in the foundations of quantum theory, which complement the more mainstream research in quantum computation. Earlier workshops in this series, with the same acronym under the name "Quantum Programming Languages", were held in Ottawa (2003), Turku (2004), Chicago (2005), and Oxford (2006). The first QPL under the new name Quantum Physics and Logic was held in Reykjavik (2008), followed by Oxford (2009 and 2010), Nijmegen (2011), Brussels (2012) and Barcelona (2013).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Reasoning about Meaning in Natural Language with Compact Closed Categories and Frobenius Algebras

Compact closed categories have found applications in modeling quantum information protocols by Abramsky-Coecke. They also provide semantics for Lambek's pregroup algebras, applied to formalizing the grammatical structure of natural language, and are implicit in a distributional model of word meaning based on vector spaces. Specifically, in previous work Coecke-Clark-Sadrzadeh used the product category of pregroups with vector spaces and provided a distributional model of meaning for sentences. We recast this theory in terms of strongly monoidal functors and advance it via Frobenius algebras over vector spaces. The former are used to formalize topological quantum field theories by Atiyah and Baez-Dolan, and the latter are used to model classical data in quantum protocols by Coecke-Pavlovic-Vicary. The Frobenius algebras enable us to work in a single space in which meanings of words, phrases, and sentences of any structure live. Hence we can compare meanings of different language constructs and enhance the applicability of the theory. We report on experimental results on a number of language tasks and verify the theoretical predictions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Terminality implies non-signalling

A 'process theory' is any theory of systems and processes which admits sequential and parallel composition. `Terminality' unifies normalisation of pure states, trace-preservation of CP-maps, and adding up to identity of positive operators in quantum theory, and generalises this to arbitrary process theories. We show that terminality and non-signalling coincide in any process theory, provided one makes causal structure explicit. In fact, making causal structure explicit is necessary to even make sense of non-signalling in process theories. We conclude that because of its much simpler mathematical form, terminality should be taken to be a more fundamental notion than non-signalling.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Frobenius anatomy of word meanings I: subject and object relative pronouns

This paper develops a compositional vector-based semantics of subject and object relative pronouns within a categorical framework. Frobenius algebras are used to formalise the operations required to model the semantics of relative pronouns, including passing information between the relative clause and the modified noun phrase, as well as copying, combining, and discarding parts of the relative clause. We develop two instantiations of the abstract semantics, one based on a truth-theoretic approach and one based on corpus statistics.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Frobenius anatomy of word meanings II: possessive relative pronouns

Within the categorical compositional distributional model of meaning, we provide semantic interpretations for the subject and object roles of the possessive relative pronoun `whose'. This is done in terms of Frobenius algebras over compact closed categories. These algebras and their diagrammatic language expose how meanings of words in relative clauses interact with each other. We show how our interpretation is related to Montague-style semantics and provide a truth-theoretic interpretation. We also show how vector spaces provide a concrete interpretation and provide preliminary corpus-based experimental evidence. In a prequel to this paper, we used similar methods and dealt with the case of subject and object relative pronouns.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An alternative Gospel of structure: order, composition, processes

We survey some basic mathematical structures, which arguably are more primitive than the structures taught at school. These structures are orders, with or without composition, and (symmetric) monoidal categories. We list several `real life' incarnations of each of these. This paper also serves as an introduction to these structures and their current and potentially future uses in linguistics, physics and knowledge representation.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Compositional Quantum Logic

Quantum logic aims to capture essential quantum mechanical structure in order-theoretic terms. The Achilles' heel of quantum logic is the absence of a canonical description of composite systems, given descriptions of their components. We introduce a framework in which order-theoretic structure comes with a primitive composition operation. The order is extracted from a generalisation of C*-algebra that applies to arbitrary dagger symmetric monoidal categories, which also provide the composition operation. In fact, our construction is entirely compositional, without any additional assumptions on limits or enrichment. Interpreted in the category of finite-dimensional Hilbert spaces, it yields the projection lattices of arbitrary finite-dimensional C*-algebras. Interestingly, there are models that falsify standardly assumed correspondences, most notably the correspondence between noncommutativity of the algebra and nondistributivity of the order.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lambek vs. Lambek: Functorial Vector Space Semantics and String Diagrams for Lambek Calculus

The Distributional Compositional Categorical (DisCoCat) model is a mathematical framework that provides compositional semantics for meanings of natural language sentences. It consists of a computational procedure for constructing meanings of sentences, given their grammatical structure in terms of compositional type-logic, and given the empirically derived meanings of their words. For the particular case that the meaning of words is modelled within a distributional vector space model, its experimental predictions, derived from real large scale data, have outperformed other empirically validated methods that could build vectors for a full sentence. This success can be attributed to a conceptually motivated mathematical underpinning, by integrating qualitative compositional type-logic and quantitative modelling of meaning within a category-theoretic mathematical framework. The type-logic used in the DisCoCat model is Lambek's pregroup grammar. Pregroup types form a posetal compact closed category, which can be passed, in a functorial manner, on to the compact closed structure of vector spaces, linear maps and tensor product. The diagrammatic versions of the equational reasoning in compact closed categories can be interpreted as the flow of word meanings within sentences. Pregroups simplify Lambek's previous type-logic, the Lambek calculus, which has been extensively used to formalise and reason about various linguistic phenomena. The apparent reliance of the DisCoCat on pregroups has been seen as a shortcoming. This paper addresses this concern, by pointing out that one may as well realise a functorial passage from the original type-logic of Lambek, a monoidal bi-closed category, to vector spaces, or to any other model of meaning organised within a monoidal bi-closed category. The corresponding string diagram calculus, due to Baez and Stay, now depicts the flow of word meanings.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Environment and classical channels in categorical quantum mechanics

We present a both simple and comprehensive graphical calculus for quantum computing. In particular, we axiomatize the notion of an environment, which together with the earlier introduced axiomatic notion of classical structure enables us to define classical channels, quantum measurements and classical control. If we moreover adjoin the earlier introduced axiomatic notion of complementarity, we obtain sufficient structural power for constructive representation and correctness derivation of typical quantum informatic protocols.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Strong Complementarity and Non-locality in Categorical Quantum Mechanics

Categorical quantum mechanics studies quantum theory in the framework of dagger-compact closed categories. Using this framework, we establish a tight relationship between two key quantum theoretical notions: non-locality and complementarity. In particular, we establish a direct connection between Mermin-type non-locality scenarios, which we generalise to an arbitrary number of parties, using systems of arbitrary dimension, and performing arbitrary measurements, and a new stronger notion of complementarity which we introduce here. Our derivation of the fact that strong complementarity is a necessary condition for a Mermin scenario provides a crisp operational interpretation for strong complementarity. We also provide a complete classification of strongly complementary observables for quantum theory, something which has not yet been achieved for ordinary complementarity. Since our main results are expressed in the (diagrammatic) language of dagger-compact categories, they can be applied outside of quantum theory, in any setting which supports the purely algebraic notion of strongly complementary observables. We have therefore introduced a method for discussing non-locality in a wide variety of models in addition to quantum theory. The diagrammatic calculus substantially simplifies (and sometimes even trivialises) many of the derivations, and provides new insights. In particular, the diagrammatic computation of correlations clearly shows how local measurements interact to yield a global overall effect. In other words, we depict non-locality.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The logic of quantum mechanics - Take II

We put forward a new take on the logic of quantum mechanics, following Schroedinger's point of view that it is composition which makes quantum theory what it is, rather than its particular propositional structure due to the existence of superpositions, as proposed by Birkhoff and von Neumann. This gives rise to an intrinsically quantitative kind of logic, which truly deserves the name `logic' in that it also models meaning in natural language, the latter being the origin of logic, that it supports automation, the most prominent practical use of logic, and that it supports probabilistic inference.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Trichromatic Open Digraphs for Understanding Qubits

We introduce a trichromatic graphical calculus for quantum computing. The generators represent three complementary observables that are treated on equal footing, hence reflecting the symmetries of the Bloch sphere. We derive the Euler angle decomposition of the Hadamard gate within it as well as the so-called supplementary relationships, which are valid equations for qubits that were not derivable within Z/X-calculus of Coecke and Duncan. More specifically, we have: dichromatic Z/X-calculus + Euler angle decomposition of the Hadamard gate = trichromatic calculus.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Causal categories: relativistically interacting processes

A symmetric monoidal category naturally arises as the mathematical structure that organizes physical systems, processes, and composition thereof, both sequentially and in parallel. This structure admits a purely graphical calculus. This paper is concerned with the encoding of a fixed causal structure within a symmetric monoidal category: causal dependencies will correspond to topological connectedness in the graphical language. We show that correlations, either classical or quantum, force terminality of the tensor unit. We also show that well-definedness of the concept of a global state forces the monoidal product to be only partially defined, which in turn results in a relativistic covariance theorem. Except for these assumptions, at no stage do we assume anything more than purely compositional symmetric-monoidal categorical structure. We cast these two structural results in terms of a mathematical entity, which we call a `causal category'. We provide methods of constructing causal categories, and we study the consequences of these methods for the general framework of categorical quantum mechanics.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Interacting Quantum Observables: Categorical Algebra and Diagrammatics

This paper has two tightly intertwined aims: (i) To introduce an intuitive and universal graphical calculus for multi-qubit systems, the ZX-calculus, which greatly simplifies derivations in the area of quantum computation and information. (ii) To axiomatise complementarity of quantum observables within a general framework for physical theories in terms of dagger symmetric monoidal categories. We also axiomatize phase shifts within this framework. Using the well-studied canonical correspondence between graphical calculi and symmetric monoidal categories, our results provide a purely graphical formalisation of complementarity for quantum observables. Each individual observable, represented by a commutative special dagger Frobenius algebra, gives rise to an abelian group of phase shifts, which we call the phase group. We also identify a strong form of complementarity, satisfied by the Z and X spin observables, which yields a scaled variant of a bialgebra.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Picturing classical and quantum Bayesian inference

We introduce a graphical framework for Bayesian inference that is sufficiently general to accommodate not just the standard case but also recent proposals for a theory of quantum Bayesian inference wherein one considers density operators rather than probability distributions as representative of degrees of belief. The diagrammatic framework is stated in the graphical language of symmetric monoidal categories and of compact structures and Frobenius structures therein, in which Bayesian inversion boils down to transposition with respect to an appropriate compact structure. We characterize classical Bayesian inference in terms of a graphical property and demonstrate that our approach eliminates some purely conventional elements that appear in common representations thereof, such as whether degrees of belief are represented by probabilities or entropic quantities. We also introduce a quantum-like calculus wherein the Frobenius structure is noncommutative and show that it can accommodate Leifer's calculus of `conditional density operators'. The notion of conditional independence is also generalized to our graphical setting and we make some preliminary connections to the theory of Bayesian networks. Finally, we demonstrate how to construct a graphical Bayesian calculus within any dagger compact category.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Proceedings CSR 2010 Workshop on High Productivity Computations

This volume contains the proceedings of the Workshop on High Productivity Computations (HPC 2010) which took place on June 21-22 in Kazan, Russia. This workshop was held as a satellite workshop of the 5th International Computer Science Symposium in Russia (CSR 2010). HPC 2010 was intended to organize the discussions about high productivity computing means and models, including but not limited to high performance and quantum information processing.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Spekkens's toy theory as a category of processes

We provide two mathematical descriptions of Spekkens's toy qubit theory, an inductively one in terms of a small set of generators, as well as an explicit closed form description. It is a subcategory MSpek of the category of finite sets, relations and the cartesian product. States of maximal knowledge form a subcategory Spek. This establishes the consistency of the toy theory, which has previously only been constructed for at most four systems. Our model also shows that the theory is closed under both parallel and sequential composition of operations (= symmetric monoidal structure), that it obeys map-state duality (= compact closure), and that states and effects are in bijective correspondence (= dagger structure). From the perspective of categorical quantum mechanics, this provides an interesting alternative model which enables us to describe many quantum phenomena in a discrete manner, and to which mathematical concepts such as basis structures, and complementarity thereof, still apply. Hence, the framework of categorical quantum mechanics has delivered on its promise to encompass theories other than quantum theory.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The GHZ/W-calculus contains rational arithmetic

Graphical calculi for representing interacting quantum systems serve a number of purposes: compositionally, intuitive graphical reasoning, and a logical underpinning for automation. The power of these calculi stems from the fact that they embody generalized symmetries of the structure of quantum operations, which, for example, stretch well beyond the Choi-Jamiolkowski isomorphism. One such calculus takes the GHZ and W states as its basic generators. Here we show that this language allows one to encode standard rational calculus, with the GHZ state as multiplication, the W state as addition, the Pauli X gate as multiplicative inversion, and the Pauli Z gate as additive inversion.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Three qubit entanglement within graphical Z/X-calculus

The compositional techniques of categorical quantum mechanics are applied to analyse 3-qubit quantum entanglement. In particular the graphical calculus of complementary observables and corresponding phases due to Duncan and one of the authors is used to construct representative members of the two genuinely tripartite SLOCC classes of 3-qubit entangled states, GHZ and W. This nicely illustrates the respectively pairwise and global tripartite entanglement found in the W- and GHZ-class states. A new concept of supplementarity allows us to characterise inhabitants of the W class within the abstract diagrammatic calculus; these method extends to more general multipartite qubit states.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Time-asymmetry and causal structure

We consider devices with two inputs and two outputs, Alice and Bob each having access to one input and one output. To such a device we associate time-reverses by exchanging the roles of the inputs and the outputs. We find that there are devices which admit a local hidden variable representation, but for which time-reverses enable perfect signaling between Alice and Bob. That is, a `perfect channel in one time direction' becomes a `non-channel in the other direction'. Also, for PR boxes time-reverses enable signaling between Alice and Bob, but never as a perfect channel. These results undermine the representation of causal structures as partial orders or similar `time-symmetric structures', as is often assumed in search of a theory of quantum gravity. They also provide new insights into the structure of the polytope of generalized probabilistic correlations, and contribute to the growing area of research into quantum information processing in relativistic spacetimes.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Time-asymmetry of probabilities versus relativistic causal structure: an arrow of time

There is an incompatibility between the symmetries of causal structure in relativity theory and the signaling abilities of probabilistic devices with inputs and outputs: while time-reversal in relativity will not introduce the ability to signal between spacelike separated regions, this is not the case for probabilistic devices with space-like separated input-output pairs. We explicitly describe a non-signaling device which becomes a perfect signaling device under time-reversal, where time-reversal can be conceptualized as playing backwards a videotape of an agent manipulating the device. This leads to an arrow of time that is identifiable when studying the correlations of events for spacelike separated regions. Somewhat surprisingly, although time-reversal of Popuscu-Roerlich boxes also allows agents to signal, it does not yield a perfect signaling device. Finally, we realize time-reversal using post-selection, which could lead experimental implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A universe of processes and some of its guises

Our starting point is a particular `canvas' aimed to `draw' theories of physics, which has symmetric monoidal categories as its mathematical backbone. In this paper we consider the conceptual foundations for this canvas, and how these can then be converted into mathematical structure. With very little structural effort (i.e. in very abstract terms) and in a very short time span the categorical quantum mechanics (CQM) research program has reproduced a surprisingly large fragment of quantum theory. It also provides new insights both in quantum foundations and in quantum information, and has even resulted in automated reasoning software called `quantomatic' which exploits the deductive power of CQM. In this paper we complement the available material by not requiring prior knowledge of category theory, and by pointing at connections to previous and current developments in the foundations of physics. This research program is also in close synergy with developments elsewhere, for example in representation theory, quantum algebra, knot theory, topological quantum field theory and several other areas.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Concrete Sentence Spaces for Compositional Distributional Models of Meaning

Coecke, Sadrzadeh, and Clark (arXiv:1003.4394v1 [cs.CL]) developed a compositional model of meaning for distributional semantics, in which each word in a sentence has a meaning vector and the distributional meaning of the sentence is a function of the tensor products of the word vectors. Abstractly speaking, this function is the morphism corresponding to the grammatical structure of the sentence in the category of finite dimensional vector spaces. In this paper, we provide a concrete method for implementing this linear meaning map, by constructing a corpus-based vector space for the type of sentence. Our construction method is based on structured vector spaces whereby meaning vectors of all sentences, regardless of their grammatical structure, live in the same vector space. Our proposed sentence space is the tensor product of two noun spaces, in which the basis vectors are pairs of words each augmented with a grammatical role. This enables us to compare meanings of sentences by simply taking the inner product of their vectors.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Mathematical Foundations for a Compositional Distributional Model of Meaning

We propose a mathematical framework for a unification of the distributional theory of meaning in terms of vector space models, and a compositional theory for grammatical types, for which we rely on the algebra of Pregroups, introduced by Lambek. This mathematical framework enables us to compute the meaning of a well-typed sentence from the meanings of its constituents. Concretely, the type reductions of Pregroups are `lifted' to morphisms in a category, a procedure that transforms meanings of constituents into a meaning of the (well-typed) whole. Importantly, meanings of whole sentences live in a single space, independent of the grammatical structure of the sentence. Hence the inner-product can be used to compare meanings of arbitrary sentences, as it is for comparing the meanings of words in the distributional model. The mathematical structure we employ admits a purely diagrammatic calculus which exposes how the information flows between the words in a sentence in order to make up the meaning of the whole sentence. A variation of our `categorical model' which involves constraining the scalars of the vector spaces to the semiring of Booleans results in a Montague-style Boolean-valued semantics.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Phase groups and the origin of non-locality for qubits

We describe a general framework in which we can precisely compare the structures of quantum-like theories which may initially be formulated in quite different mathematical terms. We then use this framework to compare two theories: quantum mechanics restricted to qubit stabiliser states and operations, and Spekkens's toy theory. We discover that viewed within our framework these theories are very similar, but differ in one key aspect - a four element group we term the phase group which emerges naturally within our framework. In the case of the stabiliser theory this group is Z4 while for Spekkens's toy theory the group is Z2 x Z2. We further show that the structure of this group is intimately involved in a key physical difference between the theories: whether or not they can be modelled by a local hidden variable theory. This is done by establishing a connection between the phase group, and an abstract notion of GHZ state correlations. We go on to formulate precisely how the stabiliser theory and toy theory are `similar' by defining a notion of `mutually unbiased qubit theory', noting that all such theories have four element phase groups. Since Z4 and Z2 x Z2 are the only such groups we conclude that the GHZ correlations in this type of theory can only take two forms, exactly those appearing in the stabiliser theory and in Spekkens's toy theory. The results point at a classification of local/non-local behaviours by finite Abelian groups, extending beyond qubits to finitary theories whose observables are all mutually unbiased.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The compositional structure of multipartite quantum entanglement

While multipartite quantum states constitute a (if not the) key resource for quantum computations and protocols, obtaining a high-level, structural understanding of entanglement involving arbitrarily many qubits is a long-standing open problem in quantum computer science. In this paper we expose the algebraic and graphical structure of the GHZ-state and the W-state, as well as a purely graphical distinction that characterises the behaviours of these states. In turn, this structure yields a compositional graphical model for expressing general multipartite states. We identify those states, named Frobenius states, which canonically induce an algebraic structure, namely the structure of a commutative Frobenius algebra (CFA). We show that all SLOCC-maximal tripartite qubit states are locally equivalent to Frobenius states. Those that are SLOCC-equivalent to the GHZ-state induce special commutative Frobenius algebras, while those that are SLOCC-equivalent to the W-state induce what we call anti-special commutative Frobenius algebras. From the SLOCC-classification of tripartite qubit states follows a representation theorem for two dimensional CFAs. Together, a GHZ and a W Frobenius state form the primitives of a graphical calculus. This calculus is expressive enough to generate and reason about arbitrary multipartite states, which are obtained by "composing" the GHZ- and W-states, giving rise to a rich graphical paradigm for general multipartite entanglement.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Quantum Picturalism

The quantum mechanical formalism doesn't support our intuition, nor does it elucidate the key concepts that govern the behaviour of the entities that are subject to the laws of quantum physics. The arrays of complex numbers are kin to the arrays of 0s and 1s of the early days of computer programming practice. In this review we present steps towards a diagrammatic `high-level' alternative for the Hilbert space formalism, one which appeals to our intuition. It allows for intuitive reasoning about interacting quantum systems, and trivialises many otherwise involved and tedious computations. It clearly exposes limitations such as the no-cloning theorem, and phenomena such as quantum teleportation. As a logic, it supports `automation'. It allows for a wider variety of underlying theories, and can be easily modified, having the potential to provide the required step-stone towards a deeper conceptual understanding of quantum theory, as well as its unification with other physical theories. Specific applications discussed here are purely diagrammatic proofs of several quantum computational schemes, as well as an analysis of the structural origin of quantum non-locality. The underlying mathematical foundation of this high-level diagrammatic formalism relies on so-called monoidal categories, a product of a fairly recent development in mathematics. These monoidal categories do not only provide a natural foundation for physical theories, but also for proof theory, logic, programming languages, biology, cooking, ... The challenge is to discover the necessary additional pieces of structure that allow us to predict genuine quantum phenomena.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

A new description of orthogonal bases

We show that an orthogonal basis for a finite-dimensional Hilbert space can be equivalently characterised as a commutative dagger-Frobenius monoid in the category FdHilb, which has finite-dimensional Hilbert spaces as objects and continuous linear maps as morphisms, and tensor product for the monoidal structure. The basis is normalised exactly when the corresponding commutative dagger-Frobenius monoid is special. Hence orthogonal and orthonormal bases can be axiomatised in terms of composition of operations and tensor product only, without any explicit reference to the underlying vector spaces. This axiomatisation moreover admits an operational interpretation, as the comultiplication copies the basis vectors and the counit uniformly deletes them. That is, we rely on the distinct ability to clone and delete classical data as compared to quantum data to capture basis vectors. For this reason our result has important implications for categorical quantum mechanics.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Kindergarten Quantum Mechanics

These lecture notes survey some joint work with Samson Abramsky as it was presented by me at several conferences in the summer of 2005. It concerns `doing quantum mechanics using only pictures of lines, squares, triangles and diamonds'. This picture calculus can be seen as a very substantial extension of Dirac's notation, and has a purely algebraic counterpart in terms of so-called Strongly Compact Closed Categories (introduced by Abramsky and I in quant-ph/0402130 and [4]) which subsumes my Logic of Entanglement quant-ph/0402014. For a survey on the `what', the `why' and the `hows' I refer to a previous set of lecture notes quant-ph/0506132. In a last section we provide some pointers to the body of technical literature on the subject.

0 citations0 reviewsNo code linkedOpen access