QPL2016 : Accepted papers

Quantum Physics and Logic
6 – 10 June 2016, Glasgow, Scotland

The following list, in alphabetical order, all the contributions which have been accepted for presentation at QPL 2016. For the order of the presentations see the schedule. To download a paper, click on the PDF link next to its title.

After the conference, the Programme Committee will invite the best original contributions to appear in the proceedings volume, which will be published by EPTCS.

Please note that the distinction between short and long talks has no bearing on whether the submission was original or not; it's simply a compromise to allow more talks to be accepted.

Invited Lectures

Elham Kashefi
Abstract: TBA << Hide abstract
Tom Leinster
In search of the spectrum

The word "spectrum" is used in multiple ways in mathematics and physics, most of them related. But what is the spectrum in abstract terms? Different answers to this question have been given for different types of spectrum, including Hakim's very elegant topos-theoretic characterization of the spectrum of a commutative ring.

I will focus on a meaning of "spectrum" that is very elementary, yet still poses a challenge: the set of eigenvalues of an operator on a finite-dimensional vector space, with their algebraic multiplicities. Spectra of linear operators are indisputably important but irredeemably unfunctorial, in the sense that knowing the spectra of two operators on a space tells you almost nothing about the spectrum of their composite. Nevertheless, I will describe a universal property that characterizes the spectrum, and I will say a little about the invariants that arise when one interprets this universal property in categories other than finite-dimensional vector spaces.

<< Hide abstract
Martin Roetteler
Reversible circuit compilation with space constraints

