In the lab

A few weeks ago I needed the state $| \psi \rangle = \sum_{i \in \mathbb Z^*_N} |i\rangle$ where $\mathbb Z^*_N$ is the group of integers modulo N with multiplication.

I first thought it would be hard to build it. Then I came with this algoritm:

Create the superposition of the first N integers $| \psi_0 \rangle = \sum_{i=0}^{N-1} | i \rangle | 0 \rangle$
Compute the GCD with N, $\quad | \psi_1 \rangle = \sum_{i=0}^{N-1} | i \rangle | \text{gcd}(i,N) \rangle$
Measure the second register.
If the result is 1, $| \psi \rangle$ is in the first register. Else, repeat.

(it succeeds with probability at least 4/15)

I find that delightful. Step 2 is performing Euclid’s Algorithm on a quantum superposition: the oldest algorithm on the most cutting-edge device. I loved it. It made my day.

(I guess this was already known, but it’s fun)

Physics is informational

Posting a question on Mathoverflow is bad for academic productivity.

Old and new