Another famous algorithm that made a splash in the world of quantum<\/p>\n\n\n\n
computing was invented by L. K. Grover in 1997 [40]. This algorithm is in<\/p>\n\n\n\n
a di\ufb00erent class from the ones we have studied so far, which may all be said<\/p>\n\n\n\n
to be QFT-based. Grover\u2019s algorithm introduced a new technique: amplitude<\/p>\n\n\n\n
ampli\ufb01cation. Even though it did not demonstrate an exponential speed-up<\/p>\n\n\n\n
over the classical case, it was still dramatic enough to get noticed.<\/p>\n\n\n\n
The problem Grover attacked was that of search for an element in an<\/p>\n\n\n\n
unstructured database. The problem is like doing a reverse search in a phone<\/p>\n\n\n\n
directory: you have a number and need to know the person it belongs to. Thus<\/p>\n\n\n\n
there is no regular short-cut to the search, you have to go through each entry<\/p>\n\n\n\n
in the book and check if it matches the number you have.<\/p>\n\n\n\n
The problem can be phrased in the language of oracles, if we assume that<\/p>\n\n\n\n
the criterion for the search is built into a function evaluator: a function that<\/p>\n\n\n\n
tells you whether the input number matches the search criterion or not. So<\/p>\n\n\n\n
we imagine that the numbers x are indices to the entries in the database, and<\/p>\n\n\n\n
one index, let\u2019s say k, belongs to the entry being searched for. Then<\/p>\n\n\n\n
f<\/p>\n\n\n\n
k<\/p>\n\n\n\n
(x) =<\/p>\n\n\n\n
(<\/p>\n\n\n\n
1 if x = k<\/p>\n\n\n\n
0 otherwise.<\/p>\n\n\n\n
(8.70)<\/p>\n\n\n\n
Here, if x is an n-bit number, then the size of the database is 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
= N . As<\/p>\n","protected":false},"excerpt":{"rendered":"
Another famous algorithm that made a splash in the world of quantum computing was invented by L. K. Grover in 1997 [40]. This algorithm is in a di\ufb00erent class from the ones we have studied so far, which may all be said to be QFT-based. Grover\u2019s algorithm introduced a new technique: amplitude ampli\ufb01cation. Even though […]<\/p>\n","protected":false},"author":1,"featured_media":4042,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[497],"tags":[],"class_list":["post-4097","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-quantum-algorithms"],"jetpack_featured_media_url":"https:\/\/workhouse.sweetdishy.com\/wp-content\/uploads\/2024\/09\/algorithm-1.png","_links":{"self":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4097","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/comments?post=4097"}],"version-history":[{"count":1,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4097\/revisions"}],"predecessor-version":[{"id":4098,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4097\/revisions\/4098"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media\/4042"}],"wp:attachment":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media?parent=4097"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4097"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4097"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}