The IQC-QuICS Math and Computer Science Seminar


This virtual seminar is jointly sponsored by Institute for Quantum Computing (University of Waterloo) and the Joint Center for Quantum Information and Computer Science (University of Maryland). We are interested in understanding the theoretical tools that underlie current results in quantum information, especially insofar as they overlap with mathematics and theoretical computer science. Talks are 50 minutes long, with additional time for Q&A and discussion.

This is a hybrid of the IQC Math and Computer Science Seminar and the QuICS Math RIT on Quantum Information.


QuICS Organizers: Yusuf Alnawakhtha and Carl Miller.

IQC Organizers: Daniel Grier and Adam Bene Watts.


Future Meetings

Date: Thursday, August 18th, 2022, 2:00-3:00pm EDT

Speaker: Jerry Li

Speaker Affiliation: Microsoft Research


Past Meetings

Title: The quantum sign problem: perspectives from computational physics and quantum computer science
Speaker: Dominik Hangleiter
Speaker Affiliation: Freie Universität Berlin
Date: Tuesday, February 16th, 2021, 11:00am-12:00pm EST
Abstract: In quantum theory, whenever we make a measurement, the outcomes will be random samples, distributed according to a distribution that is determined by the Born rule. On a high level, this probability distribution arises via high-dimensional interference of paths in quantum state space. Often, this 'sign problem' is made responsible for the hardness of classical simulations on the one hand, and the power of quantum computers on the other hand. In my talk, I will provide different perspectives and results on the sign problem and ponder the question inhowfar it might serve as a delineator between quantum and classical computing. In the first part of the talk, I will motivate the emergence of the sign problem from a physics perspective, and briefly discuss how a hardness argument for sampling from the output of generic quantum computations exploits the sign problem. In the second part of the talk, I will take on a computational-physics perspective. Within the framework of Monte Carlo simulations of complex quantum systems, I will discuss the question: Can we mitigate or *ease* the sign problem computationally by finding a perhaps more suitable basis in which to describe a given system? Specifically, I will discuss various measures of the sign problem, how they are related, and how to optimize them -- practically and in principle.

Title: Computability and compression of nonlocal games

Speaker: Sajjad Nezhadi
Speaker Affiliation: University of Maryland — College Park
Date: Monday, March 22nd, 2021, 10:00-11:00am EDT

Abstract:Recently, works such as the landmark MIP*=RE paper by Ji et. al. have established deep connections between computability theory and the power of nonlocal games with entangled provers. Many of these works start by establishing compression procedures for nonlocal games, which exponentially reduce the verifier's computational task during a game. These compression procedures are then used to construct reductions from uncomputable languages to nonlocal games, by a technique known as iterated compression. 

In this talk, I will introduce and contrast various versions of the compression procedure and discuss their use cases. In particular, I will demonstrate how each can be used to construct reductions from various languages in the first two levels of the arithmetical hierarchy to complexity classes defined using entangled nonlocal games. Time permitting, I will also go through a high-level overview of some ingredients involved in performing compression.


Title: Efficient quantum algorithm for dissipative nonlinear differential equations
Speaker: Jin-Peng Liu
Speaker Affiliation: University of Maryland — College Park
Date: Thursday, April 8th, 2021, 3:00-4:00pm EDT

Abstract: Differential equations are ubiquitous throughout mathematics, natural and social science, and engineering. There has been extensive previous work on efficient quantum algorithms for linear differential equations. However, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. We give the first quantum algorithm for dissipative nonlinear differential equations that is efficient provided the dissipation is sufficiently strong relative to the nonlinearity and the inhomogeneity. We also establish a lower bound showing that differential equations with sufficiently weak dissipation have worst-case complexity exponential in time, giving an almost tight classification of the quantum complexity of simulating nonlinear dynamics. Finally, we discuss potential applications of this approach to problems arising in biology as well as in fluid and plasma dynamics.
Reference: Liu, Jin-Peng, et al. "Efficient quantum algorithm for dissipative nonlinear differential equations." arXiv:2011.03185 (2020).


Title: Schur-Weyl duality and symmetric problems with quantum input

Speaker: Laura Mancinska

