Published: 21st June 2016
DOI: 10.4204/EPTCS.214
ISSN: 2075-2180


Proceedings of the 7th International Workshop on
Physics and Computation
Manchester, UK, 14 July 2016

Edited by: Alastair A. Abbott and Dominic C. Horsman

Alastair A. Abbott and Dominic C. Horsman
Invited Presentation: Quantitative Informational Aspects in Discrete Physics
Gilles Dowek
Invited Presentation: Postquantum Steering
Ana Belén Sainz
Sequent Calculus Representations for Quantum Circuits
Cameron Beebe
An Overview of Approaches to Modernize Quantum Annealing Using Local Searches
Nicholas Chancellor
The Information Content of Systems in General Physical Theories
Ciarán M. Lee and Matty J. Hoban
Quantum Probability as an Application of Data Compression Principles
Allan F. Randall
Physical Computation, P/poly and P/log*
Richard Whyman


This volume constitutes the proceedings of the 7th International Workshop on Physics and Computation (PC 2016). The workshop was held on the 14th of July 2016 in Manchester, UK, as a satellite workshop to UCNC 2016, the 15th International Conference on Unconventional Computation and Natural Computation. Previous workshops in the series were held in Vienna (2008), the Azores (2009), on the Nile River in Egypt (2010), Turku (2011), Swansea (2012), and Auckland (2015).

The goal of the workshop series is to bring together researchers working on the interaction between physics and the theory of computation. This intrinsically interdisciplinary domain of research strives to go beyond the traditional use of mathematics as a tool to model and understand the behaviour of physical systems. Instead, it looks to the theory of computation and information to provide new insights into physical systems and processes, and, in turn, how these insights can lead to new methods, models and notions of computation and new approaches to computational and mathematical problems. Topics falling into this category at the interface of physics and computation that are within the scope of the conference include, amongst many others: the axiomatisation of physics, hypercomputation, the role of information in physical systems, quantum information, randomness in physics, theories of measurement, and the philosophy of physics and computation.

Submissions to the workshop were each reviewed by three members of the programme committee, who selected 5 for presentation at the conference, of which 3 were full papers and 2 were extended abstracts. This volume contains revised versions of these original scientific contributions to the conference, and was published prior to the workshop taking place. Following the workshop, authors of selected submissions will be invited to submit extended and revised versions of their contributions to a special issue of the International Journal of Unconventional Computing (IJUC). In addition to the contributions appearing in this volume, two invited lectures were also given at the workshop by Gilles Dowek (INRIA, CNRS and ENS Cachan, France) and Ana Belén Sainz (University of Bristol, UK).

We would like to thank the programme committee for their work in reviewing and selecting the submissions to the workshop, as well as the organisers of UCNC 2016 for inviting us to hold this workshop in conjunction with the conference and for handling the local logistics.

July 2016,
Alastair Abbott and Dominic Horsman.

Programme Committee

Quantitative Informational Aspects in Discrete Physics

Gilles Dowek

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 General Relativity.

Postquantum Steering

Ana Belén Sainz

The discovery of postquantum nonlocality, i.e. the existence of nonlocal correlations stronger than any quantum correlations but nevertheless consistent with the no-signalling 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 generalised 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.