February 2021

Research on indefinite causal structures is a rapidly evolving field that has a potential not only to make a radical revision of the classical understanding of space-time but also to achieve enhanced functionalities of quantum information processing. For example, it is known that indefinite causal structures provide exponential advantage in communication complexity when compared to causal protocols. In quantum computation, such structures can decide whether two unitary gates commute or anticommute with a single call to each gate, which is impossible with conventional (causal) quantum algorithms. A generalization of this effect to $n$ unitary gates, originally introduced in M. Ara’ujo et al., Phys. Rev. Lett. 113, 250402 (2014) and often called Fourier promise problem (FPP), can be solved with the quantum-$n$-switch and a single call to each gate, while the best known causal algorithm so far calls $O(n^2)$ gates. In this work, we show that this advantage is smaller than expected. In fact, we present a causal algorithm that solves the only known specific FPP with $O(n log(n))$ queries and a causal algorithm that solves every FPP with $O(nsqrt{n})$ queries. Besides the interest in such algorithms on their own, our results limit the expected advantage of indefinite causal structures for these problems.

Recently, Vedral and one of us proposed an entanglement-based witness of non-classicality in systems that need not obey quantum theory, based on constructor-information-theoretic ideas, which offers a robust foundation for recently proposed table-top tests of non-classicality in gravity. The witness asserts that if a mediator can entangle locally two quantum systems, then it has to be non-classical. Hall and Reginatto claimed that there are classical systems that can entangle two quantum systems, thus violating our proposed witness. Here we refute that claim, explaining that the counterexample proposed by Hall and Reginatto in fact validates the witness, vindicating the witness of non-classicality in its full generality.

Gauge symmetries play a fundamental role in Physics, as they provide a mathematical justification for the fundamental forces. Usually, one starts from a non-interactive theory which governs `matter’, and features a global symmetry. One then extends the theory so as make the global symmetry into a local one (a.k.a gauge-invariance). We formalise a discrete counterpart of this process, known as gauge extension, within the Computer Science framework of Cellular Automata (CA). We prove that the CA which admit a relative gauge extension are exactly the globally symmetric ones (a.k.a the colour-blind). We prove that any CA admits a non-relative gauge extension. Both constructions yield universal gauge-invariant CA, but the latter allows for a first example where the gauge extension mediates interactions within the initial CA.

In this paper, we continue the analysis of the effective model of quantum Schwarzschild black holes recently proposed by some of the authors in [1,2]. In the resulting spacetime the central singularity is resolved by a black-to-white hole bounce, quantum effects become relevant at a unique mass independent curvature scale, while they become negligible in the low curvature region near the horizon and classical geometry is approached asymptotically. This is the case independently of the relation between the black and white hole masses, which are thus freely specifiable independent observables. A natural question then arises about the phenomenological implications of the resulting non-singular effective spacetime and whether some specific relation between the masses can be singled out from a phenomenological perspective. Here we focus on the thermodynamic properties of the effective polymer black hole and analyse the corresponding quantum corrections as functions of black and white hole masses. The study of the relevant thermodynamic quantities such as temperature, specific heat and horizon entropy reveals that the effective spacetime generically admits an extremal minimal-sized configuration of quantum-gravitational nature characterised by vanishing temperature and entropy. For large masses, the classically expected results are recovered at leading order and quantum corrections are negligible, thus providing us with a further consistency check of the model. The explicit form of the corrections depends on the specific relation among the masses. In particular, a first-order logarithmic correction to the entropy is obtained for a quadratic mass relation. The latter corresponds to the case of proper finite length effects which turn out to be compatible with a minimal length generalised uncertainty principle associated with an extremal Planck-sized black hole.