5 ms·

In 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,

In 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 ago
This 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 ago
  I 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
  - eigenket 5y ago
    Yeah thats pretty much what I thought, I would call this object a spin-chain rather than a quantum walk though. I guess it might have some "walkey" characteristics if you whack the right Hamiltonian on it though.
    - drdeca 5y ago
      Hm, the way I interpreted what you described as a spin-chain seems different to me? I thought when you said "a qubit for each integer" that you meant that if dealing with integers from 1-n to n, that you would have 2n qubits, while what I thought they meant was, say you had n qubits, then the possible positions would be elements of Z/((2^n)Z), so e.g. you could start with |0000> , and then via Hadamard go to (|0000> + |0001>)/\sqrt{2} , and then by incrementing, go to (|0001> + |0010>)/\sqrt{2} and then by Hadamard, go to (|0000> - |0001> + |0010> + |0011>)/2 , and then by decrementing, go to (|1111> - |0000> + |0011> + |0010>)/2 and then repeat the above. So, next step would be another Hadamard, and go to (|1110> - |1111> - |0000> + |0001> + |0010> - |0011> + |0010> + |0011>)/sqrt(8) = (|1110> - |1111> - |0000> + |0001> + 2|0010> )/sqrt(8) Then increment, etc. I think this seems to effectively be using the least significant digit as the coin. I wouldn't say that this has a qubit for each integer, only a qubit for each digit. Would this be a spin chain? Wikipedia turns up the Heisenberg model for that, which looks to be a continuous time thing?
      - eigenket 5y ago
        It can be written as a spin chain, there is a Hamiltonian that generates the unitary you wrote above. Maybe it isn't very natural to do so but I also don't really that its natural to call this thing a "qantum walk" (like how is this thing walking?). The difference between integers / digits is basically just a difference in numbering, I think they're completely equivalent if you replace n with 2^n or log_2(n) or something.
        drdeca 5y ago
        Ah, alright. Thanks. As for how much this resembles walking, if we label the states with integers rather than their binary expansion (uh, maybe assume infinitely many bits, and represent the negative numbers with the ones starting with all 1s?), Well, the state corresponding to a given integer is sent to a linear combination of itself and the states corresponding to integers either one or 2 higher or lower. If this were a transition function for a classical random process (with non-negative coefficients which sum to 1 instead of having absolute value squared-s which sum to 1), that seems to me like it could be called a random walk. hadamard on last digit does, If n is even, |n> -> (|n> + |(n+1)>)/sqrt(2) If n is odd, |n> -> (|(n-1)> - |n>)/sqrt(2) So, combining this with the incrementing, For n even, |n> -> (|(n+1)> + |(n+2)>)/sqrt(2) If n is odd, |n> -> (|(n)> - |(n+1)>)/sqrt(2) Composing with the hadamard again For n even, |n> -> ((|n> -|(n+1)>)/sqrt(2) + (|(n+2)> + |(n+3)>)/sqrt(2) )/sqrt(2) = ( |n> - |(n+1)> + |(n+2)> + |(n+3)>)/2 For n odd, |n> -> (|(n-1)> - |n> - |(n+1)> - |(n+2)>)/2 And so, including the final decrement, the whole operation does For n even, |n> -> ( |(n-1)> - |n> + |(n+1)> + |(n+2)>)/2 For n odd, |n> -> (|(n-2)> - |(n-1)> - |n> - |(n+1)>)/2 Certainly if you measured the result after each application of this, you would observe behavior like a classical random walk of sorts (it would have a bias towards increasing when n is even and a bias towards decreasing when n is odd, but otherwise looks balanced.) Though, I don’t really see much advantage of this over simply taking what is initially being used as the least significant bit of an integer, and instead using it as your coin qubit, and using the rest of the bits for the integer, instead of using this weird mashup of the two (which seems to maybe give something almost but not quite equivalent to it.) Edit: oh! They clarified what they meant, good
