We propose a method for classical simulation of finite-dimensional quantum systems, based on sampling from a quasiprobability distribution, i.e., a generalized Wigner function. Our construction applies to all finite dimensions, with the most interesting case being that of qubits. For multiple qubits, we find that quantum computation by Clifford gates and Pauli measurements on magic states can be efficiently classically simulated if the quasiprobability distribution of the magic states is non-negative. This provides the so far missing qubit counterpart of the corresponding result [V. Veitch et al., New J. Phys. 14, 113011 (2012)] applying only to odd dimension. Our approach is more general than previous ones based on mixtures of stabilizer states. Namely, all mixtures of stabilizer states can be efficiently simulated, but for any number of qubits there also exist efficiently simulable states outside the stabilizer polytope. Further, our simulation method extends to negative quasiprobability distributions, where it provides amplitude estimation. The simulation cost is then proportional to a robustness measure squared. For all quantum states, this robustness is smaller than or equal to robustness of magic.
Joint work with Juani Bermejo-Vega, Emily Tyhurst, Cihan Okay, Michael Zurel.
Contextuality has been proposed as a resource that powers quantum computing. The measurement-based model provides a concrete manifestation of contextuality as a computational resource, as follows. If local measurements on a multi-qubit state can be used to evaluate nonlinear boolean functions with only linear control processing, then this computation constitutes a proof of strong contextuality—the possible local measurement outcomes cannot all be pre-assigned. We prove a generalisation of this result to the case when the local measured systems are qudits and discuss some important differences arising between the qubit and qudit case from a resource-theoretic perspective.
Joint work with Sam Roberts and Stephen Bartlett.
We start by introducing the notions of measurement scenario and empirical model, the basic ingredients of a general, sheaf-theoretic approach to non-locality and contextuality. We then focus on studying contextuality from the point of view of resource theory. We introduce natural operations that combine contextual systems and control their use as resources, including the kind of classical control of quantum systems required by measurement-based quantum computation (MBQC) schemes. We consider a quantitative measure of contextuality – the contextual fraction – which behaves as a monotone under these 'free' operations, and we relate it to quantifiable advantages afforded by access to contextual resources, including in non-local games and in a form of MBQC.
Joint work with Samson Abramsky, Shane Mansfield, and Martti Karvonen. Some more recent developments will be covered in Martti's talk.
We start with a very simple notion of an empirical model simulating another one and then extend it to a more useful notion by considering measurement protocols. This captures various notions of intraconversions between correlations that have been studied in the literature on non-locality, and should be seen as a resource theory for contextuality. We prove that these simulations allow exactly the same transformations as the free operations discussed in the previous talk. Next we move to applications of this framework: a case in point is a no-cloning/no-broadcasting theorem which states that an empirical model can simulate two independent copies of itself iff it is non-contextual. If time permits, we will discuss ongoing work and further questions suggested by the framework.
We introduce a simple single-system game inspired by the Clauser-Horne-Shimony-Holt (CHSH) game. For qubit systems subjected to unitary gates and projective measurements, we prove that any strategy in our game can be mapped to a strategy in the CHSH game, which implies that Tsirelson’s bound also holds in our setting. More generally, we show that the optimal success probability depends on the reversible or irreversible character of the gates, the quantum or classical nature of the system, and the system dimension.
We focus on irreversibility and the use of quantum mechanics as the sources of computational advantages for the game. We analyze the former in light of Landauer’s principle, showing the entropic costs of the erasure associated with the game. On the other hand, quantum advantages can be explained by appealing to the presence of a particular form of contextuality.
We compare the two analysis and explore a possible general connection between erasure of information and contextuality.
How explicit can we make the role of contextuality in quantum computation? To explore this question, I present the 'quantum infusion' model. In this model, almost all qubits (in an unbounded 'data register') are subject only to 'classical' multiply-controlled-NOT operations. However, using these operations, the data register can also interact with a constant-sized 'infusion register' – qubits which may be initialised to a non-classical state, and acted on with arbitrary unitary operations. By interacting with this 'infusion register', we may simulate various X and Z rotations on the other qubits despite using only multiply-controlled-NOT operations. In this talk, I elaborate on the motivation behind considering this model of computation, and suggest it as a platform in which to demonstrate the role of contextuality for computation.
In this talk I review some basic elements of descriptive complexity, including the logical characterisation of complexity classes. I will discuss the distinction between syntactic and semantic complexity classes, especially in connection with the class BQP.
In the later part of the talk, I will discuss the logic FPC, the associated notion of "counting width" and its connections with local consistency on the one hand and notions of symmetric computation on the other.
The notion of the core of a finite graph [1] has proved a useful tool in combinatorics and the study of classical graph algorithms. In this talk I will present my work, with Anuj Dawar, on generalising this notion to other categories and the problems encountered in doing so. In particular, I will look at the coKleisli category of Abramsky, Dawar and Wang's k-pebbling comonad [2] which captures a weakened version of homomorphism and explore whether cores might exist here and what properties they might have.
[1] The core of a graph, P. Hell & J. Ne&shacek;et&rhacek;il, 1990
[2] The pebbling comonad in finite model theory, S. Abramsky, A. Dawar & P. Wang, 2017
In this talk, based on the joint work (arXiv:1905.07723) with Daniel Sheinbaum, I will introduce a topological space to study contextuality in quantum mechanics. The resulting space is a classifying space in the sense of algebraic topology. This approach is in parallel with the topological approach of [1]. There is a distinguished class in the second cohomology group that detects strong contextuality. Moreover, the empirical model of a state, in the sense of [2], or the Wigner function can be interpreted as a class in the twisted K-theory of the classifying space.
[1] Topological proofs of contextuality in quantum mechanics - C. Okay, S. Roberts, S.D. Bartlett, R. Raussendorf
[2] The sheaf-theoretic structure of non-locality and contextuality - S. Abramsky and A. Brandenburger
Matchgate (MG) circuits, like Clifford circuits, give rise to classes of classically simulatable quantum computations. We will begin by introducing the formalism of matchgates and give an overview of their classical simulation properties, comparing and contrasting them to the case of Clifford circuits.
The notion of magic state, originally introduced by Bravyi and Kitaev in the context of Clifford circuits, is a resource that elevates classically simulatable Clifford computations to universal quantum capability while maintaining the same gate set. We will discuss the notion of magic state in the context of MG computations where it becomes more subtle, and outline our recent result that every pure fermionic state (i.e. superposition of only even or only odd parity bit strings) which cannot be generated by MGs from a computational basis state, is a magic state for MG computations.
I will provide an introduction to the Schur Transform and survey its recent applications in the context of Permutational Quantum Computing (PQC). I will further show that most of its widely-believed quantum features are classically tractable: the outputs of Schur sampling circuits are unconditionally strongly simulatable and weakly simulatable under certain sparsity assumptions. I will also discuss the Kushilevitz-Mansour algorithm which is used to estimate heavy Fourier/Clebsch-Gordan coefficients of the output states of quantum circuits and discuss possible ways of regaining supra-classical power in PQC.
Bravyi, Gosset, and König recently showed that bounded depth (shallow) quantum circuits are more powerful than their classical analogues. Their principle contribution can be described as an upper bound on the ability of any shallow classical circuit to reproduce the output statistics of a certain shallow quantum circuit. We allow the classical circuit to sample a contextual resource, and derive their bound as a special case of an inequality introduced by Abramsky, Barbosa, and Mansfield: p̃F ≥ NCF(e) · (n - k)/n. Here, p̃F denotes the average failure probability of a no-communication strategy e for a non-local game, NCF(e) is the non-contextual fraction of the strategy, and (n - k)/n is a measure of the hardness of the game.
I will recall two ‘quantisations’ recently appearing in quantum information theory. The first is the notion of quantum graph isomorphism, a quantum strategy for a nonlocal game generalising the linear constraint system game. The second is the notion of quantum (or noncommutative) graph, encoding the zero-error Shannon theory of a quantum channel. I will review recent work (with Benjamin Musto and David Reutter) positioning both these structures within the standard framework of noncommutative mathematics. We thereby obtain a full classification of quantum strategies for the graph isomorphism game in terms of the compact quantum automorphism group of one of the graphs. Remarkably, our results also extend to the classification and construction of quantum isomorphisms to and between quantum graphs. l will preview forthcoming work (with David Reutter) giving a physical semantics for these quantum isomorphisms. Indeed, quantum isomorphisms between general quantum graphs induce transformations of channels preserving all entanglement-assisted single-shot (EASS) capacities. In the case of classical-quantum graph isomorphisms, this reduces EASS capacity computations for quantum channels to EASS capacity computations for classical channels. In the case of classical-classical graph isomorphisms, this means that quantum solutions to classically non-satisfiable linear constraint systems may all be interpreted as entanglement-symmetries of classical channels.
I will introduce a notion of contextuality for transformations in sequential contexts. It is distinct from the notions of contextuality due to Bell–Kochen–Specker and Spekkens. There is considerable evidence that contextuality of these latter forms lies at the root of certain forms of quantum advantage over classical systems for performing a variety of informatic tasks. I will present a basic example where sequential transformation contextuality can be seen to lead to similar advantage in single qubit protocols, where contextuality of the other forms could not be present. The talk will largely be based on Physical Review Letters 121 (23), 230401 (arXiv:1801.08150 [quant-ph]).
Contextuality is a non-classical behaviour that can be exhibited by quantum systems. It is increasingly studied for its relationship to quantum-over-classical advantages in informatic tasks. To date, it has largely been studied in discrete variable scenarios, where observables take values in discrete and usually finite sets. Practically, on the other hand, continuous-variable scenarios offer some of the most promising candidates for implementing quantum computations and informatic protocols. Here we set out a framework for treating contextuality in continuous-variable scenarios. It is shown that the Fine–Abramsky–Brandenburger theorem extends to this setting, an important consequence of which is that nonlocality can be viewed as a special case of contextuality, as in the discrete case. The contextual fraction, a quantifiable measure of contextuality that bears a precise relationship to Bell inequality violations and quantum advantages, can also be defined in this setting. It is shown to be a non-increasing monotone with respect to classical operations that include binning to discretise data. Finally, we consider how the contextual fraction can be formulated as an infinite linear program, and calculated with increasing accuracy using semi-definite programming approximations.
Joint work with Rui Soares Barbosa, Tom Douce, Elham Kashefi, Shane Mansfield.