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.

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

**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 2^{nd}, 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.

**Date:** Thursday, January 27^{th}, 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 https://arxiv.org/abs/2106.

**Date:** Thursday, March 3^{rd}, 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^{ }17^{th},
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 31^{st}, 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 21^{st},
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 5^{th}, 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 30^{th} 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.

**Date:** Thursday, July 21^{th}, 2022,
2:00pm-3:00pm EDT

**Title:** A sufficient family of necessary
inequalities for the quantum marginals problem

**Speaker:** TC Fraser

**Speaker Affiliation**: Perimeter Institute,
Waterloo, Ontario

**Abstract:** The quantum marginals problem (QMP)
aims to understand how the various marginals of a joint quantum state are
related to one another by deciding whether or not a given collection of
marginals is compatible with some joint quantum state. Although existing
techniques for the QMP are well developed for the special case of disjoint
marginals, the same is not true for the generic case of overlapping marginals.
The leading technique for the generic QMP, published by Yu et. al. (2021),
resorts to evaluating a hierarchy of semidefinite programs.

In this talk, I will introduce a slightly different approach to the QMP by demonstrating how to construct a simple hierarchy of operator inequality constraints each of which are necessarily satisfied by any collection of marginals of a joint quantum state. Then, using state-estimation techniques and large deviation theory, I will sketch the proof that the satisfaction of these inequalities is additionally sufficient for a collection of marginals to be compatible with some joint quantum state.

**Date: **Thursday, August 4th 2022
at 10:00am-11:00am EDT

**Title:** Strong converse bounds for compression of mixed states

**Speaker:** Zahra Khanian

**Speaker Affiliation:** Technical University of Munich

**Abstract:** The optimal rates for compression of mixed states was found
by Koashi and Imoto in 2001 for the blind case and by Horodecki and
independently by Hayashi for the visible case respectively in 2000 and
2006. However, it was not known so far whether the strong converse property
holds for these compression problems. In this work, we show that the strong
converse holds for the blind compression scheme. For the visible scheme, the
strong converse holds up to the continuity of the regularized Renyi entanglement
of purification.

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

**Title: **Uncertainty Relations from Graph
Theory

**Speaker: **Kiara Hansenne

**Speaker Affiliation: **Universität Siegen

**Abstract: **Quantum measurements are inherently probabilistic.
Further defying our classical intuition, quantum theory often forbids us to
precisely determine the outcomes of simultaneous measurements. This phenomenon
is captured and quantified through uncertainty relations. Although studied
since the inception of quantum theory, this problem of determining the possible
expectation values of a collection of quantum measurements remains, in general,
unsolved.

In this talk, we will go over some basic notions of graph theory that will allow us to derive uncertainty relations valid for any set of dichotomic quantum observables. We will then specify the many cases for which these relations are tight, depending on properties of some graphs, and discuss a conjecture for the untight cases. Finally, we will show some direct applications to several problems in quantum information, namely, in constructing entropic uncertainty relations, separability criteria and entanglement witnesses.

**Date:** Thursday,^{ }August 18^{th},
2022, 2:00-3:00pm EDT

**Title:** Tight bounds for Quantum Learning and
Testing without Quantum Memory

**Speaker: **Jerry Li

**Speaker Affiliation:** Microsoft Research

**Abstract: **In this talk, we consider two fundamental tasks
in quantum state estimation, namely, quantum tomography and quantum state
certification. In the former, we are given n copies of an unknown mixed state
rho, and the goal is to learn it to good accuracy in trace norm. In the latter,
the goal is to distinguish if rho is equal to some specified state, or far from
it. When we are allowed to perform arbitrary (possibly entangled) measurements
on our copies, then the exact sample complexity of these problems is
well-understood. However, arbitrary measurements are expensive, especially in
terms of quantum memory, and impossible to perform on near-term devices. In
light of this, a recent line of work has focused on understanding the
complexity of these problems when the learner is restricted to making incoherent
(aka single-copy) measurements, which can be performed much more efficiently,
and crucially, capture the set of measurements that can be performed without
quantum memory. However, characterizing the copy complexity of such algorithms
has proven to be a challenging task, and closing this gap has been posed as an
open question in various previous papers.

In this talk, we give tight bounds on the sample complexity of these problems.
More specifically, we show improved lower bounds for both problems which (essentially)
match the existing upper bounds in the literature. Our techniques for both
problems are based on new reductions to matrix martingale concentration which
we believe may be of independent interest.

**Date:** Thursday,^{ }August 25^{th},
2022, 2:00-3:00pm EDT

**Title:** Publicly Verifiable Quantum Money from
Random Lattices

**Speaker: **Andrey Boris Khesin

**Speaker Affiliation:** Massachusetts Institute of
Technology

**Abstract: **Publicly verifiable quantum money is a
protocol for the preparation of quantum states that can be efficiently verified
by any party for authenticity but is computationally infeasible to counterfeit.
We develop a cryptographic scheme for publicly verifiable quantum money based
on Gaussian superpositions over random lattices. We introduce a
verification-of-authenticity procedure based on the lattice discrete Fourier
transform, and subsequently prove the unforgeability of our quantum money under
the hardness of the short vector problem from lattice-based cryptography.