stephenjordan.github.io/FrenchV1_8.html at master · stephenjordan/stephenjordan.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html
  PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr" lang="fr">

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  <title>Zoo des Algorithmes Quantiques</title>
  <meta name="description" content="Une liste complète des algorithmes quantiques." />
  <meta name="keywords" content="algorithme quantique algorithmes zoo liste catalogue" />
  <meta name="author" content="Stephen Jordan" />
  <link rel="stylesheet" type="text/css" href="newzoo.css" />
  <script type="text/javascript" id="MathJax-script" async
    src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
  <link rel="icon" type="image/png" sizes="16x16" href="favicon/favicon_16px.png">
  <link rel="icon" type="image/png" sizes="32x32" href="favicon/favicon_32px.png">
  <link rel="icon" type="image/png" sizes="48x48" href="favicon/favicon_48px.png">
  <link rel="apple-touch-icon" sizes="180x180" href="favicon/favicon_180px.png">
</head>

<body>
  <div id="wrap">
    <div id="header">
      <h1>Zoo des Algorithmes Quantiques</h1>
    </div>
    <div id="main">
      <div id="notice">
        <p>Ceci est un catalogue complet des algorithmes quantiques. Si vous remarquez des erreurs ou des omissions,
          veuillez m'envoyer un e-mail à spj.jordan@gmail.com. (Alternativement, vous pouvez soumettre une pull request
           sur ce <a href="https://github.com/stephenjordan/stephenjordan.github.io">dépôt</a> GitHub.) Bien que
          je ne puisse garantir une réponse rapide, votre aide est appréciée et sera <a
            href="#acknowledgments">reconnue</a>.</p>
      </div>

      <a name="algebraic"></a>
      <h2>Algorithmes Algébriques et Théoriques des Nombres</h2>

      <b>Algorithme :</b> Factorisation<br />
      <b>Accélération :</b> Superpolynomiale<br />
      <b>Implémentation :</b> <a href="https://short.classiq.io/shor">Classiq</a>, <a
        href="https://github.com/quantumlib/Cirq/blob/main/examples/shor.py">Cirq</a><br />
      <b>Description :</b> Étant donné un entier <i>n</i>-bit, trouver la factorisation en nombres premiers.
      L'algorithme quantique de Peter Shor résout cela en \( \widetilde{O} (n^3) \) temps
      [<a href="#Shor_factoring">82</a>,<a href="#Shor_factoring94">125</a>].
      L'algorithme classique le plus rapide connu pour la factorisation d'entiers est le crible général des nombres, qui
      est censé fonctionner en temps \(
      2^{\widetilde{O}(n^{1/3})} \). La meilleure limite supérieure rigoureusement prouvée sur la complexité classique
      de la factorisation est \( O(2^{n/4+o(1)}) \) via l'algorithme de Pollard-Strassen
      [<a href="#Pol">252</a>, <a href="#Stras">362</a>]. L'algorithme de factorisation de Shor brise le chiffrement à
      clé publique RSA et les algorithmes quantiques étroitement liés pour les logarithmes discrets brisent les schémas
      de signature numérique DSA et ECDSA et le protocole d'échange de clés de Diffie-Hellman. Un algorithme quantique
      encore plus rapide que celui de Shor pour le cas spécial de la factorisation des « semi-premiers », qui sont
      largement utilisés en cryptographie, est donné dans [<a href="#GLFB15">271</a>].
      Si de petits facteurs existent, l'algorithme de Shor peut être battu par un algorithme quantique utilisant la
      recherche de Grover pour accélérer la méthode de factorisation par courbe elliptique
      [<a href="#PQRSA">366</a>]. Des versions optimisées supplémentaires de l'algorithme de Shor sont données dans
      [<a href="#EH17">384</a>, <a href="#BBM17">386</a>, <a href="#GE21">431</a>].
      Il existe des systèmes de chiffrement à clé publique classiques qui ne sont pas censés être brisés par des
      algorithmes quantiques, <i>cf.</i>
      [<a href="#BBD09">248</a>]. Au cœur de l'algorithme de factorisation de Shor se trouve la recherche d'ordre, qui
      peut être réduite au <a href="#abelian_HSP">problème du sous-groupe caché abélien</a>,
      qui est résolu à l'aide de la transformation de Fourier quantique. Un certain nombre d'autres
      problèmes sont connus pour se réduire à la factorisation entière, y compris le
      problème d'appartenance pour les groupes de matrices sur des corps de degré impair
      [<a href="#BBS09">253</a>], et certains problèmes diophantiens pertinents pour
      la synthèse de circuits quantiques [<a href="#RS12">254</a>].
      <br /><br />

      <b>Algorithme :</b> Logarithme discret<br />
      <b>Accélération :</b> Superpolynomiale<br />
      <b>Implémentation :</b> <a href="https://short.classiq.io/discrete_log">Classiq</a><br />
      <b>Description :</b> Nous avons trois nombres <i>n</i>-bit <i>a</i>, <i>b</i>, et <i>N</i>, avec la promesse que
      \( b = a^s \mod N \) pour un certain <i>s</i>. La tâche est de trouver <i>s</i>.
      Comme le montre Shor [<a href="#Shor_factoring">82</a>], cela peut être réalisé
      sur un ordinateur quantique en poly(<i>n</i>) temps. L'algorithme classique le plus rapide
      nécessite un temps superpolynomial en <i>n</i>. Grâce à des techniques similaires à celles de [<a
        href="#Shor_factoring">82</a>], les ordinateurs quantiques
      peuvent résoudre le problème du logarithme discret sur des courbes elliptiques, brisant ainsi
      la cryptographie à courbe elliptique [<a href="#Zalka_ellip">109</a>, <a href="#BL95">14</a>].
      D'autres optimisations de l'algorithme de Shor sont données dans [<a href="#E17">385</a>, <a
        href="#RNSL17">432</a>].
      L'accélération quantique superpolynomiale a également été étendue au problème du logarithme discret sur des
      semi-groupes [<a href="#Childs_Ivanyos">203</a>,
      <a href="#Banin_Tsaban">204</a>]. Voir aussi <a href="#abelian_HSP">sous-groupe caché abélien</a>.
      <br /><br />

      <b>Algorithme :</b> Équation de Pell<br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Étant donné un entier positif non carré <i>d</i>,
      l'équation de Pell est \( x^2 - d y^2 = 1 \). Pour tout <i>d</i> tel que
      il existe une infinité de paires d'entiers (<i>x,y</i>) résolvant cette équation. Soit \( (x_1,y_1) \) la paire
      qui minimise
      \( x+y\sqrt{d} \). Si <i>d</i> est un entier <i>n</i>-bit
      (<i>c'est-à-dire</i> \( 0 \leq d \lt 2^n \) ), \( (x_1,y_1) \)
      peut en général nécessiter un nombre exponentiel de bits pour être écrit. Ainsi, il
      est en général impossible de trouver \( (x_1,y_1) \) en temps polynomial.
      Soit \( R = \log(x_1+y_1 \sqrt{d}) \). \( \lfloor R \rceil \)
      identifie de manière unique \( (x_1,y_1) \). Comme le montre Hallgren
      [<a href="#Hallgren_Pell">49</a>], étant donné un nombre
      <i>n</i>-bit <i>d</i>, un ordinateur quantique peut trouver \( \lfloor R \rceil \)
      en poly(<i>n</i>) temps. Aucun algorithme classique en temps polynomial pour
      ce problème n'est connu. La factorisation se réduit à ce problème. Cet
      algorithme brise le système de cryptage Buchman-Williams. Voir aussi <a href="#abelian_HSP">sous-groupe caché
        abélien</a>.
      <br /><br />

      <b>Algorithme :</b> Idéal Principal <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Nous avons un entier <i>n</i>-bit <i>d</i> et un
      idéal inversible <i>I</i> de l'anneau \( \mathbb{Z}[\sqrt{d}] \).
      <i>I</i> est un idéal principal s'il existe \( \alpha \in \mathbb{Q}(\sqrt{d}) \)
      tel que \( I = \alpha \mathbb{Z}[\sqrt{d}] \). \( \alpha \) peut être exponentiellement
      grand en <i>d</i>. Par conséquent, \( \alpha \) ne peut en général même pas être écrit
      en temps polynomial. Cependant, \( \lfloor \log \alpha \rceil \)
      identifie de manière unique \( \alpha \). La tâche est de déterminer si <i>I</i>
      est principal et si oui, de trouver \( \lfloor \log \alpha \rceil \).
      Comme le montre Hallgren, cela peut être fait en temps polynomial sur un ordinateur quantique
      [<a href="#Hallgren_Pell">49</a>]. Un algorithme quantique modifié pour ce problème
      utilisant moins de qubits a été donné dans [<a href="#Schmidt_PIP">131</a>]. Un algorithme
      quantique résolvant le problème de l'idéal principal dans des corps de degré arbitraire
      (<i>c'est-à-dire</i> évoluant polynômialement en degré) a été donné par la suite dans
      [<a href="#Biasse_Song16">329</a>]. La factorisation se réduit à la résolution de l'équation de Pell,
      qui se réduit au problème de l'idéal principal. Ainsi, le problème de l'idéal principal
      est au moins aussi difficile que la factorisation et n'est donc probablement pas dans P. Voir aussi
      <a href="#abelian_HSP">sous-groupe caché abélien</a>.
      <br /><br />

      <b>Algorithme :</b> Groupe Unitaire <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Le corps de nombres \( \mathbb{Q}(\theta) \)
      est dit de degré <i>d</i> si le polynôme de plus bas degré dont
      \( \theta \) est une racine a un degré <i>d</i>. L'ensemble \( \mathcal{O} \)
      des éléments de \( \mathbb{Q}(\theta) \) qui sont racines de polynômes moniques dans
      \( \mathbb{Z}[x] \) forme un anneau, appelé l'anneau des entiers de
      \( \mathbb{Q}(\theta) \). L'ensemble des unités (éléments inversibles) de l'anneau
      \( \mathcal{O} \) forme un groupe noté \( \mathcal{O}^* \). Comme le montre
      Hallgren [<a href="#Hallgren_unit">50</a>], et indépendamment par Schmidt et
      Vollmer [<a href="#Schmidt">116</a>], pour tout \( \mathbb{Q}(\theta) \)
      de degré fixe, un ordinateur quantique peut trouver en temps polynomial un ensemble
      de générateurs pour \( \mathcal{O}^* \) donné une description de \( \theta \).
      Aucun algorithme classique en temps polynomial pour ce problème n'est connu. Hallgren
      et ses collaborateurs ont ensuite découvert comment obtenir une échelle polynomiale
      en degré [<a href="#EHKS14">213</a>]. Voir aussi [<a href="#Biasse_Song16">329</a>].
      Les algorithmes reposent sur la résolution de problèmes de sous-groupes cachés abéliens sur le groupe additif des
      réels.
      <br /><br />

      <b>Algorithme :</b> Groupe de Classes <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b>
      Le corps de nombres \( \mathbb{Q}(\theta) \)
      est dit de degré <i>d</i> si le polynôme de plus bas degré dont
      \( \theta \) est une racine a un degré <i>d</i>. L'ensemble \( \mathcal{O} \)
      des éléments de \( \mathbb{Q}(\theta) \) qui sont racines de polynômes moniques dans
      \( \mathbb{Z}[x] \) forme un anneau, appelé l'anneau des entiers de
      \( \mathbb{Q}(\theta) \), qui est un domaine de Dedekind. Pour un domaine de Dedekind, les idéaux fractionnaires
      non nuls modulo les idéaux principaux non nuls forment un groupe appelé le groupe de classes.
      Comme le montre Hallgren [<a href="#Hallgren_unit">50</a>], un ordinateur quantique peut trouver
      un ensemble de générateurs pour le groupe de classes de l'anneau des
      entiers de tout corps de nombres de degré constant, donné une description de \( \theta \), en temps
      poly(log(\( | \mathcal{O} | \))). Un algorithme quantique amélioré, dont le temps d'exécution est également
      polynomial en <i>d</i>, a été donné par la suite dans [<a href="#Biasse_Song16">329</a>].
      Aucun algorithme classique en temps polynomial pour ces problèmes n'est connu. Voir aussi <a
        href="#abelian_HSP">sous-groupe caché abélien</a>.
      <br /><br />

      <b>Algorithme :</b> Sommes de Gauss <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Soit \( \mathbb{F}_q \) un corps fini. Les éléments autres
      que zéro de \( \mathbb{F}_q \) forment un groupe \( \mathbb{F}_q^\times \) sous
      multiplication, et les éléments de \( \mathbb{F}_q \) forment un groupe (abélien mais
      pas nécessairement cyclique) \( \mathbb{F}_q^+ \) sous addition. Nous pouvons choisir
      un certain caractère \( \chi^\times \) de \( \mathbb{F}_q^\times \) et un
      caractère \( \chi^+ \) de \( \mathbb{F}_q^+ \). La somme de Gauss correspondante
      est le produit intérieur de ces caractères :
      \( \sum_{x \neq 0 \in \mathbb{F}_q} \chi^+(x) \chi^\times(x) \)
      Comme le montre van Dam et Seroussi [<a href="#vanDam_Gauss">90</a>], les sommes de Gauss
      peuvent être estimées à une précision polynomiale sur un ordinateur quantique en temps polynomial.
      Bien qu'un anneau fini ne forme pas un groupe sous
      multiplication, son ensemble d'unités le fait. En choisissant une représentation pour
      le groupe additif de l'anneau, et en choisissant une représentation pour le
      groupe multiplicatif de ses unités, on peut obtenir une somme de Gauss sur
      les unités d'un anneau fini. Celles-ci peuvent également être estimées à une précision polynomiale sur un
      ordinateur quantique en temps polynomial [<a href="#vanDam_Gauss">90</a>]. Aucun algorithme classique en temps
      polynomial
      pour estimer les sommes de Gauss n'est connu. Le logarithme discret
      se réduit à l'estimation de la somme de Gauss [<a href="#vanDam_Gauss">90</a>]. Certaines fonctions de partition
      du modèle Potts peuvent être calculées par un algorithme quantique en temps polynomial
      lié à l'estimation de la somme de Gauss [<a href="#Geraci_exact">47</a>].
      <br /><br />

      <b>Algorithme :</b> Preuve de Primalité<br />
      <b>Accélération :</b> Polynomiale<br />
      <b>Description :</b> Étant donné un nombre <i>n</i>-bit, retourner une preuve de sa primalité. Les algorithmes
      classiques les plus rapides sont AKS, dont les meilleures versions [<a href="#AKS1">393</a>, <a
        href="#AKS2">394</a>] ont
      une complexité essentiellement quartique, et ECPP, où la complexité heuristique de la version la plus rapide
      [<a href="#ECPP">395</a>] est également essentiellement quartique. L'algorithme quantique le plus rapide connu
      pour ce
      problème est la méthode de Donis-Vela et Garcia-Escartin [<a href="#DVGE">396</a>], avec une complexité
      \( O(n^2 (\log \ n)^3 \log \ \log \ n) \). Cela améliore un algorithme quantique basé sur la factorisation
      pour la preuve de primalité [<a href="#ChauLo">397</a>] qui a une complexité \( O(n^3 \log \ n \ \log \ \log \ n)
      \).
      Un résultat récent de Harvey et Van Der Hoeven [<a href="#HVDH">398</a>] peut être utilisé pour améliorer la
      complexité de l'algorithme quantique basé sur la factorisation pour la preuve de primalité à \( O(n^3 \log n) \)
      et il peut être possible de réduire de manière similaire la complexité de l'algorithme de
      Donis-Vela-Garcia-Escartin
      à \( O(n^2 (\log \ n)^3) \) [<a href="#Greathouse">399</a>].
      <br /><br />

      <b>Algorithme :</b> Résolution de Congruences Exponentielles<br />
      <b>Accélération :</b> Polynomiale<br />
      <b>Description :</b>
      Nous avons \( a,b,c,f,g \in \mathbb{F}_q \). Nous devons trouver des entiers \(x,y\)
      tels que \( a f^x + b g^y = c \). Comme le montre [<a href="#VDS08">111</a>],
      les ordinateurs quantiques peuvent résoudre ce problème en \( \widetilde{O}(q^{3/8}) \) temps alors que le
      meilleur
      algorithme classique nécessite \( \widetilde{O}(q^{9/8}) \) temps. L'algorithme quantique de
      [<a href="#VDS08">111</a>] est basé sur les algorithmes quantiques pour les logarithmes discrets
      et la recherche.
      <br /><br />

      <b>Algorithme :</b> Éléments de Matrice et Coefficients de Kronecker des Représentations de Groupes<br />
      <b>Accélération :</b> Superpolynomiale<br />
      <b>Description :</b> Toutes les représentations de groupes finis et de groupes linéaires compacts peuvent être
      exprimées comme des matrices unitaires données un choix approprié de
      base. Conjuguant la représentation régulière d'un groupe par le circuit de transformation de Fourier quantique sur
      ce groupe, on obtient une somme directe
      des représentations irréductibles du groupe. Ainsi, la transformation de Fourier quantique efficace sur le groupe
      symétrique [<a href="#Beals_general">196</a>], ainsi que le test de Hadamard, permettent un algorithme quantique
      rapide pour approximer
      individuellement les éléments de matrice des représentations irréductibles du \( S_n \). De même, en utilisant la
      transformation de Schur quantique [<a href="#Schur">197</a>], on peut approximer efficacement les éléments de
      matrice des représentations irréductibles de SU(n) qui ont un poids polynomial.
      Des mises en œuvre directes des représentations irréductibles individuelles pour
      les groupes U(n), SU(n), SO(n), et \( A_n \) par des circuits quantiques efficaces sont données dans [<a
        href="#SPJ08">106</a>]. Des instances qui semblent
      exponentiellement difficiles pour les algorithmes classiques connus sont également
      identifiées dans [<a href="#SPJ08">106</a>]. Les coefficients de Kronecker comptent la multiplicité
      d'une représentation irréductible donnée dans le produit tensoriel d'une paire de représentations irréductibles
      données. Dans [<a href="#BCG23">460</a>], il est montré que les coefficients de Kronecker normalisés du groupe
      symétrique peuvent être approximés à une erreur additive inverse polynomiale par un algorithme quantique en temps
      polynomial, tandis qu'aucun algorithme classique en temps polynomial n'est connu pour atteindre cela.<br /><br />

      <b>Algorithme :</b> Vérification des Produits de Matrices <br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Étant donné trois matrices \( n \times n \), <i>A,B</i>, et <i>C</i>,
      le problème de vérification du produit de matrices consiste à décider si <i>AB=C</i>.
      Classiquement, le meilleur algorithme (randomisé) atteint cela en temps \( O(n^2) \),
      tandis que le meilleur algorithme classique pour la multiplication de matrices fonctionne en temps
      \( O(n^{2.373}) \). Ambainis <i>et al.</i> ont découvert un algorithme quantique pour ce
      problème avec un temps d'exécution \( O(n^{7/4}) \) [<a href="#Ambainis_matrix">6</a>]. Par la suite,
      Buhrman et &#352;palek ont amélioré cela, obtenant un algorithme quantique pour ce
      problème avec un temps d'exécution \( O(n^{5/3}) \) [<a href="#Buhrman_matrix">19</a>]. Cet algorithme
      est basé sur des résultats concernant les marches quantiques qui ont été prouvés dans
      [<a href="#Szegedy">85</a>].
      <br /><br />

      <b>Algorithme :</b> Sous-ensemble-somme <br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Étant donné une liste d'entiers \( x_1,\ldots,x_n \), et
      un entier cible <i>s</i>, le problème de sous-ensemble-somme consiste à déterminer
      si la somme de n'importe quel sous-ensemble des entiers donnés s'additionne à
      <i>s</i>. Ce problème est NP-complet, et il est donc peu probable qu'il soit
      résoluble par des algorithmes classiques ou quantiques avec une complexité
      pire que polynomiale. Dans les cas difficiles, les entiers donnés
      sont de l'ordre de \( 2^n \) et de nombreuses recherches sur le problème de sous-ensemble-somme se concentrent sur
      les instances de cas moyen dans ce régime. Dans [<a href="#BJLM13">178</a>], un algorithme
      quantique est donné qui résout de telles instances en temps \( 2^{0.241n} \),
      jusqu'à des facteurs polynomiaux. Cet algorithme quantique fonctionne en appliquant une
      variante de l'algorithme de marche quantique d'Ambainis pour
      l'élément distinct [<a href="#Ambainis_distinctness">7</a>] pour accélérer un algorithme
      classique sophistiqué pour ce problème dû à Howgrave-Graham et
      Joux. L'algorithme classique le plus rapide pour de telles instances de sous-ensemble-somme fonctionne en temps
      \( 2^{0.291n} \), jusqu'à des facteurs polynomiaux [<a href="#BCJ11">404</a>].<br /><br />

      <b>Algorithme :</b> Décodage <br />
      <b>Accélération :</b> Varie <br />
      <b>Description :</b> Les codes de correction d'erreurs classiques permettent la
      détection et la correction des inversions de bits en stockant les données
      de manière redondante. Le décodage par maximum de vraisemblance pour des
      codes linéaires arbitraires est NP-complet dans le pire des cas, mais pour des codes structurés ou des erreurs
      bornées, des algorithmes de décodage efficaces sont connus. Des algorithmes quantiques ont
      été formulés pour accélérer le décodage des codes convolutionnels
      [<a href="#GM14">238</a>] et des codes simplex
      [<a href="#BZ98">239</a>].<br /><br />

      <b>Algorithme :</b> Cryptanalyse Quantique <br />
      <b>Accélération :</b> Divers <br />
      <b>Description :</b> Il est bien connu que les algorithmes de Shor pour
      la factorisation et les logarithmes discrets
      [<a href="#Shor_factoring">82</a>,<a href="#Shor_factoring94">125</a>]
      brisent complètement les systèmes de chiffrement RSA et Diffie-Hellman, ainsi que
      leurs variantes basées sur les courbes elliptiques [<a href="#Zalka_ellip">109</a>, <a href="#BL95">14</a>].
      (Un certain nombre de systèmes de chiffrement à clé publique "post-quantique" ont été proposés pour remplacer ces
      primitives, qui ne sont pas connus pour être brisés par des attaques quantiques.)
      Au-delà de l'algorithme de Shor, il existe un corpus croissant de travaux sur des algorithmes
      quantique spécifiquement conçus pour attaquer les systèmes de chiffrement. Ces
      algorithmes tombent généralement dans trois catégories. La première est des algorithmes quantiques
      fournissant des attaques en temps polynomial ou sub-exponentiel sur des systèmes de chiffrement
      sous des hypothèses standard. En particulier, l'algorithme de Childs,
      Jao et Soukharev pour trouver des isogénies de courbes elliptiques brise
      certains systèmes de chiffrement basés sur des courbes elliptiques en temps subexponentiel
      qui n'ont pas déjà été brisés par l'algorithme de Shor
      [<a href="#CJS14">283</a>]. La deuxième catégorie est des algorithmes quantiques
      réalisant une amélioration polynomiale par rapport aux attaques cryptanalytiques classiques connues en accélérant
      des parties de ces algorithmes classiques à l'aide
      de la recherche de Grover, de la recherche de collisions quantiques, etc. De telles attaques
      sur des clés privées [<a href="#GLRS15">284</a>, <a href="#AMGMPS16">285</a>, <a href="#K14">288</a>, <a
        href="#BHT98b">315</a>, <a href="#B09">316</a>]
      et des clés publiques [<a href="#LMP13">262</a>, <a href="#F15">287</a>] ne précluent pas l'utilisation des
      systèmes de chiffrement associés mais peuvent influencer
      le choix de la taille de la clé. La troisième catégorie est des attaques qui utilisent des
      requêtes de superposition quantique sur des chiffrements par blocs. Ces attaques dans de nombreux cas brisent
      complètement
      les primitives cryptographiques [<a href="#KLLNP16">286</a>, <a href="#KM10">289</a>,
      <a href="#KM12">290</a>, <a href="#RS13">291</a>, <a href="#SS16">292</a>].
      Cependant, dans la plupart des situations pratiques, de telles requêtes de superposition sont
      peu susceptibles d'être réalisables.

      <hr />

      <a name="oracular"></a>
      <h2>Algorithmes Oraculaires</h2>

      <b>Algorithme :</b> Recherche <br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Implémentation :</b> <a href="https://short.classiq.io/quantum_counting">Classiq</a>, <a
        href="https://github.com/quantumlib/Cirq/blob/main/examples/grover.py">Cirq</a><br />
      <b>Description :</b> Nous avons un oracle avec <i>N</i>
      entrées autorisées. Pour une entrée <i>w</i> ("le gagnant"), la sortie correspondante est
      1, et pour toutes les autres entrées, la sortie correspondante est 0. La tâche est de trouver
      <i>w</i>. Sur un ordinateur classique, cela nécessite \( \Omega(N) \)
      requêtes. L'algorithme quantique de Lov Grover atteint cela en utilisant
      \( O(\sqrt{N}) \) requêtes [<a href="#Grover_search">48</a>], ce qui est
      optimal [<a href="#BBBV">216</a>]. Cet algorithme a
      ensuite été généralisé pour rechercher en présence de plusieurs
      "gagnants" [<a href="#BBHT98">15</a>], évaluer la somme d'une fonction arbitraire [<a href="#BBHT98">15</a>,<a
        href="#BHT98">16</a>,<a href="#Mos98">73</a>],
      trouver la moyenne, la médiane et le minimum global d'une fonction arbitraire
      [<a href="#DH96">35</a>,<a href="#NW99">75</a>, <a href="#KLPF08">255</a>,<a href="#KO23">465</a>,<a
        href="#CHJ22">472</a>], tirer parti d'états initiaux alternatifs [<a href="#Biham">100</a>] ou de priors
      probabilistes non uniformes
      [<a href="#Montanaro">123</a>], travailler avec des oracles dont le temps d'exécution varie
      entre les entrées [<a href="#Ambainis_linear">138</a>], approximer
      des intégrales définies [<a href="#integration">77</a>], et converger vers un
      point fixe
      [<a href="#G05">208</a>, <a href="#TGP05">209</a>, <a href="#GSLW19">433</a>]. Des considérations sur
      l'optimisation
      de la profondeur des circuits de recherche quantiques sont données dans [<a href="#ZK19">405</a>]. La
      généralisation de l'algorithme de Grover connue sous le nom d'estimation d'amplitude
      [<a href="#Amplitude">17</a>]
      est maintenant un élément fondamental dans les algorithmes quantiques. L'estimation d'amplitude forme le
      cœur de la plupart des algorithmes quantiques connus liés à la recherche de collisions et aux propriétés de
      graphes. Une des applications naturelles de la recherche de Grover est d'accélérer la
      solution à des problèmes NP-complets tels que 3-SAT. Le faire n'est pas trivial, car
      le meilleur algorithme classique pour 3-SAT n'est pas tout à fait une recherche brute. Néanmoins,
      l'amplification d'amplitude permet une accélération quadratique quantique par rapport au meilleur
      algorithme classique de 3-SAT, comme le montre [<a href="#Ambainis_SIGACT">133</a>]. Des
      accélérations quadratiques pour d'autres problèmes de satisfaction de contraintes sont obtenues
      [<a href="#CGF">134</a>]. (Des accélérations légèrement superquadratiques par rapport à la recherche brute sont
      obtenues
      en utilisant des moyens au-delà de l'amplification d'amplitude dans [<a href="#H18">493</a>,<a
        href="#DPC23">492</a>].) Pour d'autres exemples d'application de
      la recherche de Grover et de l'amplification d'amplitude, voir
      [<a href="#C14">261</a>, <a href="#LMP13">262</a>]. Un problème étroitement
      lié, mais plus difficile que la recherche de Grover, est la recherche spatiale, dans
      laquelle les requêtes de base de données sont limitées par une certaine structure de graphe. Sur
      des graphes suffisamment bien connectés, \(O(\sqrt{n})\) la complexité de requête quantique
      est toujours réalisable [<a href="#CG04">274</a>,<a href="#CNAO15">275</a>,<a href="#Wong16">303</a>,
      <a href="#JMW14">304</a>, <a href="#MW14">305</a>, <a href="#Wong15">306</a>, <a href="#HK16">330</a>].
      <br /><br />

      <a name="abelian_HSP"></a>
      <b>Algorithme :</b> Sous-groupe Caché Abélien <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Implémentation :</b> <a href="https://short.classiq.io/simon">Classiq</a>, <a
        href="https://github.com/quantumlib/Cirq/blob/main/examples/simon_algorithm.py">Cirq</a><br />
      <b>Description :</b> Soit <i>G</i> un groupe abélien généré de manière finie, et soit
      <i>H</i> un sous-groupe de <i>G</i> tel que <i>G/H</i> est fini. Soit <i>f</i>
      une fonction sur <i>G</i> telle que pour tout \( g_1,g_2 \in G \), \( f(g_1) = f(g_2) \)
      si et seulement si \( g_1 \) et \( g_2 \) sont dans le même coset de <i>H</i>. La tâche est
      de trouver <i>H</i> (<i>c'est-à-dire</i> trouver un ensemble de générateurs pour <i>H</i>) en faisant des requêtes
      à <i>f</i>. Cela est résoluble sur un ordinateur quantique en utilisant \( O(\log \vert G\vert) \)
      requêtes, tandis que classiquement \( \Omega(|G|) \) sont nécessaires. Cet algorithme a été formulé pour la
      première fois
      dans toute sa généralité par Boneh et Lipton dans [<a href="#BL95">14</a>]. Cependant,
      l'attribution correcte de cet algorithme est difficile car, comme décrit dans le chapitre 5 de
      [<a href="#Nielsen_Chuang">76</a>], il englobe de nombreux algorithmes quantiques historiquement importants comme
      cas particuliers, y compris l'algorithme de Simon [<a href="#Simon">108</a>],
      qui a été l'inspiration pour l'algorithme de recherche de période de Shor, qui forme le cœur
      de ses algorithmes de factorisation et de logarithmes discrets. L'algorithme de sous-groupe caché abélien
      est également au cœur des algorithmes d'équation de Pell, d'idéal principal, de groupe unitaire et de groupe de
      classes. Dans certains cas, le problème de sous-groupe caché abélien peut être
      résolu en utilisant une seule requête plutôt qu'un ordre de \( \log(\vert G\vert) \), comme le montre
      [<a href="#Beaudrap">30</a>]. Il est normalement supposé dans la recherche de période que la
      fonction \(f(x) \neq f(y) \) à moins que \( x-y = s \), où \( s \) est la période.
      Un algorithme quantique qui s'applique même lorsque cette restriction est assouplie est donné dans
      [<a href="#Hales_Hallgren">388</a>]. La recherche de période a été généralisée pour s'appliquer à
      des oracles qui ne fournissent que les quelques bits les plus significatifs concernant la fonction sous-jacente
      dans [<a href="#SW07">389</a>].
      <br /><br />

      <a name="nonabelian_HSP"></a>
      <b>Algorithme :</b> Sous-groupe Caché Non-Abélien <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Soit <i>G</i> un groupe généré de manière finie, et soit <i>H</i> un
      sous-groupe de <i>G</i> qui a un nombre fini de cosets à gauche. Soit <i>f</i> une
      fonction sur <i>G</i> telle que pour tout \( g_1, g_2 \), \( f(g_1) = f(g_2) \)
      si et seulement si \( g_1 \) et \( g_2 \) sont dans le même coset à gauche de <i>H</i>.
      La tâche est de trouver <i>H</i> (<i>c'est-à-dire</i> trouver un ensemble de générateurs pour <i>H</i>)
      en faisant des requêtes à <i>f</i>. Cela est résoluble sur un ordinateur quantique en
      \( O(\log(|G|) \) requêtes, tandis que classiquement \( \Omega(|G|) \)
      sont nécessaires [<a href="#Ettinger">37</a>,<a href="#Hallgren_Russell">51</a>].
      Cependant, cela ne qualifie pas comme un algorithme quantique efficace car en général,
      il peut falloir un temps exponentiel pour traiter les états quantiques obtenus à partir de ces
      requêtes. Des algorithmes quantiques efficaces pour le problème de sous-groupe caché sont connus pour
      certains groupes non abéliens spécifiques
      [<a href="#RB_NAHS">81</a>,<a href="#IMS_NAHS">55</a>,<a href="#MRRS_NAHS">72</a>,<a href="#IlG_NAHS">53</a>,<a
        href="#BCvD_NAHS">9</a>,<a href="#CKL_NAHS">22</a>,<a href="#ISS_NAHS">56</a>,<a href="#CP_NAHS">71</a>,<a
        href="#ISS2_NAHS">57</a>,<a href="#FIMSS_NAHS">43</a>,<a href="#G_NAHS">44</a>,<a href="#CvD_NAHS">28</a>,<a
        href="#DMR_NAHS">126</a>,<a href="#W_NAHS">207</a>,<a href="#NAHS_BVZ">273</a>].
      Un sondage légèrement obsolète est donné dans [<a href="#Survey_NAHS">69</a>]. D'un
      intérêt particulier sont le groupe symétrique et le groupe diédral. Une solution
      pour le groupe symétrique résoudrait l'isomorphisme de graphes. Une solution pour le
      groupe diédral résoudrait certains problèmes de réseau [<a href="#Regev_lattice">78</a>].
      Malgré de nombreux efforts, aucune solution en temps polynomial pour ces groupes n'est connue, sauf dans
      des cas particuliers [<a href="#Roet16">312</a>]. Cependant,
      Kuperberg [<a href="#Kuperberg">66</a>] a trouvé un algorithme en temps \( 2^{O( \sqrt{\log N})}) \)
      pour trouver un sous-groupe caché du groupe diédral \( D_N \). Regev
      a ensuite amélioré cet algorithme de sorte qu'il utilise non seulement un temps subexponentiel
      mais aussi un espace polynomial [<a href="#Regev_dihedral">79</a>]. Une
      autre amélioration dans l'échelle asymptotique du nombre requis
      de qubits est obtenue dans [<a href="#K13">218</a>]. Des accélérations de requêtes quantiques (bien que
      pas nécessairement des algorithmes quantiques efficaces en termes de nombre de portes) pour
      des problèmes un peu plus généraux de test d'isomorphisme de fonctions sous des ensembles de
      permutations sont données dans [<a href="#HM16">311</a>]
      <br /><br />

      <b>Algorithme :</b> Bernstein-Vazirani <br />
      <b>Accélération :</b> Polynomiale Directement, Superpolynomiale Récursivement <br />
      <b>Implémentation :</b> <a href="https://short.classiq.io/bernstein_vazirani">Classiq</a>, <a
        href="https://github.com/quantumlib/Cirq/blob/main/examples/bernstein_vazirani.py">Cirq</a><br />
      <b>Description :</b> Nous avons un oracle dont l'entrée est <i>n</i>
      bits et dont la sortie est un bit. Étant donné l'entrée \( x \in \{0,1\}^n \), la sortie est
      \( x \odot h \), où <i>h</i> est la chaîne "cachée" de <i>n</i> bits, et
      \( \odot \) désigne le produit intérieur bit à bit modulo 2. La tâche est de trouver <i>h</i>.
      Sur un ordinateur classique, cela nécessite <i>n</i> requêtes. Comme le montre Bernstein et
      Vazirani [<a href="#Bernstein_Vazirani">11</a>], cela peut être réalisé sur un ordinateur quantique
      en utilisant une seule requête. De plus, on peut construire des versions récursives
      de ce problème, appelées échantillonnage de Fourier récursif, telles que les ordinateurs quantiques nécessitent
      exponentiellement moins de requêtes que les ordinateurs classiques
      [<a href="#Bernstein_Vazirani">11</a>]. Voir
      [<a href="#HH08">256</a>, <a href="#BH10">257</a>] pour des travaux connexes
      sur l'ubiquité des accélérations quantiques provenant de circuits quantiques génériques et
      [<a href="#AA14">258</a>, <a href="#ABK15">270</a>] pour des travaux connexes sur une accélération de requête
      quantique
      pour détecter des corrélations entre une fonction oracle et la
      transformée de Fourier d'une autre.
      <br /><br />

      <b>Algorithme :</b> Deutsch-Jozsa <br />
      <b>Accélération :</b> Exponentielle par rapport à P, aucune par rapport à BPP<br />
      <b>Implémentation :</b> <a href="https://short.classiq.io/deutsch_josza">Classiq</a><br />
      <b>Description :</b> Nous avons un oracle dont l'entrée est <i>n</i> bits et dont la sortie
      est un bit. Nous avons la promesse que parmi les \( 2^n \) entrées possibles, soit toutes,
      aucune, ou la moitié d'entre elles donnent une sortie de 1. La tâche est de distinguer le cas équilibré
      (la moitié de toutes les entrées donnent une sortie de 1) du cas constant
      (toutes ou aucune des entrées donnent une sortie de 1). Il a été montré par Deutsch [<a href="#Deutsch">32</a>]
      que pour <i>n=1</i>, cela
      peut être résolu sur un ordinateur quantique en utilisant une requête, tandis que tout algorithme classique
      déterministe
      nécessite deux. C'était historiquement le premier algorithme quantique bien défini
      réalisant un gain par rapport au calcul classique. (Un exemple pédagogique connexe et plus récent est donné dans
      [<a href="#G14">259</a>].) Un algorithme quantique à requête unique pour
      un <i>n</i> arbitraire a été développé par Deutsch et Jozsa dans [<a href="#Deutsch_Jozsa">33</a>].
      Bien que probabilistiquement facile à résoudre avec <i>O(1)</i> requêtes, le problème de Deutsch-Jozsa
      a une complexité de requête déterministe exponentielle dans le pire des cas classiquement.
      <br /><br />

      <b>Algorithme :</b> Évaluation de Formule <br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Une expression booléenne est appelée formule si chaque variable est utilisée une seule fois.
      Une formule correspond à un circuit sans fanout, qui a donc la topologie
      d'un arbre. Grâce à la formalisation du programme de span de Reichardt, il est maintenant connu
      [<a href="#Reichardt_Reflection">158</a>] que la complexité de requête quantique de toute formule
      de <i>O</i>(1) fanin sur <i>N</i> variables est \( \Theta(\sqrt{N}) \).
      Ce résultat découle d'une longue lignée de travaux
      [<a href="#Childs_Jordan">27</a>,<a href="#ragged">8</a>,<a href="#Reichardt_Spalek">80</a>,<a
        href="#Reichardt_Unbalanced">159</a>,<a href="#Reichardt_Faster">160</a>],
      qui a commencé avec la découverte par Farhi <i>et al.</i> [<a href="#Farhi_NAND">38</a>]
      que les arbres NAND sur \( 2^n \) variables peuvent être évalués sur des ordinateurs quantiques en temps
      \( O(2^{0.5n}) \) en utilisant une marche quantique continue, tandis que les ordinateurs classiques
      nécessitent \( \Omega(2^{0.753n}) \) requêtes. Dans de nombreux cas, les algorithmes d'évaluation de formules
      quantiques
      sont efficaces non seulement en complexité de requête mais aussi en complexité temporelle. La
      formalisation du programme de span donne également des bornes inférieures sur la complexité de requête quantique
      [<a href="#Reichardt2010">149</a>]. Bien que découvert à partir d'un point de vue différent, l'algorithme de
      Grover peut être considéré comme un cas particulier d'évaluation de formule dans lequel
      chaque porte est un OU. La complexité quantique d'évaluation de formules non booléennes a également été
      étudiée [<a href="#Cleve_tree">29</a>], mais n'est pas aussi bien comprise. Childs <i>et al.</i>
      ont généralisé le cas où les variables d'entrée peuvent être répétées (<i>c'est-à-dire</i> la première
      couche du circuit peut inclure un fanout) [<a href="#Childs_Kimmel_Kothari">101</a>].
      Ils ont obtenu un algorithme quantique utilisant \( O(\min \{N,\sqrt{S},N^{1/2} G^{1/4} \}) \)
      requêtes, où <i>N</i> est le nombre de variables d'entrée sans tenir compte des multiplicités,
      <i>S</i> est le nombre d'entrées comptant les multiplicités, et <i>G</i> est le nombre de
      portes dans la formule. Les références [<a href="#Zhan_Kimmel_Hassidim">164</a>],
      [<a href="#Kimmel">165</a>], et [<a href="#JK15">269</a>] considèrent
      des cas particuliers du problème de l'arbre NAND dans lequel le nombre de portes NAND
      prenant des entrées inégales est limité. Certains de ces cas donnent
      une séparation superpolynomiale entre la complexité quantique et classique.
      <br /><br />

      <b>Algorithme :</b> Déplacement Caché <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Implémentation :</b> <a href="https://short.classiq.io/hidden_shift">Classiq</a>, <a
        href="https://github.com/quantumlib/Cirq/blob/main/examples/hidden_shift_algorithm.py">Cirq</a><br />
      <b>Description :</b> Nous avons accès à un oracle pour une certaine fonction <i>f</i> sur
      \( \mathbb{Z}_N \). Nous savons que <i>f(x) = g(x+s)</i> où <i>g</i> est une fonction connue
      et <i>s</i> est un décalage inconnu. Le problème de décalage caché est de trouver <i>s</i>. Par
      réduction du problème de Grover, il est clair qu'au moins \( \sqrt{N} \) requêtes
      sont nécessaires pour résoudre le décalage caché en général. Cependant, certains cas particuliers du
      problème de décalage caché sont résolubles sur des ordinateurs quantiques en utilisant <i>O(1)</i> requêtes. En
      particulier, van Dam <i>et al.</i> ont montré que cela peut être fait si <i>f</i> est un caractère multiplicatif
      d'un anneau ou d'un corps [<a href="#vanDam_shift">89</a>]. Le symbole de Legendre décalé précédemment découvert
      [<a href="#vanDam_Legendre">88</a>,<a href="#vanDam_weighing">86</a>] est englobé comme un
      cas particulier de cela, car le symbole de Legendre \( \left(\frac{x}{p} \right) \)
      est un caractère multiplicatif de \( \mathbb{F}_p \). Aucun algorithme classique fonctionnant en temps
      <i>O</i>(polylog(<i>N</i>)) n'est connu pour ces problèmes. De plus, l'algorithme
      quantique pour le problème du symbole de Legendre décalé briserait un certain
      générateur pseudorandom cryptographique donné la capacité de faire
      des requêtes quantiques au générateur [<a href="#vanDam_shift">89</a>].
      Une accélération quantique pour les problèmes de décalage caché de certains ensembles de différences est donnée
      dans [<a href="#Roet16">312</a>],
      et cela englobe également le problème du symbole de Legendre comme un cas particulier.
      Roetteler a trouvé des accélérations quantiques exponentielles pour
      trouver des décalages cachés de certaines fonctions booléennes non linéaires
      [<a href="#Roetteler08">105</a>,<a href="#Roetteler_quad">130</a>]. En s'appuyant sur ce travail,
      Gavinsky, Roetteler et Roland ont montré [<a href="#Gavinsky">142</a>] que le problème de décalage caché sur des
      fonctions booléennes aléatoires \( f:\mathbb{Z}_2^n \to \mathbb{Z}_2 \)
      a une complexité quantique moyenne de <i>O(n)</i>, tandis que la complexité de requête classique est \(
      \Omega(2^{n/2}) \). Les résultats dans [<a href="#Ettinger_Hoyer">143</a>],
      bien qu'ils soient formulés en termes de problème de sous-groupe caché pour le groupe diédral, impliquent que la
      complexité de requête quantique du problème de décalage caché pour une fonction injective
      sur \( \mathbb{Z}_N \) est <i>O</i>(log <i>n</i>), tandis que la complexité de requête classique est
      \( \Theta(\sqrt{N}) \). Cependant, la meilleure complexité de circuit quantique pour le décalage caché injectif
      sur \( \mathbb{Z}_N \) est \( O(2^{C \sqrt{\log N}}) \), atteinte par l'algorithme de tamis de Kuperberg [<a
        href="#Kuperberg">66</a>]. Un résultat récent, s'appuyant sur [<a href="#Ivanyos08">408</a>, <a
        href="#FIMSS_NAHS">43</a>],
      atteint des accélérations quantiques exponentielles pour certaines généralisations du problème de décalage caché,
      y compris le <i>problème de décalage multiple caché</i>, dans lequel on a accès à \(f_s(x) = f(x-hs) \)
      sur une certaine plage autorisée de <i>s</i> et l'on souhaite inférer <i>h</i> [<a href="#IPS18">407</a>].
      <br /><br />

      <b>Algorithme :</b> Interpolation Polynomiale <br />
      <b>Accélération :</b> Varie <br />
      <b>Description :</b> Soit \( p(x) = a_d x^d + \ldots + a_1 x + a_0 \) un polynôme sur le corps fini \(
      \mathrm{GF}(q) \). On a accès à un
      oracle qui, donné \( x \in \mathrm{GF}(q) \), retourne \( p(x) \). Le problème de reconstruction de polynôme est,
      en faisant des requêtes à l'oracle, de déterminer
      les coefficients \( a_d,\ldots,a_0 \). Classiquement, \( d + 1 \) requêtes sont nécessaires et suffisantes. (Dans
      certaines sources, on utilise le terme reconstruction au lieu
      d'interpolation pour ce problème.) Quantiquement, \( d/2 + 1/2 \) requêtes sont nécessaires et \( d/2 + 1 \)
      requêtes sont suffisantes
      [<a href="#interp1">360</a>,<a href="#interp2">361</a>]. Pour des polynômes multivariés de degré <i>d</i> dans
      <i>n</i> variables, le problème d'interpolation
      a une complexité de requête classique \( \binom{n+d}{d} \). Comme le montre [<a href="#interp3">387</a>], la
      complexité de requête quantique est
      \( O \left( \frac{1}{n+1} \binom{n+d}{d} \right) \) sur \( \mathbb{R} \) et \( \mathbb{C} \) et elle est \( O
      \left( \frac{d}{n+d} \binom{n+d}{d} \right) \)
      sur \( \mathbb{F}_q \) pour des \( q \) suffisamment grands. Des algorithmes quantiques ont également été
      découverts pour le cas où l'oracle retourne \( \chi(f(x)) \)
      où \( \chi \) est un caractère quadratique de \( \mathrm{GF}(q) \) [<a href="#RS04">390</a>], et le cas où
      l'oracle retourne \( f(x)^e \)
      [<a href="#IKS17">392</a>]. Ceux-ci généralisent l'algorithme de décalage caché de [<a
        href="#vanDam_shift">89</a>] et atteignent une accélération exponentielle par rapport
      au calcul classique. Un algorithme quantique pour reconstruire des fonctions rationnelles sur des corps finis
      donné un accès oracle bruyant et incomplet aux valeurs de fonction
      est donné dans [<a href="#HRS05">391</a>].
      <br /><br />

      <b>Algorithme :</b> Correspondance de Modèle <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Étant donné des chaînes <i>T</i> de longueur <i>n</i>
      et <i>P</i> de longueur <i>m</i> &lt; <i>n</i>, toutes deux provenant d'un alphabet fini,
      le problème de correspondance de modèle consiste à trouver une occurrence
      de <i>P</i> comme sous-chaîne de <i>T</i> ou à signaler que <i>P</i> n'est
      pas une sous-chaîne de <i>T</i>. Plus généralement, <i>T</i> et <i>P</i>
      pourraient être des tableaux <i>d</i>-dimensionnels plutôt que des tableaux unidimensionnels
      (chains). Ensuite, le problème de correspondance de modèle consiste à retourner la
      position de <i>P</i> comme un bloc de \(m \times m \times \ldots \times m\)
      dans le tableau \(n \times n \times \ldots \times n\) <i>T</i> ou à signaler qu'aucune telle position n'existe. La
      complexité de requête \( \Omega(\sqrt{N}) \)
      pour la recherche non structurée [<a href="#BBBV">216</a>] implique que la complexité de requête quantique dans le
      pire des cas
      de ce problème est \( \Omega ( \sqrt{n} + \sqrt{m} ) \). Un algorithme quantique atteignant
      cela, jusqu'à des facteurs logarithmiques, a été obtenu dans
      [<a href="#RV00">217</a>]. Cet algorithme quantique fonctionne grâce à
      l'utilisation de l'algorithme de recherche de Grover associé à une méthode classique appelée
      échantillonnage déterministe. Plus récemment, Montanaro a montré que
      des accélérations quantiques superpolynomiales peuvent être obtenues sur des instances de cas moyen
      de correspondance de modèle, à condition que <i>m</i> soit supérieur à
      logarithmique en <i>n</i>. Plus précisément, l'algorithme quantique donné dans
      [<a href="#Montanaro14">215</a>] résout la correspondance de modèle dans le cas moyen en
      \( \widetilde{O}((n/m)^{d/2} 2^{O(d^{3/2} \sqrt{\log m})})\) temps. Cet
      algorithme quantique est construit en généralisant l'algorithme quantique de tamis de Kuperberg [<a
        href="#Kuperberg">66</a>] pour les problèmes de sous-groupe caché diédral et de décalage caché de sorte qu'il
      puisse fonctionner en <i>d</i> dimensions
      et accommoder de petites quantités de bruit, puis en réduisant classiquement le
      problème de correspondance de modèle à cette version bruyante <i>d</i>-dimensionnelle du
      décalage caché. Un algorithme quantique pour la correspondance de chaînes avec une complexité \(\widetilde{O}
      (\sqrt{n}) \)
      est donné dans [<a href="#NN21">435</a>] dans un modèle d'entrée différent,
      où les chaînes sont écrites dans leur intégralité en utilisant \(n + m\) qubits plutôt
      que par des requêtes quantiques à un oracle fournissant des bits individuels.
      <br /><br />

      <b>Algorithme :</b> Recherche Ordonnée <br />
      <b>Accélération :</b> Facteur constant <br />
      <b>Description :</b> Nous avons accès à un oracle pour une liste de <i>N</i> nombres dans l'ordre
      de la plus petite à la plus grande. Étant donné un nombre <i>x</i>, la tâche est de découvrir où dans la
      liste il s'insérerait. Classiquement, le meilleur algorithme possible est la recherche binaire qui prend
      \( \log_2 N \) requêtes. Farhi <i>et al.</i> ont montré qu'un ordinateur quantique peut atteindre
      cela en utilisant 0.53 \( \log_2 N \) requêtes [<a href="#FGGS99">39</a>]. Actuellement, le meilleur
      algorithme quantique déterministe connu pour ce problème utilise 0.433 \( \log_2 N \)
      requêtes [<a href="#Landahl">103</a>]. Une borne inférieure de \( \frac{\ln 2}{\pi} \log_2 N \)
      a été prouvée pour ce problème
      [<a href="#HNS01">219</a>, <a href="#Childs_Lee">24</a>]. Dans
      [<a href="#Ben_Or_Search">10</a>], un algorithme quantique randomisé est donné dont la complexité
      de requête attendue est inférieure à \( \frac{1}{3} \log_2 N \).
      <br /><br />

      <b>Algorithme :</b> Propriétés des graphes dans le modèle de matrice d'adjacence<br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Soit <i>G</i> un graphe de <i>n</i> sommets. Nous avons accès à
      un oracle, qui, donné une paire d'entiers dans {1,2,...,<i>n</i>}, nous indique si les
      sommets correspondants sont connectés par une arête. S'appuyant sur des travaux précédents
      [<a href="#DH96">35</a>,<a href="#prev2">52</a>,<a href="#prev3">36</a>], D&uuml;rr
      <i>et al.</i> [<a href="#Durr_graphs">34</a>] montrent que la complexité de requête quantique
      pour trouver un arbre couvrant minimal de graphes pondérés, et décider de la connectivité pour
      les graphes dirigés et non dirigés a \( \Theta(n^{3/2}) \) de complexité de requête quantique,
      et que trouver les chemins de poids minimum a \( O(n^{3/2}\log^2 n) \) de complexité de requête quantique.
      Décider si un graphe est bipartite, détecter des cycles, et décider si un sommet donné
      peut être atteint depuis un autre (connectivité st) peut tous être réalisé en utilisant un nombre de requêtes et
      de portes quantiques qui évoluent comme \( \widetilde{O}(n^{3/2}) \), et seulement logarithmiquement de qubits,
      comme montré dans [<a href="#CMB16">317</a>], s'appuyant sur [<a href="#Berzina">13</a>, <a href="#Arins">272</a>,
      <a href="#BR12">318</a>].
      Un algorithme quantique basé sur les programmes de span pour détecter des arbres d'une taille donnée
      comme mineurs en \( \widetilde{O}(n) \) temps est donné dans
      [<a href="#Wang13">240</a>]. Une propriété de graphe est
      dite éparse s'il existe une constante <i>c</i> telle que chaque graphe avec cette propriété a
      un ratio d'arêtes par rapport aux sommets au plus <i>c</i>. Childs et Kothari ont montré que toutes
      les propriétés de graphes éparses ont une complexité de requête \( \Theta(n^{2/3}) \) si elles ne peuvent pas être
      caractérisées par une liste de sous-graphes interdits et \( o(n^{2/3}) \)
      (<a href="http://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation">little-o</a>)
      si elles le peuvent [<a href="#Childs_minor">140</a>]. Le premier algorithme est basé sur la recherche de Grover,
      le second sur le formalisme de marche quantique de [<a href="#Magniez_walk">141</a>].
      Selon le théorème de Mader, les propriétés de graphes éparses incluent toutes les propriétés fermées par mineurs
      non triviaux.
      Celles-ci incluent la planéité, le fait d'être une forêt, et de ne pas contenir un chemin de
      longueur donnée. Selon la conjecture largement acceptée d'Aanderaa-Karp-Rosenberg, tous les problèmes ci-dessus
      ont
      \( \Omega(n^2) \) de complexité de requête classique. Un autre
      problème computationnel intéressant est de trouver un sous-graphe <i>H</i> dans un graphe donné <i>G</i>.
      Le cas le plus simple est de trouver le triangle, c'est-à-dire le clique de taille trois. Le
      meilleur algorithme quantique connu pour cela trouve un triangle en \( O(n^{5/4}) \)
      requêtes quantiques [<a href="#CLM16">319</a>], améliorant
      [<a href="#LG14">276</a>, <a href="#Lee_Magniez_Santha12">175</a>, <a href="#Jeffery_Kothari_Magniez12">171</a>,
      <a href="#Magniez_triangle">70</a>, <a href="#Belovs_Constant">152</a>,
      <a href="#Buhrman_collision">21</a>]. Des bornes supérieures de complexité de requête quantique plus fortes sont
      connues lorsque les graphes sont
      suffisamment épars [<a href="#CLM16">319</a>, <a href="#LS15">320</a>]. Classiquement, la recherche de triangles
      nécessite \( \Omega(n^2) \) requêtes [<a href="#Buhrman_collision">21</a>].
      Plus généralement, un ordinateur quantique peut trouver un
      sous-graphe arbitraire de <i>k</i> sommets en utilisant \( O(n^{2-2/k-t}) \) requêtes où
      \( t=(2k-d-3)/(k(d+1)(m+2)) \) et <i>d</i> et <i>m</i> sont tels que <i>H</i> a
      un sommet de degré <i>d</i> et <i>m</i>+<i>d</i> arêtes
      [<a href="#Lee_Magniez_Santha">153</a>]. Cela améliore l'algorithme précédent de
      [<a href="#Magniez_triangle">70</a>]. Dans certains cas, cette complexité de requête est battue par
      l'algorithme quantique de [<a href="#Childs_minor">140</a>], qui trouve <i>H</i>
      en utilisant \( \widetilde{O}\left( n^{\frac{3}{2}-\frac{1}{\mathrm{vc}(H)+1}} \right) \)
      requêtes, à condition que <i>G</i> soit épars, où vc(<i>H</i>) est la taille de la couverture minimale
      des sommets de <i>H</i>. Un algorithme quantique pour trouver
      des sous-hypergraphes de taille constante sur des hypergraphes 3-uniformes en \(
      O(n^{1.883}) \) requêtes est donné dans [<a href="#LGNT13">241</a>].
      <br /><br />

      <b>Algorithme :</b> Propriétés des graphes dans le modèle de liste d'adjacence<br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Soit <i>G</i> un graphe de <i>N</i> sommets, <i>M</i> arêtes, et
      degré <i>d</i>. Nous avons accès à un oracle qui, lorsqu'on lui demande le label
      d'un sommet et \( j \in \{1,2,\ldots,d\} \), renvoie le <i>j</i>-ième voisin du
      sommet ou null si le sommet a un degré inférieur à <i>d</i>. Supposons que nous avons la
      promesse que <i>G</i> est soit bipartite, soit éloigné de bipartite dans le sens où
      une fraction constante des arêtes devrait être supprimée pour atteindre la bipartite. Alors,
      comme montré dans [<a href="#Ambainis_Childs_Liu">144</a>], la complexité quantique de décider
      de la bipartite est \( \widetilde{O}(N^{1/3}) \). Également dans [<a href="#Ambainis_Childs_Liu">144</a>],
      il est montré que distinguer les graphes expanseurs des graphes qui sont loin d'être
      expanseurs a une complexité quantique \( \widetilde{O}(N^{1/3}) \) et
      \( \widetilde{\Omega}(N^{1/4}) \), tandis que la complexité classique est
      \( \widetilde{\Theta}(\sqrt{N}) \). L'outil algorithmique quantique clé est l'algorithme d'Ambainis pour
      la distinctivité des éléments. Dans [<a href="#Durr_graphs">34</a>], il est montré que trouver un arbre couvrant
      minimal
      a une complexité de requête quantique \( \Theta(\sqrt{NM}) \), décider de la connectivité des graphes
      a une complexité de requête quantique \( \Theta(N) \) dans le cas non dirigé, et
      \( \widetilde{\Theta}(\sqrt{NM}) \) dans le cas dirigé, et calculer le chemin de poids minimum
      à partir d'une source donnée vers tous les autres sommets sur un graphe pondéré a une complexité de requête
      quantique
      \( \widetilde{\Theta}(\sqrt{NM}) \). Dans [<a href="#CMB16">317</a>], des algorithmes quantiques sont
      donnés pour la connectivité st, décider de la bipartite, et décider si un graphe est une forêt,
      qui s'exécutent en \( \widetilde{O}(N \sqrt{d}) \) temps et utilisent seulement un nombre logarithmique de qubits.
      <br /><br />

      <b>Algorithme :</b> Arbre soudé <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Implémentation :</b> <a href="https://short.classiq.io/glued_trees">Classiq</a><br />
      <b>Description :</b> Certains problèmes computationnels peuvent être formulés en termes de la complexité de
      requête
      pour trouver son chemin à travers un labyrinthe. C'est-à-dire qu'il y a un graphe <i>G</i>
      auquel on a accès par oracle. Lorsqu'on lui demande le label d'un nœud donné,
      l'oracle renvoie une liste des labels de tous les nœuds adjacents. La tâche consiste, en partant
      d'un nœud source (<i>c'est-à-dire</i> son label), à trouver le label d'un certain nœud
      de destination marqué. Comme montré par Childs <i>et al.</i> [<a href="#Childs_weld">26</a>],
      les ordinateurs quantiques peuvent surpasser exponentiellement les ordinateurs classiques dans cette tâche pour
      au moins certains graphes. Plus précisément, considérons le graphe obtenu en joignant
      deux arbres binaires de profondeur <i>n</i> par un "soudage" aléatoire tel que tous les nœuds sauf les deux
      racines ont un degré de trois. En partant d'une racine, un ordinateur quantique peut trouver l'autre
      racine en utilisant poly(<i>n</i>) requêtes, tandis que cela est prouvablement impossible avec des requêtes
      classiques.
      <br /><br />

      <b>Algorithme :</b> Recherche de collisions et distinctivité des éléments<br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Supposons que nous avons accès à un oracle pour une fonction deux à un
      <i>f</i> sur un domaine de taille <i>N</i>. Le problème de collision
      est de trouver une paire \( x,y \in \{1,2,\ldots,N\} \) telle que <i>f(x) = f(y)</i>.
      La complexité de requête classique aléatoire de ce problème est \( \Theta(\sqrt{N}) \),
      tandis que, comme montré par Brassard <i>et al.</i>, un ordinateur quantique peut atteindre cela
      en utilisant \(O(N^{1/3}) \) requêtes [<a href="#Brassard_collision">18</a>]. (Voir aussi [<a
        href="#BHT98b">315</a>].)
      En supprimant la
      promesse que <i>f</i> est deux à un, on obtient un problème appelé distinctivité des éléments, qui
      a une complexité de requête classique \( \Theta(N) \). Améliorant
      [<a href="#Buhrman_collision">21</a>], Ambainis propose un algorithme quantique avec une complexité de requête
      de \( O(N^{2/3}) \) pour la distinctivité des éléments, ce qui est
      optimal [<a href="#Ambainis_distinctness">7</a>, <a href="#P17">374</a>]. Le problème de
      décider si des collisions <i>k</i>-fois existent est
      appelé <i>k</i>-distinctivité. Améliorant
      [<a href="#Ambainis_distinctness">7</a>,<a href="#Belovs_Lee">154</a>],
      la meilleure complexité de requête quantique pour <i>k</i>-distinctivité est
      \( O(n^{3/4 - 1/(4(2^k-1))}) \)
      [<a href="#Belovs12">172</a>, <a href="#Childs_Jeffery_Kothari_Magniez13">173</a>]. La série de travaux
      [<a href="#Ambainis_distinctness">7</a>, <a href="#Jefferythesis">363</a>], culminant dans [<a
        href="#JZ23">464</a>], montre
      que c'est aussi la complexité temporelle quantique pour tous <i>k</i>, jusqu'à des facteurs logarithmiques.
      Étant donné deux fonctions <i>f</i> et <i>g</i>, sur des domaines de
      taille <i>N</i> et <i>M</i>, respectivement, une griffe est une paire <i>x,y</i> telle que <i>f(x) =
        g(y)</i>. Dans le cas où <i>N</i>=<i>M</i>, l'algorithme de [<a href="#Ambainis_distinctness">7</a>]
      résout la recherche de griffes en \( O(N^{2/3}) \) requêtes, améliorant l'ancien algorithme quantique \( O(N^{3/4}
      \log N) \)
      de [<a href="#Buhrman_collision">21</a>]. D'autres travaux donnent une complexité de requête améliorée pour divers
      régimes de paramètres
      dans lesquels \(N \neq M\) [<a href="#Tani">364</a>, <a href="#IwamaKawachi">365</a>]. Plus généralement, un
      problème connexe à
      la distinctivité des éléments est, étant donné un accès oracle à une séquence, de
      estimer le \(k^{\mathrm{th}}\) moment de fréquence \(F_k = \sum_j n_j^k
      \), où \(n_j\) est le nombre de fois que <i>j</i> apparaît dans la
      séquence. Un gain de vitesse quadratique approximatif pour ce problème est
      obtenu dans [<a href="#M15c">277</a>]. Voir aussi <a href="#graph_collision">collision de graphes</a>.
      <br /><br />

      <a name="graph_collision"></a>
      <b>Algorithme :</b> Collision de graphes <br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b>
      Nous avons un graphe non dirigé de <i>n</i> sommets et un accès oracle
      à un étiquetage des sommets par 1 et 0. Le problème de collision de graphes
      est, en interrogeant cet oracle, de décider s'il existe une
      paire de sommets, connectés par une arête, tous deux étiquetés
      1. On peut intégrer le problème de recherche non structurée de Grover comme un cas
      de collision de graphes en choisissant le graphe étoile, étiquetant le centre par 1,
      et étiquetant les sommets restants par les entrées de la base de données. Ainsi,
      ce problème a une complexité de requête quantique \( \Omega(\sqrt{n}) \) et
      une complexité de requête classique \( \Theta (n) \). Dans
      [<a href="#Magniez_triangle">70</a>], Magniez, Nayak, et Szegedy ont donné
      un algorithme quantique de \( O(N^{2/3}) \) pour la collision de graphes sur
      des graphes généraux. Cela reste la meilleure borne supérieure sur la complexité de requête quantique pour ce
      problème sur des graphes généraux. Cependant, des bornes supérieures plus fortes
      ont été obtenues pour plusieurs classes spéciales de
      graphes. Plus précisément, la complexité de requête quantique sur un
      graphe <i>G</i> est \( \widetilde{O}(\sqrt{n} + \sqrt{l}) \) où <i>l</i>
      est le nombre de non-arêtes dans <i>G</i> [<a href="#JKM">161</a>],
      \(O(\sqrt{n} \alpha^{1/6}) \) où \(\alpha\) est la taille de la
      plus grande ensemble indépendant de <i>G</i> [<a href="#Belovs12">172</a>],
      \(O(\sqrt{n} + \sqrt{\alpha^*})\) où \( \alpha^* \) est le degré total maximum de tout ensemble indépendant de
      <i>G</i>
      [<a href="#GI12">200</a>], et \(O(\sqrt{n} t^{1/6}) \) où <i>t</i> est
      la largeur d'arbre de <i>G</i> [<a href="#ABI13">201</a>]. De plus, la
      complexité de requête quantique est \( \widetilde{O}(\sqrt{n}) \) avec une forte
      probabilité pour des graphes aléatoires dans lesquels la présence ou l'absence d'une
      arête entre chaque paire de sommets est choisie indépendamment avec une probabilité fixe,
      (<i>c'est-à-dire</i> graphes d'Erd&#337;s-R&eacute;nyi)
      [<a href="#GI12">200</a>]. Voir [<a href="#ABI13">201</a>] pour un
      résumé de ces résultats ainsi que de nouvelles bornes supérieures pour deux
      classes supplémentaires de graphes qui sont trop compliquées à décrire ici.
      <br /><br />

      <b>Algorithme :</b> Commutativité des matrices <br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Nous avons accès oracle à <i>k</i> matrices, chacune étant
      \( n \times n \). Étant donné des entiers \( i,j \in \{1,2,\ldots,n\} \), et
      \( x \in \{1,2,\ldots,k\} \), l'oracle renvoie l'élément de matrice <i>ij</i> de la
      \( x^{\mathrm{ème}} \) matrice. La tâche est de décider si toutes ces <i>k</i>
      matrices commutent. Comme montré par Itakura [<a href="#Itakura">54</a>], cela peut être réalisé
      sur un ordinateur quantique en utilisant \( O(k^{4/5}n^{9/5}) \) requêtes, tandis que classiquement cela
      nécessite \( \Omega( k n^2 ) \) requêtes.
      <br /><br />


      <b>Algorithme :</b> Commutativité de groupe <br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Nous avons une liste de <i>k</i> générateurs pour un groupe <i>G</i> et
      accès à une boîte noire implémentant la multiplication de groupe. En interrogeant cette boîte noire, nous
      souhaitons déterminer si le groupe est commutatif. Le meilleur algorithme classique connu
      est dû à Pak et nécessite <i>O(k)</i> requêtes. Magniez et Nayak ont montré que la
      complexité de requête quantique de cette tâche est \( \widetilde{\Theta}(k^{2/3}) \)
      [<a href="#Magniez_Nayak">139</a>].
      <br /><br />

      <b>Algorithme :</b> Structures non linéaires cachées <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Tout groupe abélien <i>G</i> peut être visualisé comme un réseau. Un sous-groupe
      <i>H</i> de <i>G</i> est un sous-réseau, et les classes de cosets de <i>H</i> sont tous les décalages de
      ce sous-réseau. Le problème du sous-groupe caché abélien est normalement résolu en obtenant
      une superposition sur un coset aléatoire du sous-groupe caché, puis en prenant la transformée de Fourier
      afin d'échantillonner à partir du réseau dual. Plutôt que de généraliser aux
      groupes non abéliens (voir <a href="#nonabelian_HSP">sous-groupe caché non abélien</a>), on peut plutôt
      généraliser au
      problème d'identification de sous-ensembles cachés autres que des réseaux. Comme montré par Childs
      <i>et al.</i> [<a href="#Childs_nonlinear">23</a>], ce problème est efficacement résoluble
      sur des ordinateurs quantiques pour certains sous-ensembles définis par des polynômes, tels que des sphères.
      Decker <i>et al.</i> ont montré comment résoudre efficacement certains problèmes connexes dans
      [<a href="#Wocjan_nonlinear">31</a>, <a href="#DHIS13">212</a>].
      <br /><br />

      <b>Algorithme :</b> Centre de fonction radiale <br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Nous avons accès à un oracle qui évalue une fonction <i>f</i> de
      \( \mathbb{R}^d \) vers un ensemble arbitraire <i>S</i>, où <i>f</i> est spheriquement
      symétrique. Nous souhaitons localiser le centre de symétrie, jusqu'à une certaine précision.
      (Pour simplifier, considérons que la précision est fixe.) Dans [<a href="#Liu">110</a>],
      Liu donne un algorithme quantique, basé sur une transformée de courbe, qui résout
      ce problème en utilisant un nombre constant de requêtes quantiques indépendantes de
      <i>d</i>. Cela constitue un gain de vitesse polynomial par rapport à la borne inférieure classique,
      qui est \( \Omega(d) \) requêtes. L'algorithme fonctionne lorsque la fonction
      <i>f</i> fluctue à des échelles suffisamment petites, <i>e.g.</i>, lorsque les ensembles de niveaux
      de <i>f</i> sont suffisamment fins en coquilles sphériques. L'algorithme quantique est montré
      pour fonctionner dans un modèle continu idéalisé, et des arguments non rigoureux suggèrent que
      les effets de discrétisation devraient être faibles.
      <br /><br />

      <b>Algorithme :</b> Ordre et appartenance de groupe <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Supposons qu'un groupe fini <i>G</i> soit donné oraculairement de la manière suivante.
      À chaque élément de <i>G</i>, on attribue un label correspondant. Étant donné une paire ordonnée de
      labels d'éléments de groupe, l'oracle renvoie le label de leur produit. Il existe plusieurs
      problèmes classiquement difficiles concernant de tels groupes. L'un consiste à trouver l'ordre du groupe, étant
      donné les
      labels d'un ensemble de générateurs. Une autre tâche consiste, étant donné une chaîne de bits, à décider si elle
      correspond à un élément de groupe. La version constructive de ce problème d'appartenance nécessite,
      dans le cas positif, une décomposition de l'élément donné comme produit de générateurs de groupe.
      Classiquement, ces problèmes ne peuvent pas être résolus en utilisant des requêtes polylog(|<i>G</i>|) même si
      <i>G</i> est abélien. Pour les groupes abéliens, les ordinateurs quantiques peuvent résoudre ces problèmes en
      utilisant
      des requêtes polylog(|<i>G</i>|) par réduction au problème de sous-groupe caché abélien, comme montré
      par Mosca [<a href="#Mosca_thesis">74</a>]. De plus, comme montré par Watrous
      [<a href="#Watrous_solvable">91</a>], les ordinateurs quantiques peuvent résoudre ces problèmes
      en utilisant des requêtes polylog(|<i>G</i>|) pour tout groupe résoluble. Pour les groupes donnés sous forme de
      matrices
      sur un corps fini plutôt que oraculairement, les problèmes de recherche d'ordre et d'appartenance constructive
      peuvent être résolus en temps polynomial en utilisant les algorithmes quantiques pour le logarithme discret
      et la factorisation [<a href="#Babai">124</a>]. Voir aussi <a href="#group_isomorphism">isomorphisme de
        groupe</a>.
      <br /><br />

      <a name="group_isomorphism"></a>
      <b>Algorithme :</b> Isomorphisme de groupe <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Soit <i>G</i> un groupe fini. À chaque élément de
      <i>G</i> est attribué un label arbitraire (chaîne de bits). Étant donné une paire ordonnée
      de labels d'éléments de groupe, l'oracle de groupe renvoie le label de leur
      produit. Étant donné l'accès aux oracles de groupe pour deux groupes <i>G</i> et
      <i>G'</i>, et une liste de générateurs pour chaque groupe, nous devons décider si
      <i>G</i> et <i>G'</i> sont isomorphes. Pour les groupes abéliens, nous pouvons résoudre ce
      problème en utilisant des requêtes poly(log |<i>G</i>|, log |<i>G'</i>|) à l'oracle
      en appliquant l'algorithme quantique de [<a href="#Cheung_Mosca">127</a>], qui
      décompose tout groupe abélien en un produit direct canonique de groupes cycliques.
      L'algorithme quantique de [<a href="#LeGall">128</a>] résout le problème de
      l'isomorphisme de groupe en utilisant des requêtes poly(log |<i>G</i>|, log |<i>G'</i>|) pour une
      certaine classe de groupes non abéliens. Plus précisément, un groupe <i>G</i> est dans cette
      classe si <i>G</i> a un sous-groupe abélien normal <i>A</i> et un élément
      <i>y</i> d'ordre premier avec |<i>A</i>| tel que G
      = <i>A</i>, <i>y</i>. Zatloukal a récemment donné un gain
      quantique exponentiel pour certaines instances d'un problème étroitement lié à
      l'isomorphisme de groupe, à savoir le test d'équivalence des extensions de groupe
      [<a href="#Z13">202</a>].
      <br /><br />

      <b>Algorithme :</b> Différence statistique <br />
      <b>Accélération :</b> Polynomiale <br />
      <b>Description :</b> Supposons que nous avons deux boîtes noires <i>A</i> et <i>B</i>
      dont le domaine est les entiers de 1 à <i>T</i> et dont l'image est les entiers
      de 1 à <i>N</i>. En choisissant uniformément au hasard parmi les entrées autorisées, nous obtenons une
      distribution de probabilité sur les sorties possibles. Nous souhaitons approximer à une précision constante
      la distance L1 entre les distributions de probabilité déterminées par <i>A</i>
      et <i>B</i>. Classiquement, le nombre de requêtes nécessaires évolue essentiellement de manière linéaire
      avec N. Comme montré dans [<a href="#Bravyi_difference">117</a>], un ordinateur quantique peut
      atteindre cela en utilisant \( O(\sqrt{N}) \) requêtes. L'uniformité approximative et l'orthogonalité
      des distributions de probabilité peuvent également être décidées sur un ordinateur quantique en utilisant
      \( O(N^{1/3}) \) requêtes. L'outil principal est l'algorithme de comptage quantique de
      [<a href="#BHT98">16</a>]. Un algorithme quantique amélioré pour
      cette tâche est obtenu dans [<a href="#M15b">265</a>].
      <br /><br />

      <b>Algorithme :</b> Anneaux finis et idéaux <br />
      <b>Accélération :</b> Superpolynomiale <br />
      <b>Description :</b> Supposons que nous avons des boîtes noires implémentant les opérations d'addition et
      de multiplication sur un anneau fini <i>R</i>, pas nécessairement commutatif, avec
      un ensemble de générateurs pour <i>R</i>. En ce qui concerne l'addition, <i>R</i> forme un
      groupe abélien fini (<i>R</i>,+). Comme montré dans [<a href="#Arvind">119</a>], sur un ordinateur quantique,
      on peut trouver en temps poly(log |<i>R</i>|) un ensemble de générateurs additifs
      \( \{h_1,\ldots,h_m\} \subset R \) tel que
      \( (R,+) \simeq \langle h_1 \rangle \times \ldots \times \langle h_M \rangle\)
      et <i>m</i> est polylogarithmique en |<i>R</i>|. Cela permet un calcul efficace d'un
      tenseur de multiplication pour <i>R</i>. Comme montré dans [<a href="#WJAB">118</a>], on peut
      également trouver un ensemble générateur additif pour tout idéal dans <i>R</i>. Cela permet de
      trouver l'intersection de deux idéaux, de trouver leur quotient, de prouver si un élément d'anneau donné
      appartient à un idéal donné, de prouver si un élément donné est une unité et, le cas échéant,
      de trouver son inverse, de trouver les identités additive et multiplicative, de calculer l'ordre d'un
      idéal, de résoudre des équations linéaires sur des anneaux, de décider si un idéal est maximal, de trouver
      des annihilateurs, et de tester l'injectivité et la surjectivité des homomorphismes d'anneaux. Comme montré
      dans [<a href="#Arvind2">120</a>], on peut également utiliser un ordinateur quantique pour décider efficacement
      si un polynôme donné est identiquement nul sur un anneau fini en boîte noire donné.
      Les algorithmes classiques connus pour ces problèmes évoluent comme poly(|<i>R</i>|).
      <br /><br />

      <b>Algorithme :</b> Pièces contrefaites<br />
      <b>Accélération :</b> Polynomiale<br />
      <b>Description :</b> Supposons que nous avons <i>N</i> pièces, dont <i>k</i> sont
      contrefaites. Les vraies pièces ont toutes le même poids, et les pièces contrefaites ont
      toutes un autre poids égal. Nous avons une balance à plateau et pouvons comparer le poids de
      n'importe quelle paire de sous-ensembles de pièces. Classiquement, nous avons besoin de \( \Omega(k \log(N/k)) \)
      pesées pour identifier toutes les pièces contrefaites. Nous pouvons introduire un oracle tel
      que, donné une paire de sous-ensembles de pièces de cardinalité égale, il renvoie un bit
      indiquant si c'est équilibré ou déséquilibré. S'appuyant sur des travaux précédents de Terhal et Smolin
      [<a href="#TS">137</a>], Iwama <i>et al.</i> ont montré [<a href="#Iwama">136</a>]
      que sur un ordinateur quantique, on peut identifier toutes les pièces contrefaites en utilisant
      \( O(k^{1/4}) \) requêtes. Les techniques fondamentales derrière le gain quantique sont l'amplification
      d'amplitude
      et l'algorithme de Bernstein-Vazirani.<br /><br />


      <b>Algorithme :</b> Rang de matrice<br />
      <b>Accélération :</b> Polynomiale<br />
      <b>Description :</b> Supposons que nous ayons accès par oracle aux entrées (entières) d'une
      matrice \( n \times m \) <i>A</i>. Nous souhaitons déterminer le rang de la matrice.
      Classiquement, cela nécessite un ordre de \( nm \) requêtes. En s'appuyant sur
      [<a href="#Reichardt2010">149</a>], Belovs [<a href="#Belovs_Rank">150</a>] propose un
      algorithme quantique qui peut utiliser moins de requêtes, étant donné la promesse que le rang de la
      matrice est d'au moins <i>r</i>. Plus précisément, l'algorithme de Belovs utilise
      \( O(\sqrt{r(n-r+1)}LT) \) requêtes, où <i>L</i> est la racine carrée de la moyenne des inverses
      des <i>r</i> plus grandes valeurs singulières de <i>A</i> et <i>T</i> est un facteur qui dépend de la
      parcimonie de la matrice. Pour une matrice générale <i>A</i>,
      \( T = O(\sqrt{nm}) \). Si <i>A</i> a au plus <i>k</i> entrées non nulles dans n'importe quelle ligne ou
      colonne, alors \( T = O(k \log(n+m)) \). (Pour atteindre la complexité de requête correspondante dans
      le cas <i>k</i>-parcimonieux, l'oracle doit prendre un index de colonne comme entrée et fournir une
      liste des éléments non nuls de la matrice de cette colonne en sortie.) Comme un cas spécial important,
      on peut utiliser ces algorithmes quantiques pour le problème de déterminer si une
      matrice carrée est singulière, ce qui est parfois appelé le problème du déterminant.
      Pour une matrice générale <i>A</i>, la complexité de requête quantique du problème du déterminant n'est pas
      inférieure à la complexité de requête classique [<a href="#Dorn">151</a>]. Cependant,
      [<a href="#Dorn">151</a>] ne rejette pas une accélération quantique donnée une promesse sur <i>A</i>,
      telle que la parcimonie ou l'absence de petites valeurs singulières.<br /><br />

      <b>Algorithme :</b> Multiplication de matrices sur des semi-anneaux<br />
      <b>Accélération :</b> Polynomiale<br />
      <b>Description :</b> Un semi-anneau est un ensemble doté d'opérations d'addition et
      de multiplication qui obéissent à tous les axiomes d'un anneau, sauf l'existence d'inverses additifs. La
      multiplication de matrices sur divers semi-anneaux a de nombreuses applications aux problèmes de graphes.
      La multiplication de matrices sur des semi-anneaux peut être accélérée par des améliorations
      directes de Grover sur la multiplication scolaire, donnant un algorithme quantique qui multiplie une paire de
      matrices \(n \times n\) en \( \widetilde{O}(n^{5/2}) \) temps. Pour certains semi-anneaux, cet algorithme
      surpasse les algorithmes classiques les plus rapides connus et pour certains
      semi-anneaux, il ne le fait pas [<a href="#LeGall_Nishimura13">206</a>].
      Un cas d'intérêt particulier est le semi-anneau booléen, dans lequel l'OR
      sert d'addition et l'ET sert de multiplication. Aucun algorithme quantique n'est connu pour la multiplication
      de matrices sur un semi-anneau booléen dans le cas général qui surpasse le meilleur algorithme classique,
      qui a une complexité de \( n^{2.373} \). Cependant, pour des entrées ou des sorties parcimonieuses,