Search Talks

"If one only performs experiments involving passive observations, in general there are multiple causal structures that can explain the same set of distributions over the observed variables. In this case, we say that these causal structures are observationally equivalent. In this work, we explore all the known techniques for proving observational equivalence or inequivalence, as well as some original ones. Even if the existing rules are not enough to achieve the full classification of the causal structures with four observed variables, our results get close to such classification and show that admitting inequality constraints is a generic feature among structures with four observed variables."

"Imsets, introduced by Studený (see Studený, 2005 for details), are an algebraic method for representing conditional independence models. They have many attractive properties when applied to such models, and they are particularly nice when applied to directed acyclic graph (DAG) models. In particular, the standard imset for a DAG is in one-to-one correspondence with the independence model it induces, and hence is a label for its Markov equivalence class. We present a proposed extension to standard imsets for maximal ancestral graph (MAG) models, which have directed and bidirected edges, using the parameterizing set representation of Hu and Evans (2020). By construction, our imset also represents the Markov equivalence class of the MAG. We show that for many such graphs our proposed imset defines the model, though there is a subclass of graphs for which the representation does not. We prove that it does work for MAGs that include models with no adjacent bidirected edges, as well as for a large class of purely bidirected models. If there is time, we will also discuss applications of imsets to structure learning in MAGs. This is joint work with Zhongyi Hu (Oxford). References Z. Hu and R.J. Evans, Faster algorithms for Markov equivalence, In Proceedings for the 36th Conference on Uncertainty in Artificial Intelligence (UAI-2020), 2020. M. Studený, Probabilistic Conditional Independence Structures, Springer-Verlag, 2005."

There are numerous properties of quantum states that one might be interested in characterizing, including statistical moments of observables such as expectations or variances, or more generally purities, entropies, probabilities, eigenvalues, symmetries, marginals, etc. Given a fixed collection of properties, the realizability problem aims to determine which value-assignments to those properties are jointly exhibited by at least one quantum state. In addition to the decision problem of realizability, one might also be interested in quantifying what proportion of quantum states possesses those property values. 

Any property of a quantum state can always, at least in principle, be estimated empirically by suitably measuring an ensemble of many independently and identically prepared copies of that quantum state. The particular sequence of positive operator valued measures which estimates a given property is known as a property estimation scheme. The purpose of this talk is to discuss a strategy for tackling realizability problems by studying the large deviation behaviour of property estimation schemes.

The key idea of this approach is the following:
A given collection of properties is realized by a quantum state if and only if a random quantum state occasionally produces that collection of properties as estimates.
Under suitable conditions, this observation leads to a complete hierarchy of necessary conditions for realizability.

Zoom link:  https://pitp.zoom.us/j/91945653382?pwd=QTZqSnpjYjlxYndqaHZwN2lES1h1Zz09

Entanglement entropies of two-dimensional gapped ground states are expected to satisfy an area law, with a constant correction term known as the topological entanglement entropy (TEE). In many models, the TEE takes a universal value that characterizes the underlying topological phase. However, the TEE is not truly universal: it can differ even for two states related by constant-depth circuits, which are necessarily in the same phase. The difference between the TEE and the value predicted by the anyon theory is often called the spurious topological entanglement entropy. We show this spurious contribution is always nonnegative, thus the value predicted by the anyon theory provides a universal lower bound. This observation also leads to a definition of TEE which is invariant under constant-depth quantum circuits.

Based on a joint work with Daniel Ranard (MIT), Michael Levin (U Chicago), Ting-Chun Lin (UCSD), and Bowen Shi (UCSD)

Zoom link:  https://pitp.zoom.us/j/93809342984?pwd=QXJkK0ZYR3QzdjlUUWlkMEFXMWRnQT09

For n≥3, we demonstrate the existence of quantum codes which are local in dimension n with V qubits, distance V^{(n−1)/n}, and dimension V^{(n−2)/n}, up to a polylog(V) factor. The distance is optimal up to the polylog factor. The dimension is also optimal for this distance up to the polylog factor. The proof combines the existence of asymptotically good quantum codes, a procedure to build a manifold from a code by Freedman-Hastings, and a quantitative embedding theorem by Gromov-Guth.

Zoom link:  https://pitp.zoom.us/j/96227350980?pwd=TEFtamRmTXg3dnBMNEhKUkpHbmVoZz09

Quantum error mitigation has been proposed as a means to combat unwanted and unavoidable errors in near-term quantum computing using no or few additional quantum resources, in contrast to fault-tolerant schemes that come along with heavy overheads. Error mitigation has been successfully applied to reduce noise in near-term applications. 

In this work, however, we identify strong limitations to the degree to which quantum noise can be effectively `undone' for larger system sizes. We set up a framework that rigorously captures large classes of error mitigation schemes in use today. The core of our argument combines fundamental limits of statistical inference with a construction of families of random circuits that are highly sensitive to noise.

We show that even at poly loglog depth, a super-polynomial number of samples is needed in the worst case to estimate the expectation values of noiseless observables, the principal task of error mitigation. Notably, our construction implies that scrambling due to noise can kick in at exponentially smaller depths than previously thought. They also impact other near-term applications, constraining kernel estimation in quantum machine learning, causing an earlier emergence of noise-induced barren plateaus in variational quantum algorithms and ruling out exponential quantum speed-ups in estimating expectation values in the presence of noise or preparing the ground state of a Hamiltonian.

Zoom link:  https://pitp.zoom.us/j/95736148335?pwd=akZLaHE5aStNQVZOeVFETlltNzVwdz09

Recent progress in the development of quantum technologies has enabled the direct investigation of dynamics of increasingly complex quantum many-body systems. This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage. Here we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian. For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error. In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb–Robinson bound. Our results use cluster expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence. This has important physical consequences besides our efficient algorithms. In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.

Joint work with Dominik S. Wild (arXiv:2210.11490)

Zoom link:  https://pitp.zoom.us/j/97166113711?pwd=UEg4NnJlQkkxQXFnN2xXYTBxS001Zz09

The theory of polynomial optimisation considers a polynomial objective function subject to countable many polynomial constraints. In a seminal contribution Navascués, Pironio and Acín (NPA) generalised a previous result from Lassere, allowing for its application in quantum information theory by considering its non-commutative variant. Non-commutative variables are represented as bounded operators on potentially infinite dimensional Hilbert spaces. These infinite-dimensional non-commutative polynomials optimisation (NPO) problems are recast as a complete hierarchy of semidefinite programming (SDP) relaxations by a suitable partitioning of the underlying spaces.

The reformulation into convex optimisation problems allows for numerical analysis. We focus on an operator theoretical approach to the NPA hierarchy and show its equiv-
alence to the original NPA hierarchy. To do so, we introduce the necessary mathematical preliminaries from operator algebra theory and semidefinite programming. We conclude by showing how certain relations on operators translate to SDP relaxations yielding drastically reduced problem sizes.

Zoom Link: https://pitp.zoom.us/j/98583295694?pwd=SlcvNG90RzFrODBKSHNaUi84bG9DZz09