Quantum Physics

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013). Based on: arxiv:2006.12760

In this talk, I will discuss two problems: quantum data compression
and quantum causal order discovery, both for multipartite quantum
systems. For data compression, we model finitely correlated states as
tensor networks, and design quantum compression algorithms. We first
establish an upper bound on the amount of memory needed to store an
arbitrary state from a given state family. The bound is determined by
the minimum cut of a suitable flow network, and is related to the flow
of information from the manifold of parameters that specify the states
to the physical systems in which the states are embodied. We then
provide a compression algorithm for general state families, and show
that the algorithm runs in polynomial time for matrix product states.

For quantum causal order discovery, we develop the first efficient
quantum causal order discovery algorithm with polynomial black-box
queries with respect to the number of systems. We model the causal
order with quantum combs, and our algorithm outputs the order of
inputs and outputs that the given process is compatible with. Our
method guarantees a polynomial running time for quantum combs with a
low Kraus rank, namely processes with low noise and little information
loss. For special cases where the causal order can be inferred from
local observations, we also propose algorithms that have lower query
complexity and only require local state preparation and local
measurements. Our results will provide efficient ways to detect and
optimize available transmission paths in quantum communication
networks, as well as methods to verify quantum circuits and to
discover the latent structure of multipartite quantum systems.

A priori, there exists no preferential temporal direction as microscopic physical laws are time-symmetric. Still, the second law of thermodynamics allows one to associate the 'forward' temporal direction to a positive variation of the total entropy produced in a thermodynamic process, and a negative variation with its 'time-reversal' counterpart.
This definition of a temporal axis is normally considered to apply in both classical and quantum contexts. Yet, quantum physics admits also superpositions between forward and time-reversal processes, thereby seemingly eluding conventional definitions of time's arrow. In this talk, I will demonstrate that a quantum measurement of entropy production can distinguish the two temporal directions, effectively projecting such superpositions of thermodynamic processes onto the forward (time-reversal) time-direction when large positive (negative) values are measured.
Remarkably, for small values (of the order of plus or minus one), the amplitudes of forward and time-reversal processes can interfere, giving rise to entropy-production distributions featuring a more or less reversible process than either of the two components individually, or any classical mixture thereof.
Finally, I will extend these concepts to the case of a thermal machine running in a superposition of the heat engine and the refrigerator mode, illustrating how such interference effects can be employed to reduce undesirable fluctuations.

There is a deep relation between classical error-correcting codes, Euclidean lattices, and chiral 2d CFTs. We show this relation
extends to include quantum codes, Lorentzian lattices, and non-chiral CFTs. The relation to quantum codes provides a simple way to solve
modular bootstrap constraints and identify interesting examples of conformal theories. In particular we construct many examples of physically distinct isospectral theories, examples of "would-be" CFT partition function -- non-holomorphic functions satisfying all constraints of the modular bootstrap, yet not associated with any

known CFT, and find theory with the maximal spectral gap among all Narain CFTs with the central charge c=4. At the level of code theories the problem of finding maximal spectral gap reduces to the problem of finding optimal code, leading to "baby bootstrap" program. We also discuss averaging over the ensemble of all CFTs associated with quantum codes, and its possible holographic interpretation. The talk is based on arXiv:2009.01236 and arXiv:2009.01244.

A proposal is made for a fundamental theory,  in which the history of the universe is constituted of views of itself.  Views are attributes of events, and the theory's only be-ables; they comprise information about energy and momentum transferred to an event from its causal past. 

The  theory is called the causal theory of views (CTV) and is a candidate for a completion of QM.  It is partly based on energetic causal sets (ECS),   an approach developed  with Marina Cortes.  A key result that applies also here is that spacetime is emergent from the ECS dynamics.  This implies that the fundamental dynamics involve no notion of space, distance or derivatives.  Instead I propose that a measure of similarity of views replaces derivatives as the basic measure of change and difference.

