Greg Kuperberg

I am interested in various areas of research, including geometric topology, quantum algebra, and combinatorics. Lately I have also been thinking about quantum computation.

The Jones polynomial is one famous notion in the intersection of geometric topology and quantum algebra. The Jones polynomial is usually computed from a projection of a knot or link, but it only depends on the underlying link; it is a topological invariant. On the algebra side, the Jones polynomial comes from a Lie group called SU(2), or rather, a modification which is called a quantum group. The Jones polynomial can also be defined directly by a simple skein relation. I found another set of skein relations, involving tangled graphs as well as knots and links, for the link invariant corresponding to the Lie group G₂ [1]. All of these invariants are also related to quantum field theory.

My special interest in combinatorics is modern counting problems. One of these is to count the number of n x n alternating-sign matrices. There is a simple formula which reveals that their number is very round; it is a product of small numbers even though the total number is very large. The formula was a long-standing conjecture, first proved by Doron Zeilberger in 1996. I found a shorter proof the same year using some fellow travellers of the Jones polynomial, quantum SU(2) and the Yang-Baxter equation, and a determinant formula from them due to Izergin and Korepin [3].

Quantum computation is the study of a new class of computers that have not yet been built but one day might. Peter Shor established beyond all doubt that that quantum non-determinism is a powerful computational resource; he found a quantum algorithm to factor numbers in polymomial time. I think of this as similar to the fact that classical factoring algorithms are moderately faster with classical non-determinism, i.e., random guessing. In my work, I found a quantum acceleration for the problem of determining whether two functions differ by a hidden shift [4].

Most recently I have been thinking about high-dimensional generalization of Simpson's rule. These formulas are called "cubature rules". Suppose for example that you want to approximate the integral of a function on a 100-dimensional cube by a weighted average. How many values do you need to be exact for quintic polynomials? I found a rule with 2¹⁶ = 65536 points (all inside the cube and with positive weights) [5]. This is the current record for this particular problem.

Selected publications

[1] The quantum G₂ link invariant, Internat. J. Math. 5 (1994), no. 1, 61-85, arXiv:9201302 [math.QA].

[2] Non-involutory Hopf algebras and 3-manifold invariants, Duke Math. J. 84 (1996), 83-129, arXiv:9712047 [q-alg].

[3] Symmetry classes of alternating-sign matrices under one roof, Ann. of Math. (2) 156 (2002), no. 3, 835-866, arXiv:0008184 [math.CO].

[4] A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, arXiv:0302112 [quant-ph].

[5] Numerical cubature using error-correcting codes, arXiv:0402047 [math.NA].

Last updated: 2005/12/14