Speaker Affiliation: University of Copenhagen
Date: Monday, April 26th, 2021, 10:00-11:00am EDT

Abstract: In many natural situations where the input consists of n quantum systems, each associated with a state space Cd, we are interested in problems that are symmetric under the permutation of the n systems as well as the application of the same unitary U to all n systems. Under these circumstances, the optimal algorithm often involves a basis transformation, known as (quantum) Schur transform, which simultaneously block-diagonalizes the said actions of the permutation and the unitary groups.  I will illustrate how Schur-Weyl duality can be used to identify optimal quantum algorithm for quantum majority vote and, more generally, compute symmetric Boolean functions on quantum data.  This is based on joint work "Quantum majority and other Boolean functions with quantum inputs" with H. Buhrman, N. Linden, A. Montanaro, and M. Ozols.


Title: Fault-tolerant error correction using flags and error weight parities
Speaker: Theerapat Tansuwannont
Speaker Affiliation: University of Waterloo
Date: Tuesday, June 8th, 2021, 4:00-5:00pm EDT
Abstract: Fault-tolerant error correction (FTEC), a procedure which suppresses error propagation in a quantum circuit, is one of the most important components for building large-scale quantum computers. One major technique often used in recent works is the flag technique, which uses a few ancillas to detect faults that can lead to errors of high weight and is applicable to various fault-tolerant schemes. In this talk, I will further improve the flag technique by introducing the use of error weight parities in error correction. The new technique is based on the fact that for some families of codes, errors of different weights are logically equivalent if they correspond to the same syndrome and the same error weight parity, and need not be distinguished from one another. I will also give a brief summary of my works on FTEC protocols for several families of codes, including cyclic CSS codes, concatenated Steane code, and capped color codes, which requires only a few ancillas.

Title: Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
Speaker: Michał Oszmaniec
Speaker Affiliation: Center for Theoretical Physics, Polish Academy of Sciences
Date: Tuesday, June 15th, 2021, 10:00am-11:00am EDT
Abstract: Fermionic Linear Optics (FLO) is a restricted model of quantum computation which in its original form is known to be efficiently classically simulable. We show that, when initialized with suitable input states, FLO circuits can be used to demonstrate quantum computational advantage with strong hardness guarantees. Based on this, we propose a quantum advantage scheme which is a fermionic analogue of Boson Sampling: Fermion Sampling with magic input states.
We consider in parallel two classes of circuits: particle-number conserving (passive) FLO and active FLO that preserves only fermionic parity and is closely related to Matchgate circuits introduced by Valiant. Mathematically, these classes of circuits can be understood as fermionic representations of the Lie groups U(d) and SO(2d). This observation allows us to prove our main technical results. We first show anticoncentration for probabilities in random FLO circuits of both kind. Moreover, we prove robust average-case hardness of computation of probabilities. To achieve this, we adapt the worst-to-average-case reduction based on Cayley transform, introduced recently by Movassagh, to representations of low-dimensional Lie groups. Taken together, these findings provide hardness guarantees comparable to the paradigm of Random Circuit Sampling.
Importantly, our scheme has also a potential for experimental realization. Both passive and active FLO circuits are relevant for quantum chemistry and many-body physics and have been already implemented in proof-of-principle experiments with superconducting qubit architectures. Preparation of the desired quantum input states can be obtained by a simple quantum circuit acting independently on disjoint blocks of four qubits and using 3 entangling gates per block. We also argue that due to the structured nature of FLO circuits, they can be efficiently certified.
Reference: Oszmaniec, Michał, et al. "Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states." arXiv preprint arXiv:2012.15825 (2020).

Title: Quantum coding with low-depth random circuits
Speaker: Michael Gullans
Speaker Affiliation: University of Maryland — College Park
Date: Tuesday, July 20th, 2021, 4:00pm-5:00pm EDT
Abstract: We study quantum error correcting codes generated by local random circuits and consider the circuit depth required to achieve high-performance against local error models. Notably, we find that random circuits in D spatial dimensions generate high-performing codes at depth at most O(log N) independent of D. Our approach to quantum code design is rooted in arguments from statistical physics and establishes several deep connections between random quantum coding and critical phenomena in phase transitions. In addition, we introduce a method of targeted measurements to achieve high-performance coding at sub-logarithmic depth above one dimension. These latter results provide interesting connections to the topic of measurement-induced entanglement phase transitions.
Reference: Gullans, Michael J., et al. "Quantum coding with low-depth random circuits." arXiv preprint arXiv:2010.09775 (2020).

