Can someone please explain Scott Aaronson lecture #9?

[mike1000]

Here is a link to a lecture by Scott Aaronson.
http://www.scottaaronson.com/democritus/lec9.html

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...

https://lh3.googleusercontent.com/KvO3ZBgTUQsLbxSEEUuF6Mo9pXYdV2LJHHAXOUzC7Qwjtio0WoxmiMipIYuLoBImj7Xp-G_UqAvKi6NYei4AqOLedhNPtKSnv1ebfMK1BcORFjvFhw-9_1ZwUsc0SXB5iPiC6q_qVi5bgVWF6WPlWREKBJPxdmSVZImHH1-TCnz2XyyRkLbPxBvhQSZqWONKLD0C-xh_dAgvqeBg112wLdSiGz3gT-0A3VGp4kdXGw_75OVpXSBbboUO3I_izoP0C7xWHwWOKKD1Y62qY2bhFWB-Qbvli0opxIUFDU_Oh83bfDNkNgZyA7pmjGTWfUJbA2-7o0UXLHNpkZjQxl-9isYmASDu0mHlsfc4qkc6DnNZ1MbCclcNljsR_9nUqsxzJB8uP1-UoHQGe8uzEo5z_VT-tM1n-ZvWG5uA-GNU4gm8FlhsFL-8tROFmEmO9EE0VOs2xEoIYsY2bj5XatWBJ59LL-9PQ-Fm_W_VUdM2Ry98DKgPTwQnFutHGiDSo-6ueXow0_SvqacctzhzpdhDU_0n9mPh_b6aMtgwqh1WrwFpv2aZQYQE1rc0KmMe-zMeLzmhDSzjrdAJBmQNk8HRGSaBVe2UnjEvjL4UNtvy8ayCyEM3XNiR=w1350-h741-no

 

[Mentz114]

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'.

 

[mike1000]

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 matix in the lecture is sometimes called the 'quincunx matrix'.

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.

 

[Mentz114]

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.

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

I would expect it to be

 

[mike1000]

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

I would expect it to be

View attachment 113606

How did you get that?

 

[Nugatory]

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>.

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.

I seriously doubt that this is the correct interpretation for how the tree is constructed...

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.

 

[Demystifier]

Are you familiar with the Quincunx ?

I like it!

 

[mike1000]

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.

Thank you for your explanation.

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

https://lh3.googleusercontent.com/Y7ofc2dfXgLoGo0NB0EbyRE0jc1dZ37tvw9VMaey-LS_ydU3CjKTel9N-ksf-YXmQYHh31dVo-cyajGVRWMZrOpwWuoS7p7JPdsWFNzvbWjZ55t0oiFabA0btO2I3BWcVdhBj7PBhUH0tt4BnmeEfd4oloMFe5CmtpWxOUoN3V9c14MMBmT2_y3BWIBJRPFhqcqhEXADm7qyff1f1ilzGZAohX65bBbL4sMSeEaRVXsv89MIMNw3hViMagZi0RtSX28hFQ5GUl9CxxS3WO8CoJe3IZwgoRX5TNwHGkk_-bnkoHf0eXKJMp1_0hZh1KhUviJObTHHKZZ4KfvU3pbrdbR13wbqfbuARcFAfhM4PzyFS1qbJPez7sJyzfbbBNznTbou8X8k0UkT97YcZ2J1tc_z3iOeabfS_zIXLw9U8Gcu0wt1ZJ4b4KUonmFMnfH0CKlnkHUjDfxj5Dr7y6X0AsUiS8B5QgeEznyxPxx1nafOGyjgRtTOZlY59UBePjykI_hlj_WEt8EcLFPU84ZbGVNVEggJq1MReTotTiOPVGs5OblSvU4RZJ4RfvDBp-hdlj_g_K3bKqZ2cOTT4ru8KSsJXjlS5NTd7tpN-m_lsUp8jOzE0yl9=w1175-h645-no

 

[PeterDonis]

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

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.

 

[mike1000]

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.

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...)

 

[PeterDonis]

The third level is the result of applying U twice.

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.

 

[mike1000]

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.

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.

 

[PeterDonis]

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.

Yes, I know that. And the four leaf nodes are the ones Aaronson described. Do you agree with that?

 

[PeterDonis]

In your OP

Correction: in your post #3.

 

[mike1000]

Yes, I know that. And the four leaf nodes are the ones Aaronson described. Do you agree with that?

Yes.

 

[PeterDonis]

Yes.

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.

 

[mike1000]

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.

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.

 

[PeterDonis]

Do I write it like this ... UU | 0>

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.

or like this U | U0>

That won't work because the ket $\vert U 0 \rangle$ doesn't make sense.

 

[PeterDonis]

I have again revised the tree. I think this is the way you think I should write it.

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]
$$

 

[mike1000]

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]
$$

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...

 

[PeterDonis]

I think the first way I rewrote the tree is probably the best way to show that.

