Colloquia take place online and consist of talks dedicated to topics of interest in Quantum Computation and Quantum Complexity Theory.
Our goal is to create an inclusive forum for discussion and rapid dissemination of ideas. Anyone interested in quantum computing is welcome to join.
Subscribe to our mailing list
for talk announcements.
Some of the talks are recorded and made available at the Colloquium's YouTube Channel
28 March 2023, 3pm London time - Video of Talk
(University of Maryland)
Quantum divide and conquer
The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem into smaller subproblems, along with some auxiliary work, to give a recurrence relation for the classical complexity. We describe a quantum divide-and-conquer framework that, in certain cases, yields quantum speedup through an analogous recurrence relation for the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems, such as (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence. Based on joint work with Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang (arXiv:2210.06419).
28 February 2023, 4pm London time - Video of talk
The sum-of-squares for fermionic systems, and the SYK model
The central problem in physics and quantum chemistry is to determine properties of the ground state of an interacting system of fermions. As a quantum mechanical problem, there may be no efficient classical witness to the ground state energy, or even to an approximation of that energy. A commonly considered witness is a so-called "Gaussian state", or free fermion wavefunction. As a prominent example , the Sachdev-Ye-Kitaev (SYK) model has no Gaussian state which achieves a good approximation to the energy; this model is sometimes considered as one of the "most entangled" or "most strongly interacting" models possible. I will discuss applications of the sum-of-squares method to this model. Sum-of-squares is a semidefinite programming relaxation. I will show that this method can give classically efficient constant-factor lower bounds on the energy, and it inspires a quantum algorithm which gives constant-factor upper bounds. Joint work with R. O'Donnell.
25 October 2022, 2pm London time - Video of talk
(University of Chicago)
Quantum pseudorandom states are efficiently preparable
states that are indistinguishable from truly Haar random states to an
efficient observer. First defined by Ji, Liu and Song, such states
have found a wide variety of applications in areas such as
cryptography and quantum gravity. A fundamental question is exactly
how much entanglement is required to create such states. Haar-random
states, as well as t-designs, exhibit near-maximal
entanglement. Here we provide the first construction of pseudorandom
states with only polylogarithmic entanglement entropy across an
equipartition of the qubits, which is the minimum possible. Our
construction can be based on any one-way function secure against
quantum attack. We additionally show that the entanglement in our
construction is fully "tunable".
More fundamentally, our work calls into question to what extent
entanglement is a "feelable" quantity of quantum systems. Inspired by
recent work of Gheorghiu and Hoban, we define a new notion which we
call "pseudoentanglement", which are ensembles of efficiently
constructable quantum states which hide their entanglement entropy. We
show such states exist in the strongest form possible while
simultaneously being pseudorandom states.
Based on joint work with Adam Bouland, Soumik Ghosh, Umesh Vazirani
and Zixin Zhou.
19 August 2022, 2pm London time -
Video of talk
Mean Estimation When You Have The Source Code; or, Quantum Monte Carlo Methods
Suppose y is a real random variable, and one is given access to "the code" that generates it (for example, a randomized or quantum circuit whose output is y). We give a quantum procedure that runs the code O(n) times and returns an estimate for E[y] with optimal dependence on n for quantum algorithms.
The central subroutine for our result is essentially Grover's algorithm but with complex phases.
Joint work with Robin Kothari (Microsoft).
1 July 2022, 2pm London time -
Video of talk
Ronald de Wolf
Quantum machine learning from a theoretical perspective
Machine learning can be enhanced by quantum computing, both by allowing quantum data and by having quantum speedups for the optimization process that finds a good model for given data. This talk will examine both aspects, from the perspective of theoretical computer science.