A measure of the diversity of views in a  causal network is introduced, called the variety (originally invented with Julian  Barbour).  I postulate a dynamics for CTV based on an action involving the variety and show that in an appropriate limit, it reduces to Schrodinger quantum mechanics.  A key result is that  the variety reduces to Bohm's quantum potential.

Based on arXiv:1307.6167,  arXiv:1308.2206 , arXiv:1712.0479 and a paper in preparation.

In a quantum measurement process, classical information about the measured system spreads through the environment. In contrast, quantum information about the system becomes inaccessible to local observers. In this talk, I will present a result about quantum channels indicating that an aspect of this phenomenon is completely general. We show that for any evolution of the system and environment, for everywhere in the environment excluding an O(1)-sized region we call the "quantum Markov blanket," any locally accessible information about the system must be approximately classical, i.e. obtainable from some fixed measurement. The result strengthens the earlier result of arXiv:1310.8640 in which the excluded region was allowed to grow with total environment size.  I will also discuss applications to many-body physics.

Using a process-theoretic formalism, we introduce the notion of a causal-inferential theory: a triple consisting of a theory of causal influences, a theory of inferences (of both the Boolean and Bayesian varieties), and a specification of how these interact. Recasting the notions of operational and realist theories in this mold clarifies what a realist account of an experiment offers beyond an operational account. It also yields a novel characterization of the assumptions and implications of standard no-go theorems for realist representations of operational quantum theory, namely, those based on Bell’s notion of locality and those based on generalized noncontextuality. Moreover, our process-theoretic characterization of generalised noncontextuality is shown to be implied by an even more natural principle which we term Leibnizianity. Most strikingly, our framework offers a way forward in a research program that seeks to circumvent these no-go results. Specifically, we argue that if one can identify axioms for a realist causal-inferential theory such that the notions of causation and inference can differ from their conventional (classical) interpretations, then one has the means of defining an intrinsically quantum notion of realism, and thereby a realist representation of operational quantum theory that salvages the spirit of locality and of noncontextuality.

"Analogue" Hamiltonian simulation involves engineering a Hamiltonian of
interest in the laboratory and studying its properties experimentally.
Large-scale Hamiltonian simulation experiments have been carried out in
optical lattices, ion traps and other systems for two decades. Despite
this, the theoretical basis for Hamiltonian simulation is surprisingly
sparse. Even a precise definition of what it means to simulate a
Hamiltonian was lacking.

AdS/CFT duality postulates that quantum gravity in a d-dimensional
anti-de-Sitter bulk space is equivalent to a strongly interacting field
theory on its d-1 dimensional boundary. Recently, connections between
AdS/CFT duality and quantum error-correcting codes have led (amongst
other things) to tensor network toy models that capture important aspects
of this holographic duality. However, these toy models struggle to
encompass dualities between bulk and boundary energy scales and dynamics.

On the face of it, these two topics seem to have nothing whatsoever to do
with one another.

In my talk, I will explain how we put analogue Hamiltonian simulation on
a rigorous theoretical footing, by drawing on techniques from Hamiltonian
complexity theory and Jordan algebras. I will show how this proved far
more fruitful than a mere mathematical tidying-up exercise, leading to
the discovery of universal quantum Hamiltonians [Science, 351:6 278,
p.1180, 2016], [Proc. Natl. Acad. Sci. 115:38 p.9497, 2018]. And I will
explain how this new Hamiltonian simulation formalism, together with
hyperbolic Coxeter groups, allowed us to extend the toy models of AdS/CFT
to encompass energy scales, dynamics, and even (toy models of) black hole
formation [arXiv:1810.08992].

