Answer key · Unit 10

Computing in the real world.

Each lesson’s practice questions, their correct answers and the mistakes they spot. Answers read off the Scene use the same setting the learner sees.

Misconception catalogue

Answer key 4

Lesson 1 of 4 · About 25 minutes

Ray tracing

How a computer draws a 3D world: a ray through each pixel, shadow rays to the light, bounces that bring reflections and light from other surfaces, and how many rays it takes for the noise to go.

Open the lesson

The 6 steps and their answers

Step 1 of 6
Open this step
Two pictures
Practice · Choose
Question
The Scene holds two pictures of the same set. The whole studio is drawn like every Scene on this site, by rasterisation. The picture on the frame in front of the camera was worked out by ray tracing. What does the mirror ball show in each?

Correct answer
- Correct In the picture on the frame it reflects the red ball and the set; in the studio it shows a stored picture of a room, with no red ball
Setup, choices and feedback
The Scene at this step
Rays per pixel
16
Bounces
2
Light size
1 m
Trace the rays
Picture
Choices
Shown in a random order.
- Correct In the picture on the frame it reflects the red ball and the set; in the studio it shows a stored picture of a room, with no red ball
- Wrong Both reflect the red ball: every computer picture works out reflections
  Feedback
  Rasterisation draws each surface on its own and does not know what else is in the scene. To make a mirror look shiny it pastes a ready-made picture of surroundings onto it. Look at the mirror ball in the studio: there is no red ball in it.
- Wrong Only the studio’s reflects the red ball
  Feedback
  The other way round. It is ray tracing that carries the ray on after it hits the mirror, so only in the picture on the frame does the mirror show what is really beside it.
- Wrong Neither: a mirror on a computer is just a shiny grey
  Feedback
  In the picture on the frame, a ray that hits the mirror carries on in the reflected direction and hits the red ball, so the ball shows in it.
Feedback for a right answer
Ray tracing follows the ray on after it hits the mirror: it reflects, carries on and hits the red ball, so the ball appears in the reflection. Rasterisation draws each surface on its own, so the studio’s mirror ball shows only a ready-made picture of a room.

Hint
Compare the mirror ball in the studio with the one in the picture on the frame. In which does the red ball appear?

Worked solution
1. Rasterisation projects every triangle of every object onto the screen and colours the pixels it covers. Each surface is coloured on its own.
2. When it colours a surface it knows only that surface and the lights, not what else is around it. So a reflection is faked with a stored picture of surroundings.
3. Ray tracing sends a ray through each pixel. When the ray hits the mirror it reflects and carries on to the next surface, here the red ball.
4. So only in the picture on the frame does the mirror ball reflect the red ball.
If you thought every computer picture works out reflections: games fake them most of the time, because rasterisation is far faster.
Step 2 of 6
Open this step
Camera rays
Practice · Choose
Question
In real light, photons leave the light source, hit objects, and only a tiny share of them reach the camera. Where do the rays the computer follows start?

Correct answer
- Correct At the camera: a ray through each pixel, out into the set, the opposite way to the light
Setup, choices and feedback
The Scene at this step
Rays per pixel
16
Bounces
2
Light size
1 m
Trace the rays
Camera rays
Choices
Shown in a random order.
- Correct At the camera: a ray through each pixel, out into the set, the opposite way to the light
- Wrong At the light, as in nature; the computer counts the rays that end up at the camera
  Misconception: Thinks a ray tracer follows rays out from the light to the camera, as light travels.
  Feedback from the catalogue
  Real light leaves the light source, but almost all of it is absorbed or scattered in other directions and never reaches the camera. A computer that followed the light forwards would waste nearly all its work. So ray tracing goes backwards: one ray leaves the camera through each pixel, and only from the place it hits is a shadow ray sent to the light. That way every ray worked out adds to the picture.
- Wrong At every surface in the set, in every direction
  Feedback
  Then the computer would have to follow endless rays from every point, and most would never reach the camera. Ray tracing works out only the rays that set the pixels’ colours.
Feedback for a right answer
Each ray leaves the camera, passes through one pixel of the frame and stops at the first surface it meets. The colour it brings back is the pixel’s colour. Real light travels the other way, but along the same path, so the picture comes out the same.

Hint
Move Trace the rays to Camera rays and look where the lines start.

Worked solution
1. Only light that reaches the lens makes a picture, and almost all the light a lamp sends out goes elsewhere.
2. A light ray’s path is the same in both directions, so it may be followed backwards.
3. Ray tracing starts at the camera, through a pixel, and finds which surface that pixel sees.
4. That way the computer works out only rays that add to the picture: at least one ray per pixel.
If you chose the light, you described the physics correctly but not the computation: tracing that way would waste almost every ray.
Step 3 of 6
Open this step
Shadow rays
Practice · Predict, then look
Question
The Light size is 2 m, a big softbox. What will happen to the edges of the shadows when you slide Light size down to 0.1 m?

Correct answer
- Correct The edges will be sharp
Setup, choices and feedback
The Scene at this step
Rays per pixel
64
Bounces
2
Light size
2 m
Trace the rays
Picture
Choices
- Correct The edges will be sharp
- Wrong The edges will be softer and more blurred
  Feedback
  The other way round. A big lamp makes soft edges, because some points see only part of it. A small lamp is almost a point: each place sees all of it, or none of it.
- Wrong The edges will not change: a shadow depends only on the object casting it
  Feedback
  A shadow depends on the light too. Shadow rays go to random points on the lamp, and with a big lamp some are blocked at the shadow’s edge and some are not.
Once the prediction is locked in, the Scene changes
Light size
0.1 m
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
With a small lamp each point on the floor sees the whole lamp or none of it, so the shadow ends in a sharp line. With a big softbox there is a band, the penumbra, where only some of the shadow rays are blocked, and the shadow fades gradually.

Hint
A shadow ray goes to a random point on the light. What happens at a shadow’s edge when the light is big?

Worked solution
1. From every point a camera ray hits, a shadow ray goes to a random point on the light.
2. A big light: near a shadow’s edge part of the lamp is hidden by the ball and part is not. Some shadow rays are blocked, and the point is partly lit: a wide penumbra.
3. A small light: nearly the whole lamp is hidden at once, or seen at once. There is hardly any penumbra.
4. So with a small lamp the edges are sharp.
Photographers use softboxes for exactly this: soft light that gives gentle shadows.
Step 4 of 6
Open this step
Bounces
Practice · Calculate
Question
Bounces is set to 3. At each hit on a matte surface one shadow ray is sent to the light, and if bounces are left, the ray carries on from that point in a new direction. At most, how many rays in all can one camera ray lead to, itself included?

Correct answer
8 ± 0.1
Setup, choices and feedback
The Scene at this step
Rays per pixel
16
Bounces
3fixed
Light size
1 m
Trace the rays
Bounces
Accepted within
± 0.1
Computed from the Scene at this step’s setting
The most rays one camera ray can lead to: itself, up to `bounces` bounce rays and a shadow ray at each of its bounces + 1 hits, 2 × (bounces + 1)/nodes/set/outputs/raysPerPath
Wrong answers it recognises
- 4 ± 0.1
  Misconception: Counts only the camera ray and its bounces, and forgets the shadow ray sent at each hit.
  Feedback from the catalogue
  Every hit on a matte surface sends one more ray: a shadow ray to a point on the light, to check whether anything hides it. The camera ray’s first hit and the hit after each bounce each send a shadow ray of their own, so with $b$ ⁠ bounces there are up to $b + 1$ ⁠ shadow rays, on top of the camera ray and its $b$ ⁠ bounce rays.
