forked from stephenjordan/stephenjordan.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
4983 lines (4461 loc) · 235 KB
/
index.html
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="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Quantum Algorithm Zoo</title>
<meta name="description" content="A comprehensive list of quantum algorithms." />
<meta name="keywords" content="quantum algorithm algorithms zoo list catalog" />
<meta name="author" content="Stephen Jordan" />
<link rel="stylesheet" type="text/css" href="newzoo.css" />
<script type="text/javascript" async
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
</head>
<body>
<div id="wrap">
<div id="header">
<h1>Quantum Algorithm Zoo</h1>
</div>
<div id="main">
<div id="notice">
<p>This is a comprehensive catalog of quantum algorithms. If you notice any errors or
omissions, please email me at [email protected]. (Alternatively, you may
submit a pull request to the <a href="https://github.com/stephenjordan/stephenjordan.github.io">repository</a> on github.)
Although I cannot guarantee a prompt response, your help is appreciated and will be
<a href="#acknowledgments">acknowledged</a>.</p>
</div>
<a name="algebraic"></a>
<h2>Algebraic and Number Theoretic Algorithms</h2>
<b>Algorithm:</b> Factoring<br />
<b>Speedup:</b> Superpolynomial<br />
<b>Implementation:</b> <a href="https://short.classiq.io/shor">Classiq</a><br />
<b>Description:</b> Given an <i>n</i>-bit integer, find the prime
factorization. The quantum algorithm of Peter Shor solves this in
\( \widetilde{O} (n^3) \) time
[<a href="#Shor_factoring">82</a>,<a href="#Shor_factoring94">125</a>].
The fastest known classical algorithm for integer factorization is the
general number field sieve, which is believed to run in time \(
2^{\widetilde{O}(n^{1/3})} \). The best rigorously proven upper bound
on the classical complexity of factoring is \( O(2^{n/4+o(1)}) \) via the Pollard-Strassen algorithm
[<a href="#Pol">252</a>, <a href="#Stras">362</a>]. Shor's
factoring algorithm breaks RSA public-key encryption and the
closely related quantum algorithms for discrete logarithms break the DSA
and ECDSA digital signature schemes and the Diffie-Hellman
key-exchange protocol. A quantum algorithm even faster than Shor's for
the special case of factoring “semiprimes”, which are
widely used in cryptography, is given in [<a href="#GLFB15">271</a>].
If small factors exist, Shor's algorithm can be beaten by a quantum
algorithm using Grover search to speed up the elliptic curve factorization
method [<a href="#PQRSA">366</a>]. Additional optimized versions of Shor's algorithm are given in
[<a href="#EH17">384</a>, <a href="#BBM17">386</a>, <a href="#GE21">431</a>].
There are proposed classical public-key
cryptosystems not believed to be broken by quantum algorithms, <i>cf.</i>
[<a href="#BBD09">248</a>]. At the core of Shor's factoring algorithm is
order finding, which can be reduced to the <a href="#abelian_HSP">Abelian hidden subgroup problem</a>,
which is solved using the quantum Fourier transform. A number of other
problems are known to reduce to integer factorization including the
membership problem for matrix groups over fields of odd order
[<a href="#BBS09">253</a>], and certain diophantine problems relevant to
the synthesis of quantum circuits [<a href="#RS12">254</a>].
<br /><br />
<b>Algorithm:</b> Discrete-log<br />
<b>Speedup:</b> Superpolynomial<br />
<b>Description:</b> We are given three <i>n</i>-bit
numbers <i>a</i>, <i>b</i>, and <i>N</i>, with the promise that
\( b = a^s \mod N \) for some <i>s</i>. The task is to find <i>s</i>.
As shown by Shor [<a href="#Shor_factoring">82</a>], this can be achieved
on a quantum computer in poly(<i>n</i>) time. The fastest known
classical algorithm requires time superpolynomial in <i>n</i>. By similar
techniques to those in [<a href="#Shor_factoring">82</a>], quantum computers
can solve the discrete logarithm problem on elliptic curves, thereby breaking
elliptic curve cryptography [<a href="#Zalka_ellip">109</a>, <a href="#BL95">14</a>].
Further optimizations to Shor's algorithm are given in [<a href="#E17">385</a>, <a href="#RNSL17">432</a>].
The superpolynomial quantum speedup has also been extended to the discrete
logarithm problem on semigroups [<a href="#Childs_Ivanyos">203</a>,
<a href="#Banin_Tsaban">204</a>]. See also <a href="#abelian_HSP">Abelian hidden subgroup</a>.
<br /><br />
<b>Algorithm:</b> Pell's Equation<br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> Given a positive nonsquare integer <i>d</i>,
Pell's equation is \( x^2 - d y^2 = 1 \). For any such <i>d</i>
there are infinitely many pairs of integers (<i>x,y</i>)
solving this equation. Let \( (x_1,y_1) \) be the pair that minimizes
\( x+y\sqrt{d} \). If <i>d</i> is an <i>n</i>-bit integer
(<i>i.e.</i> \( 0 \leq d \lt 2^n \) ), \( (x_1,y_1) \)
may in general require exponentially many bits to write down. Thus it
is in general impossible to find \( (x_1,y_1) \) in polynomial time.
Let \( R = \log(x_1+y_1 \sqrt{d}) \). \( \lfloor R \rceil \)
uniquely identifies \( (x_1,y_1) \). As shown by Hallgren
[<a href="#Hallgren_Pell">49</a>], given a <i>n</i>-bit number
<i>d</i>, a quantum computer can find \( \lfloor R \rceil \)
in poly(<i>n</i>) time. No polynomial time classical algorithm for
this problem is known. Factoring reduces to this problem. This
algorithm breaks the Buchman-Williams cryptosystem. See also <a href="#abelian_HSP">Abelian
hidden subgroup</a>.
<br /><br />
<b>Algorithm:</b> Principal Ideal <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> We are given an <i>n</i>-bit integer <i>d</i> and an
invertible ideal <i>I</i> of the ring \( \mathbb{Z}[\sqrt{d}] \).
<i>I</i> is a principal ideal if there exists \( \alpha \in \mathbb{Q}(\sqrt{d}) \)
such that \( I = \alpha \mathbb{Z}[\sqrt{d}] \). \( \alpha \) may be exponentially
large in <i>d</i>. Therefore \( \alpha \) cannot in general even be written down
in polynomial time. However, \( \lfloor \log \alpha \rceil \)
uniquely identifies \( \alpha \). The task is to determine whether <i>I</i>
is principal and if so find \( \lfloor \log \alpha \rceil \).
As shown by Hallgren, this can be done in polynomial time on a quantum computer
[<a href="#Hallgren_Pell">49</a>]. A modified quantum algorithm for this problem
using fewer qubits was given in [<a href="#Schmidt_PIP">131</a>]. A quantum
algorithm solving the principal ideal problem in number fields of arbitrary degree
(<i>i.e.</i> scaling polynomially in the degree) was subsequently given in
[<a href="#Biasse_Song16">329</a>]. Factoring reduces to solving Pell's equation,
which reduces to the principal ideal problem. Thus the principal ideal problem
is at least as hard as factoring and therefore is probably not in P. See also
<a href="#abelian_HSP">Abelian hidden subgroup</a>.
<br /><br />
<b>Algorithm:</b> Unit Group <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> The number field \( \mathbb{Q}(\theta) \)
is said to be of degree <i>d</i> if the lowest degree polynomial of which
\( \theta \) is a root has degree <i>d</i>. The set \( \mathcal{O} \)
of elements of \( \mathbb{Q}(\theta) \) which are roots of monic polynomials in
\( \mathbb{Z}[x] \) forms a ring, called the ring of integers of
\( \mathbb{Q}(\theta) \). The set of units (invertible elements) of the ring
\( \mathcal{O} \) form a group denoted \( \mathcal{O}^* \). As shown by
Hallgren [<a href="#Hallgren_unit">50</a>], and independently by Schmidt and
Vollmer [<a href="#Schmidt">116</a>], for any \( \mathbb{Q}(\theta) \)
of fixed degree, a quantum computer can find in polynomial time a set
of generators for \( \mathcal{O}^* \) given a description of \( \theta \).
No polynomial time classical algorithm for this problem is known. Hallgren
and collaborators subsequently discovered how to achieve polynomial scaling
in the degree [<a href="#EHKS14">213</a>]. See also [<a href="#Biasse_Song16">329</a>].
The algorithms rely on solving Abelian hidden subgroup problems over the additive
group of real numbers.
<br /><br />
<b>Algorithm:</b> Class Group <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b>
The number field \( \mathbb{Q}(\theta) \)
is said to be of degree <i>d</i> if the lowest degree polynomial of which
\( \theta \) is a root has degree <i>d</i>. The set \( \mathcal{O} \)
of elements of \( \mathbb{Q}(\theta) \) which are roots of monic polynomials in
\( \mathbb{Z}[x] \) forms a ring, called the ring of integers of
\( \mathbb{Q}(\theta) \), which is a Dedekind domain. For a Dedekind domain, the nonzero
fractional ideals modulo the nonzero principal ideals form a group called the class group.
As shown by Hallgren [<a href="#Hallgren_unit">50</a>], a quantum computer can find
a set of generators for the class group of the ring of
integers of any constant degree number field, given a description of \( \theta \), in time
poly(log(\( | \mathcal{O} | \))). An improved quantum algorithm, whose runtime is also
polynomial in <i>d</i> was subsequently given in [<a href="#Biasse_Song16">329</a>].
No polynomial time classical algorithm for these problems are known. See also <a href="#abelian_HSP">Abelian
hidden subgroup</a>.
<br /><br />
<b>Algorithm:</b> Gauss Sums <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> Let \( \mathbb{F}_q \) be a finite field. The elements other
than zero of \( \mathbb{F}_q \) form a group \( \mathbb{F}_q^\times \) under
multiplication, and the elements of \( \mathbb{F}_q \) form an (Abelian but
not necessarily cyclic) group \( \mathbb{F}_q^+ \) under addition. We can choose
some character \( \chi^\times \) of \( \mathbb{F}_q^\times \) and some
character \( \chi^+ \) of \( \mathbb{F}_q^+ \). The corresponding Gauss sum
is the inner product of these characters:
\( \sum_{x \neq 0 \in \mathbb{F}_q} \chi^+(x) \chi^\times(x) \)
As shown by van Dam and Seroussi [<a href="#vanDam_Gauss">90</a>], Gauss sums
can be estimated to polynomial precision on a quantum computer in polynomial
time. Although a finite ring does not form a group under
multiplication, its set of units does. Choosing a representation for
the additive group of the ring, and choosing a representation for the
multiplicative group of its units, one can obtain a Gauss sum over
the units of a finite ring. These can also be estimated to polynomial
precision on a quantum computer in polynomial
time [<a href="#vanDam_Gauss">90</a>]. No polynomial time
classical algorithm for estimating Gauss sums is known. Discrete log
reduces to Gauss sum estimation [<a href="#vanDam_Gauss">90</a>]. Certain partition
functions of the Potts model can be computed by a polynomial-time quantum algorithm
related to Gauss sum estimation [<a href="#Geraci_exact">47</a>].
<br /><br />
<b>Algorithm:</b>Primality Proving<br />
<b>Speedup:</b>Polynomial<br />
<b>Description:</b> Given an <i>n</i>-bit number, return a proof of its primality. The fastest classical
algorithms are AKS, the best versions of which [<a href="#AKS1">393</a>, <a href="#AKS2">394</a>] have
essentially-quartic complexity, and ECPP, where the heuristic complexity of the fastest version
[<a href="#ECPP">395</a>] is also essentially quartic. The fastest known quantum algorithm for this
problem is the method of Donis-Vela and Garcia-Escartin [<a href="#DVGE">396</a>], with complexity
\( O(n^2 (\log \ n)^3 \log \ \log \ n) \). This improves upon a prior factoring-based quantum algorithm
for primality proving [<a href="#ChauLo">397</a>] that has complexity \( O(n^3 \log \ n \ \log \ \log \ n) \).
A recent result of Harvey and Van Der Hoeven [<a href="#HVDH">398</a>] can be used to improve the
complexity of the factoring-based quantum algorithm for primality proving to \( O(n^3 \log n) \)
and it may be possible to similarly reduce the complexity of the Donis-Vela-Garcia-Escartin algorithm
to \( O(n^2 (\log \ n)^3) \) [<a href="#Greathouse">399</a>].
<br /><br />
<b>Algorithm:</b>Solving Exponential Congruences<br />
<b>Speedup:</b>Polynomial<br />
<b>Description:</b>
We are given \( a,b,c,f,g \in \mathbb{F}_q \). We must find integers \(x,y\)
such that \( a f^x + b g^y = c \). As shown in [<a href="#VDS08">111</a>],
quantum computers can solve this problem in \( \widetilde{O}(q^{3/8}) \) time whereas the best
classical algorithm requires \( \widetilde{O}(q^{9/8}) \) time. The quantum algorithm of
[<a href="#VDS08">111</a>] is based on the quantum algorithms for discrete logarithms
and searching.
<br /><br />
<b>Algorithm:</b> Matrix Elements of Group Representations<br />
<b>Speedup:</b> Superpolynomial<br />
<b>Description:</b> All representations of finite groups and compact linear
groups can be expressed as unitary matrices given an appropriate choice of
basis. Conjugating the regular representation of a group by the
quantum Fourier transform circuit over that group yields a direct sum
of the group's irreducible representations. Thus, the efficient
quantum Fourier transform over the symmetric
group [<a href="#Beals_general">196</a>], together with the Hadamard
test, yields a fast quantum algorithm for additively approximating
individual matrix elements of the arbitrary irreducible
representations of \( S_n \). Similarly, using the quantum Schur
transform [<a href="#Schur">197</a>], one can efficiently approximate matrix elements of
the irreducible representations of SU(n) that have polynomial weight.
Direct implementations of individual irreducible representations for
the groups U(n), SU(n), SO(n), and \( A_n \) by efficient quantum
circuits are given in [<a href="#SPJ08">106</a>]. Instances that appear
to be exponentially hard for known classical algorithms are also
identified in [<a href="#SPJ08">106</a>].<br /><br />
<b>Algorithm:</b> Verifying Matrix Products <br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> Given three \( n \times n \) matrices, <i>A,B</i>, and <i>C</i>,
the matrix product verification problem is to decide whether <i>AB=C</i>.
Classically, the best known algorithm achieves this in time \( O(n^2) \),
whereas the best known classical algorithm for matrix multiplication runs in time
\( O(n^{2.373}) \). Ambainis <i>et al.</i> discovered a quantum algorithm for this
problem with runtime \( O(n^{7/4}) \) [<a href="#Ambainis_matrix">6</a>]. Subsequently,
Buhrman and Špalek improved upon this, obtaining a quantum algorithm for this
problem with runtime \( O(n^{5/3}) \) [<a href="#Buhrman_matrix">19</a>]. This latter
algorithm is based on results regarding quantum walks that were proven in
[<a href="#Szegedy">85</a>].
<br /><br />
<b>Algorithm:</b> Subset-sum <br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> Given a list of integers \( x_1,\ldots,x_n \), and
a target integer <i>s</i>, the subset-sum problem is to determine
whether the sum of any subset of the given integers adds up
to <i>s</i>. This problem is NP-complete, and therefore is unlikely to
be solvable by classical or quantum algorithms with polynomial
worst-case complexity. In the hard instances the given integers
are of order \( 2^n \) and much research on subset sum focuses on
average case instances in this regime. In [<a href="#BJLM13">178</a>], a quantum
algorithm is given that solves such instances in time \( 2^{0.241n} \),
up to polynomial factors. This quantum algorithm works by applying a
variant of Ambainis's quantum walk algorithm for
element-distinctness [<a href="#Ambainis_distinctness">7</a>] to speed up a sophisticated
classical algorithm for this problem due to Howgrave-Graham and
Joux. The fastest known classical algorithm for such instances of subset-sum runs in time
\( 2^{0.291n} \), up to polynomial factors [<a href="#BCJ11">404</a>].<br /><br />
<b>Algorithm:</b> Decoding <br />
<b>Speedup:</b> Varies <br />
<b>Description:</b> Classical error correcting codes allow the
detection and correction of bit-flips by storing data
reduntantly. Maximum-likelihood decoding for arbitrary linear codes is
NP-complete in the worst case, but for structured codes or bounded
error efficient decoding algorithms are known. Quantum algorithms have
been formulated to speed up the decoding of convolutional codes
[<a href="#GM14">238</a>] and simplex codes
[<a href="#BZ98">239</a>].<br /><br />
<b>Algorithm:</b> Quantum Cryptanalysis <br />
<b>Speedup:</b> Various <br />
<b>Description:</b> It is well-known that Shor's algorithms for
factoring and discrete logarithms
[<a href="#Shor_factoring">82</a>,<a href="#Shor_factoring94">125</a>]
completely break the RSA and Diffie-Hellman cryptosystems, as well as
their elliptic-curve-based variants [<a href="#Zalka_ellip">109</a>, <a href="#BL95">14</a>].
(A number of "post-quantum" public-key cryptosystems have been proposed to replace these
primitives, which are not known to be broken by quantum attacks.)
Beyond Shor's algorithm, there is a growing body of work on quantum
algorithms specifically designed to attack cryptosystems. These
generally fall into three categories. The first is quantum algorithms
providing polynomial or sub-exponential time attacks on cryptosystems
under standard assumptions. In particular, the algorithm of Childs,
Jao, and Soukharev for finding isogenies of elliptic curves breaks
certain elliptic curve based cryptosystems in subexponential time
that were not already broken by Shor's algorithm
[<a href="#CJS14">283</a>]. The second category is quantum algorithms
achieving polynomial improvement over known classical cryptanalytic
attacks by speeding up parts of these classical algorithms using
Grover search, quantum collision finding, etc. Such attacks
on private-key [<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>]
and public-key [<a href="#LMP13">262</a>, <a href="#F15">287</a>] primitives, do not
preclude the use of the associated cryptosystems but may influence
choice of key size. The third category is attacks that make use of quantum
superposition queries to block ciphers. These attacks in many cases completely
break the cryptographic primitives [<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>].
However, in most practical situations such superposition queries are
unlikely to be feasible.
<hr />
<a name="oracular"></a>
<h2>Oracular Algorithms</h2>
<b>Algorithm:</b> Searching <br />
<b>Speedup:</b> Polynomial <br />
<b>Implementation:</b> <a href="https://short.classiq.io/quantum_counting">Classiq</a><br />
<b>Description:</b> We are given an oracle with <i>N</i>
allowed inputs. For one input <i>w</i> ("the winner") the corresponding output is
1, and for all other inputs the corresponding output is 0. The task is to find
<i>w</i>. On a classical computer this requires \( \Omega(N) \)
queries. The quantum algorithm of Lov Grover achieves this using
\( O(\sqrt{N}) \) queries [<a href="#Grover_search">48</a>], which is
optimal [<a href="#BBBV">216</a>]. This has algorithm has
subsequently been generalized to search in the presence of multiple
"winners" [<a href="#BBHT98">15</a>], evaluate the sum of an arbitrary
function [<a href="#BBHT98">15</a>,<a href="#BHT98">16</a>,<a href="#Mos98">73</a>],
find the global minimum of an arbitrary function
[<a href="#DH96">35</a>,<a href="#NW99">75</a>, <a href="#KLPF08">255</a>], take advantage of alternative
initial states [<a href="#Biham">100</a>] or nonuniform probabilistic priors
[<a href="#Montanaro">123</a>], work with oracles whose runtime varies
between inputs [<a href="#Ambainis_linear">138</a>], approximate
definite integrals [<a href="#integration">77</a>], and converge to a
fixed-point
[<a href="#G05">208</a>, <a href="#TGP05">209</a>, <a href="#GSLW19">433</a>]. Considerations on optimizing
the depth of quantum search circuits are given in [<a href="#ZK19">405</a>]. The
generalization of Grover's algorithm known as amplitude estimation
[<a href="#Amplitude">17</a>]
is now an important primitive in quantum algorithms. Amplitude estimation forms the
core of most known quantum algorithms related to collision finding and graph
properties. One of the natural applications for Grover search is speeding up the
solution to NP-complete problems such as 3-SAT. Doing so is nontrivial, because
the best classical algorithm for 3-SAT is not quite a brute force search. Nevertheless,
amplitude amplification enables a quadratic quantum speedup over the best
classical 3-SAT algorithm, as shown in [<a href="#Ambainis_SIGACT">133</a>]. Quadratic
speedups for other constraint satisfaction problems are obtained in
[<a href="#CGF">134</a>]. For further examples of application of
Grover search and amplitude amplification see
[<a href="#C14">261</a>, <a href="#LMP13">262</a>]. A problem closely
related to, but harder than, Grover search, is spatial search, in
which database queries are limited by some graph structure. On
sufficiently well-connected graphs, \(O(\sqrt{n})\) quantum query
complexity is still achievable [<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>Algorithm:</b> Abelian Hidden Subgroup <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Implementation:</b> <a href="https://short.classiq.io/simon">Classiq</a><br />
<b>Description:</b> Let <i>G</i> be a finitely generated Abelian group, and let
<i>H</i> be some subgroup of <i>G</i> such that <i>G/H</i> is finite. Let <i>f</i>
be a function on <i>G</i> such that for any \( g_1,g_2 \in G \), \( f(g_1) = f(g_2) \)
if and only if \( g_1 \) and \( g_2 \) are in the same coset of <i>H</i>. The task is
to find <i>H</i> (<i>i.e.</i> find a set of generators for <i>H</i>) by making queries
to <i>f</i>. This is solvable on a quantum computer using \( O(\log \vert G\vert) \)
queries, whereas classically \( \Omega(|G|) \) are required. This algorithm was first
formulated in full generality by Boneh and Lipton in [<a href="#BL95">14</a>]. However,
proper attribution of this algorithm is difficult because, as described in chapter 5 of
[<a href="#Nielsen_Chuang">76</a>], it subsumes many historically important quantum
algorithms as special cases, including Simon's algorithm [<a href="#Simon">108</a>],
which was the inspiration for Shor's period finding algorithm, which forms the core
of his factoring and discrete-log algorithms. The Abelian hidden subgroup algorithm
is also at the core of the Pell's equation, principal ideal, unit group, and class
group algorithms. In certain instances, the Abelian hidden subgroup problem can be
solved using a single query rather than order \( \log(\vert G\vert) \), as shown
in [<a href="#Beaudrap">30</a>]. It is normally assumed in period finding that the
function \(f(x) \neq f(y) \) unless \( x-y = s \), where \( s \) is the period.
A quantum algorithm which applies even when this restiction is relaxed is given in
[<a href="#Hales_Hallgren">388</a>]. Period finding has been generalized to apply to
oracles which provide only the few most significant bits about the underlying
function in [<a href="#SW07">389</a>].
<br /><br />
<a name="nonabelian_HSP"></a>
<b>Algorithm:</b> Non-Abelian Hidden Subgroup <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> Let <i>G</i> be a finitely generated group, and let <i>H</i> be
some subgroup of <i>G</i> that has finitely many left cosets. Let <i>f</i> be a
function on <i>G</i> such that for any \( g_1, g_2 \), \( f(g_1) = f(g_2) \)
if and only if \( g_1 \) and \( g_2 \) are in the same left coset of <i>H</i>.
The task is to find <i>H</i> (<i>i.e.</i> find a set of generators for <i>H</i>)
by making queries to <i>f</i>. This is solvable on a quantum computer using
\( O(\log(|G|) \) queries, whereas classically \( \Omega(|G|) \)
are required [<a href="#Ettinger">37</a>,<a href="#Hallgren_Russell">51</a>].
However, this does not qualify as an efficient quantum algorithm because in general,
it may take exponential time to process the quantum states obtained from these
queries. Efficient quantum algorithms for the hidden subgroup problem are known for
certain specific non-Abelian groups
[<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>].
A slightly outdated survey is given in [<a href="#Survey_NAHS">69</a>]. Of
particular interest are the symmetric group and the dihedral group. A solution
for the symmetric group would solve graph isomorphism. A solution for the
dihedral group would solve certain lattice problems [<a href="#Regev_lattice">78</a>].
Despite much effort, no polynomial-time solution for these groups is known, except in
special cases [<a href="#Roet16">312</a>]. However,
Kuperberg [<a href="#Kuperberg">66</a>] found a time \( 2^{O( \sqrt{\log N})}) \)
algorithm for finding a hidden subgroup of the dihedral group \( D_N \). Regev
subsequently improved this algorithm so that it uses not only subexponential time
but also polynomial space [<a href="#Regev_dihedral">79</a>]. A
further improvement in the asymptotic scaling of the required number
of qubits is obtained in [<a href="#K13">218</a>]. Quantum query speedups (though
not necessarily efficient quantum algorithms in terms of gate count) for
somewhat more general problems of testing for isomorphisms of functions under sets of
permutations are given in [<a href="#HM16">311</a>]
<br /><br />
<b>Algorithm:</b> Bernstein-Vazirani <br />
<b>Speedup:</b> Polynomial Directly, Superpolynomial Recursively <br />
<b>Implementation:</b> <a href="https://short.classiq.io/bernstein_vazirani">Classiq</a><br />
<b>Description:</b> We are given an oracle whose input is <i>n</i>
bits and whose output is one bit. Given input \( x \in \{0,1\}^n \), the output is
\( x \odot h \), where <i>h</i> is the "hidden" string of <i>n</i> bits, and
\( \odot \) denotes the bitwise inner product modulo 2. The task is to find <i>h</i>.
On a classical computer this requires <i>n</i> queries. As shown by Bernstein and
Vazirani [<a href="#Bernstein_Vazirani">11</a>], this can be achieved on a quantum
computer using a single query. Furthermore, one can construct recursive versions of
this problem, called recursive Fourier sampling, such that quantum computers require
exponentially fewer queries than classical computers
[<a href="#Bernstein_Vazirani">11</a>]. See
[<a href="#HH08">256</a>, <a href="#BH10">257</a>] for related work
on the ubiquity of quantum speedups from generic quantum circuits and
[<a href="#AA14">258</a>, <a href="#ABK15">270</a>] for related work on a quantum query speedup
for detecting correlations between the an oracle function and the
Fourier transform of another.
<br /><br />
<b>Algorithm:</b> Deutsch-Jozsa <br />
<b>Speedup:</b> Exponential over P, none over BPP<br />
<b>Implementation:</b> <a href="https://short.classiq.io/deutsch_josza">Classiq</a><br />
<b>Description:</b> We are given an oracle whose input is <i>n</i> bits and whose output
is one bit. We are promised that out of the \( 2^n \) possible inputs, either all of them,
none of them, or half of them yield output 1. The task is to distinguish the balanced case
(half of all inputs yield output 1) from the constant case (all or none of the inputs yield
output 1). It was shown by Deutsch [<a href="#Deutsch">32</a>] that for <i>n=1</i>, this
can be solved on a quantum computer using one query, whereas any deterministic classical
algorithm requires two. This was historically the first well-defined quantum algorithm
achieving a speedup over classical computation. (A related, more recent, pedagogical
example is given in [<a href="#G14">259</a>].) A single-query quantum algorithm for
arbitrary <i>n</i> was developed by Deutsch and Jozsa in [<a href="#Deutsch_Jozsa">33</a>].
Although probabilistically easy to solve with <i>O(1)</i> queries, the Deutsch-Jozsa problem
has exponential worst case deterministic query complexity classically.
<br /><br />
<b>Algorithm:</b> Formula Evaluation <br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> A Boolean expression is called a formula if each variable is used only
once. A formula corresponds to a circuit with no fanout, which consequently has the topology
of a tree. By Reichardt's span-program formalism, it is now known
[<a href="#Reichardt_Reflection">158</a>] that the quantum query complexity of any formula
of <i>O</i>(1) fanin on <i>N</i> variables is \( \Theta(\sqrt{N}) \).
This result culminates from a long line of work
[<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>],
which started with the discovery by Farhi <i>et al.</i> [<a href="#Farhi_NAND">38</a>]
that NAND trees on \( 2^n \) variables can be evaluated on quantum computers in time
\( O(2^{0.5n}) \) using a continuous-time quantum walk, whereas classical computers
require \( \Omega(2^{0.753n}) \) queries. In many cases, the quantum formula-evaluation
algorithms are efficient not only in query complexity but also in time-complexity. The
span-program formalism also yields quantum query complexity lower bounds
[<a href="#Reichardt2010">149</a>]. Although originally discovered from a different point of
view, Grover's algorithm can be regarded as a special case of formula evaluation in which
every gate is OR. The quantum complexity of evaluating non-boolean formulas has also been
studied [<a href="#Cleve_tree">29</a>], but is not as fully understood. Childs <i>et al.</i>
have generalized to the case in which input variables may be repeated (<i>i.e.</i> the first
layer of the circuit may include fanout) [<a href="#Childs_Kimmel_Kothari">101</a>]. They
obtained a quantum algorithm using \( O(\min \{N,\sqrt{S},N^{1/2} G^{1/4} \}) \)
queries, where <i>N</i> is the number of input variables not including multiplicities,
<i>S</i> is the number of inputs counting multiplicities, and <i>G</i> is the number of
gates in the formula. References [<a href="#Zhan_Kimmel_Hassidim">164</a>],
[<a href="#Kimmel">165</a>], and [<a href="#JK15">269</a>] consider
special cases of the NAND tree problem in which the number of NAND
gates taking unequal inputs is limited. Some of these cases yield
superpolynomial separation between quantum and classical query
complexity.
<br /><br />
<b>Algorithm:</b> Hidden Shift <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Implementation:</b> <a href="https://short.classiq.io/hidden_shift">Classiq</a><br />
<b>Description:</b> We are given oracle access to some function <i>f</i> on
\( \mathbb{Z}_N \). We know that <i>f(x) = g(x+s)</i> where <i>g</i> is a known function
and <i>s</i> is an unknown shift. The hidden shift problem is to find <i>s</i>. By
reduction from Grover's problem it is clear that at least \( \sqrt{N} \) queries
are necessary to solve hidden shift in general. However, certain special cases of the
hidden shift problem are solvable on quantum computers using <i>O(1)</i> queries. In
particular, van Dam <i>et al.</i> showed that this can be done if <i>f</i> is a multiplicative
character of a finite ring or field [<a href="#vanDam_shift">89</a>]. The previously
discovered shifted Legendre symbol algorithm
[<a href="#vanDam_Legendre">88</a>,<a href="#vanDam_weighing">86</a>] is subsumed as a
special case of this, because the Legendre symbol \( \left(\frac{x}{p} \right) \)
is a multiplicative character of \( \mathbb{F}_p \). No classical algorithm running in time
<i>O</i>(polylog(<i>N</i>)) is known for these problems. Furthermore, the quantum algorithm
for the shifted Legendre symbol problem would break a certain
cryptographic pseudorandom generator given the ability to make
quantum queries to the generator [<a href="#vanDam_shift">89</a>].
A quantum speedup for hidden shift problems of difference sets is given in [<a href="#Roet16">312</a>],
and this also subsumes the Legendre symbol problem as a special case.
Roetteler has found exponential quantum speedups for
finding hidden shifts of certain nonlinear Boolean functions
[<a href="#Roetteler08">105</a>,<a href="#Roetteler_quad">130</a>]. Building on this work,
Gavinsky, Roetteler, and Roland have shown [<a href="#Gavinsky">142</a>] that the hidden
shift problem on random boolean functions \( f:\mathbb{Z}_2^n \to \mathbb{Z}_2 \)
has <i>O(n)</i> average case quantum complexity, whereas the classical query
complexity is \( \Omega(2^{n/2}) \). The results in [<a href="#Ettinger_Hoyer">143</a>],
though they are phrased in terms of the hidden subgroup problem for the dihedral group, imply
that the quantum <i>query</i> complexity of the hidden shift problem for an injective function
on \( \mathbb{Z}_N \) is <i>O</i>(log <i>n</i>), whereas the classical query complexity is
\( \Theta(\sqrt{N}) \). However, the best known quantum <i>circuit</i> complexity for injective
hidden shift on \( \mathbb{Z}_N \) is \( O(2^{C \sqrt{\log N}}) \), achieved by Kuperberg's
sieve algorithm [<a href="#Kuperberg">66</a>]. A recent result, building upon [<a href="#Ivanyos08">408</a>, <a href="#FIMSS_NAHS">43</a>],
achieves exponential quantum speedups for some generalizations of the Hidden shift problem including
the <i>hidden multiple shift problem</i>, in which one has query access to \(f_s(x) = f(x-hs) \)
over some allowed range of <i>s</i> and one wishes to infer <i>h</i> [<a href="#IPS18">407</a>].
<br /><br />
<b>Algorithm:</b> Polynomial interpolation <br />
<b>Speedup:</b> Varies <br />
<b>Description:</b> Let \( p(x) = a_d x^d + \ldots + a_1 x + a_0 \) be a polynomial over the finite field \( \mathrm{GF}(q) \). One is given access to an oracle that, given \( x \in \mathrm{GF}(q) \), returns \( p(x) \). The polynomial reconstruction problem is, by making queries to the oracle, to determine the coefficients \( a_d,\ldots,a_0 \). Classically, \( d + 1 \) queries are necessary and sufficient. (In some sources use the term reconstruction instead of interpolation for this problem.) Quantumly, \( d/2 + 1/2 \) queries are necessary and \( d/2 + 1 \) queries are sufficient [<a href="#interp1">360</a>,<a href="#interp2">361</a>]. For multivariate polynomials of degree <i>d</i> in <i>n</i> variables the interpolation problem has classical query complexity \( \binom{n+d}{d} \). As shown in [<a href="#interp3">387</a>], the quantum query complexity is \( O \left( \frac{1}{n+1} \binom{n+d}{d} \right) \) over \( \mathbb{R} \) and \( \mathbb{C} \) and it is \( O \left( \frac{d}{n+d} \binom{n+d}{d} \right) \) over \( \mathbb{F}_q \) for sufficiently large <i>q</i>. Quantum algorithms have also been discovered for the case that the oracle returns \( \chi(f(x)) \) where \( \chi \) is a quadratic character of \( \mathrm{GF}(q) \) [<a href="#RS04">390</a>], and the case where the oracle returns \( f(x)^e \) [<a href="#IKS17">392</a>]. These generalize the hidden shift algorithm of [<a href="#vanDam_shift">89</a>] and achieve an exponential speedup over classical computation. A quantum algorithm for reconstructing rational functions over finite fields given noisy and incomplete oracle access to the function values is given in [<a href="#HRS05">391</a>].
<br /><br />
<b>Algorithm:</b> Pattern matching <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> Given strings <i>T</i> of length <i>n</i>
and <i>P</i> of length <i>m</i> < <i>n</i>, both from some finite
alphabet, the pattern matching problem is to find an occurrence
of <i>P</i> as a substring of <i>T</i> or to report that <i>P</i> is
not a substring of <i>T</i>. More generally, <i>T</i> and <i>P</i>
could be <i>d</i>-dimensional arrays rather than one-dimensional
arrays (strings). Then, the pattern matching problem is to return the
location of <i>P</i> as a \(m \times m \times \ldots \times m\)
block within the \(n \times n \times \ldots \times n\) array <i>T</i>
or report that no such location exists. The \( \Omega(\sqrt{N}) \)
query lower bound for unstructured search [<a href="#BBBV">216</a>]
implies that the worst-case quantum query complexity of this problem
is \( \Omega ( \sqrt{n} + \sqrt{m} ) \). A quantum algorithm achieving
this, up to logarithmic factors, was obtained in
[<a href="#RV00">217</a>]. This quantum algorithm works through the
use of Grover's algorithm together with a classical method called
deterministic sampling. More recently, Montanaro showed that
superpolynomial quantum speedup can be achieved on average case
instances of pattern matching, provided that <i>m</i> is greater than
logarithmic in <i>n</i>. Specifically, the quantum algorithm given in
[<a href="#Montanaro14">215</a>] solves average case pattern matching in
\( \widetilde{O}((n/m)^{d/2} 2^{O(d^{3/2} \sqrt{\log m})})\) time. This
quantum algorithm is constructed by generalizing Kuperberg's quantum
sieve algorithm [<a href="#Kuperberg">66</a>] for dihedral hidden subgroup and
hidden shift problems so that it can operate in <i>d</i> dimensions
and accomodate small amounts of noise, and then classically reducing the
pattern matching problem to this noisy <i>d</i>-dimensional version of
hidden shift. A quantum algorithm for string matching with \(\widetilde{O} (\sqrt{n}) \)
complexity is given in [<a href="#NN21">435</a>] in a different input model,
where the strings are written out in their entirety using \(n + m\) qubits rather
than through quantum queries to an oracle providing individual bits.
<br /><br />
<b>Algorithm:</b> Ordered Search <br />
<b>Speedup:</b> Constant factor <br />
<b>Description:</b> We are given oracle access to a list of <i>N</i> numbers in order
from least to greatest. Given a number <i>x</i>, the task is to find out where in the
list it would fit. Classically, the best possible algorithm is binary search which takes
\( \log_2 N \) queries. Farhi <i>et al.</i> showed that a quantum computer can achieve
this using 0.53 \( \log_2 N \) queries [<a href="#FGGS99">39</a>]. Currently, the best
known deterministic quantum algorithm for this problem uses 0.433 \( \log_2 N \)
queries [<a href="#Landahl">103</a>]. A lower bound of \( \frac{\ln 2}{\pi} \log_2 N \)
quantum queries has been proven for this problem
[<a href="#HNS01">219</a>, <a href="#Childs_Lee">24</a>]. In
[<a href="#Ben_Or_Search">10</a>], a randomized quantum algorithm is given whose expected
query complexity is less than \( \frac{1}{3} \log_2 N \).
<br /><br />
<b>Algorithm:</b> Graph Properties in the Adjacency Matrix Model<br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> Let <i>G</i> be a graph of <i>n</i> vertices. We are given access to
an oracle, which given a pair of integers in {1,2,...,<i>n</i>} tells us whether the
corresponding vertices are connected by an edge. Building on previous work
[<a href="#DH96">35</a>,<a href="#prev2">52</a>,<a href="#prev3">36</a>], Dürr
<i>et al.</i> [<a href="#Durr_graphs">34</a>] show that the quantum query complexity
of finding a minimum spanning tree of weighted graphs, and deciding connectivity for
directed and undirected graphs have \( \Theta(n^{3/2}) \) quantum query complexity,
and that finding lowest weight paths has \( O(n^{3/2}\log^2 n) \) quantum query complexity. Deciding whether a graph is bipartite, detecting cycles, and deciding whether a given vertex can be reached from another (st-connectivity) can all be achieved using a number of queries and quantum gates that both scale as \( \widetilde{O}(n^{3/2}) \), and only logarithmically many qubits, as shown in [<a href="#CMB16">317</a>], building upon [<a href="#Berzina">13</a>, <a href="#Arins">272</a>, <a href="#BR12">318</a>]. A span-program-based quantum algorithm for detecting trees of a given
size as minors in \( \widetilde{O}(n) \) time is given in
[<a href="#Wang13">240</a>]. A graph property is
sparse if there exists a constant <i>c</i> such that every graph with the property has
a ratio of edges to vertices at most <i>c</i>. Childs and Kothari have shown that all
sparse graph properties have query complexity \( \Theta(n^{2/3}) \) if they cannot be
characterized by a list of forbidden subgraphs and \( o(n^{2/3}) \)
(<a href="http://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation">little-o</a>)
if they can [<a href="#Childs_minor">140</a>]. The former algorithm is based on Grover
search, the latter on the quantum walk formalism of [<a href="#Magniez_walk">141</a>].
By Mader's theorem, sparse graph properties include all nontrivial minor-closed properties.
These include planarity, being a forest, and not containing a path of
given length. According to the widely-believed Aanderaa-Karp-Rosenberg conjecture, all of the above problems have \( \Omega(n^2) \) classical query complexity. Another
interesting computational problem is finding a subgraph <i>H</i> in a given graph <i>G</i>.
The simplest case of this finding the triangle, that is, the clique of size three. The
fastest known quantum algorithm for this finds a triangle in \( O(n^{5/4}) \)
quantum queries [<a href="#CLM16">319</a>], improving upon
[<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>]. Stronger quantum query complexity upper bounds are known when the graphs are sufficiently sparse [<a href="#CLM16">319</a>, <a href="#LS15">320</a>]. Classically, triangle finding
requires \( \Omega(n^2) \) queries [<a href="#Buhrman_collision">21</a>].
More generally, a quantum computer can find an
arbitrary subgraph of <i>k</i> vertices using \( O(n^{2-2/k-t}) \) queries where
\( t=(2k-d-3)/(k(d+1)(m+2)) \) and <i>d</i> and <i>m</i> are such that <i>H</i> has
a vertex of degree <i>d</i> and <i>m</i>+<i>d</i> edges
[<a href="#Lee_Magniez_Santha">153</a>]. This improves on the previous algorithm of
[<a href="#Magniez_triangle">70</a>]. In some cases, this query complexity is beaten by
the quantum algorithm of [<a href="#Childs_minor">140</a>], which finds <i>H</i>
using \( \widetilde{O}\left( n^{\frac{3}{2}-\frac{1}{\mathrm{vc}(H)+1}} \right) \)
queries, provided <i>G</i> is sparse, where vc(<i>H</i>) is the size of the minimal
vertex cover of <i>H</i>. A quantum algorithm for finding
constant-sized sub-hypergraphs over 3-uniform hypergraphs in \(
O(n^{1.883}) \) queries is given in [<a href="#LGNT13">241</a>].
<br /><br />
<b>Algorithm:</b> Graph Properties in the Adjacency List Model<br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> Let <i>G</i> be a graph of <i>N</i> vertices, <i>M</i> edges, and
degree <i>d</i>. We are given access to an oracle which, when queried with the label
of a vertex and \( j \in \{1,2,\ldots,d\} \) outputs the <i>j</i>th neighbor of the
vertex or null if the vertex has degree less than <i>d</i>. Suppose we are given the
promise that <i>G</i> is either bipartite or is far from bipartite in the sense that
a constant fraction of the edges would need to be removed to achieve bipartiteness. Then,
as shown in [<a href="#Ambainis_Childs_Liu">144</a>], the quantum complexity of deciding
bipartiteness is \( \widetilde{O}(N^{1/3}) \). Also in [<a href="#Ambainis_Childs_Liu">144</a>],
it is shown that distinguishing expander graphs from graphs that are far from
being expanders has quantum complexity \( \widetilde{O}(N^{1/3}) \) and
\( \widetilde{\Omega}(N^{1/4}) \), whereas the classical complexity is
\( \widetilde{\Theta}(\sqrt{N}) \). The key quantum algorithmic tool is Ambainis' algorithm for
element distinctness. In [<a href="#Durr_graphs">34</a>], it is shown that finding a minimal
spanning tree has quantum query complexity \( \Theta(\sqrt{NM}) \), deciding graph
connectivity has quantum query complexity \( \Theta(N) \) in the undirected case, and
\( \widetilde{\Theta}(\sqrt{NM}) \) in the directed case, and computing the lowest weight
path from a given source to all other vertices on a weighted graph has quantum
query complexity \( \widetilde{\Theta}(\sqrt{NM}) \). In [<a href="#CMB16">317</a>] quantum algorithms are given for st-connectivity, deciding bipartiteness, and deciding whether a graph is a forest, which run in \( \widetilde{O}(N \sqrt{d}) \) time and use only logarithmically many qubits.
<br /><br />
<b>Algorithm:</b> Welded Tree <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> Some computational problems can be phrased in terms of the query
complexity of finding one's way through a maze. That is, there is some graph <i>G</i>
to which one is given oracle access. When queried with the label of a given node,
the oracle returns a list of the labels of all adjacent nodes. The task is, starting
from some source node (<i>i.e.</i> its label), to find the label of a certain marked
destination node. As shown by Childs <i>et al.</i> [<a href="#Childs_weld">26</a>],
quantum computers can exponentially outperform classical computers at this task for
at least some graphs. Specifically, consider the graph obtained by joining together
two depth-<i>n</i> binary trees by a random "weld" such that all nodes but the two
roots have degree three. Starting from one root, a quantum computer can find the other
root using poly(<i>n</i>) queries, whereas this is provably impossible using classical
queries.
<br /><br />
<b>Algorithm:</b> Collision Finding and Element Distinctness<br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> Suppose we are given oracle access to a two to one
function <i>f</i> on a domain of size <i>N</i>. The collision problem
is to find a pair \( x,y \in \{1,2,\ldots,N\} \) such that <i>f(x) = f(y)</i>.
The classical randomized query complexity of this problem is \( \Theta(\sqrt{N}) \),
whereas, as shown by Brassard <i>et al.</i>, a quantum computer can achieve this
using \(O(N^{1/3}) \) queries [<a href="#Brassard_collision">18</a>]. (See also [<a href="#BHT98b">315</a>].) Removing the
promise that <i>f</i> is two-to-one yields a problem called element distinctness, which
has \( \Theta(N) \) classical query complexity. Improving upon
[<a href="#Buhrman_collision">21</a>], Ambainis gives a quantum algorithm with query
complexity of \( O(N^{2/3}) \) for element distinctness, which is
optimal [<a href="#Ambainis_distinctness">7</a>, <a href="#P17">374</a>]. The problem of
deciding whether any <i>k</i>-fold collisions exist is
called <i>k</i>-distinctness. Improving upon
[<a href="#Ambainis_distinctness">7</a>,<a href="#Belovs_Lee">154</a>],
the best quantum query complexity for <i>k</i>-distinctness is
\( O(n^{3/4 - 1/(4(2^k-1))}) \)
[<a href="#Belovs12">172</a>, <a href="#Childs_Jeffery_Kothari_Magniez13">173</a>]. For <i>k</i>=2,3 this is also the time-complexity, up to logarithmic
factors, by [<a href="#Ambainis_distinctness">7</a>]. For \( k > 3\) the fastest known quantum algorithm has time complexity \( O(n^{(k-1)/k}) \) [<a href="#Jefferythesis">363</a>].
Given two functions <i>f</i> and <i>g</i>, on domains of
size <i>N</i> and <i>M</i>, respectively a claw is a pair <i>x,y</i> such that <i>f(x) =
g(y)</i>. In the case that <i>N</i>=<i>M</i>, the algorithm of [<a href="#Ambainis_distinctness">7</a>]
solves claw-finding in \( O(N^{2/3}) \) queries, improving on the previous \( O(N^{3/4} \log N) \) quantum algorithm
of [<a href="#Buhrman_collision">21</a>]. Further work gives improved query complexity for various parameter regimes
in which \(N \neq M\) [<a href="#Tani">364</a>, <a href="#IwamaKawachi">365</a>]. More generally, a related problem to
element distinctness, is, given oracle access to a sequence, to
estimate the \(k^{\mathrm{th}}\) frequency moment \(F_k = \sum_j n_j^k
\), where \(n_j\) is the number of times that <i>j</i> occurs in the
sequence. An approximately quadratic speedup for this problem is
obtained in [<a href="#M15c">277</a>]. See also <a href="#graph_collision">graph collision</a>.
<br /><br />
<a name="graph_collision"></a>
<b>Algorithm:</b> Graph Collision <br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b>
We are given an undirected graph of <i>n</i> vertices and oracle
access to a labelling of the vertices by 1 and 0. The graph collision
problem is, by querying this oracle, to decide whether there exist a
pair of vertices, connected by an edge, both of which are labelled
1. One can embed Grover's unstructured search problem as an instance
of graph collision by choosing the star graph, labelling the center 1,
and labelling the remaining vertices by the database entries. Hence,
this problem has quantum query complexity \( \Omega(\sqrt{n}) \) and
classical query complexity \( \Theta (n) \). In
[<a href="#Magniez_triangle">70</a>], Magniez, Nayak, and Szegedy gave
a \( O(N^{2/3}) \)-query quantum algorithm for graph collision on
general graphs. This remains the best upper bound on quantum query
complexity for this problem on general graphs. However, stronger upper
bounds have been obtained for several special classes of
graphs. Specifically, the quantum query complexity on a
graph <i>G</i> is \( \widetilde{O}(\sqrt{n} + \sqrt{l}) \) where <i>l</i>
is the number of non-edges in <i>G</i> [<a href="#JKM">161</a>],
\(O(\sqrt{n} \alpha^{1/6}) \) where \(\alpha\) is the size of the
largest independent set of <i>G</i> [<a href="#Belovs12">172</a>],
\(O(\sqrt{n} + \sqrt{\alpha^*})\) where \( \alpha^* \) is the maximum
total degree of any independent set of <i>G</i>
[<a href="#GI12">200</a>], and \(O(\sqrt{n} t^{1/6}) \) where <i>t</i> is
the treewidth of <i>G</i> [<a href="#ABI13">201</a>]. Furthermore, the
quantum query complexity is \( \widetilde{O}(\sqrt{n}) \) with high
probability for random graphs in which the presence or absence of an
edge between each pair of vertices is chosen independently with fixed
probability, (<i>i.e.</i> Erdős-Rényi graphs)
[<a href="#GI12">200</a>]. See [<a href="#ABI13">201</a>] for a
summary of these results as well as new upper bounds for two
additional classes of graph that are too complicated to describe here.
<br /><br />
<b>Algorithm:</b> Matrix Commutativity <br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> We are given oracle access to <i>k</i> matrices, each of which are
\( n \times n \). Given integers \( i,j \in \{1,2,\ldots,n\} \), and
\( x \in \{1,2,\ldots,k\} \) the oracle returns the <i>ij</i> matrix element of the
\( x^{\mathrm{th}} \) matrix. The task is to decide whether all of these <i>k</i>
matrices commute. As shown by Itakura [<a href="#Itakura">54</a>], this can be achieved
on a quantum computer using \( O(k^{4/5}n^{9/5}) \) queries, whereas classically this
requires \( \Omega( k n^2 ) \) queries.
<br /><br />
<b>Algorithm:</b> Group Commutativity <br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> We are given a list of <i>k</i> generators for a group <i>G</i> and
access to a blackbox implementing group multiplication. By querying this blackbox we
wish to determine whether the group is commutative. The best known classical algorithm
is due to Pak and requires <i>O(k)</i> queries. Magniez and Nayak have shown that the
quantum query complexity of this task is \( \widetilde{\Theta}(k^{2/3}) \)
[<a href="#Magniez_Nayak">139</a>].
<br /><br />
<b>Algorithm:</b> Hidden Nonlinear Structures <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> Any Abelian group <i>G</i> can be visualized as a lattice. A subgroup
<i>H</i> of <i>G</i> is a sublattice, and the cosets of <i>H</i> are all the shifts of
that sublattice. The Abelian hidden subgroup problem is normally solved by obtaining
superposition over a random coset of the Hidden subgroup, and then taking the Fourier
transform so as to sample from the dual lattice. Rather than generalizing to
non-Abelian groups (see <a href="#nonabelian_HSP">non-Abelian hidden subgroup</a>), one can instead generalize to
the problem of identifying hidden subsets other than lattices. As shown by Childs
<i>et al.</i> [<a href="#Childs_nonlinear">23</a>] this problem is efficiently solvable
on quantum computers for certain subsets defined by polynomials, such as spheres.
Decker <i>et al.</i> showed how to efficiently solve some related problems in
[<a href="#Wocjan_nonlinear">31</a>, <a href="#DHIS13">212</a>].
<br /><br />
<b>Algorithm:</b> Center of Radial Function <br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> We are given an oracle that evaluates a function <i>f</i> from
\( \mathbb{R}^d \) to some arbitrary set <i>S</i>, where <i>f</i> is spherically
symmetric. We wish to locate the center of symmetry, up to some precision.
(For simplicity, let the precision be fixed.) In [<a href="#Liu">110</a>],
Liu gives a quantum algorithm, based on a curvelet transform, that solves
this problem using a constant number of quantum queries independent of
<i>d</i>. This constitutes a polynomial speedup over the classical lower
bound, which is \( \Omega(d) \) queries. The algorithm works when the function
<i>f</i> fluctuates on sufficiently small scales, <i>e.g.</i>, when the level sets
of <i>f</i> are sufficiently thin spherical shells. The quantum algorithm is shown
to work in an idealized continuous model, and nonrigorous arguments suggest that
discretization effects should be small.
<br /><br />
<b>Algorithm:</b> Group Order and Membership <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> Suppose a finite group <i>G</i> is given oracularly in the following way.
To every element in <i>G</i>, one assigns a corresponding label. Given an ordered pair of
labels of group elements, the oracle returns the label of their product. There are several
classically hard problems regarding such groups. One is to find the group's order, given the
labels of a set of generators. Another task is, given a bitstring, to decide whether it
corresponds to a group element. The constructive version of this membership problem requires,
in the yes case, a decomposition of the given element as a product of group generators.
Classically, these problems cannot be solved using polylog(|<i>G</i>|) queries even if
<i>G</i> is Abelian. For Abelian groups, quantum computers can solve these problems using
polylog(|<i>G</i>|) queries by reduction to the Abelian hidden subgroup problem, as shown
by Mosca [<a href="#Mosca_thesis">74</a>]. Furthermore, as shown by Watrous
[<a href="#Watrous_solvable">91</a>], quantum computers can solve these problems
using polylog(|<i>G</i>|) queries for any solvable group. For groups given as matrices
over a finite field rather than oracularly, the order finding and constructive membership
problems can be solved in polynomial time by using the quantum algorithms for discrete log
and factoring [<a href="#Babai">124</a>]. See also <a href="#group_isomorphism">group isomorphism</a>.
<br /><br />
<a name="group_isomorphism"></a>
<b>Algorithm:</b> Group Isomorphism <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> Let <i>G</i> be a finite group. To every element of
<i>G</i> is assigned an arbitrary label (bit string). Given an ordered pair
of labels of group elements, the group oracle returns the label of their
product. Given access to the group oracles for two groups <i>G</i> and
<i>G'</i>, and a list of generators for each group, we must decide whether
<i>G</i> and <i>G'</i> are isomorphic. For Abelian groups, we can solve this
problem using poly(log |<i>G</i>|, log |<i>G'</i>|) queries to the oracle
by applying the quantum algorithm of [<a href="#Cheung_Mosca">127</a>], which
decomposes any Abelian group into a canonical direct product of cyclic groups.
The quantum algorithm of [<a href="#LeGall">128</a>] solves the group
isomorphism problem using poly(log |<i>G</i>|, log |<i>G'</i>|) queries for a
certain class of non-Abelian groups. Specifically, a group <i>G</i> is in this
class if <i>G</i> has a normal Abelian subgroup <i>A</i> and an element
<i>y</i> of order coprime to |<i>A</i>| such that G
= <i>A</i>, <i>y</i>. Zatloukal has recently given an exponential
quantum speedup for some instances of a problem closely related to
group isomorphism, namely testing equivalence of group extensions
[<a href="#Z13">202</a>].
<br /><br />
<b>Algorithm:</b> Statistical Difference <br />
<b>Speedup:</b> Polynomial <br />
<b>Description:</b> Suppose we are given two black boxes <i>A</i> and <i>B</i>
whose domain is the integers 1 through <i>T</i> and whose range is the integers
1 through <i>N</i>. By choosing uniformly at random among allowed inputs we obtain a
probability distribution over the possible outputs. We wish to approximate to constant
precision the L1 distance between the probability distributions determined by <i>A</i>
and <i>B</i>. Classically the number of necessary queries scales essentially linearly
with N. As shown in [<a href="#Bravyi_difference">117</a>], a quantum computer can
achieve this using \( O(\sqrt{N}) \) queries. Approximate uniformity and orthogonality
of probability distributions can also be decided on a quantum computer using
\( O(N^{1/3}) \) queries. The main tool is the quantum counting algorithm of
[<a href="#BHT98">16</a>]. A further improved quantum algorithm for
this task is obtained in [<a href="#M15b">265</a>].
<br /><br />
<b>Algorithm:</b> Finite Rings and Ideals <br />
<b>Speedup:</b> Superpolynomial <br />
<b>Description:</b> Suppose we are given black boxes implementing the addition and
multiplication operations on a finite ring <i>R</i>, not necessarily commutative, along
with a set of generators for <i>R</i>. With respect to addition, <i>R</i> forms a
finite Abelian group (<i>R</i>,+). As shown in [<a href="#Arvind">119</a>], on a quantum
computer one can find in poly(log |<i>R</i>|) time a set of additive generators
\( \{h_1,\ldots,h_m\} \subset R \) such that
\( (R,+) \simeq \langle h_1 \rangle \times \ldots \times \langle h_M \rangle\)
and <i>m</i> is polylogarithmic in |<i>R</i>|. This allows efficient computation of a
multiplication tensor for <i>R</i>. As shown in [<a href="#WJAB">118</a>], one can
similarly find an additive generating set for any ideal in <i>R</i>. This allows one
to find the intersection of two ideals, find their quotient, prove whether a given ring
element belongs to a given ideal, prove whether a given element is a unit and if so
find its inverse, find the additive and multiplicative identities, compute the order of
an ideal, solve linear equations over rings, decide whether an ideal is maximal, find
annihilators, and test the injectivity and surjectivity of ring homomorphisms. As shown
in [<a href="#Arvind2">120</a>], one can also use a quantum computer to efficiently
decide whether a given polynomial is identically zero on a given finite black box ring.
Known classical algorithms for these problems scale as poly(|<i>R</i>|).
<br /><br />
<b>Algorithm:</b> Counterfeit Coins<br />
<b>Speedup:</b> Polynomial<br />
<b>Description:</b> Suppose we are given <i>N</i> coins, <i>k</i> of which are
counterfeit. The real coins are all of equal weight, and the counterfeit coins are
all of some other equal weight. We have a pan balance and can compare the weight of
any pair of subsets of the coins. Classically, we need \( \Omega(k \log(N/k)) \)
weighings to identify all of the counterfeit coins. We can introduce an oracle such
that given a pair of subsets of the coins of equal cardinality, it outputs one bit
indicating balanced or unbalanced. Building on previous work by Terhal and Smolin
[<a href="#TS">137</a>], Iwama <i>et al.</i> have shown [<a href="#Iwama">136</a>]
that on a quantum computer, one can identify all of the counterfeit coins using
\( O(k^{1/4}) \) queries. The core techniques behind the quantum speedup are amplitude
amplification and the Bernstein-Vazirani algorithm.<br /><br />
<b>Algorithm:</b> Matrix Rank<br />
<b>Speedup:</b> Polynomial<br />
<b>Description:</b> Suppose we are given oracle access to the (integer) entries of an
\( n \times m \) matrix <i>A</i>. We wish to determine the rank of the matrix.
Classically this requires order <i>nm</i> queries. Building on
[<a href="#Reichardt2010">149</a>], Belovs [<a href="#Belovs_Rank">150</a>] gives a
quantum algorithm that can use fewer queries given a promise that the rank of the
matrix is at least <i>r</i>. Specifically, Belovs' algorithm uses
\( O(\sqrt{r(n-r+1)}LT) \) queries, where <i>L</i> is the root-mean-square
of the reciprocals of the <i>r</i> largest singular values of <i>A</i> and
<i>T</i> is a factor that depends on the sparsity of the matrix. For general <i>A</i>,
\( T = O(\sqrt{nm}) \). If <i>A</i> has at most <i>k</i> nonzero entries in any row or
column then \( T = O(k \log(n+m)) \). (To achieve the corresponding query complexity in
the <i>k</i>-sparse case, the oracle must take a column index as input, and provide a
list of the nonzero matrix elements from that column as output.) As an important special
case, one can use these quantum algorithms for the problem of determining whether a
square matrix is singular, which is sometimes referred to as the determinant problem.
For general <i>A</i> the quantum query complexity of the determinant problem is no
lower than the classical query complexity [<a href="#Dorn">151</a>]. However,
[<a href="#Dorn">151</a>] does not rule out a quantum speedup given a promise on <i>A</i>,
such as sparseness or lack of small singular values.<br /><br />
<b>Algorithm:</b> Matrix Multiplication over Semirings<br />
<b>Speedup:</b> Polynomial<br />
<b>Description:</b> A semiring is a set endowed with addition and
multiplication operations that obey all the axioms of a ring except
the existence additive inverses. Matrix multiplication over various
semirings has many applications to graph problems. Matrix
multiplication over semirings can be sped up by straightforward Grover
improvements upon schoolbook multiplication, yielding a quantum
algorithm that multiplies a pair of \(n \times n\) matrices in \(
\widetilde{O}(n^{5/2}) \) time. For some semirings this algorithm
outperforms the fastest known classical algorithms and for some
semirings it does not [<a href="#LeGall_Nishimura13">206</a>].
A case of particular interest is the Boolean semiring, in which OR
serves as addition and AND serves as multiplication. No quantum
algorithm is known for Boolean semiring matrix multiplication in the
general case that beats the best classical algorithm, which has
complexity \( n^{2.373} \). However, for sparse input our output,
quantum speedups are known. Specifically, let <i>A,B</i>
be <i>n</i> by <i>n</i> Boolean matrices. Let <i>C</i>=<i>AB</i>,
and let <i>l</i> be the number of entries of <i>C</i> that are equal
to 1 (<em>i.e.</em> TRUE). Improving upon
[<a href="#Buhrman_matrix">19</a>, <a href="#LeGall_Matrix">155</a>, <a href="#Williams_Williams">157</a>],
the best known upper bound on quantum query complexity is
\(\widetilde{O}(n \sqrt{l}) \), as shown in
[<a href="#JKM">161</a>]. If instead the input matrices are sparse, a
quantum speedup over the fastest known classical algorithm also has
been found in a certain regime [<a href="#LeGall_Nishimura13">206</a>].
For detailed comparison to classical algorithms, see
[<a href="#LeGall_Matrix">155</a>, <a href="#LeGall_Nishimura13">206</a>]. Quantum
algorithms have been found to perform matrix multiplication over the
(max,min) semiring in \(\widetilde{O}(n^{2.473})\) time and over the
distance dominance semiring in \(\widetilde{O}(n^{2.458})\) time
[<a href="#LeGall_Nishimura13">206</a>]. The fastest known classical
algorithm for both of these problems has \(\widetilde{O}(n^{2.687})\)
complexity.
<br /><br />
<b>Algorithm:</b> Subset finding<br />
<b>Speedup:</b> Polynomial<br />
<b>Description:</b> We are oracle access to a function \( f:D \to R \) where <i>D</i> and
<i>R</i> are finite sets. Some property \( P \subset (D \times R)^k \) is specified, for
example as an explicit list. Our task is to find a size-<i>k</i> subset of <i>D</i>
satisfying <i>P</i>, <i>i.e.</i> \( ((x_1,f(x_1)),\ldots,(x_k,f(x_k)))
\in P \), or reject if none exists. As usual, we wish to do this
with the minimum number of queries to <i>f</i>. Generalizing the
result of [<a href="#Ambainis_distinctness">7</a>], it was shown in
[<a href="#Childs_Eisenberg">162</a>] that this can be achieved using
\(O(|D|^{k/(k+1)}) \) quantum queries. As an noteworthy special case, this algorithm
solves the <i>k</i>-subset-sum problem of finding <i>k</i> numbers from a list with some
desired sum. A matching lower bound for the quantum query complexity is proven in
[<a href="#Belovs_Spalek">163</a>].<br /><br />
<b>Algorithm:</b> Search with Wildcards<br />
<b>Speedup:</b> Polynomial<br />
<b>Description:</b>
The search with wildcards problem is to identify a hidden <i>n</i>-bit
string <i>x</i> by making queries to an oracle <i>f</i>. Given \( S
\subseteq \{1,2,\ldots,n\} \) and \( y \in \{0,1\}^{|S|} \), <i>f</i>
returns one if the substring of <i>x</i> specified by <i>S</i> is equal
to <i>y</i>, and returns zero otherwise. Classically, this problem has
query complexity \(\Theta(n)\). As shown in
[<a href="#Ambainis_Montanaro12">167</a>], the quantum query
complexity of this problem is \( \Theta(\sqrt{n}) \). Interestingly,
this quadratic speedup is achieved not through amplitude
amplification or quantum walks, but rather through use of the
so-called Pretty Good Measurement. The paper
[<a href="#Ambainis_Montanaro12">167</a>] also gives a quantum speedup
for the related problem of combinatorial group testing. This result
and subsequent faster quantum algorithms for group testing are
discussed in the entry on Junta Testing and Group Testing.
<br /><br />
<b>Algorithm: </b> Network flows <br />
<b>Speedup:</b> Polynomial<br />
<b>Description:</b> A network is a directed graph whose edges are
labeled with numbers indicating their carrying capacities, and two of
whose vertices are designated as the source and the sink. A flow on a
network is an assignment of flows to the edges such that no flow
exceeds that edge's capacity, and for each vertex other than the
source and sink, the total inflow is equal to the total outflow. The
network flow problem is, given a network, to find the flow that maximizes
the total flow going from source to sink. For a network with <i>n</i>
vertices, <i>m</i> edges, and integer capacities of maximum
magnitude <i>U</i>, [<a href="#Ambainis_Spalek05">168</a>]
gives a quantum algorithm to find the maximal flow in time \( O(\min
\{n^{7/6} \sqrt{m} \ U^{1/3}, \sqrt{nU}m\} \times \log n) \). The
network flow problem is closely related to the problem of finding a
maximal matching of a graph, that is, a maximal-size subset of edges
that connects each vertex to at most one other vertex. The paper
[<a href="#Ambainis_Spalek05">168</a>] gives algorithms for finding
maximal matchings that run in time \( O(n \sqrt{m+n} \log n) \) if
the graph is bipartite, and \( O(n^2 ( \sqrt{m/n} + \log n) \log n) \)
in the general case. The core of these algorithms is Grover search.
The known upper bounds on classical complexity of the network flow and
matching problems are complicated to state because different classical
algorithms are preferable in different parameter regimes. However, in
certain regimes, the above quantum algorithms beat all known classical
algorithms. (See [<a href="#Ambainis_Spalek05">168</a>] for