8 ms·
I'm a bit unclear about what the process they are using for the quantum random walk. Like, after 2 steps, what is the state that it is in? Presumably not just (
by drdeca 6y ago
I'm a bit unclear about what the process they are using for the quantum random walk.
Like, after 2 steps, what is the state that it is in?
Presumably not just (1/2)|-1> + sqrt(1/2)|0> + (1/2)|1> , because then that would seem to just give the same behavior as the classical random walk.
The linked code has a Hadamard gate, which it cnot's onto some other qubit, and then negates, and then cnots onto some third quibit.
Ah, the wikipedia article at https://en.wikipedia.org/wiki/Quantum_walk https://en.wikipedia.org/wiki/Quantum_walk makes what it is describing much clearer!
- Strilanc 6y agoYeah, the descending arrows diagram they show in the post can't be correct because there are cases where two outputs overlap at only one spot. That makes it impossible for them to be orthogonal which breaks reversibility.
- eigenket 6y agoI think thats fine, you just need the spin (what gets calls the "coin") degree of freedom states to be orthogonal for the bit that came from the left and the bit that came from the right. A quantum walk with a unitary like U = sum_i |0><0| ⊗ |i><i+1| + |1><1| ⊗ |i><i-1| where the first Hilbert space is a qubit and the second is L^2(Z), an integer-valued "position". Will do this. Two states |a>|-1> and |b>|+1> will after one time step find themselves overlapping at exactly one lattice point (at |0>) but the coin degrees of freedom will keep them orthogonal. Edit: in case of unicode issues the "⊗" symbol is supposed to be \otimes, a tensor product.
- Strilanc 6y agoIn a quantum walk the locations typically correspond to states, not to qubits. You're right that turning them into qubits would allow the diagram to work, but then I don't think it would match up with the "vampire fangs".
- eigenket 6y agoI don't understand this comment at all. Let me clarify my point slightly. The quantum walk is a unitary operator acting on a Hilbert space H consisting of two parts H_spin and H_space H = H_spin ⊗ H_space In this example H_spin is just a qubit and H_space is L^2(Z). In my example above the |0><0| and |1><1| are projectors acting on the spin degree of freedom (the first Hilbert space) and the sum_i |i><i+1| and sum_i |i><i-1| are shift operators acting on the space degree of freedom (the second Hilbert space). If you take the unitary I wrote and do the iteration U (H⊗I) U (H⊗I) U (H⊗I) U (H⊗I) ... U (H⊗I) where U (H⊗I) is the Hadamard operator on the spin Hilbert space and I is the identity on the space part you get exactly the quantum walk that gives the "fangs" picture.
- Strilanc 6y agoSorry, I misread your comment initially. Yes, if you have an additional degree of freedom that is not being plotted (a coined walk), then the overlap is fine.
- eigenket 6y agoIf there is no additional degree of freedom the walk has to be trivial (assuming homogeneity).
- Strilanc 6y agoIn a coined walk you apply a hadamard to the least significant qubit of an integer register, then increment the register, hadamard the least significant qubit, decrement the register, and repeat. Although there is no additional degree of freedom, you are alternating between two non-commuting effects.
- eigenket 6y agoThis seems completely different to the sorts of walks I'm used to. When you say "qubit of an integer register" what are you actually talking about here? Do you have a qubit for each integer like a spin chain or something? The sorts of quantum walks I'm used to are exactly the ones in the article and are also mentioned in the wikipedia page here. https://en.wikipedia.org/wiki/Quantum_walk#Discrete_time https://en.wikipedia.org/wiki/Quantum_walk#Discrete_time The example given on the wiki page is the classic example that gets called a "coined walk" in the literature.