Talks

We define a map from an arbitrary quantum circuit to a local Hamiltonian whose ground state encodes the quantum computation. All previous maps relied on the Feynman-Kitaev construction, which introduces an ancillary ‘clock register’ to track the computational steps. Our construction, on the other hand, relies on injective tensor networks with associated parent Hamiltonians, avoiding the introduction of a clock register. This comes at the cost of the ground state containing only a noisy version of the quantum computation, with independent stochastic noise. We can remedy this - making our construction robust - by using quantum fault tolerance. In addition to the stochastic noise, we show that any state with energy density exponentially small in the circuit depth encodes a noisy version of the quantum computation with adversarial noise. We also show that any ‘combinatorial state’ with energy density polynomially small in depth encodes the quantum computation with adversarial noise. This serves as evidence that any state with energy density polynomially small in depth has a similar property. As an application, we give a new proof of the QMA-completeness of the local Hamiltonian problem (with logarithmic locality) and show that contracting injective tensor networks to additive error is BQP- hard. We also discuss the implication of our construction to the quantum PCP conjecture, combining with an observation that QMA verification can be done in logarithmic depth. Based on joint work with Anurag Anshu and Nikolas P. Breuckmann. (https://arxiv.org/abs/2309.16475)

---

Zoom link

Self-organised phenomena are widespread in Nature and have been studied for long time in variousdomains, physics, chemistry, biology, ecology, neurophysiology, to name a few [1]. Despite the richliterature on the subject, there is still need for understanding, analysing and predicting theiremergent behaviours.Patterns are commonly based on local interaction rules that determine the creation and destructionof the entities, species, at spatial locations, upon which the action of a diffusion process determinesthe migration of the species. For this reason reaction-diffusion systems are a common frameworkfor modelling such systems [2].In 50’s A. Turing wrote a pioneer article where he considered a two-species model ofmorphogenesis [3]. For the first time, he established the conditions for a stable spatiallyhomogeneous state, to migrate towards a new heterogeneous, spatially patched, equilibrium underthe driving effect of diffusion, at odd with the idea that diffusion is a source of homogeneity. Eventhough the explanation for morphogenesis has evolved and now relies more on geneticprogramming, many actual results are grounded on this pioneering work. Nowadays, Turing instability goes beyond this initial framework and it can be used to explain emergence of self-organised collective patterns. The geometry of the underlying support where the reaction-diffusion acts, plays a relevant role inthe patterned outcome, it can be because of the non flat geometry [4] (possibly growing) [5] orbecause of its anisotropy [6]. In several applications the underlying domain can be supposed to bedivided into local patches where reactions occurs and diffusion across patches is realised via the links existing among the latter; this framework leads naturally to the introduction of reaction-diffusion systems defined on complex networks [7]. The aim of this talk is to introduce some of the recent developments we obtained with mycollaborators concerning the emergence of Turing patterns on complex networks and theirgeneralisation, such as multiplex [8, 9], time varying networks [10,11], or higher-order structuressuch as hypergraphs [12,13] or simplicial complexes [14].