- 7 ± 0.1
  Misconception: Counts only the camera ray and its bounces, and forgets the shadow ray sent at each hit.
  Feedback
  You left out the shadow ray of one hit. There is the camera ray’s hit and one more after each bounce: four hits, so four shadow rays.
Feedback for a right answer
The camera ray, 3 bounce rays and 4 shadow rays, one per hit: $1 + 3 + 4 = 8$ ⁠, that is $2 \times (3 + 1)$ ⁠. A ray that leaves the set, hits the mirror or reaches the light stops sooner, so this is the most.

Hint
Count hits: how many times does the ray hit a surface with 3 bounces? Each hit sends a shadow ray.

Worked solution
1. A path with $b = 3$ ⁠ bounces hits a surface $b + 1 = 4$ ⁠ times: the camera ray’s hit and one more after each bounce.
2. The rays along the path: the camera ray and $3$ ⁠ bounce rays, $4$ ⁠.
3. The shadow rays: one per hit, $4$ ⁠.
4. In all $4 + 4 = 8 = 2(b + 1)$ ⁠.
If you got $4$ ⁠, you counted only the path itself and forgot the shadow rays.
Step 5 of 6
Open this step
Noise
Practice · Predict, then look
Question
At 16 rays per pixel, the chart beside the Scene shows how much noise is left compared with one ray. What will happen to the noise when you go to 64 rays per pixel, four times as many?

Correct answer
- Correct It will halve
Setup, choices and feedback
The Scene at this step
Rays per pixel
16fixed
Bounces
2
Light size
1 m
Trace the rays
Picture
Choices
- Correct It will halve
- Wrong It will fall to a quarter
  Misconception: Thinks the noise falls in proportion to the rays per pixel: four times the rays, a quarter of the noise.
  Feedback from the catalogue
  Each pixel is an average of random rays, and the noise of an average shrinks like $\dfrac{1}{\sqrt{N}}$ ⁠, not like $\dfrac{1}{N}$ ⁠. Four times the rays only halve the noise, and a hundred times the rays cut it tenfold. That is why a perfectly smooth picture takes so many rays.
- Wrong It will vanish altogether
  Feedback
  An average of a finite number of random rays always leaves a little noise. It only shrinks, and slowly.
- Wrong It will not change
  Feedback
  Every extra ray is one more sample in the pixel’s average, so more rays always reduce the noise.
Once the prediction is locked in, the Scene changes
Rays per pixel
64fixed
The Scene then shows: 0.125 · The noise left, as a share of the noise with one ray per pixel (1/√rays)/nodes/set/outputs/noise
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
$\dfrac{1}{\sqrt{16}} = \dfrac{1}{4}$ ⁠ and $\dfrac{1}{\sqrt{64}} = \dfrac{1}{8}$ ⁠: the noise falls from 25% to 12.5% of one ray’s, a half. Halving it again takes four times the rays again, so the time grows much faster than the picture improves.

Hint
Each pixel is an average of $N$ ⁠ random rays, and the noise of an average shrinks like $\dfrac{1}{\sqrt{N}}$ ⁠.

Worked solution
1. The noise of an average of $N$ ⁠ random samples shrinks like $\dfrac{1}{\sqrt{N}}$ ⁠.
2. At 16 rays: $\dfrac{1}{\sqrt{16}} = \dfrac{1}{4}$ ⁠.
3. At 64 rays: $\dfrac{1}{\sqrt{64}} = \dfrac{1}{8}$ ⁠.
4. $\dfrac{1}{8}$ ⁠ is half of $\dfrac{1}{4}$ ⁠: four times the rays halve the noise.
If you expected a quarter, you assumed the noise falls in proportion to the rays. The square root is what makes a smooth picture so costly.
Step 6 of 6
Open this step
The whole picture
Practice · Calculate
Question
The picture is 96 pixels wide and 60 high. Rays per pixel: $16$ ⁠, and Bounces: $2$ ⁠, so each camera ray brings up to $2(b + 1) = 6$ ⁠ rays. At most how many rays does the whole picture take?

Correct answer
553000 ± 1%
Setup, choices and feedback
The Scene at this step
Rays per pixel
16fixed
Bounces
2fixed
Light size
1 m
Trace the rays
Bounces
Accepted within
± 1%
Computed from the Scene at this step’s setting
The most rays the whole picture can take: cameraRays × raysPerPath/nodes/set/outputs/maxRays
Wrong answers it recognises
- 276500 ± 1%
  Misconception: Counts only the camera ray and its bounces, and forgets the shadow ray sent at each hit.
  Feedback from the catalogue
  Every hit on a matte surface sends one more ray: a shadow ray to a point on the light, to check whether anything hides it. The camera ray’s first hit and the hit after each bounce each send a shadow ray of their own, so with $b$ ⁠ bounces there are up to $b + 1$ ⁠ shadow rays, on top of the camera ray and its $b$ ⁠ bounce rays.
Feedback for a right answer
About $553{,}000$ ⁠ rays, for one small picture.

Hint
Multiply the number of pixels by the rays per pixel, then by the rays per path.

Worked solution
1. Pixels: $96 \times 60 = 5760$ ⁠.
2. Camera rays: $5760 \times 16 = 92\,160$ ⁠.
3. Each camera ray up to $6$ ⁠ rays: $92\,160 \times 6 = 552\,960$ ⁠.
For a full-screen picture, about $2$ ⁠ million pixels, that is already hundreds of millions of rays for every picture. If you answered 276,480, you counted only the $3$ ⁠ rays along the path and forgot the shadow rays.

Lesson 2 of 4 · About 30 minutes

A feedback loop

A controller balancing a pole on a cart: sensor, controller and motor in a closed loop, too little gain that drops the pole, tuning for the shortest settling time, and overshoot that grows when the correction arrives late.

Open the lesson

The 7 steps and their answers

Step 1 of 7
Open this step
The loop
Practice · Choose
Question
What makes the rig a closed loop, rather than a string of pushes planned in advance?

Correct answer
- Correct The encoder measures the tilt a hundred times a second, and the controller works out each push from the latest reading
Setup, choices and feedback
The Scene at this step
Controller gain
1 N/°
Show the feedback
On
Choices
Shown in a random order.
- Correct The encoder measures the tilt a hundred times a second, and the controller works out each push from the latest reading
- Wrong The controller knows when the tap will come and works out every push in advance
  Feedback
  That is how an open loop works: a plan that does not look at the result. Any upset it did not plan for, a gust or a harder tap, would topple the pole. The controller here knows nothing about the tap; it sees only the tilt the tap causes.
- Wrong The motor is strong enough to hold the pole upright
  Feedback
  The motor does not hold the pole; it moves the cart. Only because the pushes depend on what the encoder measures does the cart get under the pole each time.
