Loïck
on Thursday, July 15 2010, 20:48
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)

Comments

#1 Fred Grosshans
Friday, July 16 2010, 10:22

Question form a stupid physicist :
I don't understand the difference between |ψ⟩ and |ψ₀⟩. They look the same to me !

#2 tonio
Friday, July 16 2010, 17:59

@Fred, I think that $\mathbb Z^*_N$ does not contain the divisors of N.

#3 Loïck
Thursday, July 22 2010, 01:12

@Fred: Tonio is right.

@Tonio: well-tried. I have not enabled LaTeX in comments… yet. The plugin needs to be hacked.

Physics is informational

Old and new

Comments