Title: Lower Bounds on Stabilizer Rank
Speaker: Dr. Ben Lee Volk
Speaker Affiliation: The University of Texas at Austin
Date: Tuesday, July 27th, 2021, 4:00pm-5:00pm EDT
Abstract: The stabilizer rank of a quantum state ψ is the minimal integer r such that ψ can be written as a linear combination of r stabilizer states. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n-th tensor power of single-qubit magic states. In this talk we'll present a recent improved lower bound of Ω(n) on the stabilizer rank of such states, and an Ω(sqrt{n}/log n) lower bound on the rank of any state which approximates them to a high enough accuracy. Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of the boolean cube, along with some tools from computational complexity theory.
Reference: Peleg, Shir, Amir Shpilka, and Ben Lee Volk. "Lower Bounds on Stabilizer Rank." arXiv preprint arXiv:2106.03214 (2021).

Title: Linear growth of quantum circuit complexity
Speaker: Jonas Haferkamp
Speaker Affiliation: Freie Universität Berlin
Date: Tuesday, August 10th, 2021, 10:00am-11:00am EDT
Abstract: Quantifying quantum states’ complexity is a key problem in various subfields of science, from quantumcomputing to black-hole physics. We prove a prominent conjecture by Brown and Susskind about how randomquantum circuits’ complexity increases. Consider constructing a unitary from Haar-random two-qubit quantumgates. Implementing the unitary exactly requires a circuit of some minimal number of gates - the unitary’sexact circuit complexity. We prove that this complexity grows linearly in the number of random gates, withunit probability, until saturating after exponentially many random gates. Our proof is surprisingly short, giventhe established difficulty of lower-bounding the exact circuit complexity. Our strategy combines differentialtopology and elementary algebraic geometry with an inductive construction of Clifford circuits.
Reference: Haferkamp, Jonas, et al. "Linear growth of quantum circuit complexity." arXiv preprint arXiv:2106.05305 (2021).

Date: Thursday, September 9th, 2:00-3:00pm EDT

Title: Trapdoor claw-free functions in quantum cryptography

Speaker: Carl Miller

Speaker Affiliation: University of Maryland

Abstract: Trapdoor claw-free functions (TCFs) are central to a recent wave of groundbreaking work in quantum cryptography that was originated by U. Mahadev and other authors.  TCFs enable protocols for cryptography that involve quantum computers and classical communication.  In this expository talk I will present the definition of a TCF and its variants, and I will discuss quantum applications, including the recent paper "Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication" by T. Hiroka et al. (arXiv:2105.05393).


Date: Tuesday, September 14th, 2021, 4:00-5:00pm EDT

Title: How to perform the coherent measurement of a curved phase space

Speaker: Dr. Christopher Sahadev Jackson

Speaker Affiliation: Sandia National Laboratories

Abstract: In quantum optics, the Hilbert space of a mode of light corresponds to functions on a plane called the phase space (so called because it reminded Boltzmann of oscillators in 2-d real space.)  This correspondence offers three important features:  it can autonomously handle quantum theoretical calculations, it allows for the infinite-dimensional Hilbert space to be easily visualized, and it is intimately related to a basic experimental measurement (the so-called heterodyne detection).  Continuous phase space correspondences exist naturally for many types of Hilbert space besides this particular infinite-dimensional one.  Specifically, the two-sphere is a natural phase space for quantum spin systems.  Although well studied on the theoretical and visualization fronts, the corresponding measurement (theoretically referred to as the spin-coherent-state positive-operator-valued measure or SCS POVM) has yet to find a natural way to be experimentally performed.  In this talk, I will review the history of phase space, it’s connection to representation theory, quantization, coherent states, and continuous measurement.  Finally, I will explain how the SCS POVM can be simply performed, independent of the quantization.  Such a demonstration is a fundamental contribution to the theory of continuous quantum measurement which revives several differential-geometric ideas from the classical and modern theory of complex semisimple Lie groups.


