Discrete Analysis Seminar

In this talk I will discuss one of the main pieces in the proof of Theorem 1.3 in [BBvH21], which is a statement about strong convergence of a general family \(H_1^N,\dots, H_k^N\) of Gaussian random matrices. In particular, this result implies that random matrices obtained by evaluating a non-commutative polynomial in the \(H_i^N\) do not have eigenvalue outliers, and gives some machinery to compute the edge of the bulk. This talk will be self-contained and its key ideas, which can be applied to other random matrix models, go back to a paper of Haagerup and Thorbjornsen from 2005. More specifically, the starting point of the talk will be a bound on the norm of the resolvant of linear pencils with matrix coefficients on the \(H_i^N\) which will be used as a black-box (this bound is proven in [BBvH21] using the interpolation technique that Tarun explained in the previous two talks), from where I will explain how to control quantities of the form \(\|p(H_1^N, \dots, H_k^N)\|\), where \(p\) is a non-commutative polynomial.

Suppose \(M\) is a random matrix and \(M'\) is a matrix we get after applying some noise, when is the top eigenvector of \(M'\) barely different from that of \(M\)? When is it completely uncorrelated? The behavior observed is a phase transition from near-perfect correlation to near-zero correlation as we increase the amount of noise, and the location of this phase transition is now understood for several random matrix models of interest. Notably, when \(M\) is a Wigner matrix, and \(M'\) is obtained by resampling \(k\) random entries of \(M\), the top eigenvectors of \(M\) and \(M'\) are closely aligned when \(k \ll n^{5/3-o(1)}\) and are near-orthogonal when \(k \gg n^{5/3}\). The goal of this talk is to go over a proof of this fact when M is a Gaussian matrix.

We examine the nodal count, namely the number of 0's, of eigenfunctions of quantum graphs. Alon, Band, and Berkolaiko conjecture that the normalized distribution of nodal counts for the first \(n\) eigenfunctions converges to the Gaussian distribution as n goes to infinity. We give their proof of this conjecture for certain limiting cases, and also give a method for computing these distributions efficiently.

In the second part of my talk, we will prove that the nodal surplus is equal to the number of positive eigenvalues of the Hessian on the space of equipartitions. In order to define an equipartition, we examine properties of the zero set of eigenfunctions on quantum graphs. Finally, we will show how this Hessian can be calculated in the torus of phases introduced in the first part of the talk.

To start, I'll first spend some time introducing the CSS code framework for quantum coding, and then describe the new "left-right Cayley complex" construction and how to obtain the rate and distance bounds for its corresponding quantum code. This new construction also has connections to the recent breakthrough of Dinur et al, in which they construct the first known \(c^3\) locally testable codes. Similar ideas can be used both to prove linearly growing minimum distance for the quantum code, and to prove local testability for Dinur et al's classical code.

This week, we'll dive into the actual construction of quantum Tanner codes by Leverrier and Zemor, based on the square Cayley complex of Dinur et al. The main technical challenge we will tackle is understanding the quantum distance of these quantum Tanner codes.

In this talk, we are going to wrap up the series on the Quantum Tanner Codes of (Leverrier and Zemor, 2022) by showing their quantum distance lower bound. First, we will prove the robustness proposition stated in the last talk. After that, we are going to show the distance lower bound for the Expander Codes of (Sipser and Spielman, 1996) as a warm-up toward the quantum distance lower bound. Finally, we will end by proving the quantum distance lower bound.

Final part in this series, see part 3 for abstract.

Say one is given a defective oracle for multiplying matrices over some finite field \(\mathbb{F}\). Specifically, say that it only outputs the correct value of \(AB\) for just 1% of possible pairs of matrices \(A,B\). Can the oracle be repaired? The answer is yes: the oracle can be efficiently turned into a randomized algorithm which computes \(AB\) in all cases with probability 99%.

Carvalho Pinto and Petit recently devised a method for efficiently computing paths of length \(\frac{7}{3}\log_pq\) in the LPS Ramanujan graph \(X^{p,q}\). This approach to the problem in a discrete setting has adaptations to continuous settings such as quantum hardware design, where the path length grows as \(\frac{7}{3}\log_{59}\frac{1}{\varepsilon^3}\) for precision $\varepsilon$. In this talk we will cover these algorithms for factorizations in LPS graphs and \(PU(2)\) (single-qubit gates, via golden gates), and time permitting discuss additional number-theoretic aspects of these constructions.