Published: 2nd July 2018
DOI: 10.4204/EPTCS.273
ISSN: 2075-2180

EPTCS 273

Proceedings of the 9th International Workshop on
Physics and Computation
Fontainebleau, France, 26 June 2018

Edited by: Michael Cuffaro and Philippos Papayannopoulos

Preface
A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing—Abridged Version
Alastair A. Abbott, Cristian S. Calude, Michael J. Dinneen and Richard Hua
1
One-Sided Device-Independent Certification of Unbounded Random Numbers
Brian Coyle, Matty J. Hoban and Elham Kashefi
14
Objective and Subjective Solomonoff Probabilities in Quantum Mechanics
Allan F. Randall
27
An Atemporal Model of Physical Complexity
Richard Whyman
39

Preface

This volume constitutes the proceedings of the 9th International Workshop on Physics and Computation (PC 2018). The workshop was held on the 26th of June 2018 in Fontainebleau, France, as a satellite workshop of the 17th International Conference on Unconventional Computation and Natural Computation (UCNC 2018). Previous workshops in the series were held in Vienna (2008), the Azores (2009), on the Nile River in Egypt (2010), Turku (2011), Swansea (2012), Auckland (2015), Manchester (2016), and Fayetteville (2017).

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, to 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: axiomatisations of physics, dynamical systems, hypercomputation, molecular computation and reaction-diffusion models, multiple-substrate computation, novel models of computation, philosophy of physics and computation, the (physical) Church-Turing thesis, quantum computation and information, quantum logics, physics and computational complexity, randomness (quantum, dynamical, and physical randomness), relativistic computation, the theory of measurement (axiomatisation, complexity), and the thermodynamics of computation.

Submissions to the workshop were each blind-reviewed by two members of the programme committee, who selected six papers for presentation at the conference. This volume contains revised versions of four 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 2018, the PC workshop coincided with the publication of the interdisciplinary volume by Cambridge University Press entitled: Physical Perspectives on Computation, Computational Perspectives on Physics (Michael E. Cuffaro and Samuel C. Fletcher, eds.). In addition to the contributions appearing in this volume, two of the aforementioned volume's contributors, Judit X. Madarász (Alfréd Rényi Institute of Mathematics) and Oron Shagrir (The Hebrew University of Jerusalem), were invited to give lectures.

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 2018 for inviting us to hold this workshop in conjunction with the conference and for handling the local logistics.

June 2018,

Michael Cuffaro and Philippos Papayannopoulos

Programme Committee: