Scientific Series

The Church-Turing thesis is one of the pillars of computer science; it postulates that every classical system has equivalent computability power to the so-called Turing machine. While this thesis is crucial for our understanding of computing devices, its implications in other scientific fields have hardly been explored. What if we consider the Church-Turing thesis as a law of nature? In this talk I will present our first results in connection with quantum information theory [1] by showing that computer science laws have profound implications for some of the most fundamental results of quantum theory.  First I will show how they question our knowledge on what a mixed quantum state is, as we identified situations in which ensembles of quantum states defining the same mixed state, indistinguishable according to the quantum postulates, do become distinguishable when prepared by a computer (or any classical system). Then I will introduce a new loophole for Bell-like experiments: if some of the parties in a Bell-like experiment use a computer to decide which measurements to make, then the computational resources of an eavesdropper have to be limited in order to have a proper observation of non-locality.

I will talk about 4d N=2 gauge theories with a co-dimension-two full surface operator, which exhibit a fascinating interplay of supersymmetric gauge theories, equivariant Gromov-Witten theory and geometric representation theory. For pure Yang-Mills and N=2* theory, a full surface operator can be described as the 4d gauge theory coupled to a 2d N=(2,2) gauge theory. By supersymmetric localizations, we present the exact partition functions of both 4d and 2d theories which satisfy integrable equations. In addition, I will show the validity of the orbifold method in one-loop computations when a full surface operator is inserted, and the form of the structure constants with a semi-degenerate field in SL(N,R) WZNW model is predicted from one-loop determinants.

Recent comparison between observation and expectation could point to problems with the standard cold, non-interacting dark matter picture, one of which being how small the smallest gravitationally bound dark matter halos are. I will review the cold dark matter picture and the experimental tests. One solution to the problems comes from coupling the dark matter to neutrinos. I will describe the model building requirements of such a coupling and determine how to test this scenario.

Forthcoming 21cm intensity mapping surveys on the Square Kilometre Array (SKA) will be capable of probing unprecedentedly large volumes of the Universe. This will make it possible to detect effects beyond the matter-radiation equality peak in the power spectrum, including primordial non-Gaussianity, GR corrections, and possible signatures of modified gravity. I give an overview of the proposed SKA intensity mapping surveys, the science that they will be able to do, and some of the challenges that they face.

The study of ground spaces of local Hamiltonians is a fundamental task in condensed matter physics. In terms of computational complexity theory, a common focus in this area has been to estimate a given Hamiltonian’s ground state energy. However, from a physics perspective, it is sometimes more relevant to understand the structure of the ground space itself. In this talk, we pursue the latter direction by introducing the notion of “ground state connectivity” of local Hamiltonians. In particular, we show that determining how “connected” the ground space of a local Hamiltonian is can range from QCMA-complete to NEXP-complete. (Here, QCMA is the same as QMA, but with a classical witness.) As a result, we obtain a natural QCMA-complete problem, a task which has generally proven difficult since the conception of QCMA over a decade ago. 

Moduli fields with Planck suppressed couplings to light species are ubiquitous in string theory and supersymmetry. These scalar fields are expected to dominate the energy budget in the early universe. Their out-of-equilibrium decays can produce dark matter and baryons. Dark matter generated in this non-thermal manner typically has large annihilation rates that are strongly constrained by indirect detection. The resulting bounds on superpartner masses offer dim prospects for collider discovery of supersymmetry. We will discuss extensions of the Minimal Supersymmetric Standard Model (MSSM) that allow low scale supersymmetry accessible by direct searches, while being consistent with astrophysical and cosmological probes. The tension with indirect searches is most easily relieved by allowing the lightest MSSM superpartner to decay into new stable states that play the role of dark matter. We examine the viability of this scenario in models with light Abelian and non-Abelian hidden sectors, and asymmetric dark matter. This latter possibility has a natural connection to theories of baryogenesis.

A quantum isolated horizon can be modeled by an SU(2) Chern-Simons theory on a punctured 2-sphere. We show how a local 2-dimensional conformal symmetry arises at each puncture inducing an infinite set of new observables localized at the horizon which satisfy a Kac-Moody algebra. By means of the isolated horizon boundary conditions, we represent the gravitational fluxes degrees of freedom in terms of the zero modes of the Kac-Moody algebra defined on the boundary of a punctured disk. In this way, our construction encodes a precise notion of CFT/gravity correspondence. The higher modes in the algebra represent new non-geometric charges which can be represented in terms of free matter field degrees of freedom. When computing the CFT partition function of the system, these new states induce an extra degeneracy factor, representing the density of horizon states at a given energy level, which reproduces the Bekenstein's holographic bound for an imaginary Barbero-Immirzi parameter.

A prime challenge to our understanding of galaxy formation concerns the scarcity of dwarf galaxies compared with the numerous low-mass halos expected in the current ΛCDM paradigm. This is usually accounted for by assuming that energetic feedback from evolving stars confines dwarf galaxy formation to relatively massive halos spanning a narrow mass range. I will highlight a number of observations that may be used to test this assumption and discuss the puzzles and challenges that arise from this analysis. I will also discuss a number of challenges that ΛCDM faces on the scale of dwarf galaxies and their possible resolutions.

According to the Newtonian intuition, a constant gravitational field has no physical effect on a system since it can always be redefined, and a homogeneous gradient of the gravitational field (i.e. a homogeneous gravitational force) is equivalent to an accelerated reference frame. I will show how to extend this intuition to cosmological scales; in the presence of a single clock a constant curvature perturbation and its gradient can be set to zero through a coordinate transformation. This allows one to connect the squeezed limit of an $n$-point correlation function of the curvature perturbation to an (n+1)-point correlation function in the limit in which one of the momenta is very small (the so-called squeezed limit). These consistency relations are valid from inflation to the LSS. As an example, I will use them to write down a non-perturbative relativistic relation between galaxy number over-density correlation functions.

Pure states and pure transformations play a crucial role in most of the recent reconstructions of quantum theory. In the frameworks of general probabilistic theories, purity is defined in terms of probabilistic mixtures and bears an intuitive interpretation of ``maximal knowledge" of the state of the system or of the evolution undergone by it.  On the other hand, many quantum features do not need the probabilistic structure of the theory. For example, Schumacher and Westmoreland formulated a toy theory that only specifies which events are possible (without quantifying they probability) and still reproduces a large number of quantum features. In this talk I will provide a probability-free definition of pure states and pure transformations, which can expressed in the categorical framework of process theories developed by Abramsky and Coecke and coincides with the usual notion under standard assumptions. Building on this definition, I will present a probability-free version of the purification principle, which allows one to retrieve a large number of quantum features even in the lack of probabilistic structure. This work is part of a larger programme that aims at drawing the line between those aspects of quantum theory that can be defined solely in terms of operations in a circuit and those that rely on the subjective expectations of an agent.

Related works:  
-GC, Distinguishability and copiability of programs in general process theories, arXiv:1411.3035;  
-Categorical purification, http://www.cs.ox.ac.uk/CQM2014/programme/Giulio.pdf 
-GC, G. M. D'Ariano, and P. Perinotti, Probabilistic theories with purification, Phys. Rev. A 81, 062348 (2010)

In unidirectional communication theory, two of the most prominent problems are those of compressing a source of information and of transmitting data noiselessly over a noisy channel. In 1948, Shannon introduced information theory as a tool to address both of these problems. Since then, information theory has flourished into an important field of its own. It has also been successfully extended to the quantum setting, where it has also served to address questions about quantum source compression and transmission of classical and quantum data over noisy quantum channels.

However, in interactive communication theory, more specifically communication complexity, it is much more recently that tools from information theory have been successfully applied. Indeed, the interactive nature of communication protocols in this setting imposes new constraints and tools specific to this setting need to be developed, both for the interactive analogue of source compression and that of coding for noisy channels. The exciting field of classical interactive information theory has been very active in recent years.

We discuss recent works for its quantum counterpart. In particular, we discuss joint work showing that a constant factor overhead is sufficient for robustly implementing interactive quantum communication over noisy channels [1]. We also discuss work introducing a new notion of quantum information complexity that exactly captures the amortized cost per copy for implementing many copies of a communication task in parallel, such that compressing to this information complexity leads to a bounded-round direct sum theorem [2].

For both of these, we further discuss many interesting potential research directions that follow.

[1] joint work with Gilles Brassard, Ashwin Nayak, Alain Tapp, Falk Unger, QIP’14, FOCS’14 [2] Merge of arXiv:1404.3733 and arXiv:1409.4391, to appear at QIP’15

Quantum many-body systems ranging from a many-electron atom to a solid material are described by effective Hamiltonians which are obtained from more accurate Hamiltonians by neglecting or treating weak interactions perturbatively. Quantum complexity theory asks about the quantum computational power of such quantum many-body models for both practical as well as fundamental purposes. Three distinct computational classes have emerged within this framework: namely (1) classical Hamiltonians such as the Ising model, (2) sign-free or stoquastic Hamiltonians such as the transverse field Ising model, and (3) fully quantum Hamiltonians such as the Heisenberg model. Each class can be characterized by certain prototype universal Hamiltonians which can encode the physics of any other Hamiltonian in that class. We will show how this encoding is established through the use of perturbation theory via perturbative gadgets. We will discuss the technical expression of this classification in terms of the complexity classes NP, Stoquastic MA and QMA and the power of these Hamiltonians for performing quantum adiabatic computation.