4 ms·
Yeah, 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 imp
by Strilanc 5y ago
Yeah, 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 5y 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 5y 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 5y 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 5y 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 5y agoIf there is no additional degree of freedom the walk has to be trivial (assuming homogeneity).
- Strilanc 5y 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 5y 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.
- drdeca 5y agoI imagine they mean there is a collection of qubits interpreted as storing an integer (would be storing an integer if they were mere bits) And so the qubit for the least significant bit, would be the one for the 1s place. I could be wrong though