Feedback for a right answer
Sensor, controller and motor in a ring: the encoder measures the tilt, the controller works out a push that grows with the tilt, and the motor moves the cart. The movement changes the tilt, and the next reading sees the result. The result is fed back: that is feedback.

Hint
Follow the feedback arrows: where does the controller get its information?

Worked solution
1. An open loop follows a plan and does not check the result, like a toaster on a timer.
2. A closed loop measures what happened and corrects by it, like a thermostat.
3. Here the encoder measures the tilt every 10 ms, and the controller works out the next push from it.
4. So the controller corrects even an upset it did not foresee, such as the tap.
It is the same loop a processor runs: read, compute, write, repeat. Here the input comes from a sensor and the output moves a motor.
Step 2 of 7
Open this step
Too little gain
Practice · Predict, then look
Question
At 1 N/° the cart catches the pole after every tap. What will happen after the tap when you slide Controller gain down to 0.2 N/°?

Correct answer
- Correct The pole will fall
Setup, choices and feedback
The Scene at this step
Controller gain
1 N/°
Show the feedback
On
Choices
- Correct The pole will fall
- Wrong The cart will catch the pole, only more slowly
  Misconception: Thinks a controller with too little gain still balances the pole, only more slowly.
  Feedback from the catalogue
  An upright pole does not wait. The further it leans, the faster gravity tips it, so the cart has to accelerate under it faster than it falls. A push that is too weak never catches it: the tilt grows, and the pole falls. There is a smallest gain, and below it the loop fails rather than just slowing down.
- Wrong The pole will come back upright gently, without swinging
  Misconception: Thinks a controller with too little gain still balances the pole, only more slowly.
  Feedback from the catalogue
  An upright pole does not wait. The further it leans, the faster gravity tips it, so the cart has to accelerate under it faster than it falls. A push that is too weak never catches it: the tilt grows, and the pole falls. There is a smallest gain, and below it the loop fails rather than just slowing down.
Once the prediction is locked in, the Scene changes
Controller gain
0.2 N/°
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
The push is too weak: the cart accelerates more slowly than the pole falls, the tilt keeps growing, and past 25° the controller gives up and the pole rests on the bumper. With too little gain the loop does not slow down; it fails.

Hint
A leaning pole is pulled aside by a force that grows with the tilt. What has to happen for the cart to catch it?

Worked solution
1. The pole is unstable: the further it leans, the faster gravity tips it.
2. To bring it back, the cart has to accelerate under it faster than it falls.
3. This rig needs about 0.2 N per degree just to beat gravity, and more because of the late reading: about 0.45 N/°.
4. At 0.2 N/° the pole falls.
If you expected the cart just to be slower, think of a broom on your palm: a lazy hand does not balance it slowly, it drops it.
Step 3 of 7
Open this step
Settling time
Practice · Reach the target
Question
The settling time is the time from the tap until the tilt stays within 2° of upright. Tune the Controller gain so the pole settles 1.3–1.5 s after the tap, the quickest this rig can manage.

Goal
- 1.4 s ± 0.1 s
  At the start of the step: 1.79 s
Setup, choices and feedback
The Scene at this step
Controller gain
1 N/°
Show the feedback
On
Read from the Scene at
Cart-pole: seconds from the tap until the tilt stays within 2° of upright; NaN when the pole falls or never settles/nodes/rig/outputs/settlingTime
One setting that reaches it
Controller gain
1.3 N/°
Feedback for a right answer
At about 1.3–1.5 N/° the cart catches the pole quickly, and the small swings die away quickly. With less gain the tilt comes down slowly, and with more the pole swings to and fro for longer. The shortest settling time is in the middle.

Feedback for a wrong answer
Not yet. Try values between 1 N/° and 1.9 N/°, and wait for the next tap each time.

Hint
On the strip chart, a small gain leaves the pole leaning for a long time, and a large one leaves it swinging. Look in the middle.

Worked solution
1. At 1 N/° the settling time is about 1.8 s: the cart catches the pole, but the tilt stays above 2° for a long time.
2. More gain catches it sooner: at 1.5 N/° the settling time is about 1.3 s.
3. Beyond that the swings come back: at 1.9 N/° it is about 1.9 s again, and from 2.2 N/° the pole never settles.
4. So the gains that work are about 1.3–1.5 N/°.
Control engineers look for exactly this middle: quick enough to correct, and not so strong that the correction overshoots.
Step 4 of 7
Open this step
Overshoot
Practice · Predict, then look
Question
At 1.5 N/°, after the tap, the pole swings across upright to the other side a few times before it calms down. What will happen to the number of times when you slide Controller gain up to 1.9 N/°?

Correct answer
- Correct It will go up
Setup, choices and feedback
The Scene at this step
Controller gain
1.5 N/°
Show the feedback
On
Choices
- Correct It will go up
- Wrong It will go down: a stronger push corrects more precisely
  Misconception: Thinks a stronger push per degree always corrects faster and more accurately.
  Feedback from the catalogue
  The controller acts on a reading that reaches it late, here by 50 ms. A strong push corrects where the pole was, and by the time it arrives the pole is already on its way back, so the push sends it over to the other side. The bigger the gain, the more each correction overshoots, until the swings stop dying away at all. A good gain sits in the middle of the range, not at its top.
- Wrong It will not change: the gain only changes how fast the correction is
  Feedback
  The gain sets how hard the controller pushes per degree, and a harder push arriving late carries the pole further over to the other side.
Once the prediction is locked in, the Scene changes
Controller gain
1.9 N/°
The Scene then shows: 5 · Cart-pole: times the pole swings past upright after the tap, before the rig resets (counted once it is 0.5° past)/nodes/rig/outputs/overshoots
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
With more gain each push carries the pole past upright, the next carries it back, and so on: it crosses upright more often and swings for longer. That is overshoot.

Hint
The push reaches the motor 50 ms late. What does a harder push do to a pole already on its way back?

Worked solution
1. The controller pushes in proportion to a tilt measured about 50 ms earlier.
2. When the pole is already coming back upright, the push carries on by the old reading and carries it over to the other side.
3. The bigger the gain, the harder that push, and the further the pole goes over.
4. So at 1.9 the pole crosses upright more often than at 1.5.
If you expected a strong push to correct more precisely: it corrects harder, but for where the pole was.
Step 5 of 7
Open this step
Delay
Practice · Choose
Question
At 2.6 N/° the pole shakes to and fro and never settles, even though the controller pushes hard. Why?

Correct answer
- Correct Each reading reaches the motor 50 ms late, and the strong push corrects where the pole was
Setup, choices and feedback
The Scene at this step
Controller gain
2.6 N/°
Show the feedback
On
Choices
Shown in a random order.
- Correct Each reading reaches the motor 50 ms late, and the strong push corrects where the pole was
- Wrong The motor is too weak: a stronger motor would steady the pole
  Misconception: Thinks a stronger push per degree always corrects faster and more accurately.
  Feedback from the catalogue
  The controller acts on a reading that reaches it late, here by 50 ms. A strong push corrects where the pole was, and by the time it arrives the pole is already on its way back, so the push sends it over to the other side. The bigger the gain, the more each correction overshoots, until the swings stop dying away at all. A good gain sits in the middle of the range, not at its top.
