search

Renmusxd / RustQIP

Quantum computing using rust. Efficient and a borrow-checked no cloning theorem!
https://docs.rs/qip/
MIT License
223 stars 18 forks source link

Document grovers algorithm example #37

Closed oxarbitrage closed 2 years ago

oxarbitrage commented 2 years ago

Grovers algorithm code (https://github.com/Renmusxd/RustQIP/blob/master/examples/grovers.rs) has no comments in the code so understating how it works is not easy.

For example i can't understand why iterating 100 times with an N of 10 and how the correct key value x (42) is found from the printed outputs:

0   0.00877
1   0.02422
2   0.04711
3   0.07706
4   0.11362
5   0.15621
6   0.20416
7   0.25673
8   0.31310
9   0.37239
10  0.43367
11  0.49598
12  0.55836
13  0.61982
14  0.67942
15  0.73621
16  0.78932
17  0.83791
18  0.88123
19  0.91859
20  0.94943
21  0.97324
22  0.98967
23  0.99846
24  0.99946
25  0.99267
26  0.97819
27  0.95624
28  0.92717
29  0.89144
30  0.84959
31  0.80229
32  0.75026
33  0.69433
34  0.63537
35  0.57430
36  0.51206
37  0.44964
38  0.38800
39  0.32811
40  0.27091
41  0.21728
42  0.16806
43  0.12402
44  0.08586
45  0.05416
46  0.02941
47  0.01202
48  0.00224
49  0.00023
50  0.00602
51  0.01953
52  0.04053
53  0.06870
54  0.10361
55  0.14471
56  0.19135
57  0.24281
58  0.29828
59  0.35690
60  0.41776
61  0.47990
62  0.54235
63  0.60415
64  0.66431
65  0.72192
66  0.77605
67  0.82588
68  0.87063
69  0.90958
70  0.94215
71  0.96781
72  0.98617
73  0.99694
74  0.99995
75  0.99516
76  0.98264
77  0.96258
78  0.93531
79  0.90124
80  0.86091
81  0.81494
82  0.76406
83  0.70905
84  0.65078
85  0.59016
86  0.52813
87  0.46566
88  0.40373
89  0.34330
90  0.28532
91  0.23069
92  0.18026
93  0.13482
94  0.09508
95  0.06167
96  0.03509
97  0.01578
98  0.00402
99  0.00000

@Renmusxd if you can explain me briefly how it works in this issue i will be happy to send a PR to add comments details to the file.

Renmusxd commented 2 years ago

I can comment this - my mistake, essentially what the code is doing here is demonstrating that the probability of measuring the marked state is oscillating since each application of Us Uw is rotating by some angle. Since rotations are by 2 pi*sqrt(1/N) we see that 100 iterations goes full circle (maximizing the probability when at 25 and 75 since it's aligned and antialigned [which doesn't matter up to a global phase]). I'll take care of the documentation though to fully explain the reasoning.

Renmusxd commented 2 years ago

We don't see the correct key from the output, instead we see the chance you'd get the correct key if you stopped the algorithm at N iterations.

Renmusxd commented 2 years ago

Addressed in 56757b5a3eb2474542aa8a47ff839470d98d4f91