IQC-QuICS Math-CS Seminar

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.

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.

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.

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.

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.

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.

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 cla

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.

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.

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