Date: Thursday, October 7st, 2021, 10:00-11:00am EDT

Title: Bounding quantum capacities via partial orders and complementarity

Speaker: Christoph Hirche
Speaker Affiliation: Technische Universität München and National University of Singapore

Abstract: Calculating quantities such as the quantum or private capacity of a quantum channel is a fundamental, but unfortunately a generally very hard, problem. A well known class of channels for which the task simplifies is that of degradable channels, and it was later shown that the same also holds for a potentially bigger class of channels, the so called less noisy channels. Based on the former, the concept of approximately degradable channels was introduced to find bounds on capacities for general channels. We discuss how the idea can be transferred to other partial orders, such as less noisy and more capable channels, to find potentially better capacity bounds. Unfortunately these are not necessarily easy to compute, but we show how they can be used to find operationally meaningful bounds on capacities that are based on the complement of the quantum channel and might give a deeper understanding of phenomena such as superadditivity. Finally, we discuss how the framework can be transferred to quantum states to bound the one-way distillable entanglement and secret key of a bipartite state. 


Date: Thursday, October 21st, 2021, 2:00-3:00pm EDT

Title: Clifford groups are not always 2-designs

Speaker: Matthew Graydon
Speaker Affiliation: University of Waterloo

Abstract: A group 2-design is a unitary 2-design arising via the image of a suitable compact group under a projective unitary representation in dimension d.  The Clifford group in dimension d is the quotient of the normalizer of the Weyl-Heisenberg group in dimension d, by its centre: namely U(1).  In this talk, we prove that the Clifford group is not a group 2-design when d is not prime. Our main proofs rely, primarily, on elementary representation theory, and so we review the essentials. We also discuss the general structure of group 2-designs. In particular, we show that the adjoint action induced by a group 2-design splits into exactly two irreducible components; moreover, a group is a group 2-design if and only if the norm of the character of its so-called U-Ubar representation is the square root of two. Finally, as a corollary, we see that the multipartite Clifford group (on some finite number of quantum systems) also often fails to be a group 2-design. This talk is based on joint work with Joshua Skanes-Norman and Joel J. Wallman; arXiv:2108.04200 [quant-ph].


Date: Thursday, November 4th, 2021, 2:00-3:00pm EDT

Title: Google's quantum experiment: a mathematical perspective

Speaker: Gail Letzter
Speaker Affiliation: National Security Agency and University of Maryland, College Park

Abstract: In 2019, Google announced that they had achieved quantum supremacy: they performed a task on their newly constructed quantum device that could not be accomplished using classical computers in a reasonable amount of time.  In this talk, we present the mathematics and statistics involved in the set-up and analysis of the experiment, sampling from random quantum circuits.  We start with the theory of random matrices and explain how to produce a sequence of (pseudo) random unitary matrices using quantum circuits.  We then discuss how the Google team compares quantum and classical approaches using cross entropy and the Porter-Thomas distribution.  Along the way, we present other problems with potential quantum advantage and some of the latest results related to noisy near-term quantum computers. 


Date: Thursday, November 11th, 2021, 2:00-3:00pm EST

Title: Noncommutative Nullstellensatz and Perfect Games
Speaker: Adam Bene Watts

Speaker Affiliation: University of Waterloo

Abstract: The foundations  of classical Algebraic Geometry and Real Algebraic Geometry are the Nullstellensatz and Positivstellensatz.  Over the last two decades the basic analogous theorems for matrix and operator theory (noncommutative variables) have emerged.  In this talk I'll discuss commuting operator strategies for nonlocal games, recall NC Nullstellensatz which are helpful, and then apply them to a very broad collection of nonlocal games.  The main results of this procedure will be two characterizations, based on Nullstellensatz, which apply to games with perfect commuting operator strategies. The first applies to all games and reduces the question of whether or not a game has a perfect commuting operator strategy to a question involving left ideals and sums of squares. The second characterization is based on a new Nullstellensatz. It applies to a class of games we call torically determined games, special cases of which are XOR and linear system games. For these games we show the question of whether or not a game has a perfect commuting operator strategy reduces to instances of the subgroup membership problem. Time permitting, I'll also discuss how to recover some standard characterizations of perfect commuting operator strategies, such as the synchronous and linear systems games characterizations, from the Nullstellensatz formalism.