- Wrong The encoder cannot keep up with such fast swings
  Feedback
  The encoder reads every 10 ms, far faster than the swings. The trouble is not how often it measures, but how long it takes for the push to arrive.
- Wrong At a high gain gravity pulls the pole harder
  Feedback
  Gravity knows nothing about the controller: it pulls the pole the same way at every gain. What changes is the cart’s push.
Feedback for a right answer
Each reading is news from 50 ms ago. A strong controller reacts hard to where the pole was, the push carries it past upright, and the next push, late as well, carries it back further still. The swings grow until the motor slams between its force limits.

Hint
The reading goes through filtering, computing and starting the motor before the push arrives. Where is the pole when it does?

Worked solution
1. From reading to push takes 50 ms: filtering, computing and starting the motor.
2. At a low gain the push is mild, and by the time the pole moves it hardly matters.
3. At a high gain the push is large, and it arrives when the pole is already on its way back, so it carries it over to the other side.
4. Each correction overshoots more than the last, and the swing does not die away.
That is why engineers work to cut the delay: a faster loop allows a higher gain before it starts to overshoot. It is like setting a shower whose hot water arrives late.
Step 6 of 7
Open this step
A small tilt
Practice · Reach the target
Question
In each test the pole is tapped, and it tips over until the cart catches it. Tune the Controller gain so the pole tips no more than 3° at its farthest, and press Check.

Goal
- 3 ± 0.1
  At the start of the step: 3.798
Setup, choices and feedback
The Scene at this step
Controller gain
1 N/°
Show the feedback
On
Read from the Scene at
Cart-pole: the furthest the tap tips the pole before the cart catches it, the first peak of the tilt; NaN when it falls/nodes/rig/outputs/peakTilt
One setting that reaches it
Controller gain
1.7 N/°
Feedback for a right answer
At about 1.8 N/°: the tilt is small, but the pole starts to overshoot and swing.

Hint
At 1 N/° the pole tips almost 3.8°. A bigger gain reacts harder to the same tilt.

Worked solution
1. The bigger the gain, the harder the cart pushes for each degree of tilt, and the sooner it catches the pole.
2. At 1.7–1.8 N/° the largest tilt falls to 3°.
3. But at that gain the pole already swings across upright a few times before it calms down.
That is the trade-off in every controller: a harder, faster response gives a small error, but more overshoot and more ringing.
Step 7 of 7
Open this step
Ringing
Practice · Reach the target
Question
At 1 N/° the cart catches the pole and it settles quickly. At 2.6 N/° it shakes and never settles. Find a Controller gain at which it rings: crossing upright back and forth many times, but settling in the end. Press Check.

Goal
- 3 ± 0
  At the start of the step: 2
Setup, choices and feedback
The Scene at this step
Controller gain
1 N/°
Show the feedback
On
Read from the Scene at
Cart-pole: what a test shows, 1 the pole falls, 2 it balances, 3 it rings, 4 it shakes (NaN for the arm)/nodes/rig/outputs/regime
One setting that reaches it
Controller gain
1.7 N/°
Feedback for a right answer
At about 1.7–2.1 N/°: a little more, and it will never settle.

Hint
Look between 1 N/° and 2.6 N/°.

Worked solution
1. Up to about 1.6 N/° the pole overshoots a little and settles.
2. Between about 1.7 and 2.1 N/° each push is too hard and sends it to the other side, and it crosses upright many times before it settles.
3. From 2.2 N/° on, the controller’s delay makes each push come too late, and the shaking never dies away.
Engineers tune a controller well clear of this range, because a small change in the system can tip it into shaking.

Lesson 3 of 4 · About 30 minutes

A robot arm

An arm with three joints: how trigonometry turns the angles into the gripper's position, how to find angles that bring it to a point, two poses for one point, and what the joint limits take away from them.

Open the lesson

The 7 steps and their answers

Step 1 of 7
Open this step
Joints
Practice · Predict, then look
Question
Turn the Base turn from -70° to 90°, without touching the Shoulder or the Elbow. What will happen to the gripper’s horizontal distance from the base axis?

Correct answer
- Correct It will not change; only the direction the arm faces will
Setup, choices and feedback
The Scene at this step
Base turn
-70 °
Shoulder
40 °
Elbow
-70 °
Show the workspace
Off
Choices
- Correct It will not change; only the direction the arm faces will
- Wrong It will grow
  Feedback
  The base turns the arm’s whole plane about an upright axis, like a turntable. The shoulder and elbow do not move within that plane, so the distance from the axis stays.
- Wrong It will shrink
  Feedback
  The base turns the arm’s whole plane about an upright axis, like a turntable. The shoulder and elbow do not move within that plane, so the distance from the axis stays.
Once the prediction is locked in, the Scene changes
Base turn
90 °
The Scene then shows: 0.6335 m · Arm: how far the fingertips are from the base axis, horizontally/nodes/robot/outputs/reach
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
The base turns the whole arm about an upright axis. The distance from the axis and the height are set by the shoulder and elbow alone, so they stay; only $x$ ⁠ and $y$ ⁠ on the chart change. That splits the problem: the base aims the arm at the point, and the shoulder and elbow bring the gripper to it.

Hint
Picture the arm from above. What does turning about an upright axis do to the distance from that axis?

Worked solution
1. The shoulder and elbow swing the arm within one upright plane.
2. Within that plane they set two numbers: the distance from the base axis and the height.
3. The base turns the whole plane about the upright axis, carrying the gripper round a circle centred on the axis.
4. On such a circle the distance from the centre is fixed, so the distance does not change.
Step 2 of 7
Open this step
From angles to a position
Practice · Calculate
Question
Shoulder at 30° above the horizontal and Elbow at -60°. The upper arm is 0.42 m long and the forearm 0.36 m. How far is the gripper from the base axis, horizontally?

Correct answer
0.6755 m ± 0.01 m
Setup, choices and feedback
The Scene at this step
Base turn
-70 °fixed
Shoulder
30 °fixed
Elbow
-60 °fixed
Show the workspace
Off
Accepted within
± 0.01 m
Computed from the Scene at this step’s setting
Arm: how far the fingertips are from the base axis, horizontally/nodes/robot/outputs/reach
Any unit of the same quantity is accepted; it is converted before checking.
Wrong answers it recognises
- 0.78 m ± 0.005 m
  Misconception: Adds the link lengths to get the gripper's reach, as if the arm were always straight and level.
  Feedback from the catalogue
  Each link adds to the horizontal distance only its shadow on the floor: $L\cos\theta$ ⁠, where $\theta$ ⁠ is the link’s angle above the horizontal. The upper arm points at the shoulder’s angle, and the forearm at the shoulder’s angle plus the elbow’s bend. Only when both angles are $0^\circ$ ⁠ are both cosines $1$ ⁠, and the reach the sum of the lengths.
- 0.5437 m ± 0.005 m
  Misconception: Adds the link lengths to get the gripper's reach, as if the arm were always straight and level.
  Feedback
  The forearm does not point at the elbow’s angle alone. The elbow bends it relative to the upper arm, so its angle above the horizontal is $30^\circ + (-60^\circ) = -30^\circ$ ⁠.
