UCNC day 4, with an embarrassment of riches in the form of invited talks.
Next was the workshop on Physics and Computation. Gilles Dowek started with an invited talk on “Quantitative Informational Aspects in Discrete Physics”. Gandy has shown that if a system (1) is homogeneous in space and time; (2) has a bounded speed of information transport; (3) has a bounded density of information, then it can be simulated by a cellular automaton. Since physics appears to satisfy these properties, it should be so simulable. Then came a short but necessary digression on Planck’s constant. The physical constant c has the dimensions of a speed, and it is the speed of light. Planck’s constant has the dimension of an action; what action is it? After a bit of discussion, it turns out that it is (a small multiple of) the area of a bit of information (in a particular choice of units where everything has a dimension that is some power of length) as given by the Bekenstein bound. Then Dowek went through how to build a CA in Newtonian physics, special relativity, and general relativity, that models free fall (subject to some assumptions. It can’t be done in Newtonian physics, because there is no bound on speed. In SR it can be done, with particles that contain 320 bits of information (using the Planck area); in GR they only need 168 bits. This is an existence proof, but the CAs defined are not very satisfactory, for several reasons. The task is to do better! Listening to this, I recalled Randal Beer’s Game of Life talk from ALife last week: looking at a CA in terms of processes rather than cells gives a much more natural formulation. I wonder if that would work here?
Then we had a talk about “The Information Content of Systems in General Physics Theories”. The idea here is to look at a broad range of probabilistic theories, of which quantum mechanics is one instance. Investigating their computational complexity of the “advice” given by a physical system can shed light on what makes QM special, different from just a general theory.
After lunch Ana Belén Sainz gave an invited talk on “Postquantum Steering”. This was in the same vein as the previous talk: look at a general theory, then compare with QM. Here the idea was applied to one particular kind of system: how much can Bob “steer” distant Alice’s state, by making measurements on his own state?
Next came some more talks. The first, on “Sequent Calculus Representations for Quantum Circuits”, was an approach to making reasoning about quantum circuits look like proof theoretic reasoning in other branches of computer science, by finding an appropriate set of axioms. Next was a talk on “Physical Computation, P/poly and P/log*”, looking at the computational complexity of physical computing as an unconventional co-processor, in terms of its advice complexity. After coffee we had a talk on “Local Searches Using Quantum Annealers: How to Beat Noise and Take Advantage of the Classical Algorithms we Already Have, or, Modernising Quantum Annealing using Local Search”. This contrasted classical simulated annealing, including its two improvements of parallel tempering and population annealing, with the quantum version: quantum annealing. Each has is strengths and weakeness; here was a suggestion of how to use the quantum annealing as a “subroutine”, getting the best of both approaches. The final workshop talk was on “Quantum Probability as an Application of Data Compression Principles”, a philosophical look at probabilities in general, and branching world probabilities in particular.