- Strilanc 5y ago
  I mean n qubits that are interpreted as a little endian 2s complement integer. Here's a coined walk circuit: https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%80%A2%22%2C%22inc9%22%5D%2C%5B%22~s0ae%22%5D%2C%5B1%2C%22Chance9%22%5D%2C%5B%22Chance10%22%5D%5D%2C%22gates%22%3A%5B%7B%22id%22%3A%22~m9ah%22%2C%22name%22%3A%22x2%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%80%A2%22%2C%22inc9%22%5D%2C%5B%22H%22%5D%2C%5B%22%E2%80%A2%22%2C%22inc9%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~34ha%22%2C%22name%22%3A%22x8%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~m9ah%22%5D%2C%5B%22~m9ah%22%5D%2C%5B%22~m9ah%22%5D%2C%5B%22~m9ah%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~gii%22%2C%22name%22%3A%22x32%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~34ha%22%5D%2C%5B%22~34ha%22%5D%2C%5B%22~34ha%22%5D%2C%5B%22~34ha%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~p9lg%22%2C%22name%22%3A%22x128%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~gii%22%5D%2C%5B%22~gii%22%5D%2C%5B%22~gii%22%5D%2C%5B%22~gii%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~hblb%22%2C%22name%22%3A%22x256%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~p9lg%22%5D%2C%5B%22~p9lg%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~7m3k%22%2C%22name%22%3A%22x64%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~gii%22%5D%2C%5B%22~gii%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~s0ae%22%2C%22name%22%3A%22x499%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%80%A2%22%2C%22inc9%22%5D%2C%5B%22~m9ah%22%5D%2C%5B%22~34ha%22%5D%2C%5B%22~34ha%22%5D%2C%5B%22~gii%22%5D%2C%5B%22~7m3k%22%5D%2C%5B%22~p9lg%22%5D%2C%5B%22~hblb%22%5D%5D%7D%7D%5D%7D https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%2... Here's an uncoined walk circuit: https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B1%2C%22Chance9%22%5D%2C%5B%22Chance10%22%5D%5D%2C%22gates%22%3A%5B%7B%22id%22%3A%22~inrj%22%2C%22name%22%3A%22x4%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22H%22%5D%2C%5B%22inc10%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~6bnk%22%2C%22name%22%3A%22x16%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~inrj%22%5D%2C%5B%22~inrj%22%5D%2C%5B%22~inrj%22%5D%2C%5B%22~inrj%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~jddj%22%2C%22name%22%3A%22x64%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~6bnk%22%5D%2C%5B%22~6bnk%22%5D%2C%5B%22~6bnk%22%5D%2C%5B%22~6bnk%22%5D%5D%7D%7D%5D%7D https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%2... Because an increment gate decomposes into a controlled increment with the least significant qubit as a control and the rest of the qubits as the target, these circuits are actually almost exactly identical in function. Basically take a coined walk, replace H with H*Z, arbitrarily consider the coin qubit to be part of the register, and that's equivalent to an uncoined walk. At least for this particularly simple system.

eigenket 5y ago

This 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 ago
I 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
- eigenket 5y ago
  Yeah thats pretty much what I thought, I would call this object a spin-chain rather than a quantum walk though. I guess it might have some "walkey" characteristics if you whack the right Hamiltonian on it though.
  - drdeca 5y ago
    Hm, the way I interpreted what you described as a spin-chain seems different to me? I thought when you said "a qubit for each integer" that you meant that if dealing with integers from 1-n to n, that you would have 2n qubits, while what I thought they meant was, say you had n qubits, then the possible positions would be elements of Z/((2^n)Z), so e.g. you could start with |0000> , and then via Hadamard go to (|0000> + |0001>)/\sqrt{2} , and then by incrementing, go to (|0001> + |0010>)/\sqrt{2} and then by Hadamard, go to (|0000> - |0001> + |0010> + |0011>)/2 , and then by decrementing, go to (|1111> - |0000> + |0011> + |0010>)/2 and then repeat the above. So, next step would be another Hadamard, and go to (|1110> - |1111> - |0000> + |0001> + |0010> - |0011> + |0010> + |0011>)/sqrt(8) = (|1110> - |1111> - |0000> + |0001> + 2|0010> )/sqrt(8) Then increment, etc. I think this seems to effectively be using the least significant digit as the coin. I wouldn't say that this has a qubit for each integer, only a qubit for each digit. Would this be a spin chain? Wikipedia turns up the Heisenberg model for that, which looks to be a continuous time thing?
    - eigenket 5y ago
      It can be written as a spin chain, there is a Hamiltonian that generates the unitary you wrote above. Maybe it isn't very natural to do so but I also don't really that its natural to call this thing a "qantum walk" (like how is this thing walking?). The difference between integers / digits is basically just a difference in numbering, I think they're completely equivalent if you replace n with 2^n or log_2(n) or something.
      - drdeca 5y ago
        Ah, alright. Thanks. As for how much this resembles walking, if we label the states with integers rather than their binary expansion (uh, maybe assume infinitely many bits, and represent the negative numbers with the ones starting with all 1s?), Well, the state corresponding to a given integer is sent to a linear combination of itself and the states corresponding to integers either one or 2 higher or lower. If this were a transition function for a classical random process (with non-negative coefficients which sum to 1 instead of having absolute value squared-s which sum to 1), that seems to me like it could be called a random walk. hadamard on last digit does, If n is even, |n> -> (|n> + |(n+1)>)/sqrt(2) If n is odd, |n> -> (|(n-1)> - |n>)/sqrt(2) So, combining this with the incrementing, For n even, |n> -> (|(n+1)> + |(n+2)>)/sqrt(2) If n is odd, |n> -> (|(n)> - |(n+1)>)/sqrt(2) Composing with the hadamard again For n even, |n> -> ((|n> -|(n+1)>)/sqrt(2) + (|(n+2)> + |(n+3)>)/sqrt(2) )/sqrt(2) = ( |n> - |(n+1)> + |(n+2)> + |(n+3)>)/2 For n odd, |n> -> (|(n-1)> - |n> - |(n+1)> - |(n+2)>)/2 And so, including the final decrement, the whole operation does For n even, |n> -> ( |(n-1)> - |n> + |(n+1)> + |(n+2)>)/2 For n odd, |n> -> (|(n-2)> - |(n-1)> - |n> - |(n+1)>)/2 Certainly if you measured the result after each application of this, you would observe behavior like a classical random walk of sorts (it would have a bias towards increasing when n is even and a bias towards decreasing when n is odd, but otherwise looks balanced.) Though, I don’t really see much advantage of this over simply taking what is initially being used as the least significant bit of an integer, and instead using it as your coin qubit, and using the rest of the bits for the integer, instead of using this weird mashup of the two (which seems to maybe give something almost but not quite equivalent to it.) Edit: oh! They clarified what they meant, good