Feedback for a right answer
$0.42\cos 30^\circ + 0.36\cos(-30^\circ) = 0.78 \times 0.866 \approx 0.68$ ⁠ metres. That is forward kinematics: from the angles to the position, and it always has exactly one answer.

Hint
A link’s shadow on the floor is $L\cos\theta$ ⁠. The forearm’s angle is the shoulder’s angle plus the elbow’s.

Worked solution
1. The upper arm points at the shoulder’s angle, $30^\circ$ ⁠. Its shadow: $0.42\cos 30^\circ \approx 0.364$ ⁠ metres.
2. The forearm points at the shoulder’s angle plus the elbow’s: $30^\circ + (-60^\circ) = -30^\circ$ ⁠. Its shadow: $0.36\cos(-30^\circ) \approx 0.312$ ⁠ metres.
3. The wrist is $0.364 + 0.312 \approx 0.676$ ⁠ metres from the axis, and the gripper hangs straight down from it, at the same distance.
4. The answer: about 0.68 m.
If you answered 0.78 m, you added the lengths as if the arm were straight and level. The base turn does not change the distance, so it was not needed.
Step 3 of 7
Open this step
From a position to angles
Practice · Reach the target
Question
Bring the gripper to a point 0.60 m from the base axis and 0.60 m above the floor, using the Shoulder and Elbow. On the chart beside the Scene the height is $z$ ⁠, and the distance from the axis is $\sqrt{x^2 + y^2}$ ⁠.

Goal
- 0.6 m ± 0.02 m
  At the start of the step: 0.6335 m
- 0.6 m ± 0.02 m
  At the start of the step: 0.75 m
Setup, choices and feedback
The Scene at this step
Base turn
-70 °fixed
Shoulder
40 °
Elbow
-70 °
Show the workspace
Off
Read from the Scene at
Arm: how far the fingertips are from the base axis, horizontally/nodes/robot/outputs/reach
Read from the Scene at
Arm: the fingertips' height above the floor (the chart's z)/nodes/robot/outputs/height
One setting that reaches it
Shoulder
30 °
Elbow
-80 °
Feedback for a right answer
For example shoulder 30° and elbow -80°. What you did by hand, trying and correcting until the gripper got there, the controller does by calculation: inverse kinematics, from a position to the angles.

Feedback for a wrong answer
Not yet. Check both numbers: the height $z$ ⁠ and the distance from the axis $\sqrt{x^2 + y^2}$ ⁠.

Hint
Lower the Elbow until $z$ ⁠ is near 0.60 m, then adjust the Shoulder, and check both again.

Worked solution
1. The gripper hangs 0.14 m below the wrist, so the wrist must be 0.74 m high: 0.06 m below the shoulder, which is 0.80 m high.
2. The distance from the shoulder to the wrist: $\sqrt{0.60^2 + 0.06^2} \approx 0.603$ ⁠ metres.
3. The triangle with sides 0.42 m, 0.36 m and 0.603 m fixes the elbow’s bend: by the law of cosines, about $79^\circ$ ⁠.
4. With the elbow up that is an elbow of about -80° and a shoulder of about 30°.
The other pose, elbow down, would need the shoulder below its limit, so here the arm has only one answer facing forwards.
Step 4 of 7
Open this step
Two poses
Practice · Predict, then look
Question
Shoulder at 0° and Elbow at -90°. Most points the arm reaches have another pose that reaches the same point, with the elbow bent the other way. Can the arm use it here?

Correct answer
- Correct No: the other pose needs the shoulder below its -30° limit
Setup, choices and feedback
The Scene at this step
Base turn
-70 °
Shoulder
0 °
Elbow
-90 °
Show the workspace
Offfixed
Choices
- Correct No: the other pose needs the shoulder below its -30° limit
- Wrong Yes: every point always has two poses that can be used
  Feedback
  The mathematics gives two answers, but a real arm’s joints do not turn without limit. An answer that needs an angle past a limit does not exist for the controller.
- Wrong No: the elbow cannot bend to 90°
  Feedback
  The elbow moves up to 150° either way, so 90° is allowed. The trouble is the shoulder.
Once the prediction is locked in, the Scene changes
Show the workspace
Onfixed
The Scene then shows: -81.2 ° · Arm: the shoulder angle of the other pose that reaches the same point/nodes/robot/outputs/twinShoulder
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
The other pose, elbow 90°, would need a shoulder of about -81°, far below the -30° limit, so the ghost turns red: only one pose is really available. That is how the controller chooses among the answers of inverse kinematics: only those within the joint limits.

Hint
In the other pose the arm’s triangle flips to the other side of the line from shoulder to wrist. Where would the upper arm have to point?

Worked solution
1. The two poses are the two sides of one triangle: the upper arm, the forearm and the line from shoulder to wrist.
2. Here the wrist is low: the upper arm is level, and the forearm drops straight down from it.
3. To flip the triangle, the upper arm would have to drop below that line, to about -81°.
4. The shoulder does not go below -30°, so the other pose is not available.
Step 5 of 7
Open this step
The edge of the workspace
Practice · Choose
Question
Move the Elbow to 0°: the arm is straight, and the gripper is on the edge of the workspace. How many different poses of the shoulder and elbow bring the gripper to exactly this point, without turning the base?

Correct answer
- Correct One
Setup, choices and feedback
The Scene at this step
Base turn
-70 °
Shoulder
20 °
Elbow
-40 °
Show the workspace
On
Choices
Shown in a random order.
- Correct One
- Wrong Two, as at every point
  Feedback
  The two poses exist because the triangle of upper arm, forearm and the line to the wrist can be flipped. When the arm is straight the triangle is flat, and the two poses merge into one.
- Wrong None: the arm cannot reach the edge
  Feedback
  The gripper is there now. The edge is exactly where the arm reaches when it is stretched all the way.
Feedback for a right answer
One pose: the elbow’s two poses merge when the arm is straight. This is a singular pose. From there the gripper cannot move any further out, and a small step of it needs a large, fast movement of the joints, so paths are planned to keep away from it.

Hint
Slowly move the Elbow towards 0° and watch the ghost arm.

Worked solution
1. A point’s two poses are the two sides of a triangle: the upper arm, the forearm and the line from shoulder to wrist.
2. The further away the point, the flatter the triangle and the less the elbow bends.
3. When the arm is straight, the line to the wrist is as long as both links together, and the triangle is completely flat.
4. A flat triangle has no two sides, so there is one pose.
Step 6 of 7
Open this step
Elbow up, elbow down
Practice · Calculate
Question
Shoulder at 30° and Elbow at -60°. A second pose brings the gripper to the same point, with the elbow bent the other way. What is the elbow angle in that pose?

Correct answer
60 ° ± 0.5 °
Setup, choices and feedback
The Scene at this step
Base turn
-70 °fixed
Shoulder
30 °fixed
Elbow
-60 °fixed
Show the workspace
Off
Accepted within
± 0.5 °
Computed from the Scene at this step’s setting
Arm: the elbow angle of the other pose, the elbow bent the other way/nodes/robot/outputs/twinElbow
Any unit of the same quantity is accepted; it is converted before checking.
Wrong answers it recognises
- -60 ° ± 0.5 °
  Misconception: Thinks a two-link arm can reach each point in only one way.
  Feedback from the catalogue
  An arm with a shoulder and an elbow has two poses for almost every point: the elbow bent to one side of the line from the shoulder to the gripper, or to the other. Only at the edge of the workspace, with the arm straight, do the two become one.