I will present LIQUi|>, a quantum programming language and simulation environment developed at Microsoft Research (available at http://stationq.github.io/Liquid/) and REVS, a tool for resource-aware compilation of higher-level, irreversible programs into lower-level, reversible circuits. Our main focus is on optimizing the memory footprint of the resulting reversible networks.

We discuss a number of examples to illustrate our compilation strategy for problems at scale, including a reversible implementation of hash functions such as SHA-256, automatic generation of reversible integer arithmetic from irreversible descriptions, as well as a test-bench of Boolean circuits that is used by the classical Circuits and Systems community. Our main findings are that, when compared with Bennett's original ``compute-copy-uncompute'', it is possible to reduce the space complexity by 75 percent or more, at the price of having an only moderate increase in circuit size as well as in compilation time.

Based on joint work with Matt Amy, Alex Parent, and Krysta M. Svore: http://arxiv.org/abs/1510.00377 and http://arxiv.org/abs/1603.01635.

<< Hide abstract
Stephanie Wehner
From Bell inequality violations towards device independence of general quantum cryptographic protocols

Bell tests form an essential ingredient for device independent quantum cryptography. Recently, the elusive goal of performing a loophole free Bell test has finally been achieved by using entangled electron spins in diamond. We start by reporting on this experiment, before discussing general methods to analyze the statistical significance of Bell experiments. We proceed to develop the theory of device-independent two-party quantum cryptography. Concretely, we propose a model and protocol for device-independent weak string erasure in the bounded and noisy-storage model that can in turn be converted to other protocols such as bit commitment or position verification.

Joint work with :

- B. Hensen, H. Bernien, A. Dreau, A. Reiserer, N. Kalb, M. Blok, J. Ruitenberg, R.F.L. Vermeulen, R.N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D.J. Twitchen, D. Elkouss, S. Wehner, T.H. Taminiau, R. Hanson - arXiv:1508.05949, Nature.
- D. Elkouss and S. Wehner - arXiv:1510.07233 (NPJ Quantum Information, To appear)
- J. Ribeiro, J. Kaniewski, T. Le, J. Helsen and S. Wehner - In preparation.
<< Hide abstract

Tutorial Lectures

Kohei Kishida
Non-Locality, Contextuality, and Sheaves

Non-locality and contextuality are among the most paradoxical properties of quantum physics contradicting the intuitions behind classical physics. In addition to their foundational significance, non-locality is fundamental to quantum information, and recent studies suggest contextuality is a key computational resource of quantum computation. This has motivated inquiries into higher-level, structural expressions of non-locality and contextuality that are independent of the concrete formalism of quantum mechanics. One approach uses the mathematical tool of sheaf theory, and has yielded the insight that non-locality and contextuality are matters of topological nature.

In this tutorial, we first review several ideas as well as formal expressions of non-locality, and extract from them the sheaf formalism for quantum measurement scenarios and a characterization of non-locality in this formalism. In fact, as we show, the same characterization captures contextuality as well (so that non-locality amounts to a special case of contextuality). We will then illustrate the power of this higher-level, unifying formalism: On the one hand, it leads to several new methods of contextuality argument. On the other hand, it shows contextuality to be a ubiquitous phenomenon that can be found in various other disciplines.

<< Hide abstract
Aleks Kissinger
Process Theories and Graphical Languages

I'll give an overview of the core topics from the upcoming textbook "Picturing Quantum Processes", starting with the notions of process theory and string diagram and building up to a full fledged theory of quantum processes and quantum/classical interaction. Along the way, I'll introduce concepts such as the "doubling" of a process theory, connectedness, and causality and demonstrate the power of reasoning purely with diagrams by deriving many typically quantum features, such as no-go theorems for cloning and universal separability, quantum teleportation, complementarity, entanglement classification, and quantum non-locality.

<< Hide abstract
Conor McBride
Logic and Functional Programming
Abstract: TBA << Hide abstract
Daniel Oi
Quantum Foundations and Bell Experiments

Quantum mechanics is one of our best tested and successful physical theories and underlies most fundamental physics. However, there is still considerable debate over its interpretation and attempts to reconcile it with the classical worldview have met with failure. At the heart of the mystery of quantum theory is the status of the wavefunction, the meaning of measurement, and the existence of non-locality. This tutorial will give a bird's eye overview of the foundational questions surrounding quantum theory. We will also briefly cover Bell's Inequality and its constraint on local-realistic theories.

<< Hide abstract
Ognyan Oreshkov
Causality and indefinite causal structures in quantum theory

Quantum theory can be understood as a theory of information processing in the circuit framework for operational probabilistic theories. This approach presupposes a definite casual structure and a preferred time direction. But in certain scenarios, such as those involving gravity, or in higher-order information processing models, the causal structure may be dynamical and not predefined. In this lecture, I will discuss the notion of causality in quantum theory from an operational perspective and will describe recent advances towards developing generalized frameworks for quantum theory that allow for dynamical and indefinite causal structures.

<< Hide abstract
Peter Selinger
Introduction to Quipper

This will be a tutorial introduction to Quipper, a scalable embedded functional programming language for quantum computing.

<< Hide abstract

Long Talks

Samson Abramsky, Rui Soares Barbosa and Shane Mansfield
Quantifying contextuality via linear programming PDF
Abstract: We explore how the qualitative hierarchy of strengths of contextuality introduced in [3] relates to the quantitative notion of the non-contextual fraction of an empirical model. We show that this provides a fully general quantitative measure of contextuality, applicable to any empirical model, which is related to the maximal possible violation of generalised Bell inequalities. The calculation of this measure, as well as finding such witnessing inequalities, can be formulated as linear optimisation problems. We have implemented these methods and used them to explore the degree of non-locality of empirical models arising from local equatorial measurements on the |φ+⟩ Bell state and the n-partite GHZ states.<< Hide abstract
Miriam Backens, Simon Perdrix and Quanlong Wang
A Simplified Stabilizer ZX-calculus PDF
Abstract: The stabilizer ZX-calculus is a rigorous graphical language for reasoning about stabilizer quantum mechanics. This language has been proved to be complete in two steps: first in a setting where scalars (diagrams with no inputs or outputs) are ignored and then in a more general setting where a new symbol and three additional rules have been added to keep track of scalars. Here, we introduce a simplified version of the stabilizer ZX-calculus: we give a smaller set of axioms and prove that meta-rules like `only the topology matters', `colour symmetry' and `upside-down symmetry', which were considered as axioms in previous versions of the stabilizer ZX-calculus, can in fact be derived. In particular, we show that the additional symbol and one of the rules introduced for proving the completeness of the scalar stabilizer ZX-calculus are not necessary. We furthermore show that the remaining two rules dedicated to scalars cannot be derived from the other rules, i.e. they are necessary.<< Hide abstract
On the Cohomology of Contextuality PDF
Abstract: Recent work by Abramsky and Brandenburger used sheaf theory to give a mathematical formulation of non-locality and contextuality. By adopting this viewpoint, it has been possible to define cohomological obstructions to the existence of global sections. In the present work, we illustrate new insights into different aspects of this theory. We shed light on the power of detection of the cohomological obstruction by showing that it is not a complete invariant for strong contextuality even under symmetry and connectedness restrictions on the measurement cover. We generalise obstructions to higher cohomology groups and show that they give rise to a refinement of the notion of cohomological contextuality: different “levels” of contextuality are organised in a hierarchy of logical implications. Finally, we present an alternative description of the first cohomology group in terms of torsors relative to a presheaf, resulting in a new interpretation of the cohomological obstructions.<< Hide abstract
Giulio Chiribella and Carlo Maria Scandolo
An operational resource theory of purity PDF
Abstract: Abstract A successful approach to the foundations of thermodynamics is to consider purity as a resource. Operationally, this can be done in different ways, depending on which set of operations is regarded as “free”, or easy to implement. In classical and quantum theory, all the reasonable choices of free operations lead to the same ordering of states, characterised by the majorisation criterion. But what are the roots of such an equivalence? In this paper we address the question in the framework of general probabilistic theories. For arbitrary theories a notion of purity as a resource can be defined by choosing random reversible channels as free operations. For theories satisfying the axioms of Causality, Purity Preservation, Purification, and Pure Sharpness, we show that one can put forward two alternative notions of purity as a resource: one where free operations are unital channels, and another where free operations are generated by reversible interactions with an environment in the invariant state. One additional axiom, Permutability/Strong Symmetry, guarantees that all the above resource theories are equivalent, i.e. they all lead to the same ordering relations between states. For theories satisfying the five axioms we show that the notion of purity as a resource is completely characterised by a majorisation criterion, in the very same way as it is in quantum theory.<< Hide abstract
Von Neumann Algebras Form a Model for the Quantum Lambda Calculus PDF
Abstract: We present a model of Selinger and Valiron's quantum lambda calculus based on von Neumann algebras, and show that the model is adequate with respect to the operational semantics.
<< Hide abstract
Ross Duncan and Kevin Dunne
Interacting Frobenius Algebras are Hopf PDF
Abstract: Theories featuring the interaction between a Frobenius algebra and a Hopf algebra have recently appeared in several areas in computer science: concurrent programming, control theory, and quantum computing, among others. Bonchi, Sobocinski, and Zanasi (2014) have shown that, given a suitable distributive law, a pair of Hopf algebras forms two Frobenius algebras. Here we take the opposite approach, and show that interacting Frobenius algebras form Hopf algebras. We generalise (BSZ 2014) by including non-trivial dynamics of the underlying object---the so-called phase group---and investigate the effects of finite dimensionality of the underlying model. We recover the system of Bonchi et al as a subtheory in the prime power dimensional case, but the more general theory does not arise from a distributive law.<< Hide abstract
Mariam Gachechialdze, Nikoloz Tsimakuridze, Costantino Budroni and Otfried Guehne
Hypergraph states, their entanglement and robustness properties PDF
Abstract: We study nonlocal properties of hypergraph states, or nonlocal stabilizer states, which are generalisations of well-known graph states. We find that some families of hypergraph states violate local realism exponentially like GHZ states, but are more robust than their graph-state analogues. We give applications in quantum metrology and measurement-based quantum computation. Additionally, we extend the rule of local complementation for characterizing unitaries transformations. Finally, we discuss the computational complexity of stabilizing group of hypergraph states in the framework of monomial stabilizer formalism.<< Hide abstract
A Generalised Quantifier Theory of Natural Language in Categorical Compositional Distributional Semantics with Bialgebras PDF
Abstract: Categorical compositional distributional semantics is a model of natural language; it combines the statistical vector space models of words with the compositional models of grammar. We formalise in this model the generalised quantifier theory of natural language, due to Barwise and Cooper. The underlying setting is a compact closed category with bialgebras. We start from a generative grammar formalisation and develop an abstract categorical compositional semantics for it, then instantiate the abstract setting to sets and relations and to finite dimensional vector spaces and linear maps. We prove the equivalence of the relational instantiation to the truth theoretic semantics of generalized quantifiers. The vector space instantiation formalises the statistical usages of words and enables us to, for the first time, reason about quantified phrases and sentences compositionally in distributional semantics.<< Hide abstract
Ravi Kunjwal and Robert Spekkens
Noncontextuality inequalities for Specker’s compatibility scenario PDF
Abstract: We derive operational noncontextuality inequalities for the simplest compatibility scenario capable of exhibiting contextuality: Specker’s scenario. In doing this, we show how to rehabilitate the so-called "state-dependent" proofs of quantum contextuality to tests of contextuality for arbitrary operational theories. We explicitly take into account the lack of perfect predictability of measurement outcomes in realistic experiments. Too much noise would render these inequalities impossible to violate, unlike the case of Kochen-Specker type inequalities which fail to take noise into account. We also construct a quantum realization of Specker’s scenario and demonstrate a violation of our theory-independent inequality. Specker’s scenario involves three two-outcome measurements that are pairwise jointly measurable but need not be triplewise jointly measurable. It is the minimal scenario in which contextuality with respect to joint measurement contexts can be expected to manifest itself and our analysis provides a robust noncontextuality inequality for this scenario. We also generalize our analysis to arbitrary n-cycle scenarios.<< Hide abstract
Ciaran Lee and John Selby
Grover's search and higher-order interference PDF
Abstract: Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all classical search algorithms. Quantum interference between computational paths has been posited as the key resource behind this computational speed-up. However, there is a limit to this interference---at most pairs of paths can ever interact in a fundamental way. Sorkin has defined a hierarchy of possible interference behaviours---currently under experimental investigation---where classical theory is at the first level of the hierarchy and quantum theory belongs to the second. Informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In this work, we consider how Grover's speed-up depends on the order of interference of a theory. Surprisingly, we show that the quadratic lower bound holds regardless of the order of interference. Thus, at least from the point of view of the search problem, post-quantum interference does not imply a computational speed-up over quantum theory.<< Hide abstract
Operational meanings of orders of observables defined through quantum set theories with different conditionals PDF
Abstract: In quantum logic there is well-known arbitrariness in choosing a binary operation for conditional. Currently, we have at least three candidates, called the Sasaki conditional, the contrapositive Sasaki conditional,and the relevance conditional. A fundamental problem is to show how the form of the conditional follows from an analysis of operational concepts in quantum theory. Here, we attempt such an analysis through quantum set theory (QST).In this paper, we develop quantum set theory based on quantum logics with those three conditionals, each of which defines different quantum logical truthvalue assignment. We show that those three models satisfy the transfer principle of the same form to determine the quantum logical truth values of theorems of the ZFC set theory.We also show that the reals in the model and the truth values of their equality are the same for those models.Interestingly, however, the order relation between quantum reals significantly depends on the underlying conditionals. We characterize the operational meanings of those order relations in terms of joint probability obtained by the successive projective measurements of arbitrary two observables.Those characterizations clearly show their individual features and will play a fundamental role in future applications to quantum physics.<< Hide abstract
Dusko Pavlovic and Peter-Michael Seidel
(Modular) effect algebras are equivalent to (Frobenius) antispecial algebras PDF
Abstract: Effect algebras are one of the generalizations of Boolean algebras proposed in the quest for a *quantum logic*. Frobenius algebras are a tool of *categorical quantum mechanics*, used to present various families of observables in abstract, often nonstandard frameworks. Both effect algebras and Frobenius algebras capture their respective fragments of quantum mechanics by elegant and succinct axioms; and both come with their conceptual mysteries. A particularly elegant and mysterious constraint, imposed on Frobenius algebras to characterize a class of tripartite entangled states, is the *antispecial* law. A particularly contentious issue on the quantum logic side is the *modularity* law, proposed by von Neumann to mitigate the failure of distributivity of quantum logical connectives. We show that, if quantum logic and categorical quantum mechanics are formalized in the same framework, then the antispecial law corresponds in effect algebras to the natural requirement that the units are each other's single complements; and that the modularity law corresponds to the Frobenius condition. These correspondences lead to the equivalence announced in the title. Aligning the two formalisms, at the very least, sheds new light on the concepts that are more clearly displayed on one side than on the other (such as e.g. orthogonality). Beyond that, it may also open up new approaches to deep and important problems of quantum mechanics (such as the classification of complementary observables).<< Hide abstract
Robert Raussendorf.
Cohomological framework for contextual quantum computations PDF
Abstract: We present a cohomological formulation of measurement-based quantum computation (MBQC), the central object of which is a phase function. The phase function describes symmetries of the resource state of the MBQC, specifies the computational output, and acts as a contextuality witness. It is also a topological object, namely a 1-cocycle in group cohomology. Non-triviality of the cocycles reveals the presence of contextuality, and is a precondition for quantum speedup.<< Hide abstract
Infinite-dimensionality in quantum foundations: W*-algebras as presheaves over matrix algebras PDF
Abstract: In this paper, W*-algebras are presented as canonical colimits of diagrams of matrix algebras and completely positive maps. In other words, matrix algebras are dense in W*-algebras.<< Hide abstract
Cohomology of effect algebras PDF
Abstract: We will define cohomology groups of effect algebras, which occur in the algebraic study of quantum logic. Our definition is based on Connes' cyclic cohomology. The resulting cohomology groups are related to the state space of the effect algebra, and can be computed using variations on the Kunneth and Mayer-Vietoris sequences. Using a slightly different version of the definition, we obtain applications to no-go theorems in quantum foundations, such as Bell's theorem.<< Hide abstract
Ana Belén Sainz, Nicolas Brunner, Daniel Cavalcanti, Paul Skrzypczyk and Tamás Vértesi.
Postquantum Steering PDF
Abstract: The discovery of postquantum nonlocality, i.e. the existence of nonlocal correlations stronger than any quantum correlations but nevertheless consistent with the no-signaling principle, has deepened our understanding of the foundations quantum theory. In this work, we investigate whether the phenomenon of Einstein-Podolsky-Rosen steering, a different form of quantum nonlocality, can also be generalized beyond quantum theory. While postquantum steering does not exist in the bipartite case, we prove its existence in the case of three observers. Importantly, we show that postquantum steering is a genuinely new phenomenon, fundamentally different from postquantum nonlocality. Our results provide new insight into the nonlocal correlations of multipartite quantum systems. << Hide abstract
Dominic Verdon and Jamie Vicary
Tight reference frame--independent quantum teleportation PDF
Abstract: We give a tight scheme for teleporting a quantum state between two parties, whose reference frames are misaligned by some action of a finite symmetry group, satisfying a certain property. Unlike previously proposed schemes, ours requires no additional tokens or data to be passed between the participants; the same amount of classical information is transferred as for ordinary quantum teleportation, and the Hilbert space of the entangled resource is of the same size. Using the terminology of Peres and Scudo, the key idea is that the classical channel conveys unspeakable information.<< Hide abstract
Paschke Dilations PDF
Abstract: In 1973 Paschke defined a factorization for completely positive maps between C*-algebras. In this paper we show that for normal maps between von Neumann algebras, this factorization has a universal property, and coincides with Stinespring's dilation for normal maps into B(H).<< Hide abstract
Alexander Wilce.
A Royal Road to Quantum Theory (or thereabouts) PDF
Abstract: This paper fails to derive quantum mechanics from a few simple postulates. But it gets very close --- and it does so without much exertion. More exactly, I obtain a representation of finite-dimensional probabilistic systems in terms of formally real (equivalently, euclidean) Jordan algebras, in a strikingly easy way, from simple assumptions. This provides a framework within which real, complex and quaternionic QM can play happily together, and allows some --- but not too much --- room for more exotic alternatives.
This is based on earlier work (arXiv:1206:2897), but the development here is further simplified, and also extended in several ways. Starting with a finite-dimensional, uniform probabilistic model (a set of tests of uniform, finite cardinality, and a convex, finite-dimensional state space), I show that the existence of a weak form of spectral decomposition for states, plus the existence of a "conjugate" system, perfectly correlated with the original system by means of an analogue of the maximally entangled EPR state, suffices to obtain the self-duality of the system's state space.
The spectrality assumption can be motivated in two ways. One involves the dilation of states, not to pure bipartite states (as in the Pavia approach), but rather, to bipartite states {\em correlating} a test on the given system with a test on an ancilla system. This is natural if we wish to use the ancilla system as a recording device. The other asks for the preparability of states by means of certain processes I call "reversible filters", generalizing invertible pure CP maps. In fact, given spectrality, the mere existence of a large collection of such reversible filters is enough to make the interior of the cone generated by the states homogeneous. The formally real Jordan structure then follows from the Koecher-Vinberg Theorem. Conversely, formally real Jordan algebras satisfy, and hence, are characterized by, these assumptions.
I also discuss the possibilities for organizing probabilistic models, subject to the assumptions discussed here, into symmetric monoidal categories, showing that such a category will automatically have a dagger-compact structure. (Recent joint work with Howard Barnum and Matthew Graydon (arXiv:1507.06278) exhibits several categories of this
kind.) An interesting open question is whether, conversely, a dagger-compact category of finite-dimensional probabilistic models must be a category of euclidean Jordan algebras. << Hide abstract

Short Talks

Alastair A. Abbott and Cyril Branciard
Noise and Disturbance for Qubit Measurements: An Information-Theoretic Characterisation PDF
Abstract: Information-theoretic definitions for the noise associated with a quantum measurement and the corresponding disturbance to the state of the system have recently been introduced. These definitions, unlike more traditional ones, are invariant under relabelling of measurement outcomes, and lend themselves readily to the formulation of state-independent uncertainty relations both for the joint-estimate of observables (noise-noise relations) and the noise-disturbance tradeoff. In this contribution we derive such relations, which we prove to be tight, for complementary qubit observables. We show that the set of obtainable noise-noise values for such observables is convex, whereas the set of obtainable noise-disturbance values is not; in fact, the former is the convex-hull of the later. In doing so, we show that projective measurements can saturate the noise-disturbance uncertainty relation and are thus optimal, but are not so for joint-estimates of such complementary qubit observables where positive-operator valued measures (POVMs) with more than 2 outcomes can provide better joint-estimates.<< Hide abstract
Desislava Bankova, Bob Coecke, Martha Lewis and Dan Marsden
Graded Entailment for Compositional Distributional Semantics PDF
Abstract: 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 words. However, until recently it has lacked the crucial feature of lexical entailment. We propose a graded measure of entailment, exploiting ideas from partial knowledge in quantum computation. 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. This is an abstract of the paper Graded Entailment for Compositional Distributional Semantics, available at http://arxiv.org/abs/1601.04908. << Hide abstract
Bob Coecke and Aleks Kissinger.
Generalised no-broadcasting for process theories PDF
Abstract: The no-broadcasting theorem theorem states that there exists no quantum process that enables universal broadcasting. It has been generalised within the context of generalised probabilistic theories. Here, we generalise it within the context of process theories.<< Hide abstract
Ivan Contreras and Ali Duman
Geometric Quantization and Epistemically Restricted Theories PDF
Abstract: A large part of operational quantum mechanics can be reproduced from a classical statistical theory with a restriction which implies a limit on the amount of knowledge that an agent can have about an individual system. These epistemic restrictions have recently been restated via the symplectic structure of the underlying classical theory. Starting with this symplectic framework, we obtain -algebraic formulation for the epistemically restricted theories. In the case of continuous variables, the groupoid quantization recipe of E. Hawkins provides us a twisted group C*-algebra which is the usual Moyal quantization of a Poisson vector space. << Hide abstract
Leonardo Disilvestro and Damian Markham
Quantum Protocols within Spekkens' Toy Model PDF
Abstract: Quantum theory is believed to provide improvements both in computational power and security with respect to classical information theory. In order to better understand the origin of these improvements, we translate emblematic quantum protocols to Spekkens' toy model - a local hidden variable theory which is phenomenologically very close to quantum theory. Despite the toy model non being able to provide any computational speed up with respect to quantum theory, we see that it can still provide similar security statements as in the quantum case. We notice how the existence of anticommutation relations between toy measurements and toy transformations and the existence of `toy purifications' seems to be sufficient to implement many quantum protocols within the toy model. In particular, we show that error correction, secret sharing, and blind and verified computation are indeed possible in the toy model along with providing a proof of the impossibility of toy-bit commitment. Our results firstly suggest that purifications and anticommutaiton relations provide the structure behind the existence of these protocols within quantum theory; and secondly, the ability to perform blind and verified computation in the toy model strongly suggest that not only steering is a sufficient property for such a protocol, but that any probabilistic theory featuring purification is indeed apt to implement blind and verified computation.<< Hide abstract
Alexandru Gheorghiu, Petros Wallden and Elham Kashefi
Rigidity of quantum steering and one-sided device-independent verifiable quantum computation PDF
Abstract: The relationship between correlations and entanglement has played a major role in understanding quantum theory since the work of Einstein, Podolsky and Rosen (1935). Tsirelson (1980) proved that Bell states, shared among two parties, when measured suitably, achieve the maximum non-local correlations allowed by quantum mechanics. Conversely, Reichardt, Unger and Vazirani (2013) showed that observing the maximal correlation value over a sequence of repeated measurements, implies that the underlying quantum state is close to a tensor product of maximally entangled states and, moreover, that it is measured according to an ideal strategy. However, this strong rigidity result comes at a high price, requiring a large number of entangled pairs to be tested. In this paper, we present a significant improvement in terms of the overhead by instead considering quantum steering where the device of the one side is trusted. We first demonstrate a robust one-sided device-independent version of self-testing, which characterises the shared state and measurement operators of two parties up to a certain bound. We show that this bound is optimal up to constant factors and we generalise the results for the most general attacks. This leads us to a rigidity theorem for maximal steering correlations. As a key application we give a one-sided device-independent protocol for verifiable delegated quantum computation, and compare it to other existing protocols, to highlight the cost of trust assumptions. Finally, we show that under reasonable assumptions, the states shared in order to run a certain type of verification protocol must be unitarily equivalent to perfect Bell states.<< Hide abstract
A topological perspective on interacting algebraic theories PDF
Abstract: Techniques from higher categories and higher-dimensional rewriting are becoming increasingly important for understanding the finer, computational properties of higher algebraic theories that arise, among other fields, in quantum computation. These theories have often the property of containing simpler sub-theories, whose interaction is regulated in a limited number of ways, which reveals a topological substrate when pictured by string diagrams. By exploring the double nature of computads as presentations of higher algebraic theories, and combinatorial descriptions of "directed spaces", we develop a basic language of directed topology for the compositional study of algebraic theories. We present constructions of computads, all with clear analogues in standard topology, that capture in great generality such notions as homomorphisms and actions, and the interactions of monoids and comonoids that lead to the theory of Frobenius algebras and of bialgebras. After a number of examples, we describe how a fragment of the ZX calculus, the theory of interacting bialgebras, can be reconstructed in this framework.<< Hide abstract
Stefano Gogioso and Fabrizio Genovese
Infinite-dimensional Categorical Quantum Mechanics PDF
Abstract: We use non-standard analysis to define a category *Hilb suitable for categorical quantum mechanics in separable Hilbert spaces, and we show that standard bounded operators can be suitably embedded in it. We show the existence of unital special commutative †-Frobenius algebras, and we conclude *Hilb to be compact closed, with partial traces and a Hilbert-Schmidt inner product on morphisms. We apply our techniques to the case of 1-dimensional wavefunctions with periodic boundary conditions: we show the momentum and position observables to be well defined, and to give rise to a strongly complementary pair of unital commutative †-Frobenius algebras. The techniques are readily extended to the general case of particles on flat spaces (admitting an abelian translation group) which are either compact or discrete.<< Hide abstract
Aleks Kissinger and Sander Uijlen.
Picturing Indefinite Causal Structure PDF
Abstract: Following on from the abstract presentation of a `causal process' (which concretely captures the property of a CP-map being trace-preserving), we give a characterisaton for the most general kind of map which sends causal processes to causal processes. These new, second-order causal processes enable us to treat the input processes as `local laboratories' whose causal ordering needs not be fixed in advance. This enables us to study situations where such local labs do not have a causal order fixed in advance. Using this new characterisation, we give a fully-diagrammatic proof of a non-trivial theorem: namely that being causality-preserving on seperable processes implies being causality-preserving on strongly non-signalling bipartite processes. << Hide abstract
Dan Marsden.
Ambiguity and Incomplete Information in Categorical Models of Language PDF
Abstract: We investigate notions of ambiguity and partial information in categorical distributional models of natural language. Probabilistic ambiguity has previously been studied by Piedeleu, Kartsaklis, Coecke and Sadrzadeh using Selinger's CPM construction. This construction works well for models built upon vector spaces, as has been shown in quantum computational applications. Unfortunately, it doesn't seem to provide a satisfactory method for introducing mixing in other compact closed categories such as the category of sets and binary relations. We therefore lack a uniform strategy for extending a category to model imprecise linguistic information.
In this work we adopt a different approach. We analyze different forms of ambiguous and incomplete information, both with and without quantitative probabilistic data. Each scheme then corresponds to a suitable enrichment of the category in which we model language. We view different monads as encapsulating the informational behaviour of interest, by analogy with their use in modelling side effects in computation. Previous results of Jacobs then allow us to systematically construct suitable bases for enrichment. We show that we can freely enrich arbitrary dagger compact closed categories in order to capture all the phenomena of interest, whilst retaining the important dagger compact closed structure. This allows us to construct a model with real convex combination of binary relations that makes non-trivial use of the scalars. Finally we relate our various different enrichments, showing that finite subconvex algebra enrichment covers all the effects under consideration.<< Hide abstract
Benjamin Musto.
Constructing mutually unbiased bases from quantum Latin squares PDF
Abstract: We introduce orthogonal quantum Latin squares, which restrict to traditional orthogonal Latin squares, and investigate their application in quantum information science. We use quantum Latin squares to build maximally entangled bases, and show how a pair of mutually unbiased maximally entangled bases can be constructed in square dimension from orthogonal quantum Latin squares. We also compare our construction to an existing construction due to Beth and Wocjan and show that ours is strictly more general.<< Hide abstract
Operational Theories of Physics as Categories PDF
Abstract: We introduce a new approach to the study of operational theories of physics using category theory. We define a generalisation of the (causal) operational-probabilistic theories of Chiribella et al. and establish their correspondence with our new notion of an operational category. Our work is based on effectus theory, a recently developed area of categorical logic, to which we give an operational interpretation, demonstrating its relevance to the modelling of general probabilistic theories.<< Hide abstract
Quantum Programs as Kleisli Maps PDF
Abstract: Furber and Jacobs have shown in their study of quantum computation that the category of commutative C*-algebras and PU-maps (positive linear maps which preserve the unit) is isomorphic to the Kleisli category of a comonad on the category of commutative C*-algebras with MIU-maps (linear maps which preserve multiplication, involution and unit). In this paper, we prove a non-commutative variant of this result: the category of C*-algebras and PU-maps is isomorphic to the Kleisli category of a comonad on the subcategory of MIU-maps. A variation on this result has been used to construct a model of Selinger and Valiron’s quantum lambda calculus using von Neumann algebras. << Hide abstract