Gilles Dowek - Quantitative informational aspects in discrete physics
Joint work with Pablo Arrighi
Discrete physics investigates the hypothesis that natural phenomena
can be described using finite mathematics only. This hypothesis has a
deep connection with another: that the density of information in
nature is bounded. In this talk, I will discuss whether it is possible
to measure the complexity of physical phenomena by the amount of
information their description requires, focusing on three examples:
free fall according to Newtonian physics, to Special Relativity and to
Pablo Arrighi - Discrete Lorentz covariance for quantum walks and quantum cellular automata
Joint work with Stefano Facchini and Marcelo Forets
We formalize a notion of discrete Lorentz transforms for Quantum Walks (QW) and Quantum Cellular Automata (QCA), in (1 + 1)-dimensional discrete spacetime. The theory admits a diagrammatic representation in terms of a few local, circuit equivalence rules. Within this framework, we show the first-order-only covariance of the Dirac QW. We then introduce the Clock QW and the Clock QCA, and prove that they are exactly discrete Lorentz covariant. The theory also allows for non-homogeneous Lorentz transforms, between non-inertial frames.
Christian De Ronde - On the physical foundation of quantum superpositions (beyond measurement outcomes and mathematical structures)
Quantum superpositions are being used today in laboratories all around the world in order to create the most outstanding technological and experimental developments of the last centuries. However, while many experimentalists are showing that Schroedinger's cats are growing fat, while it becomes more and more clear that quantum superpositions are telling us something about quantum physical reality even at the macroscopic scale, philosophers of QM in charge of analyzing and interpreting these mathematical expressions (through the many interpretations of QM that can be found in the literature) have not been capable of providing a coherent physical representation of them. In this paper we attempt to discuss the importance of providing a physical representation of quantum superpositions that goes beyond the mere reference to mathematical structures and measurement outcomes.
Simon Martiel - Quantum causal graph dynamics
Joint work with Pablo Arrighi
Consider a graph having quantum systems lying at each node. Suppose that the whole thing evolves in discrete time steps, according to a global, unitary causal operator. By causal we mean that information can only propagate at a bounded speed, with respect to the distance given by the graph. Suppose, moreover, that the graph itself is subject to the evolution, and may be driven to be in a quantum superposition of graphs---in accordance to the superposition principle. We show that these unitary causal operators must decompose as a finite-depth circuit of local unitary gates. This unifies a result on Quantum Cellular Automata with another on Reversible Causal Graph Dynamics. Along the way we formalize a notion of causality which is valid in the context of quantum superpositions of time-varying graphs, and has a number of good properties. Keywords: Quantum Lattice Gas Automata, Block-representation, Curtis-Hedlund-Lyndon, No-signalling, Localizability, Quantum Gravity, Quantum Graphity, Causal Dynamical Triangulations, Spin Networks, Dynamical networks, Graph Rewriting.
Stefano Facchini - Quantum walking in curved spacetime: (3+1) dimensions, and beyond
Joint work with Pablo Arrighi
A discrete-time Quantum Walk (QW) is essentially an operator driving the evolution of a single particle on the lattice, through local unitaries. Some QWs admit a continuum limit, leading to familiar PDEs (e.g. the Dirac equation). Recently it was discovered that prior grouping and encoding allows for more general continuum limit equations (e.g. the Dirac equation in (1+1) curved spacetime). In this paper, we extend these results to arbitrary space dimension and internal degree of freedom. We recover an entire class of PDEs encompassing the massive Dirac equation in (3+1) curved spacetime. This means that the metric field can be represented by a field of local unitaries over a lattice.
Juliana Kaizer Vizzotto - (Videoconference) A double effect lambda-calculus for quantum computation
In this talk we present a double effect version of the simply
typed lambda-calculus in which we can represent both pure and impure quantum computations.
The double effect calculus comprises a quantum arrow layer defined over a quantum monadic layer.
Technically, we propose a new construct in the calculus (and equations) that allows the communication
of the monadic layer with the arrow layer of the calculus. That is, the quantum
arrow is defined over a monadic instance, enabling to consider both pure and impure quantum
computations in the same framework. As a practical contribution, the calculus allows to
express quantum algorithms including reversible operations over pure states and measurements in the middle of
the computation using a traditional style of functional programming and reasoning.
We also define equations for algebraic reasoning of computations involving measurements.
Benoît Valiron - A geometry of interaction for quantum computation
We introduce a Geometry of Interaction model for higher-order quantum
computation, and prove adequacy for a full quantum programming
language in which entanglement, duplication, and recursion are all
available. Our model comes with a multi-token machine, a proof-net
system, and a PCF-style language. It is parametric on an algebraic
notion of memory. This way, it can model quantum, but also classical
and purely probabilistic computations. Being based on a multi-token
machine associated to a memory, our model has a concrete nature which
makes it well suited to build low-level operational descriptions of
Alejandro Díaz-Caro - Typing quantum superpositions and projective measurements
Joint work with Gilles Dowek
We study a purely functional quantum extension of lambda calculus, that is, an extension of lambda calculus to express some quantum features, where the quantum memory is abstracted out. This calculus is a typed extension of the first-order linear-algebraic lambda-calculus. The type is linear on superpositions, so to forbid from cloning them, while allows to clone basis vectors.
Gabriel Senno - Robust Bell inequalities from communication complexity
Joint work with Sophie Laplante, Mathieu Laurière, Alexandre Nolin and Jérémie Roland
We contribute to the study of the relationship between nonlocality and the advantage that quantum mechanics offers in communication complexity by showing how to obtain large Bell violations for quantum distributions, from any gap between quantum communication complexity and the classical partition bound. This applies to most of the usually studied functions (Disjointness, Vector in Subspace, Tribes, etc). The violations obtainable from our construction are resistant to the detection loophole and, at the expense of an increase in the number of outputs, can be also made resistant to uniform noise.
Ariel Bendersky - Non-signaling deterministic models for non-local correlations have to be uncomputable
Joint work with Gabriel Senno, Gonzalo de la Torre, Santiago Figueira and Antonio Acin
Quantum mechanics postulates random outcomes. However, a model making the same output predictions but in a deterministic manner would be, in principle, experimentally indistinguishable from quantum theory. In this work we consider such models in the context of non-locality on a device independent scenario. That is, we study pairs of non-local boxes that produce their outputs deterministically. It is known that, for these boxes to be non-local, at least one of the boxes' output has to depend on the other party's input via some kind of hidden signaling. We prove that, if the deterministic mechanism is also algorithmic, there is a protocol which, with the sole knowledge of any upper bound on the time complexity of such algorithm, extracts that hidden signaling and uses it for the communication of information.
Renaud Vilmart - Completeness and Incompleteness of the ZX-Calculus, a diagrammatic language for quantum reasoning and computing
Joint work with Emmanuel Jeandel, Simon Perdrix and Quanlong Wang
The ZX-Calculus introduced by Bob Coecke and Ross Duncan is a diagrammatic language for quantum reasoning, and can in fact be seen as a generalisation of quantum circuitry. It is universal, and comes with a set of transformation rules that preserve the represented matrix. The stabiliser and real stabiliser quantum mechanics can be represented in the language, and they have been proven to be complete. The Clifford+T group is also expressible in the language, but its completeness in general is an open question, though it has been proven for a single qubit. Recently, a rule called supplementarity has been introduced and it has been proven it could not be derived from the others in the Clifford+T group. We can show that the restriction of the language to the Clifford+T is still not complete by introducing yet another rule. This one in addition with the supplementarity makes two other rules derivable. Moreover, we can shown that the supplementarity can be generalised to any natural number, and that it is not derivable in an infinite number of fragments.
José Carlos Puiati - (Videoconference) Implementation of an interpreter and typechecker for the double effect quantum lambda calculus