Feedback for a right answer
+60°: the same bend, the other way.

Hint
The upper arm, the forearm and the line from the shoulder to the gripper make a triangle. What does the same triangle look like reflected in that line?

Worked solution
1. The two links’ lengths and the distance from the shoulder to the gripper fix one triangle, and so the angle at the elbow.
2. The triangle can be reflected in the line from the shoulder to the gripper: the elbow moves to the other side of the line.
3. The bend stays the same size, and its direction flips: +60°. The shoulder changes to make up for it.
These are elbow up and elbow down: a robot arm’s controller must choose between them, for example by which one avoids a collision.
Step 7 of 7
Open this step
Within the limits
Practice · Reach the target
Question
Shoulder is locked at 0°, and the Elbow is at -90°: the second pose, with the elbow the other way, would need the shoulder below its limit, -30°. Change the Elbow until the second pose is possible too, and press Check.

Goal
- 1 ± 0
  At the start of the step: 0
Setup, choices and feedback
The Scene at this step
Base turn
-70 °
Shoulder
0 °fixed
Elbow
-90 °
Show the workspace
Off
Read from the Scene at
Arm: 1 when the other pose keeps every joint within its limits, else 0/nodes/robot/outputs/twinReachable
One setting that reaches it
Base turn
-180 °
Elbow
-30 °
Feedback for a right answer
With the elbow bent less, about -30° and up, the second pose is within the limits too.

Hint
The less the elbow is bent, the closer the second pose is to the first.

Worked solution
1. In the second pose the shoulder moves up or down by an angle that depends on how much the elbow is bent.
2. With the elbow at -90° it would have to go below -30°.
3. As the elbow straightens, the second pose comes closer to the first. From about -30° on, its shoulder is within the limits.
A real arm’s workspace is smaller than its links’ lengths allow, because every joint is limited.

Lesson 4 of 4 · About 40 minutes

Qubits and search

A qubit as an arrow on a sphere: a gate that makes a superposition, a measurement that gives 0 or 1 by chance, phase that makes interference, and Grover's search, which finds one item in an unsorted store in far fewer steps than an ordinary search.

Open the lesson

The 9 steps and their answers

Step 1 of 9
Open this step
A qubit
Practice · Predict, then look
Question
After the H gate the arrow lies on the equator, halfway between $|0\rangle$ ⁠ and $|1\rangle$ ⁠. A qubit like this is prepared again and again and each one is measured. What will each measurement give?

Correct answer
- Correct 0 or 1 at random: about half the measurements 0 and half 1
Setup, choices and feedback
The Scene at this step
Gate
H
Search size
4 qubits
Search rounds
0 rounds
Measure and search
Qubitfixed
Choices
- Correct 0 or 1 at random: about half the measurements 0 and half 1
- Wrong Both 0 and 1 in the same measurement
  Misconception: Thinks measuring a qubit in superposition gives both 0 and 1, or a value in between.
  Feedback from the catalogue
  Measuring a qubit always gives one bit: 0 or 1. The superposition sets only the chances. An arrow on the equator gives 0 in half the measurements and 1 in half, and each single measurement is one of them. After the measurement the qubit is no longer in a superposition: it is in the state that was read.
- Wrong The value 0.5, halfway
  Misconception: Thinks measuring a qubit in superposition gives both 0 and 1, or a value in between.
  Feedback from the catalogue
  Measuring a qubit always gives one bit: 0 or 1. The superposition sets only the chances. An arrow on the equator gives 0 in half the measurements and 1 in half, and each single measurement is one of them. After the measurement the qubit is no longer in a superposition: it is in the state that was read.
- Wrong Always 0, because the qubit started in $|0\rangle$ ⁠
  Feedback
  The gate changed the state: the arrow no longer points at $|0\rangle$ ⁠. Only with no gate at all does every measurement give 0.
Once the prediction is locked in, the Scene changes
Measure and search
Measurefixed
The Scene then shows: 0.5 · Chance the qubit reads 1 after the gate/nodes/qubit/outputs/probOne
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Each measurement gives one bit, 0 or 1. The arrow’s height sets the chance: on the equator the chance of 1 is $\dfrac{1}{2}$ ⁠, so the tubes fill about equally.

Hint
Measuring a qubit gives one bit. What does the arrow’s height decide?

Worked solution
1. A qubit is drawn as an arrow on a sphere: up is $|0\rangle$ ⁠, down is $|1\rangle$ ⁠.
2. A measurement always gives 0 or 1. The chance of 1 grows the closer the arrow is to the bottom pole.
3. On the equator the arrow is halfway, so the chance of 1 is $\dfrac{1}{2}$ ⁠.
4. Each single measurement is random, and over many about half are 0 and half 1.
If you chose “both” or “half”, you mixed up the state and the measurement: the state can be halfway, but the measurement gives one bit.
Step 2 of 9
Open this step
Phase
Practice · Choose
Question
Choose H, then Z. The Z gate turns the arrow round the equator to the far side. What is the chance a measurement gives 1 now?

Correct answer
- Correct Still a half: Z changed only the phase, not the arrow’s height
Setup, choices and feedback
The Scene at this step
Gate
H, then Z
Search size
4 qubits
Search rounds
0 rounds
Measure and search
Measure
Choices
Shown in a random order.
- Correct Still a half: Z changed only the phase, not the arrow’s height
- Wrong 1: the arrow turned, so the result flipped
  Feedback
  The arrow turned, but about the upright axis. It is still on the equator, at the same height, so the chance has not changed.
- Wrong 0: Z brought the arrow back to $|0\rangle$ ⁠
  Feedback
  Z does not move the arrow up or down. Look at the Scene: it stays on the equator.
Feedback for a right answer
The chance of 1 depends only on the arrow’s height. Z turns it about the upright axis, so the height does not change and a measurement cannot see the difference. But the difference is real, and it is called phase: further gates can turn it into a completely different result.

Hint
The chance of 1 depends only on the arrow’s height. Did Z change the height?

Worked solution
1. After H the arrow is on the equator: a chance of $\dfrac{1}{2}$ ⁠ of 1.
2. Z turns the arrow half a turn about the upright axis, to the far side of the equator.
3. Turning about the upright axis does not change the height, so the chance stays $\dfrac{1}{2}$ ⁠.
4. The two states differ only in phase, and a 0-or-1 measurement cannot tell them apart.
Step 3 of 9
Open this step
Interference
Practice · Predict, then look
Question
One H gate gives half-and-half measurements. What will the chance of 1 be after H, then H?