Date: Thursday, November 18th, 2021, 2:00-3:00pm EST

Title: Quantum Physical Unclonable Functions and Their Comprehensive Cryptanalysis

Speaker: Mina Doosti
Speaker Affiliation: University of Edinburgh

Abstract: A Physical Unclonable Function (PUF) is a device with unique behaviour that is hard to clone due to the imperfections and natural randomness during the manufacturing procedure, hence providing a secure fingerprint. A variety of PUF structures and PUF-based applications have been explored theoretically as well as being implemented in practical settings. Recently, the inherent unclonability of quantum states has been exploited to derive the quantum analogue of PUF as well as new proposals for the implementation of PUF. Nevertheless, the proper mathematical model and security framework for their study was missing from the literature. In this talk, I will present our work on the first comprehensive study of quantum Physical Unclonable Functions (qPUFs) with quantum cryptographic tools. First, I introduce the formal definition and framework of qPUF capturing the quantum analogue of all the requirements of classical PUFs. Then, I introduce a new quantum attack technique based on the universal quantum emulator algorithm of Marvin and Lloyd that we have used to explore the vulnerabilities of quantum and certain classical PUFs leading to general no-go results on the unforgeability of qPUFs. On the other hand, we prove that a large family of qPUFs (called unitary PUFs) can provide quantum selective unforgeability which is the desired level of security for most PUF-based applications. Moreover, I elaborate on the connection between qPUFs as hardware assumptions, and computational assumptions such as quantum pseudorandomness in order to establish the link between these two relatively new fields of research.


Date: Thursday, December 2nd, 2021, 2:00-3:00pm EST

Title: Divide-and-conquer method for approximating output probabilities of constant-depth, geometrically-local quantum circuits

Speaker: Nolan Coble

Speaker Affiliation: University of Maryland, College Park

Abstract: Many schemes for obtaining a computational advantage with near-term quantum hardware are motivated by mathematical results proving the computational hardness of sampling from near-term quantum circuits. Near-term quantum circuits are often modeled as geometrically-local, shallow-depth (GLSD) quantum circuits. That is, circuits consisting of two qubit gates that can act only on neighboring qubits, and that have polylogarithmic depth in the number of qubits. In this talk, we consider the task of estimating output probabilities of GLSD circuits to inverse polynomial error. In particular, we will demonstrate how the output state of a GLSD circuit can be approximated via a linear combination of product states, each of which are produced via new GLSD circuits on approximately half the original number of qubits. We will show how this idea can be used to develop a classical divide-and-conquer algorithm for calculating the output probabilities of a 3D geometrically-local circuit. This talk is based on joint work with Matthew Coudron. 

Reference: N. Coble, M. Coudron.  “Quasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits.”  arXiv:2012.05460


Date: Thursday, January 27th, 2022, 2:00-3:00pm EST

Title: A direct product theorem for quantum communication complexity with applications to device-independent QKD

Speaker: Srijita Kundu

Speaker Affiliation: University of Waterloo

Abstract: We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity in terms of the quantum partition bound for product distributions. The quantum partition or efficiency bound is a lower bound on communication complexity, a non-distributional version of which was introduced by Laplante, Lerays and Roland (2012). For a two-input boolean function, the best result for interactive quantum communication complexity known previously was due to Sherstov (2018), who showed a direct product theorem in terms of the generalized discrepancy. While there is no direct relationship between the maximum distributional quantum partition bound for product distributions, and the generalized discrepancy method, unlike Sherstov’s result, our result works for two-input functions or relations whose outputs are non-boolean as well.  As an application of our result, we show that it is possible to do device-independent quantum key distribution (DIQKD) without the assumption that devices do not leak any information after inputs are provided to them. We analyze the DIQKD protocol given by Jain, Miller and Shi (2020), and show that when the protocol is carried out with devices that are compatible with several copies of the Magic Square game, it is possible to extract a linear (in the number of copies of the game) amount of key from it, even in the presence of a linear amount of leakage. Our security proof is parallel, i.e., the honest parties can enter all their inputs into their devices at once, and works for a leakage model that is arbitrarily interactive, i.e., the devices of the honest parties Alice and Bob can exchange information with each other and with the eavesdropper Eve in any number of rounds, as long as the total number of bits or qubits communicated is bounded.  Based on, which is joint work with Rahul Jain.


