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.

**Date:** Thursday, January 27^{th}, 2021,
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

**Link:** https://uwaterloo.zoom.

**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 https://arxiv.org/abs/2106.

**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 16^{th}, 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 22^{nd}, 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 8^{th}, 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 26^{th}, 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 **C**^{d},
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 8^{th}, 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 15^{th}, 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 20^{th}, 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 27^{th}, 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 10^{th}, 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 9^{th},
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 14^{th},
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 7^{st}, 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 21^{st}, 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 4^{th}, 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

**Link: **https://umd.zoom.us/j/97616215362

**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.

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

**Date:** Thursday, December 2^{nd}, 2021,
2:00-3:00pm EST

**Speaker: **Nolan Coble

**Speaker Affiliation: **University of Maryland, College
Park

**Link: **https://umd.zoom.us/j/97341197318

**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.