Search Talks

Cellular automata are a central notion for the formulation of physical laws in an abstract information-theoretical scenario, and lead in recent years to the reconstruction of free relativistic quantum field theory. In this talk we extend the notion of a Quantum Cellular Automaton to general Operational Probabilistic Theories. For this purpose, we construct infinite composite systems, illustrating the main features of their states, effects and transformations. We discuss the generalization of the concepts of homogeneity and locality, in an framework where space-time is not a primitive object. We show that homogeneity leads to a Cayley graph structure of the memory array, thus proving the universality of the connection between homogeneity and discrete groups. We conclude illustrating the special case of Fermionic cellular automata, discussing three relevant examples: Weyl and Dirac quantum walks, the Thirring automaton and the simplest families of automata on finite graphs.

I’ll describe a novel application for near-term quantum computers with 50-70 qubits: namely, generating cryptographic random bits, whose randomness can be certified even if the quantum computer is untrusted (e.g., has been backdoored by an adversary).  Unlike schemes based on Bell inequality violation, ours requires only a single device able to solve classically hard sampling problems.  Our protocol harvests the outputs of the sampling process and feeds them into a randomness extractor, while occasionally verifying the outputs using exponential classical time.  I’ll also compare to the beautiful independent work of Brakerski et al., who proposed a scheme for the same problem that has much more efficient verification, but that probably can’t be implemented on near-term devices.  Paper still in preparation.