Date: Thursday, March 3rd, 2022, 2:00-3:00pm EST

Title: Random quantum circuits transform local noise into global white noise

Speaker: Alexander Dalzell

Speaker Affiliation: Caltech / AWS
Abstract: We examine the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. We will show that, for local noise that is sufficiently weak and unital, the output distribution p_noisy of typical circuits can be approximated by F*p_ideal + (1−F)*p_unif, where F is the probability that no local errors occur, p_ideal is the distribution that would arise if there were no errors, and p_unif is the uniform distribution. In other words, local errors are scrambled by the random quantum circuit and contribute only white noise (uniform output). Importantly, we upper bound the total variation error (averaged over random circuit instance) in this approximation and show it grows with the square root of the number of error locations (rather than linearly).  The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; it was an underlying assumption in complexity-theoretic arguments that low-fidelity random quantum circuits cannot be efficiently sampled classically. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds.


Date: Thursday, March 17th, 2022, 2:00-3:00pm EDT

Title: Geometry of Banach spaces: a new route towards Position Based Cryptography

Speaker: Aleksander Kubicki

Speaker Affiliation: University Complutense of Madrid
Abstract: In this talk I will explain how some techniques coming from the local theory of Banach spaces can be used to obtain claims about the security of protocols for Position Based Cryptography. In particular, I will show how the knowledge about certain geometrical properties of particular Banach spaces (tensor norms on tensor products of Hilbert spaces) can be translated into lower bounds on the resources needed for cheating in this cryptographic task. I will finish pointing out some open problems and future directions suggested by our work. The contents of the talk are based on arXiv:2103.16357 (joint work with M. Junge, C. Palazuelos and D. Pérez-García).


Date: Thursday, March 31st, 2022, 2:00-3:00pm EDT

Title: Post-quantum security of the Even-Mansour cipher

Speaker: Chen Bai

Speaker Affiliation: University of Maryland, College Park
Abstract: The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation E from a public random permutation P: {0,1}^n ->{0,1}^n. It is a core ingredient in a wide array of symmetric-key constructions, including several lightweight cryptosystems presently under consideration for standardization by NIST. It is secure against classical attacks, with optimal attacks requiring q_E queries to E and q_P queries to P such that q_P × q_E ≈ 2^n. If the attacker is given quantum access to both E and P, however, the cipher is completely insecure, with attacks using q_P = q_E = O(n) queries known. In any plausible real-world setting, however, a quantum attacker would have only classical access to the keyed permutation E implemented by honest parties, while retaining quantum access to P. Attacks in this setting with q_P^2 × q_E  ≈ 2^n are known, showing that security degrades as compared to the purely classical case, but leaving open the question as to whether the Even-Mansour cipher can still be proven secure in this natural ``post-quantum'' setting. We resolve this open question, showing that any attack in this post-quantum setting requires q^2_P × q_E  + q_P × q_E^2 ≈  2^n. Our results apply to both the two-key and single-key variants of Even-Mansour. Along the way, we establish several generalizations of results from prior work on quantum-query lower bounds that may be of independent interest.


Date: Thursday, April 21st, 2022, 2:00-3:00pm EDT

Title: Universal efficient compilation: Solovay-Kitaev without inverses
Speaker: Tudor Giurgica-Tiron

Speaker affiliation:  Stanford University

Abstract: The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed. It has been a longstanding open question if efficient algorithmic compilation is possible without this condition. In this work, we provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality, answering this problem in the affirmative, and providing an efficient compilation algorithm in the absence of inverses for both the special unitary, and the special linear groups in arbitrary dimension. The algorithm works by showing that approximate gate implementations of the generalized Pauli group can self-correct their errors. Arxiv: 2112.02040.


