Freedman CMSA Seminar

2:00-3:30 pm ET

Speaker: Mike Freedman, Harvard CMSA

Title: Detecting hidden structures in linear maps

Abstract: I’ll consider the problem of detecting spectral features and tensor structures within linear maps both in a quantum and classical contexts. In the quantum context there is the question of whether a Hamiltonian is local, and if so, local in distinct coordinate systems (a “duality”). Also, in the case of a unitary described by a quantum circuit, does it possess unusual spectral features or tensor structure? In ML one optimizes many linear maps. How would we know – and would we care – if the resulting maps (approximately) tensor factored?

3:30-4:00 pm ET

Break/Discussion

4:00-5:30 pm ET

Speaker: Ryan O’Donnell, Carnegie Mellon University

Title: Quartic quantum speedups for planted inference

Abstract: Consider the following task (“noisy 4XOR”), arising in CSPs, optimization, and cryptography. There is a ‘secret’ Boolean vector x in {-1,+1}^n. One gets m randomly chosen pairs (S, b), where S is a set of 4 coordinates from [n] and b is x^S := prod_{i in S} x_i with probability 1-eps, and -x^S with probability eps. Can you tell the difference between the cases eps = 0.1 and eps = 0.5?

It depends on m. The best known algorithms use the “Kikuchi method” and run in time ~n^L when m ~ n^2/L. We will review this method, and also show that the running time can be improved to roughly n^{L/4} with a quantum algorithm.

Joint work with Alexander Schmidhuber (MIT), Robin Kothari (Google), and Ryan Babbush (Google).