Correct answer
- Correct 0: every measurement will give 0
Setup, choices and feedback
The Scene at this step
Gate
Hfixed
Search size
4 qubits
Search rounds
0 rounds
Measure and search
Measure
Choices
- Correct 0: every measurement will give 0
- Wrong Still a half: two random steps give a random result
  Misconception: Thinks two gates that each give a fifty-fifty result must together give a fifty-fifty result too.
  Feedback from the catalogue
  The H gate draws no lots: it turns the arrow. One turn brings it to the equator, so a measurement there gives half and half. A second turn carries on round the same circle and brings the arrow back to $|0\rangle$ ⁠. In terms of amplitudes, the two paths that lead to 1 arrive with opposite signs and cancel: that is interference, and without it a quantum computer would be no use.
- Wrong 1: the second gate flips the result
  Feedback
  The second gate does not flip the arrow; it carries on turning it round the same circle, back to where it started, $|0\rangle$ ⁠.
Once the prediction is locked in, the Scene changes
Gate
H, then Hfixed
The Scene then shows: 0 · Chance the qubit reads 1 after the gate/nodes/qubit/outputs/probOne
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
A second H carries the arrow on round the same circle and back to $|0\rangle$ ⁠, so every measurement gives 0. Two paths lead to 1, and they cancel: interference. A quantum computer is built so that the paths to wrong answers cancel and the paths to the answer add up.

Hint
H is a turn, not a draw. Where does the arrow go if it is given the same turn again?

Worked solution
1. H is half a turn about a tilted axis, midway between the upright axis and the $x$ ⁠ axis.
2. One H brings the arrow from $|0\rangle$ ⁠ to the equator: a measurement there gives half and half.
3. A second H is another half turn about the same axis: a full turn in all, and the arrow is back at $|0\rangle$ ⁠.
4. So the chance of 1 is 0.
If you chose “still a half”, you pictured H as tossing a coin. A coin tossed twice stays random, but H is a turn, and two turns can bring you exactly back to the start.
Step 4 of 9
Open this step
Search
Practice · Calculate
Question
The Search size is 6 qubits: $2^6 = 64$ ⁠ items, one of which is the answer. How many Search rounds bring the chance of finding it closest to 100%?

Correct answer
6 ± 0.1
Setup, choices and feedback
The Scene at this step
Gate
H
Search size
6 qubitsfixed
Search rounds
0 roundsfixed
Measure and search
Search
Accepted within
± 0.1
Computed from the Scene at this step’s setting
Rounds that bring the search closest to the answer/nodes/qubit/outputs/bestRounds
Wrong answers it recognises
- 1 ± 0.1
  Misconception: Thinks a quantum computer checks every answer at once and reads off the right one in a single step.
  Feedback from the catalogue
  A superposition of every item does not help on its own: measuring it gives a random item, a blind guess. Grover’s search grows the answer’s chance step by step, by interference, and each round turns the arrow by a small angle. So it takes about $\dfrac{\pi}{4}\sqrt{N}$ ⁠ rounds: far fewer than the $\dfrac{N}{2}$ ⁠ looks of an ordinary search, but far more than one.
- 32 ± 0.6
  Misconception: Thinks a quantum computer checks every answer at once and reads off the right one in a single step.
  Feedback
  32 is about half the items: the average number of looks of an ordinary search, item by item. Grover’s search needs far fewer.
- 8 ± 0.1
  Misconception: Thinks a quantum computer checks every answer at once and reads off the right one in a single step.
  Feedback
  8 is $\sqrt{64}$ ⁠. You left out the $\dfrac{\pi}{4}$ ⁠: each round turns the state by about $\dfrac{2}{\sqrt{N}}$ ⁠ radians, and it only has to reach a right angle, $\dfrac{\pi}{2}$ ⁠.
Feedback for a right answer
$\dfrac{\pi}{4}\sqrt{64} = \dfrac{\pi}{4} \times 8 \approx 6.3$ ⁠, so 6 rounds. After them the chance of finding the answer is about 99.7%. Move the Search rounds in the next Step and check.

Hint
The best number of rounds is about $\dfrac{\pi}{4}\sqrt{N}$ ⁠, rounded down.

Worked solution
1. At the start the state is almost at “every wrong answer”: the angle $\theta$ ⁠ between them has $\sin\theta = \dfrac{1}{\sqrt{N}}$ ⁠, so $\theta \approx \dfrac{1}{\sqrt{N}}$ ⁠.
2. Each round turns the state a further $2\theta$ ⁠ towards the answer, and the answer lies at a right angle, $\dfrac{\pi}{2}$ ⁠.
3. The number of rounds: $\dfrac{\pi/2}{2\theta} = \dfrac{\pi}{4\theta} \approx \dfrac{\pi}{4}\sqrt{N}$ ⁠. Here $\dfrac{\pi}{4} \times \sqrt{64} = \dfrac{\pi}{4} \times 8 \approx 6.3$ ⁠.
4. Round down: 6 rounds. (The sphere in the Scene draws every angle doubled, so its arrow moves $4\theta$ ⁠ a round, from pole to pole; the number of rounds is the same.)
If you answered 1, you thought a quantum computer checks every item at once. It does not: each round raises the answer’s chance only a little.
Step 5 of 9
Open this step
Too many rounds
Practice · Predict, then look
Question
16 items and 3 rounds: the chance of finding the answer is about 96%. What will happen to the chance if you run 6 rounds?

Correct answer
- Correct It will drop a long way
Setup, choices and feedback
The Scene at this step
Gate
H
Search size
4 qubitsfixed
Search rounds
3 roundsfixed
Measure and search
Search
Choices
- Correct It will drop a long way
- Wrong It will rise further, close to 100%
  Misconception: Thinks more rounds of Grover's search always raise the chance of finding the answer.
  Feedback from the catalogue
  Each round turns the arrow by the same angle, from “every wrong answer” towards the answer. After the right number of rounds the arrow is almost on the answer. One more round turns it on, past the answer, and the chance falls again. So you stop at the right number of rounds and measure, rather than carrying on “to be safe”.
- Wrong It will stay about 96%: once the answer is found it stays found
  Misconception: Thinks more rounds of Grover's search always raise the chance of finding the answer.
  Feedback from the catalogue
  Each round turns the arrow by the same angle, from “every wrong answer” towards the answer. After the right number of rounds the arrow is almost on the answer. One more round turns it on, past the answer, and the chance falls again. So you stop at the right number of rounds and measure, rather than carrying on “to be safe”.
Once the prediction is locked in, the Scene changes
Search rounds
6 roundsfixed
The Scene then shows: 0.02038 · Chance the search finds the answer after its rounds/nodes/qubit/outputs/success
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
At 6 rounds the chance falls to about 2%, less even than a blind guess. After 3 rounds the arrow is almost on the answer, and 3 more rounds turn it on, nearly back to “every wrong answer”.

Hint
Each round turns the arrow by the same angle in the same direction. What happens if you keep turning after you arrive?

Worked solution
1. Each round turns the arrow by the same angle, from “every wrong answer” towards the answer.
2. With 16 items, 3 rounds bring it almost to the answer: 96%.
3. A fourth round turns it past the answer, and the chance starts to fall.
4. At 6 rounds the arrow is nearly back at the start, and the chance is about 2%.
That is why Grover’s search must know roughly how many items there are: it stops just in time and measures.
Step 6 of 9
Open this step
A million items
Practice · Choose
Question
In an unsorted store of a million items, an ordinary search checks item after item, and on average needs about half a million looks. About how many rounds does Grover’s search need?