Date: Thursday, April 28th, 2022, 2:00-3:00pm EDT

Title: Interactive Proofs for Synthesizing Quantum States and Unitaries

Speaker: Gregory Rosenthal

Speaker Affiliation: University of Toronto

Abstract: Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1.  Our main result is a "state synthesis" analogue of the inclusion 𝖯𝖲𝖯𝖠𝖢𝖤⊆𝖨𝖯: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.  Based on joint work with Henry Yuen.


Date: Thursday, May 5th, 2022, 10:00-11:00am EDT

Title: LDPC Quantum Codes: Recent developments, Challenges and Opportunities

Speaker: Nikolas Breuckmann

Speaker Affiliation: University College London

Abstract: Quantum error correction is an indispensable ingredient for scalable quantum computing. We discuss a particular class of quantum codes called "quantum low-density parity-check (LDPC) codes." The codes we discuss are alternatives to the surface code, which is currently the leading candidate to implement quantum fault tolerance. We discuss the zoo of quantum LDPC codes and discuss their potential for making quantum computers robust with regard to noise. In particular, we explain recent advances in the theory of quantum LDPC codes related to certain product constructions and discuss open problems in the field.


Date: Thursday, May 19th, 10:00-11:00am EDT
Title: Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
Speaker: Sevag Gharibian
Speaker Affiliation: Paderborn University
Abstract: The Quantum Singular Value Transformation (QSVT) is a recent technique that gives a unified framework to describe most quantum algorithms discovered so far, and may lead to the development of novel quantum algorithms. In this paper we investigate the hardness of classically simulating the QSVT. A recent result by Chia, Gilyén, Li, Lin, Tang and Wang (STOC 2020) showed that the QSVT can be efficiently "dequantized" for low-rank matrices, and discussed its implication to quantum machine learning. In this work, motivated by establishing the superiority of quantum algorithms for quantum chemistry and making progress on the quantum PCP conjecture, we focus on the other main class of matrices considered in applications of the QSVT, sparse matrices.
We first show how to efficiently "dequantize", with arbitrarily small constant precision, the QSVT associated with a low-degree polynomial. We apply this technique to design classical algorithms that estimate, with constant precision, the singular values of a sparse matrix. We show in particular that a central computational problem considered by quantum algorithms for quantum chemistry (estimating the ground state energy of a local Hamiltonian when given, as an additional input, a state sufficiently close to the ground state) can be solved efficiently with constant precision on a classical computer. As a complementary result, we prove that with inverse-polynomial precision, the same problem becomes BQP-complete. This gives theoretical evidence for the superiority of quantum algorithms for chemistry, and strongly suggests that said superiority stems from the improved precision achievable in the quantum setting. We also discuss how this dequantization technique may help make progress on the central quantum PCP conjecture.
Joint work with Francois Le Gall (Nagoya University).


Date: Thursday, June 30th 2022, 2:00pm-3:00pm EDT

Title: Rigidity for Monogamy-of-Entanglement Games

Speaker: Eric Culf 

Speaker Affiliation: University of Ottawa

Abstract: In a monogamy-of-entanglement (MoE) game, two players who do not communicate try to simultaneously guess a referee's measurement outcome on a shared quantum state they prepared. We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis and informs the players of her choice.

We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. That is, in order to win optimally, the players' strategy must be of a specific form, namely a convex combination of four unentangled optimal strategies generated by the Breidbart state. We extend this to show that strategies that win near-optimally must also be near an optimal state of this form. We also show rigidity for multiple copies of the game played in parallel.

We give three applications:  (1) We construct for the first time a weak string erasure (WSE) scheme where the security does not rely on limitations on the parties' hardware. Instead, we add a prover, which enables security via the rigidity of this MoE game. (2) We show that the WSE scheme can be used to achieve bit commitment in a model where it is impossible classically. (3) We achieve everlasting-secure randomness expansion in the model of trusted but leaky measurement and untrusted preparation and measurements by two isolated devices, while relying only on the temporary assumption of pseudorandom functions. This achieves randomness expansion without the need to certify entanglement.