The Fermi-Hubbard model is of fundamental importance in condensed-matter physics, yet is extremely challenging to solve numerically. Finding the ground state of the Hubbard model using variational methods has been predicted to be one of the first applications of near-term quantum computers. In this talk, I will discuss recent work which carried out a detailed analysis and optimisation of the complexity of variational quantum algorithms for finding the ground state of the Hubbard model, including extensive numerical experiments for systems with up to 12 sites. The depth complexities we find are substantially lower than previous work. If our numerical results on small lattice sizes are representative of the somewhat larger lattices accessible to near-term quantum hardware, they suggest that optimising over quantum circuits with a gate depth less than a thousand could be sufficient to solve instances of the Hubbard model beyond the capacity of classical exact diagonalisation. I will also discuss a proof-of-principle implementation on Rigetti quantum computing hardware.

The talk is based on joint work with Chris Cade, Lana Mineh and Stasja Stanisic ( arXiv:1912.06007 , arXiv:2006.01179 ).

The compatibility-hypergraph approach to contextuality (CA) and the contextuality-by-default approach (CbD) are usually presented as products of entirely different views on how physical measurements and measurement contexts should be understood: the latter is based on the idea that a physical measurement has to be seen by a collection of random variables, one for each context containing that measurement, while the imposition of the non-disturbance condition as a physical requirement in the former precludes such interpretation of measurements. The aim of our work is to present both approaches as entirely compatible ones and to introduce in the compatibility-hypergraph approach ideas which arises from contextuality-by-default. We

introduce in CA the non-degeneracy condition, which is the analogous of consistent connectedness (an important concept from CbD), and prove that this condition is, in general, weaker than non-disturbance. The set of non-degenerate behaviours defines a polytope, therefore one can characterize non-degeneracy using a finite set of linear inequalities. We introduce extended contextuality for behaviours and prove that a behaviour is non-contextual in the standard sense if and only if it is non-degenerate and non-contextual in the extended sense. Finally, we use extended scenarios and behaviours to shed new light on our results.

I will review work by myself and others in recent years on the use of randomization in quantum circuit optimization.  I will present general results showing that any deterministic compiler for an approximate synthesis problem can be lifted to a better random compiler.  I will discuss the subtle issue of what "better" means and how it is sensitive to the metric and computation task at hand.  I will then review specific randomized algorithms for quantum simulations, including randomized Trotter (Su & Childs) and my group's work on the qDRIFT and SPARSTO algorithms.  The qDRIFT algorithm is of particular interest as it gave the first proof that Hamiltonian simulation is possible with a gate complexity that is independent of the number of terms in the Hamiltonian.  Since quantum chemistry Hamiltonians have a very large ( ~N^4) number of terms, randomization is especially useful in that setting. I will conclude by commenting on a recent Caltech paper with interesting results on the derandomization of random algorithms!  Some of the relevant preprints include:

https://arxiv.org/abs/1910.06255

https://arxiv.org/abs/1811.08017

https://arxiv.org/abs/1612.02689

Discriminating between unknown objects in a given set is a fundamental task in experimental science. Suppose you are given a quantum system which is in one of two given states with equal probability. Determining the actual state of the system amounts to doing a measurement on it which would allow you to discriminate between the two possible states. It is known that unless the two states are mutually orthogonal, perfect discrimination is possible only if you are given arbitrarily many identical copies of the state.

In this talk we consider the task of discriminating between quantum channels, instead of quantum states. In particular, we discriminate between a pair of unitary channels acting on a quantum system whose underlying Hilbert space is infinite-dimensional. We prove that in contrast to state discrimination, one only needs a finite number of uses of these channels in order to discriminate perfectly between them. Furthermore, no entanglement is needed in the discrimination task. The measure of discrimination is given in terms of the energy-constrained diamond norm, and a key ingredient of the proofs of these results is a generalization of the Toeplitz-Hausdorff Theorem of convex analysis . Moreover, we employ our results to study a novel type of quantum speed limits which apply to pairs of quantum evolutions. This work was done jointly with Simon Becker (Cambridge), Ludovico Lami (Ulm) and Cambyse Rouze (Munich).