Correct answer
- Correct About 800
Setup, choices and feedback
The Scene at this step
Gate
H
Search size
6 qubits
Search rounds
6 rounds
Measure and search
Search
Choices
Shown in a random order.
- Correct About 800
- Wrong One round: the quantum computer checks them all at once
  Misconception: Thinks a quantum computer checks every answer at once and reads off the right one in a single step.
  Feedback from the catalogue
  A superposition of every item does not help on its own: measuring it gives a random item, a blind guess. Grover’s search grows the answer’s chance step by step, by interference, and each round turns the arrow by a small angle. So it takes about $\dfrac{\pi}{4}\sqrt{N}$ ⁠ rounds: far fewer than the $\dfrac{N}{2}$ ⁠ looks of an ordinary search, but far more than one.
- Wrong About 20, as in binary search
  Feedback
  Binary search needs about $\log_2 10^6 \approx 20$ ⁠ steps, but only in a sorted list, which it can halve at each step. An unsorted store has no order to halve, and Grover needs about $\sqrt{N}$ ⁠ rounds.
- Wrong About half a million, as in an ordinary search
  Feedback
  This is exactly where Grover saves: he needs about $\sqrt{N}$ ⁠ rounds instead of about $\dfrac{N}{2}$ ⁠ looks.
Feedback for a right answer
$\dfrac{\pi}{4}\sqrt{10^6} = \dfrac{\pi}{4} \times 1000 \approx 785$ ⁠ rounds, against about 500,000 looks. The saving is a square root: a hundred times the items need only ten times the rounds. That is a big saving, but not magic: on real hardware each round is slow and noisy, so it pays off only for enormous stores.

Hint
$\sqrt{10^6} = 1000$ ⁠. What does $\dfrac{\pi}{4}\sqrt{N}$ ⁠ give?

Worked solution
1. An ordinary search of an unsorted store: on average $\dfrac{N + 1}{2} \approx 500\,000$ ⁠ looks.
2. Grover: about $\dfrac{\pi}{4}\sqrt{N}$ ⁠ rounds.
3. $\sqrt{10^6} = 1000$ ⁠, so $\dfrac{\pi}{4} \times 1000 \approx 785$ ⁠.
4. The nearest answer: about 800.
Step 7 of 9
Open this step
A flip
Practice · Calculate
Question
Gate: X (NOT). The qubit started at $|0\rangle$ ⁠, and the gate flipped it. What is the chance a measurement gives $0$ ⁠?

Correct answer
0 ± 0.01
Setup, choices and feedback
The Scene at this step
Gate
X (NOT)fixed
Search size
4 qubits
Search rounds
0 rounds
Measure and search
Measure
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Chance the qubit reads 0 after the gate, 1 − probOne/nodes/qubit/outputs/probZero
Feedback for a right answer
$0$ ⁠: after X the qubit always measures $1$ ⁠, like a bit after NOT.

Hint
The X gate moves the arrow from the top pole to the bottom pole.

Worked solution
1. X turns $|0\rangle$ ⁠ into $|1\rangle$ ⁠: the arrow goes from pole to pole.
2. At the bottom pole the chance of measuring $1$ ⁠ is $1$ ⁠, and the chance of measuring $0$ ⁠ is $0$ ⁠.
X is an ordinary computer’s NOT. Only a gate like H, which moves the arrow to the equator, makes a state whose measurement is random.
Step 8 of 9
Open this step
How many items
Practice · Calculate
Question
The Search size is locked at 5 qubits. How many items can they search?

Correct answer
32 ± 0
Setup, choices and feedback
The Scene at this step
Gate
H
Search size
5 qubitsfixed
Search rounds
0 rounds
Measure and search
Search
Accepted within
± 0
Computed from the Scene at this step’s setting
Items in the search, 2^qubits/nodes/qubit/outputs/items
Wrong answers it recognises
- 10 ± 0
  Misconception: Thinks each qubit adds a fixed number of items to a search, rather than doubling it.
  Feedback from the catalogue
  Each qubit doubles the number of combinations: $n$ ⁠ qubits give $2^n$ ⁠ items, not $2n$ ⁠. Five qubits make $32$ ⁠ items, not $10$ ⁠.
Feedback for a right answer
$2^5 = 32$ ⁠ items.

Hint
Each extra qubit doubles the number of combinations of noughts and ones.

Worked solution
1. Each qubit has two values, $0$ ⁠ or $1$ ⁠.
2. Five qubits have $2 \times 2 \times 2 \times 2 \times 2 = 2^5 = 32$ ⁠ combinations, and each combination is one item.
Every qubit added doubles the size of the search: $50$ ⁠ qubits are already enough for more than a million billion items.
Step 9 of 9
Open this step
The ordinary way
Practice · Calculate
Question
The Search size is locked at 6 qubits, $64$ ⁠ items, one of which is the answer. An ordinary search checks item after item, in random order. How many looks does it need on average before it finds the answer, $\dfrac{N + 1}{2}$ ⁠?

Correct answer
32.5 ± 0.1
Setup, choices and feedback
The Scene at this step
Gate
H
Search size
6 qubitsfixed
Search rounds
0 rounds
Measure and search
Search
Accepted within
± 0.1
Computed from the Scene at this step’s setting
Looks a classical search of the unsorted items needs on average, (N + 1)/2/nodes/qubit/outputs/classicalTries
Wrong answers it recognises
- 64 ± 0.1
  Misconception: Thinks an ordinary search of an unsorted list must always check every item.
  Feedback from the catalogue
  The search stops as soon as it finds the answer. Sometimes that is on the first look and sometimes on the last, and on average halfway: $\dfrac{N + 1}{2}$ ⁠ looks. All $N$ ⁠ looks are needed only in the worst case.
Feedback for a right answer
$32.5$ ⁠ looks, against $6$ ⁠ rounds for the quantum search.

Hint
The answer can turn up anywhere from the first look to the last, each equally likely.

Worked solution
1. The answer is found on look $1$ ⁠, $2$ ⁠, … or $64$ ⁠, each equally likely.
2. The average: $\dfrac{64 + 1}{2} = 32.5$ ⁠ looks.
3. A quantum search needs about $\dfrac{\pi}{4}\sqrt{64} \approx 6$ ⁠ rounds.
For a million items: half a million looks against about $800$ ⁠ rounds. The bigger the search, the bigger the advantage.

Across the unit · 13 misconceptions

Misconception catalogue

Each common mistake this unit recognises, in a few words. Open one for what the learner reads when an answer matches it, and where it is asked.

Index

Ray tracing

Two pictures

Question

Correct answer

The Scene at this step

Choices

Hint

Worked solution

Camera rays

Question

Correct answer

The Scene at this step

Choices

Hint

Worked solution

Shadow rays

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Hint

Worked solution

Bounces

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

Noise

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Hint

Worked solution

The whole picture

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

A feedback loop

The loop

Question

Correct answer

The Scene at this step

Choices

Hint

Worked solution

Too little gain

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Hint

Worked solution

Settling time

Question

Goal

The Scene at this step

One setting that reaches it

Hint

Worked solution

Overshoot

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Hint

Worked solution

Delay

Question

Correct answer

The Scene at this step