Quantenalgorithmen und Implementierung - Teil 1

1. 00:00Welcome back to the course Quantum Algorithms and their Implementation. Let us now continue with Grover's algorithm.
2. 00:08In the last video, I showed you how, by applying the oracle that defines the one base state in which
3. 00:17the solution to the problem is encoded, how to give that state a negative sign. The next step
4. 00:27which one does now, is to calculate the mean value of all amplitudes and to apply to this mean value
5. 00:36then mirror all amplitudes.
6. 00:39That is, I take my amplitudes that we just calculated, three times and a half, once minus and a half, I calculate
7. 00:48the mean value of that, which would be a quarter, and I mirror all the amplitudes to that mean value.
8. 00:55This mirroring at the mean can be formulated mathematically by the figure: Amplitude passes into twice the
9. 01:03mean value of all amplitudes minus a. In our example, it leads to the fact that all amplitudes, which have the value one half
10. 01:12become zero and the amplitude minus one half becomes one.
11. 01:20And that's about it for the simplest case of two qubits.
12. 01:24So the element X hat we are looking for now has the amplitude one and all other amplitudes have the value zero.
13. 01:33That means if I now measure X, if I make a measurement on this system, then I immediately find the sought after
14. 01:41Solution.
15. 01:42That means we have reached the goal.
16. 01:45At this point, of course, you are happy that it worked and you think that it would also have worked in all other constellations.
17. 01:52just as easy.
18. 01:54Unfortunately, it isn't. Now, if we start or look at larger systems,
19. 01:59the next larger system would be the system with n equals three, with three qubits, that is large n the number of my base
20. 02:09states is eight. There it showed up, if one carries out this calculation analogously, that after application of the oracle after
21. 02:21reflection at the mean value the amplitude for x hat
22. 02:26contains the value five half five half by root eight, for all other amplitudes contains one half by root eight.
23. 02:36That is, we have a small gain of our sought amplitudes, but not yet such that we can be very sure of
24. 02:45that it is indeed the correct amplitude.
25. 02:49That is, if we were to measure now, then the noise in the measurement may mask the effect here.
26. 02:59What we can do at that point, though: We can do this principle of amplitude amplification several times
27. 03:07Now, performing this amplitude amplification again means I apply the oracle to the circuit again
28. 03:15again,
29. 03:16I do again this reflection at the mean value, then I get in the case of three qubits for the probability of the
30. 03:24target vector, of the target state already the value 121 by 128. That means a value which is not equal to one but nevertheless
31. 03:35is already very close to one. At this point, one could think that I have to use this circuit,
32. 03:46the oracle, do the amplitude amplifications only often enough, then I'll surely end up at some point with mine at
33. 03:54the value one. Again, it's not quite that simple.
34. 03:58It can happen that if one makes these iterations too much, that the amplitude amplification is destroyed again.
35. 04:06becomes.
36. 04:06That is, the art is to turn in this application of the oracle, amplitude amplification just right,
37. 04:16as often as you have to, but please, not more often. We'll see that in a moment how often you can generally use
38. 04:25case you have to apply this principle. At this point, an intermediate step is now missing in the argumentation and this intermediate step
39. 04:36consists in showing, in the general case of n qubits, that this reflection at the mean, which we performed
40. 04:45Have that this is indeed a unitary transformation. In the case of two qubits, you can show that easily. In the case
41. 04:54of multiple qubits when small n is indeterminate, you can see here on the slide the corresponding
42. 05:02equation and by doing a little bit longer calculation you can convince yourself that this transformation is indeed
43. 05:10is unitary. Means this can be represented then again as basis as application of gates. That is
44. 05:21i can perform this on the quantum computer. This iteration, the application of the oracle, and then subsequent
45. 05:30Mirroring at the mean, which is usually called Grover integration.
46. 05:37This Grover iteration also has a geometric illustration. In this geometric illustration
47. 05:47one tries to simplify the complex situation of n qubits a bit by starting from the
48. 05:59general case. In the general case, the small n qubits would be in a complex vector space.
49. 06:08And I'm now considering a two-dimensional cut through this complex vector space. In this
50. 06:16two-dimensional cut, I have on the one hand my sought solution of this x hat, which is here in the picture arrow
51. 06:24drawn upwards and I have the state S. The state S, is the uniform superposition of all my qubits.
52. 06:34That is, my target state X hat contributes to the uniform superposition
53. 06:47as do the other states with weight one by root two to the power of n. Perpendicular to my sought target state
54. 06:56are just then the other states which are perpendicular to n. This is the starting position before
55. 07:06Grover iteration.
56. 07:10if I start now with the Grover iteration, so if I apply the oracle, then the solution state gets
57. 07:19a minus sign. Means in the little picture the vector X hat is mirrored at the X axis all other states remain the same,
58. 07:30this means then the superposition of all my base states, from the red S into the green one
59. 07:39S transitions.
60. 07:39That is, the S vector flips down. This is the application of the oracle. In the second step, I now perform this reflection
61. 07:50at the mean value and this reflection at the mean value
62. 07:54is now done in such a way that I no longer mirror at the X axis, but mirror at the S state.
63. 08:03That means my green down arrow is flipped up and you can see in these little pictures that
64. 08:11after performing a Grover iteration, my overall state S is closer to the solution we are looking for X hut-
65. 08:21has moved. Now this execution of the algorithm, of the iteration can be done several times.
66. 08:28With each iteration, the green arrow moves successively upward.
67. 08:34That would be the geometric interpretation here from the Grover algorithm.
68. 08:41Now if you do this formally, do the exact calculation, you see that after each Grover iteration the
69. 08:50state of the system is rotated by the angle two by root large n.
70. 08:58Now, if I do these steps often enough, scaled by roots n, you can see that the angle between
71. 09:08the total state and the solution state is only one by root n.
72. 09:16This means that the Grove algorithm can get by with a total of root large n oracle calls.
73. 09:25So we have a quadratic speedup compared to a classical algorithm that takes n calls to solve the problem
74. 09:35is needed.
75. 09:36We have a quadratic speedup here, a quadratic acceleration.
76. 09:41That means in my problem from the lottery wheel that I started with in the Grover algorithm, we wouldn't have to do 100 times
77. 09:49into the lottery drum, but only ten times into the lottery drum to draw the main prize. This is the
78. 09:57Grover algorithm.

Щоб увімкнути запис, виберіть мову в меню налаштувань відео.