Workshop dates: June 13 -17, 2022
Location: Zoom
Hosted by the University of British Columbia, Vancouver, Canada
Room schedule:
Color coding for the talks below: held on-site (UBC campus) - available on Zoom; held on Zoom.
Arnab Adhikary (University of British Columbia): Novel efficient regimes of computation in (finite) SPT chains
Abstract: Spin chains exhibiting non-trivial symmetry protected topological (SPT) order are known to be perfect resources for measurement-based quantum computation. In a seminal work, Else et al. (2012) used group cohomological arguments to show that any 1D SPT chain is capable of shuttling quantum information without incurring any error. Unfortunately, the same analysis seemed to predict that performing any rotation away from the identity unavoidably introduces logical errors into the computation. Nevertheless, Miller and Miyake (2015) and Raussendorf et al. (2017) circumvented the roadblock by showing that logical decoherence can be efficiently managed in SPT ordered phases if the rotations are divided into smaller parts which are separated by a distance much larger than the characteristic length scale of the system. In this work, we investigate the exact opposite regime of computation, i.e. where the rotations are packed as closely as possible, and surprisingly find it to be the most resource efficient. The techniques developed in the process also make it feasible to test out our results in state of the art NISQ devices.
Matt Amy (Simon Fraser University): Symbolic representation of quantum computations
Abstract: Representations of quantum computations, from high-level programming languages to circuits and intermediate languages, often take a structural approach where individual matrices or tensors are composed to describe a linear algebraic computation. This allows high-level structural reasoning and (in some models, complete) local re-writing via simple rules, but can often be semantically opaque. In this talk I will discuss alternative representations based on symbolic sums which carry a more directly computational flavour. I will further discuss how such representations can be used as a tool for reasoning about, optimizing, and synthesizing quantum programs.
Daniel Azses (Tel Aviv University): Observing Floquet topological order by symmetry resolution
Abstract:Symmetry protected topological order in one dimension leads to protected degeneracies between symmetry blocks of the reduced density matrix. In the presence of periodic driving, topological Floquet phases can be identified in terms of a cycling of these symmetry blocks between different charge quantum numbers. We discuss an example of this phenomenon with an Ising Z_2 symmetry, using both analytic methods and real quantum computers. By adiabatically moving along the phase diagram, we demonstrate that the cycling periodicity is broken in Floquet topological phase transitions. An equivalent signature of the topological Floquet phase is identified as a computational power allowing to teleport quantum information.
Sven Bachmann (University of British Columbia): Pumping G-invertible states in one dimension
Abstract: The classification of G-invariant invertible states is well understood in low dimensions. In this talk, I will discuss the classification of loops of G-invertible states, which can be understood as generalizations of the Thouless pump from U(1) to an arbitrary compact group G. The classes in d spatial dimensions are expected to be given by the SPT classes in d-1 dimensions, a fact that can be proved for d=1. This is joint work with W. De Roeck, T. Jappens and M. Fraas.
Dmytro Bondarenko (University of British Columbia): Matrix product structures: from states through operators to channels
Abstract: This talk is dedicated to matrix product structures and their different habitats. Our specimen will come in historical order of increasing complexity. Matrix product states (MPS) are an essential tool in the investigation of 1d structures. Taking their origins in powerful numerical methods, MPS uncovered the two-way connection between 1d Hamiltonians and ground states. Recently, MPS were implemented on quantum computers and used for machine learning. The generalisation of MPS to mixed states are matrix product density operators (MPDOs). These two structures share the area law of entanglement and the success in numerical methods. Yet there are many differences between the two. I will discuss the complications in optimization of MPDOs and proceed to explain how the two-way connection between fixed states and evolution operators partially breaks down. Moving to the quantum implementation and machine learning front, we will observe the similarities between MPDOs and recurrent neural networks (RNNs). Pushing this analogy forward, one gets to matrix product quantum channels. Via studying the implementation of matrix product channels on a quantum computer, we will arrive at quantum RNNs. We will see a number of practically relevant tasks that are suitable for quantum RNNs. Examples include bandwidth filters for quantum signals and learning the evolution with a time-dependent Hamiltonian. Finally, we will combine quantum and classical RNNs to economise resources. Based on: preprint arXiv:2110.13134 and my PhD thesis.
Larry Cohen (University of Sydney): Quantum computing with LDPC codes
Abstract: I will talk about two recent papers on quantum LDPC codes. In the first paper (arxiv:2110.10794) we propose a general method for performing fault-tolerant gates with LDPC codes. Our method can be viewed as a generalisation of lattice surgery, and when supplemented with magic state distillation allows for universal quantum computations. We estimate that our proposal allows for a large improvement in the overhead associated with quantum error correction as compared to local architectures such as the surface code. In the second paper (arxiv:2202.01702) we introduce a modification for quantum LDPC codes that allows them to be tailored for biased noise. We numerically test this modification on lifted product codes using belief propagation plus ordered statistics decoding and demonstrate a several orders of magnitude improvement in the logical failure rate under biased noise.
Austin Daniel (University of New Mexico): Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
Abstract: Nonlocal games with advantageous quantum strategies give arguably the most fundamental demonstration of the power of quantum resources over their classical counterparts. Recently, certain multiplayer generalizations of nonlocal games have been used to prove unconditional separations between small computational complexity classes of shallow-depth circuits. Here, we show advantageous strategies for these nonlocal games for generic ground states of one-dimensional symmetry-protected topological orders (SPTOs), when a discrete invariant of a SPTO known as a twist phase is nontrivial and -1. Our construction demonstrates that sufficiently large string order parameters of such SPTOs are indicative of globally constrained correlations useful for the unconditional computational separation. Joint work with Akimasa Miyake; J-Ref: Phys. Rev. Lett. 126, 090505 (2021)
Nadish de Silva (Simon Fraser University): Efficient quantum gate teleportation in higher dimensions
Abstract: The Clifford hierarchy is a nested sequence of sets of quantum gates critical to achieving fault-tolerant quantum computation. Diagonal gates of the Clifford hierarchy and 'nearly diagonal' semi-Clifford gates are particularly important: they admit efficient gate teleportation protocols that implement these gates with fewer ancillary quantum resources such as magic states. Despite the practical importance of these sets of gates, many questions about their structure remain open; this is especially true in the higher-dimensional qudit setting. Our contribution is to leverage the discrete Stone-von Neumann theorem and the symplectic formalism of qudit stabiliser mechanics towards extending results of Zeng-Cheng-Chuang (2008) and Beigi-Shor (2010) to higher dimensions in a uniform manner. We further give a simple algorithm for recursively enumerating all gates of the Clifford hierarchy, a simple algorithm for recognising and diagonalising semi-Clifford gates, and a concise proof of the classification of the diagonal Clifford hierarchy gates due to Cui-Gottesman-Krishna (2016) for the single-qudit case. We generalise the efficient gate teleportation protocols of semi-Clifford gates to the qudit setting and prove that every third level gate of one qudit (of any prime dimension) and of two qutrits can be implemented efficiently. Numerical evidence gathered via the aforementioned algorithms support the conjecture that higher-level gates can be implemented efficiently.
Polina Feldmann (University of British Columbia): Cohomological Constraints on Wigner Functions
Abstract: A web of cohomological facts relates quantum error correction, measurement-based quantum computation, symmetry protected topological order and contextuality. Here we extend this web to quantum computation with magic states. In this computational scheme, the negativity of certain quasiprobability functions is an indicator for quantumness. However, when constructing quasiprobability functions to which this statement applies, a marked difference arises between the cases of even and odd local Hilbert space dimension. At a technical level, establishing negativity as an indicator of quantumness in quantum computation with magic states relies on two properties of the Wigner function: their covariance with respect to the Clifford group and positive representation of Pauli measurements. In odd dimension, Gross' Wigner function -- an adaptation of the original Wigner function to odd-finite-dimensional Hilbert spaces -- possesses these properties. In even dimension, Gross' Wigner function doesn't exist. Here we discuss the broader class of Wigner functions that, like Gross', are obtained from operator bases. We find that such Clifford-covariant Wigner functions do not exist in any even dimension, and furthermore, Pauli measurements cannot be positively represented by them in any even dimension whenever the number of qudits is n>=2. We establish that the obstructions to the existence of such Wigner functions are cohomological. Joint work with Robert Raussendorf, Cihan Okay and Michael Zurel. Based on the preprint arXiv:2110.11631.
David Gosset (University of Waterloo): How to simulate quantum measurement without computing marginals
Abstract: We describe and analyze algorithms for classically simulating
measurement of an n-qubit quantum state |psi> in the standard basis, that is, sampling a bit string x from
the probability distribution |
Paul Herringer (University of British Columbia): Classification of measurement-based quantum transmission in stabilizer PEPS
Abstract: We introduce a class of highly symmetric 2D tensor network states called stabilizer PEPS, which include the 2D cluster state, GHZ state, and toric code state. We investigate the transmission capacity of stabilizer PEPS for measurement-based quantum wire, and arrive at a complete classification of transmission behaviors. One of the classes identified corresponds to Clifford quantum cellular automata, and we also describe 12 other classes, for a total of 13.
Daniel Huerga (University of British Columbia): Variational quantum simulation of valence-bond solids
Abstract: Hybrid variational quantum-classical algorithms are at the center of today's research for their potentialities in providing with "useful" applications of currently developed noisy-intermediate scale quantum (NISQ) devices. However, recent results have cast doubts on their scalability. Their variational optimization has been shown to be impeded by major obstacles such as the emergence of 'barren plateaux', i.e. large flat regions in the optimization landscape. In this talk, I will present a hybrid algorithm to quantum simulate models of frustrated quantum magnets in the thermodynamic limit, which shows promising results towards the mitigation of barren-plateaux. It is based on a cluster-Gutzwiller ansatz where a shallow parameterized quantum circuit provides the wave function of the cluster. Information of the infinite lattice is provided through a self-consistent mean-field embedding that pushes the algorithm towards convergence. Quantum paramagnetic phases are accessed by smoothly driving the system from an ordered phase through a quantum phase transition, opening a route for quantum simulation of valence bond solid phases with current NISQ superconducting circuit devices.
Aleks Kissinger (Oxford University): Classical simulation of quantum circuits by graphical stabiliser decompositions
Abstract: Classical simulation of arbitrary Clifford+T quantum circuits is expected to be hard. However, if such a circuit prepares a state which can be decomposed as a sum of relatively few stabiliser states, the problem becomes easy, thanks to the Gottesman-Knill theorem. While optimal stabiliser decompositions are difficult to compute in general, there exists a techniques for producing stabiliser decompositions by decomposing T gates in a circuit in "chunks" of 6 or more at a time. In this talk, I'll introduce a graphical variation on this "chunking" technique based on the ZX calculus. ZX diagrams give an efficient way to represent a state prepared by a Clifford+T circuit, which can then be iteratively decomposed to into efficiently simulable parts. The diagrammatic representation gives some extra flexibility in how we perform decompositions, and most importantly, allows us to interleave decomposition with automated diagram simplification using the ZX calculus. Since non-Clifford structure can cancel out during simplification, this sometimes yields reductions in the numbers of stabiliser terms of hundreds of orders of magnitude. Using this approach, we demonstrate strong simulation of hidden shift circuits with up to 1400 T gates, which is about 20 times as large as any previously simulated with stabiliser rank techniques. Based on joint work with John van de Wetering; arXiv:2109.01076.
Cihan Okay (Bilkent University): Simplicial quantum contextuality
Abstract: In this talk I will introduce
a new framework for contextuality based on simplicial sets, combinatorial
models of topological spaces that play a prominent role in modern homotopy
theory. Our approach extends measurement scenarios to consist of spaces
(rather than sets) of measurements and outcomes, and thereby generalizes
nonsignaling distributions to simplicial distributions, which are distributions
on spaces modeled by simplicial sets. Strong contextuality can be generalized
suitably for simplicial distributions, allowing us to define cohomological
witnesses that extend the earlier topological constructions restricted to
algebraic relations among quantum observables to the level of probability
distributions. We will revisit foundational results in quantum theory,
such as the Gleason's theorem, Kochen-Specker theorem and Fine's theorem for
the CHSH scenario.
Based on the preprint arXiv:2204.06648
joint with Aziz Kharoof and Selman Ipek.
David Schmid (University of Gdansk): Classical explainability beyond prepare-measure scenarios
Abstract: It is useful to have a criterion for when the predictions of an arbitrary circuit or compositional theory should be considered classically explainable. However, most previous works in this area have focused on simple circuits such as prepare-measure scenarios. Here, we begin addressing this problem by defining the framework of ontological models as well as the principle of generalized noncontextuality within a process-theoretic framework that can be applied to arbitrary compositional scenarios or theories. We then prove that, under some reasonable assumptions, every noncontextual ontological model has a surprisingly rigid and simple mathematical structure. We leverage this structure to prove that every stabilizer subtheory in odd dimensions has a unique noncontextual representation (given by Gross's representation, or equivalently, Spekkens' toy theory), and that every stabilizer subtheory in even dimensions is contextual. This in turn allows us to provide an elegant proof that contextuality is a necessary resource for quantum computation in the state-injection model. Along the way, we mathematically formalize and conceptually clarify prior arguments concerning the equivalence of various notions of classicality, while extending these equivalences from prepare-measure scenarios to arbitrary compositional scenarios. This talk reviews results from arXiv:2005.07161 and arXiv:2101.06263.
Daochen Wang (University of Maryland): Symmetries, graph properties, and quantum speedups
Abstract: 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). Joint work with: Shalev Ben-David, Andrew M. Childs, Andras Gilyen, William Kretschmer, and Supartha Podder.
Ryohei Weil (University of British Columbia): A Simulation of a Simulation: Algorithms for Measurement-Based Quantum Computing Experiments
Abstract: The paradigm of measurement-based quantum computing (MBQC) provides an ideal theoretical playground to characterize quantum computational resources. Recent advances have yielded a formalism to characterize the computational power of finite one-dimensional MBQC resource states. In this talk, I will discuss techniques developed for the experimental realization of these results on Noisy Intermediate-Scale Quantum (NISQ) devices. I will discuss a post-processing algorithm for bypassing the generally inefficient transformation to the resource states of interest. I will also discuss a variational quantum algorithm for solving for the coefficients of this transformation. I will display the results obtained by running these algorithms on IBM quantum devices, which will demonstrate the capability of NISQ devices for showcasing phenomena relating to computational resource characterization.
Wang Yang (University of British Columbia): Characterization of computational power in symmetry protected topological phases in integer spin chains
Abstract: An important progress in the field of measurement-based quantum computation (MBQC) in the past decade is the discovery of one-dimensional symmetry protected topological states as MBQC resource states. In a recent unpublished work by Robert Raussendorf et. al., a deep connection between string order parameters in condensed matter physics and a computational order parameter for MBQC is found, where the computational order parameter can be used to quantitatively characterize the computational power of a many-body state. In this talk, I will discuss the application of the general framework to spin chains with arbitrary integer spin values, and show that the computational order parameter exactly matches with the conventional string order parameter.
Michael Zurel (University of British Columbia): Hidden variable models for quantum computation with magic states
Abstract:It was recently shown that a hidden variable model can be defined for quantum computation with magic states on qubits. We show that a hidden variable model can be defined for quantum computation with magic states on qudits of any dimension. These hidden variable models are similar in structure to previously defined q uasiprobability representations for quantum computation with magic states like the discrete Wigner function, the difference is that in these new models all states, measurements, and dynamical operations are represented probabilistically---no negativity is required. These models provide classical simulation algorithms for universal quantum computation. Further study of the polytopes on which the hidden variable models are based could lead to a better characterization of the quantum states which are useful for quantum computation with magic states. This talk is based on arXiv:2110.12318, joint work with Arne Heimendahl, Cihan Okay, and Robert Raussendorf.
In the making
Robert Raussendorf, Polina Feldmann, Dmytro Bondarenko, Wang Yang, Daniel Huerga, Michael Zurel (UBC Vancouver)