Applied Math Colloquium

The standard model of quantum computing assumes that the state of a quantum computer can be initialized to a fixed starting state (for example, 00...00). However, this is not possible in the most popular technology for implementing quantum computers, liquid-state bulk NMR. There, the starting state is a probability distribution over different quantum states. Adjusting quantum algorithms to this setting is a challenging problem.

We consider the setting in which the starting state consists of $k$ quantum bits that can be initialized to $0$ state and n-k quantum bits that have completely random starting states. This setting is called $k$-clean qubit model. We show two results for this setting. First, we observe that NC1 (the class of functions computed by polynomial-time, log-depth circuits) can be computed in this model. Second, we show that, under certain constraints, there is no general method for simulating an arbitrary m-quantum bit standard quantum computation by a quantum computation in the $k$-clean qubit model, unless $m=O(k+ log n)$. The first result follows from Barrington's theorem about simulating NC1 with branching programs. The second result is shown by a reduction to the representation theory of the symmetric group.

Growth processes have an extensive history both in the probability literature and the physics literature. A basic problem is to describe the growth of an interface when the underlying dynamics have both deterministic and stochastic components. The existence of a limiting shape of this interface has been known, in a variety of models, for some time. Given these results, a natural question is to describe the fluctuations about the limiting shape. It has been recently discovered that the limiting distribution functions that describe the fluctuations are precisely those arising in random matrix theory. After a brief introduction to random matrix theory, these developments will be summarized.

Recently Baik, Deift and Johansson showed that the number of boxes in the first row of a random Young diagram of size N behaves statistically as N becomes large, like the largest eigenvalue of a random matrix. They also conjectured that, in the large N limit, the number of boxes in the first k rows should behave like the first k eigenvalues of a random matrix, and in a later publication they verified this conjecture for the second row. The full conjecture was proved subsequently, first by Okounkov, and then independently by Borodin-Okounkov-Olshanski and Johansson. The speaker will discuss some recent related developments.

The topics of the title are intimately connected to each other, and to a host of other topics, in beautiful ways. It has been known since the time of Kirchhoff (1847) that one can solve electrical network problems by using various probabilities associated to choosing a spanning tree at random (uniformly) from a finite graph. Algorithms for generating a random spanning tree are connected to generation and counting of states in arbitrary Markov chains.

A "thermodynamic" limit defines the model on infinite graphs. Here, the connections to potential theory deepen and allow one to resolve many questions, such as the number of components and the topology of components. We will describe work on random spanning trees of Aldous, Benjamini, Broder, Burton, Kenyon, Kesten, Kirchhoff, Pemantle, Peres, Schramm, Wilson, and the speaker. Because of connections to other areas such as domino tilings, matroids, amenability, percolation, L^2-Betti numbers, Brownian motion, and conformal maps, there are still an enormous number of fascinating open questions. No background in any area will be assumed for the talk.