Why good translations matter

Sonnet by Keats, On First Looking into Chapman’s Homer. Keats was familiar with other translations of Homer, such as the one by Pope, but reading Chapman’s work was a different experience altogether:

Much have I travell’d in the realms of gold,
    And many goodly states and kingdoms seen;
    Round many western islands have I been
Which bards in fealty to Apollo hold.
Oft of one wide expanse had I been told
    That deep-brow’d Homer ruled as his demesne;
    Yet did I never breathe its pure serene
Till I heard Chapman speak out loud and bold:
Then felt I like some watcher of the skies
    When a new planet swims into his ken;
Or like stout Cortez when with eagle eyes
    He star’d at the Pacific—and all his men
Look’d at each other with a wild surmise—
    Silent, upon a peak in Darien.

Shor’s algorithm

I’d learnt Shor’s algorithm in a course a few years ago, but (as usual) forgot all about it.

Yesterday I reread it from the Algorithms textbook of Dasgupta, Papadimitriou, and Vazirani, only because someone claimed that their Chapter 10 on Quantum algorithms was incomprehensible, so here is a very vague sketch of it before I forget it again. (For a popular account, which Peter Shor called “the best job of explaining quantum computing to the man on the street that I’ve seen”, see Scott Aaronson’s post.)

1. Quantum

The quantum magic in Shor’s algorithm, the part that uses something unique to quantum computation, is simply the following fact: a quantum computer can perform the quantum Fourier transform in O(log² N) time.

That is, given a “superposition” , in O(log²N) steps the quantum fourier-magic-thing produces the superposition with . Of course, it just produces this superposition and does not output it; if we try to measure this we’d get only one of the states, specifically with probability .

(I will not write here how this QFT works. It uses the Hadamard gate etc., and roughly, what would be two recursive calls in the usual FFT can be done with just one operation here.)

All the other ideas are classical (i.e. non-quantum).

2. Fourier transform of periodic vectors

Suppose is some factor of . It can be proved with some straightforward calculation that if (viewed as a vector/sequence) is periodic with period , with the only nonzero coefficients being , then its Fourier transform is also periodic with period — the only nonzero coefficients are .

The point is that if we “measure” this, then we get one of the multiples of at random, so by taking a few measurements, we can figure out and therefore .

3. Factoring reduces to order-finding

We can see from number theory (use the Chinese remainder theorem) that if N is composite (etc.), then with probability at least 1/2, a random x modulo N has an even order r (i.e. the smallest positive integer such that ) such that is a nontrivial square root of 1 mod N. So if we can find the order , then we have such that so with neither factor being 0, so we get a factor of . So all we need to be able to do is find the order.

Modulo , pick any and consider the function . If is the order of mod then the function is periodic with period . The algorithm runs as follows:

1. First, make a superposition normalised. (Think of the as two quantum “registers”.) (This is made by starting with just and taking its Fourier transform!)
2. Now “compute” (for some random ) on it. This gives the superposition .
3. Then measure the second register. This gives a random value from the second register, but more importantly, it make the first register be a superposition of only those values that are compatible with this value — therefore, periodic with period .
4. Now do the Fourier transform on the first and measure it, so we get a random multiple of .

Doing all this the right number of times with the right constants does it. I’ve cheated in all this, because obviously the N we’re trying to factor is not a power of 2, but that can be taken care of.

I think Shor’s big idea (over Simon’s algorithm for period-finding) was in coming up with this function f whose period would give the factors of N. But I may be wrong.

Equivalent forms of the Riemann hypothesis

1. Let be the nth harmonic number, i.e. . Then, the Riemann hypothesis is true if and only if

   

   The left-hand side, which is the sum of the divisors of , is also denoted .
   See Jeffrey Lagarias, An Elementary Problem Equivalent to the Riemann Hypothesis [PDF, arXiv.

2. Define the Redheffer matrix to be the 0-1 matrix with entries (and 0 otherwise). Then the Riemann hypothesis is true if and only if for all .

For more, see Equivalences to the Riemann hypothesis (by J. Brian Conrey and David W. Farmer), and Consequences of the Riemann hypothesis (MathOverflow)

For fun: claimed [dis/]proofs.

Quote found via rjlipton:

The Riemann Hypothesis is the most basic connection between addition and multiplication that there is, so I think of it in the simplest terms as something really basic that we don’t understand about the link between addition and multiplication.
—Brian Conrey