I think Aaronson's way of writing the tree, with no U anywhere, is the best way to show that. IMO putting a U on any of the nodes of the tree is misleading, because then the node does not correspond to what it appears to say. (For example, the left node on the second row does not actually correspond to $U \vert 0 \rangle$; it just corresponds to $\vert 0 \rangle$, which is what Aaronson wrote there.) If you're going to include U at all it should be off to the left of the tree, just describing what each row of the tree corresponds to: $U \vert 0 \rangle$, $UU \vert 0 \rangle$, etc.

 

[mike1000]

I think Aaronson's way of writing the tree, with no U anywhere, is the best way to show that. IMO putting a U on any of the nodes of the tree is misleading, because then the node does not correspond to what it appears to say. (For example, the left node on the second row does not actually correspond to $U \vert 0 \rangle$; it just corresponds to $\vert 0 \rangle$, which is what Aaronson wrote there.) If you're going to include U at all it should be off to the left of the tree, just describing what each row of the tree corresponds to: $U \vert 0 \rangle$, $UU \vert 0 \rangle$, etc.

Doing it my way, would the √2 factors not have added up correctly? I think they would have worked themselves out correctly.

There are only two operations...applying U to the |0> state and applying U to the |1> state. All of the detail is handled by the tree structure. Each path through the tree will tell you what sequence of operations gave rise to that leaf node. But the state is given by the superposition of all the leaf nodes.

 

[PeterDonis]

Doing it my way, would the √2 factors not have added up correctly?

Doing what your way? Drawing the tree is not the same as actually applying the U operator to states. Your way of drawing the tree seems misleading to me, but that doesn't make it "wrong" unless you are thinking that your way of drawing the tree implies a different (wrong) way of applying the U operator to actual states.

 

[mike1000]

Doing what your way? Drawing the tree is not the same as actually applying the U operator to states. Your way of drawing the tree seems misleading to me, but that doesn't make it "wrong" unless you are thinking that your way of drawing the tree implies a different (wrong) way of applying the U operator to actual states.

I want the tree to be simple, not complex. All I am intending to show is that we can apply the operator at different levels of the tree, and if we do that , we will arrive at the exact same answer that Arraonson arrives at. The simplest form of all, is of course, Aaronsons original tree. I had to put the operators into make it clear to me what the tree represented, when it was in Aaronsons original form I wasn't sure what the tree was trying to represent. Of course now, I see it is/was something extremely simple.

In retrospect, I believe that Mr. Aaronson should have put the operators in the tree in some way to clarify what he was doing, as scaffolding. Maybe not the way that I put them in, but some way. The essence of the tree is that it encapsulates application of the U operator twice. The tree structure can encapsulate application of the U operator any number of times you care to apply it.

 

[PeterDonis]

I believe that Mr. Aaronson should have put the operators in the tree in some way to clarify what he was doing.

If they were off to the left of each row, as I suggested, I think that would do it.

 

[mike1000]

If they were off to the left of each row, as I suggested, I think that would do it.

I can do that and I want to do that. In your view which rows do I apply the "U" operators to?

 

[PeterDonis]

In your view which rows do I apply the "U" operators to?

Each row (except the top one, which is the starting state) is the result of applying the U operator to the row above it.

 

[Nugatory]

Do I write it like this ... UU | 0>?

You can, but you might find $U^2|0\rangle$ a bit more compact.

 

[mike1000]

I can do that and I want to do that. In your view which rows do I apply the "U" operators to?

I have modified the tree one more time. Thanks to both of you for your guidance.

https://lh3.googleusercontent.com/L7YlPHsr9hGlW2SSMPSw7lN01iMiHCN-ojt3rndG0dIfaYgLMfAe31A0oHrPTAyRPGFUQkJcODv_lui7GCmY_Ad1UtPUNKb5DyKT3soO5wnjjh4UYX9iPh7gBM_Qh3St2mU-v1StcHFZgJpsnWCFRI4C7_T4_4R8MP0eU9YluOEx7Tmg7ohjm7FKZNA5peLqVg5fzleqsbJNkBJy1oecLexCZahG4vxU5AvIRpRGq1PVa501QktRRBWlHTOx9W4f5AJav6jrGCuGhPNrPqp1HLpB95dAUaxnCg5IYz5an-LBAeU0qiP_s0zB9HS24Qd79CdFLNoQefIagjq9lD-sfJXxn5zhNK4iRuksEKTy2m4gCjwSXlp1rLbqflZ_viFXmCj9w9STvAnmlqcP6Kr4ABKA6uXdn7Naknb5k3IKDk-oKHOahRsvxT0FygTCF2oTe5uaxL2rVQOEYaHgCAx5PwREn0CNi98LCdS2YY5_X-S3yKox5jgZ6LsRlWRs_McgahGlPJqg3dxPTonqLWzr229X-eaeY24DvyWiYTsfhI9sb804n6xHbtdsolMtVQ_UWtBvR5n0mmew6kNqBTxrruRA25YO1mkxH4lu8dqiNWUo-mpVtZp2=w1350-h741-no

 

[PeterDonis]

I have modified the tree one more time.

Yes, this is what I was suggesting.