My husband Peter grew up Unitarian Universalism. Some of his family are Jewish, including a female rabbi, but his grandfather turned away from Judaism and only some of his grandchildren later went back. His mother grew up in a very strict Presbyterian church and became an atheist.

When I was a child we got 'Scientific American' every month and I read a lot of the articles in it but one thing that really fascinated me was this column by Martin Gardner called 'Mathematical Games' that he had every month. I was really very taken by it.

1. Determine all pairs of positive integers $(m, n)$ such that $(1 + x^{n} + x^{2n} + ... + x^{mn})$ is divisible by $(1 + x + x^{2} + ... + x^{m})$.

2. If a and b are two roots of $x^{4} + x^{3} - 1 = 0$, prove that ab is a root of $x^{6} + x^{4} + x^{3} - x^{2} -1 = 0$.

... students were honoured at ceremonies held in Washington, D.C. on June 6 and 7, thanks to a grant from IBM. They received a variety of awards ... After training for three weeks at the US Military Academy, in West Point, the students travelled as a team to Belgrade, Yugoslavia, where they scored first in the International Mathematical Olympiad over twenty other nations.

1. In a finite sequence of real numbers the sum of any seven successive terms is negative and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.

2. Let a and b be positive integers. When $a^{2} + b^{2}$ is divided by $a + b$ the quotient is $q$ and the remainder is $r$. Find all pairs $(a, b)$ given that $q^{2} + r = 1977$.

As an undergraduate at Caltech I took a lot of quantum physics - it was either two or three semesters of it. That's because I was thinking of becoming a physics major but I did not like lab courses enough to do it, so I became a math major instead. But that, I guess, introduced me to quantum mechanics.

A Latin square is an $n \times n$ array of cells each containing one of n distinct symbols such that in each row and column every symbol appears exactly once. We define a partial transversal of length j as a set of n cells with exactly one in each row and column and containing exactly j distinct symbols (this differs from the usual definition in that n - j extra positions are added). Koksma [1969] showed that an $n \times n$ Latin square has a partial transversal of length at least $\large\frac{1}{3}\normalsize (2n + 1)$. This was improved by Drake [1977] to $\large\frac{3}{4}\normalsize n$, and then simultaneously by Brouwer et al. [1978] and by Woolbright [1978] to $n - √n$. This paper will prove a lower bound of $n - c(\log n)^{2}$, where $c \approx 5.53$ (this bound is sharper than $n - √n$ for $n > 2,000,000$), and also give a recursive inequality which can be used to compute a bound sharper than $n - √n$ for much lower values of n. This is still well below Ryser's conjecture of $n - 1$, and $n$ for odd $n$.

Really you needed all of these courses to discover the factoring algorithms. So you needed some things from mathematics, some things from computer science, and some things from physics. I was taking course because I was interested in them, not because I thought they would be ultimately useful for something - that led me to discover this quantum factoring algorithm.

The bin packing problem is: given n items of size between 0 and 1, fit them into the least number of bins such that the sum of the sizes of the items in any bin does not exceed 1. This is an NP-complete problem that has received much study.

In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Best Fit and First Fit when the inputs are uniformly distributed on [0, 1]. We also give a general lower bound for the performance of any on-line bin packing algorithm on this distribution. We prove these results by analysing optimal matchings on points randomly distributed in a unit square. We give a new lower bound for the up-right matching problem.

I would like to thank ... Tom Leighton for his substantial assistance with this work and his insightful observations concerning the relationships between bin packing and planar matching.

When I got out of college I did retail management but I really didn't care at all about the sales numbers! I cared about safety and personnel issues. After a year of working really hard I realised it didn't fit my values so I quit. I moved to Boston to live with my sister who was working on a Ph.D. at MIT and got various temp jobs as a secretary. I worked for Tufts, and did telemarketing at night. My sister's good friend Peter (my future husband) was also in the math program at MIT. I couldn't believe my luck when my sister started dating another Ph.D. student (now my brother-in-law), and Peter and I started dating! After his studies at MIT and a postdoc, Peter worked for AT & T Bell Labs in New Jersey, but eventually decided to work for a university so his kids didn't have to move around a lot (his father was in the Navy). He's now a professor at MIT and enjoying teaching.

The first time that I distinctly remember listening about quantum computing and quantum information theory was during a presentation by Charlie Bennett at Bell Labs [in the late 1980s]. The topic was the quantum key distribution algorithm that he had developed together with Francois Bessette, Gilles Brassard and Louis Salvail. ... in 1992, they published a paper "Experimental Quantum Cryptography" describing the design of the apparatus that they build and the software. This ushered the experimental era of quantum cryptography and a marking moment in the development of quantum computing. However, I was still not thinking about entering/working in this field. The turning point for me was when Umesh Vazirani visited the Bell Labs to give a talk on quantum computing based on his work "Quantum complexity theory" with Ethan Bernstein. ... I have to admit that I didn't get very far until I read Dan Simon's paper "On the power of quantum computation" on the problem that was later named after him (i.e. Simon's problem).

A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor: It is not clear whether this is still true when quantum mechanics is taken into consideration. Several researchers, starting with David Deutsch, have developed models for quantum mechanical computers and have investigated their computational properties. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems. We thus give the first examples of quantum cryptanalysis.

He found many deep and remarkable results prior to 1994 in the analysis of combinatorial algorithms, many with a geometric flavour such as his discovery with Lagarias of a tiling of 10-dimensional Euclidean space by cubes with no common faces. Since 1994, he has been the principal driving force behind the development of quantum computing. First he put it on the map, so to speak, by factoring numbers fast (thus breaking the RSA encryption scheme) by a quantum computer. And second he has led a major assault on error correction and fault tolerance in this new situation, the main obstacles to the realisation of quantum computing.