Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Can someone please explain Scott Aaronson lecture #9?

  1. Feb 22, 2017 #1
    Here is a link to a lecture by Scott Aaronson.

    About half way in the lecture he talks about the "qubit". In that section he introduces a 2x2 unitary matrix which rotates a vector by 45°. He applies that transformation to the state |0>. When he does that he gets the mixed state 1.0/√2 ( |0>, |1> ). I understand where that mixed state comes form.

    Next he applies the transformation another time to the mixed result and he ends up with the state |1>. I understand where that comes from also.

    It is his next step that I do not understand. He displays a binary tree which is supposed to show all the possible "paths" when applying the transformation twice. Where does that tree come from? I see two "paths" but I do not see 4 paths. Where does the path that results in the state -|0> come from?

    EDIT: I think I see where the state -|0> comes from. If you apply the transformation a third time you get the mixed state 1.0/√2 ( -|0>, |1> ) and if you apply the transformation a fourth time you get the state -|0>. I am still not sure how he constructs that tree.

    Here is screen capture of the tree...

    Last edited: Feb 22, 2017
  2. jcsd
  3. Feb 22, 2017 #2


    User Avatar
    Gold Member

    Are you familiar with the Quincunx ? If you imagine that the tree is a two-level quincunx machine, but instead of multiplying probabilites at each branch, use the square of the products of amplitudes instead - tnen some paths are never taken. The matrix in the lecture is sometimes called the 'quincunx matrix'.
    Last edited: Feb 22, 2017
  4. Feb 22, 2017 #3
    Thanks for your response. I will look into it.

    I might have figured out what the tree represents.

    At the root of the tree is the state |0>. If you apply the transformation to that state you get a mixed state, ( |0>, |1> ) (except for the constant 1/√2). So the level below the root shows the mixed state you get if you apply the transformation to the state \0>.

    In the second level we have two states, |0> and |1>.

    The third level is obtained by applying the transformation to each of the states in the second level.

    We already know what the children for the state |0> are, so they are just copied to level 3. However, applying the transform to the state |1> yields a new mixed state which is ( -|0> and |1> ) and that mixed state is then shown as the children of the |1> state in the third level.

    I seriously doubt that this is the correct interpretation for how the tree is constructed, but it is one way in which it can be constructed. I think it is a complete tree. I would like to understand this better.
  5. Feb 22, 2017 #4


    User Avatar
    Gold Member

    I'm not so sure now that there can be a 'quantum quincunx'.

    I would expect it to be

  6. Feb 22, 2017 #5

    How did you get that?
  7. Feb 22, 2017 #6


    User Avatar

    Staff: Mentor

    Careful - these are not mixed states, they are still pure states. The only reason that ##|0\rangle## looks different than ##\sqrt{2}/2(|0\rangle+|1\rangle)## (they're different states, but that's not why they look different) is that we've chosen a basis that makes it look that way. As an analogy: there's nothing qualitatively different between "northwest" (a linear combination of north and west) and "north"; we could have chosen different basis vectors and then north would have been the linear combination.

    Not calling the superposition a "mixed" state is not a quibble. This distinction is fundamental to understanding how QM works.
    You were right until you started doubting - it's right. The easiest way to see this is to do the algebra: calculate ##\phi=U|\psi\rangle##, then apply ##U## to ##\phi##. You'll end up with four terms corresponding to the four leaves of the tree. Look at where they came from, compare with the tree, and it will all make sense.
  8. Feb 23, 2017 #7


    User Avatar
    Science Advisor

    I like it! :smile:
  9. Feb 23, 2017 #8
    Thank you for your explanation.

    I have modified the tree to make it clear what is going on.

    Last edited: Feb 23, 2017
  10. Feb 23, 2017 #9


    Staff: Mentor

    That's not the right way to construct the tree.

    The top node of the tree is just ##\vert 0 \rangle##.

    The second row of the tree is ##U \vert 0 \rangle##, which becomes two nodes, ##\vert 0 \rangle## and ##\vert 1 \rangle##. (Note that there are factors of ##1 / \sqrt{2}## which are being left out, because they don't matter for the argument Aaronson is making.)

    The third row of the tree applies ##U## to the two nodes in the second row. That becomes four nodes: two on the left for ##U \vert 0 \rangle## (applying ##U## to the left node of the second row) and two on the right for ##U \vert 1 \rangle## (applying ##U## to the right node of the second row). So to figure out what the right two nodes in the third row are, you need to calculate what ##U \vert 1 \rangle## is. That's what Aaronson did to get the third row of his tree.
  11. Feb 23, 2017 #10
    That is what I was trying to show. At the root of the tree you apply U to the state |0>. In the second level of the tree you apply U a second time. The third level is the result of applying U twice.

    (If I were to apply U a third time I would add U's to the third row and and a fourth row showing the third rows children...)
  12. Feb 23, 2017 #11


    Staff: Mentor

    Ok, then what four nodes does applying ##U## twice to the top node of the tree result in? Aaronson says it results in the four nodes ##\vert 0 \rangle##, ##\vert 1 \rangle##, ##- \vert 0 \rangle##, and ##\vert 1 \rangle##; then the first and third nodes cancel and you're just left with the state ##\vert 1 \rangle##.

    In your OP, you interpreted the last two nodes as coming from ##U## applied to ##\vert 1 \rangle## (the right node in the second row). That looks correct to me. So I think Nugatory was correct when he said you were right until you started doubting.
  13. Feb 23, 2017 #12
    When you apply U to the root node you only get two children. When you apply U to each of those two children you get the 4 leaf nodes. The 4 leaf nodes are the 4 states you mention.
  14. Feb 23, 2017 #13


    Staff: Mentor

    Yes, I know that. And the four leaf nodes are the ones Aaronson described. Do you agree with that?
  15. Feb 23, 2017 #14


    Staff: Mentor

    Correction: in your post #3.
  16. Feb 23, 2017 #15
  17. Feb 23, 2017 #16


    Staff: Mentor

    Then I think your question is answered: we agree on how the tree is constructed, and we see how the tree explains why the ##\vert 0 \rangle## state drops out in the third row, so applying ##U## twice only leaves the ##\vert 1 \rangle## state.
  18. Feb 23, 2017 #17
    Yes. The two |0> states destructively interfere and cancel out. The two |1> states constructively interfere.

    If I apply U to the state |0> twice, how do I write that in Dirac notation? Do I write it like this ... UU | 0> or like this U | U0>?

    Also, how do I show the path to the negative state in the 3rd row in Diract notation?

    There really should be paths associated with the 3rd row. Each path would show, in Dirac notation, the order and state in which the operations were carries out. I do not know how to express that in Dirac notation yet.
  19. Feb 23, 2017 #18


    Staff: Mentor

    Yes. Then you can substitute and rearrange as follows: ##UU\vert 0 \rangle = U \frac{1}{\sqrt{2}} \left( \vert 0 \rangle + \vert 1 \rangle \right) = \frac{1}{\sqrt{2}} \left( U \vert 0 \rangle + U \vert 1 \rangle \right)##, and so on.

    That won't work because the ket ##\vert U 0 \rangle## doesn't make sense.
  20. Feb 23, 2017 #19


    Staff: Mentor

    Not really, no. The operator U doesn't really apply to individual nodes; it applies to entire rows. So if you were going to try to express things in tree notation, it would look something like this (I'm not going to try to wrangle LaTeX too much to make it actually look like a tree, but just write what would be in each row of the tree):

    \vert 0 \rangle

    U \vert 0 \rangle = \frac{1}{\sqrt{2}} \left[ \vert 0 \rangle + \vert 1 \rangle \right]

    U U \vert 0 \rangle = \frac{1}{\sqrt{2}} \left[ U \vert 0 \rangle + U \vert 1 \rangle \right] = \frac{1}{2} \left[ \vert 0 \rangle + \vert 1 \rangle - \vert 0 \rangle + \vert 1 \rangle \right]
  21. Feb 23, 2017 #20
    Well, I think the first way I rewrote the tree is probably the best way to show that. The tree can be decomposed into two elementary operations...applying the operator to the state |0> and applying the operator to the state |1>. It would be very easy to extend this tree to deeper levels because everything is known. There are two simple binary trees, the binary tree formed when U is applied to the state |0> and the binary tree formed when U is applied to the state |1>.

    Here it is again...

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Can someone please explain Scott Aaronson lecture #9?