Strilanc 5y ago
I mean n qubits that are interpreted as a little endian 2s complement integer. Here's a coined walk circuit: https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%80%A2%22%2C%22inc9%22%5D%2C%5B%22~s0ae%22%5D%2C%5B1%2C%22Chance9%22%5D%2C%5B%22Chance10%22%5D%5D%2C%22gates%22%3A%5B%7B%22id%22%3A%22~m9ah%22%2C%22name%22%3A%22x2%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%80%A2%22%2C%22inc9%22%5D%2C%5B%22H%22%5D%2C%5B%22%E2%80%A2%22%2C%22inc9%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~34ha%22%2C%22name%22%3A%22x8%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~m9ah%22%5D%2C%5B%22~m9ah%22%5D%2C%5B%22~m9ah%22%5D%2C%5B%22~m9ah%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~gii%22%2C%22name%22%3A%22x32%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~34ha%22%5D%2C%5B%22~34ha%22%5D%2C%5B%22~34ha%22%5D%2C%5B%22~34ha%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~p9lg%22%2C%22name%22%3A%22x128%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~gii%22%5D%2C%5B%22~gii%22%5D%2C%5B%22~gii%22%5D%2C%5B%22~gii%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~hblb%22%2C%22name%22%3A%22x256%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~p9lg%22%5D%2C%5B%22~p9lg%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~7m3k%22%2C%22name%22%3A%22x64%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~gii%22%5D%2C%5B%22~gii%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~s0ae%22%2C%22name%22%3A%22x499%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%80%A2%22%2C%22inc9%22%5D%2C%5B%22~m9ah%22%5D%2C%5B%22~34ha%22%5D%2C%5B%22~34ha%22%5D%2C%5B%22~gii%22%5D%2C%5B%22~7m3k%22%5D%2C%5B%22~p9lg%22%5D%2C%5B%22~hblb%22%5D%5D%7D%7D%5D%7D https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%2... Here's an uncoined walk circuit: https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B%22~jddj%22%5D%2C%5B1%2C%22Chance9%22%5D%2C%5B%22Chance10%22%5D%5D%2C%22gates%22%3A%5B%7B%22id%22%3A%22~inrj%22%2C%22name%22%3A%22x4%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22H%22%5D%2C%5B%22inc10%22%5D%2C%5B%22H%22%5D%2C%5B%22inc10%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~6bnk%22%2C%22name%22%3A%22x16%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~inrj%22%5D%2C%5B%22~inrj%22%5D%2C%5B%22~inrj%22%5D%2C%5B%22~inrj%22%5D%5D%7D%7D%2C%7B%22id%22%3A%22~jddj%22%2C%22name%22%3A%22x64%22%2C%22circuit%22%3A%7B%22cols%22%3A%5B%5B%22~6bnk%22%5D%2C%5B%22~6bnk%22%5D%2C%5B%22~6bnk%22%5D%2C%5B%22~6bnk%22%5D%5D%7D%7D%5D%7D https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%2... Because an increment gate decomposes into a controlled increment with the least significant qubit as a control and the rest of the qubits as the target, these circuits are actually almost exactly identical in function. Basically take a coined walk, replace H with H*Z, arbitrarily consider the coin qubit to be part of the register, and that's equivalent to an uncoined walk. At least for this particularly simple system.