{"id":4086,"date":"2024-09-21T13:17:26","date_gmt":"2024-09-21T13:17:26","guid":{"rendered":"https:\/\/workhouse.sweetdishy.com\/?p=4086"},"modified":"2024-09-21T13:17:26","modified_gmt":"2024-09-21T13:17:26","slug":"the-bernstein-vazirani-algorithm","status":"publish","type":"post","link":"https:\/\/workhouse.sweetdishy.com\/index.php\/2024\/09\/21\/the-bernstein-vazirani-algorithm\/","title":{"rendered":"The Bernstein\u2013Vazirani Algorithm"},"content":{"rendered":"\n

We\u2019ll now look at algorithms that show more substantial speedups com-<\/p>\n\n\n\n

pared to classical ones. One such algorithm was invented by Umesh Vazirani<\/p>\n\n\n\n

and his student Ethan Bernstein in 1993 [11]. This algorithm identi\ufb01es a linear<\/p>\n\n\n\n

Boolean function in one query of the oracle.<\/p>\n\n\n\n

The problem: given a function evaluator for<\/p>\n\n\n\n

f : {0, 1}<\/p>\n\n\n\n

n<\/p>\n\n\n\n

7\u2192 {0, 1} where f (x) = a \u00b7 x, a \u2208 [0, 2<\/p>\n\n\n\n

n<\/p>\n\n\n\n

], (8.11)<\/p>\n\n\n\n

and the dot is a bitwise product with modulo 2 addition:<\/p>\n\n\n\n

a \u00b7 x \u2261 a<\/p>\n\n\n\n

0<\/p>\n\n\n\n

x<\/p>\n\n\n\n

0<\/p>\n\n\n\n

\u2295 a<\/p>\n\n\n\n

1<\/p>\n\n\n\n

x<\/p>\n\n\n\n

1<\/p>\n\n\n\n

\u2295 \u00b7\u00b7\u00b7 \u2295 a<\/p>\n\n\n\n

n\u22121<\/p>\n\n\n\n

x<\/p>\n\n\n\n

n\u22121<\/p>\n\n\n\n

, (8.12)<\/p>\n\n\n\n

determine the function, or in other words \ufb01nd a.<\/p>\n\n\n\n

Example 8.2.1. An example of such a function for n = 2 and a = 11, which<\/p>\n\n\n\n

evaluates to<\/p>\n\n\n\n

f(00) = 0<\/p>\n\n\n\n

\"\"<\/p>\n\n\n\n

Quantum Algorithms 149<\/p>\n\n\n\n

f(01) = 0.1 \u2295 1.1 = 1<\/p>\n\n\n\n

f(10) = 1.1 \u2295 0.1 = 1<\/p>\n\n\n\n

f(11) = 1.1 \u2295 1.1 = 0<\/p>\n\n\n\n

Classically, we can determine the k<\/p>\n\n\n\n

th<\/p>\n\n\n\n

bit of a if we feed the oracle the<\/p>\n\n\n\n

input x = 2<\/p>\n\n\n\n

k<\/p>\n\n\n\n

, that has only the k<\/p>\n\n\n\n

th<\/p>\n\n\n\n

bit as 1 and all the rest as 0. This becomes<\/p>\n\n\n\n

obvious when you look at the binary expansion of a:<\/p>\n\n\n\n

a = a<\/p>\n\n\n\n

0<\/p>\n\n\n\n

+ a<\/p>\n\n\n\n

1<\/p>\n\n\n\n

2<\/p>\n\n\n\n

1<\/p>\n\n\n\n

+ \u00b7\u00b7\u00b7 + a<\/p>\n\n\n\n

k<\/p>\n\n\n\n

2<\/p>\n\n\n\n

k<\/p>\n\n\n\n

+ . . . =\u21d2 a<\/p>\n\n\n\n

k<\/p>\n\n\n\n

= a \u00b7 2<\/p>\n\n\n\n

k<\/p>\n\n\n\n

. (8.13)<\/p>\n\n\n\n

This calls the function n times.<\/p>\n\n\n\n

The quantum algorithm, which uses the same circuit as for the<\/p>\n\n\n\n

Deutsch\u2013Josza algorithm, succeeds with one call!<\/p>\n\n\n\n

Let\u2019s analyze the output of the circuit of Figure 8.4 for this form of the<\/p>\n\n\n\n

function:<\/p>\n\n\n\n

X<\/p>\n\n\n\n

x<\/p>\n\n\n\n

X<\/p>\n\n\n\n

y<\/p>\n\n\n\n

1<\/p>\n\n\n\n

2<\/p>\n\n\n\n

n<\/p>\n\n\n\n

(\u22121)<\/p>\n\n\n\n

f(x)+x\u00b7y<\/p>\n\n\n\n

|yi \u2297 |\u2212i =<\/p>\n\n\n\n

1<\/p>\n\n\n\n

2<\/p>\n\n\n\n

n<\/p>\n\n\n\n

X<\/p>\n\n\n\n

y<\/p>\n\n\n\n

“<\/p>\n\n\n\n

X<\/p>\n\n\n\n

x<\/p>\n\n\n\n

(\u22121)<\/p>\n\n\n\n

a\u00b7x+y\u00b7x<\/p>\n\n\n\n

#<\/p>\n\n\n\n

|yi \u2297 |\u2212i<\/p>\n\n\n\n

. (8.14)<\/p>\n\n\n\n

The amplitude for |yi is<\/p>\n\n\n\n

1<\/p>\n\n\n\n

2<\/p>\n\n\n\n

n<\/p>\n\n\n\n

P<\/p>\n\n\n\n

x<\/p>\n\n\n\n

(\u22121)<\/p>\n\n\n\n

a\u00b7x+y\u00b7x<\/p>\n\n\n\n

=<\/p>\n\n\n\n

1<\/p>\n\n\n\n

2<\/p>\n\n\n\n

n<\/p>\n\n\n\n

P<\/p>\n\n\n\n

x<\/p>\n\n\n\n

(\u22121)<\/p>\n\n\n\n

(a+y)\u00b7x<\/p>\n\n\n\n

= 1 if<\/p>\n\n\n\n

y = a! It\u2019s easy to see why it is zero for all other values of y. Thus with<\/p>\n\n\n\n

certainty, the output of the circuit gives us a.<\/p>\n\n\n\n

A more explicit way of seeing why this works is by analyzing the circuit for<\/p>\n\n\n\n

U<\/p>\n\n\n\n

f<\/p>\n\n\n\n

. This analysis is lucidly given in Mermin [48]. The black box for a\u00b7x \ufb02ips the<\/p>\n\n\n\n

bit in the lower register whenever a bit of the input x and the corresponding<\/p>\n\n\n\n

bit of a are both 1. For instance, suppose we had a = 11010 with n = 5. Then<\/p>\n\n\n\n

it can easily be seen that a \u00b7 x is implemented by the circuit of Figure 8.5.<\/p>\n\n\n\n

a = 11010<\/p>\n\n\n\n

x<\/p>\n\n\n\n

4<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

3<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

2<\/p>\n\n\n\n

x<\/p>\n\n\n\n

1<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

0<\/p>\n\n\n\n

|0i |a \u00b7 xi<\/p>\n\n\n\n

FIGURE 8.5: A circuit that executes U<\/p>\n\n\n\n

f<\/p>\n\n\n\n

for f = 11010 \u00b7 x.<\/p>\n\n\n\n

Coming to the circuit for solving the Bernstein\u2013Vazirani problem, it has<\/p>\n\n\n\n

an H gate before each qubit enters the function evaluator and after. This is<\/p>\n\n\n\n

true even of the lower register, which can be thought of as initialized to |1i.<\/p>\n\n\n\n

Note that an H gate before and after a CNOT interchanges the roles of the<\/p>\n\n\n\n

control and target qubits (see Figure 7.8).<\/p>\n\n\n\n

\"\"<\/p>\n\n\n\n

150 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n

|0i |1i<\/p>\n\n\n\n

|0i |1i<\/p>\n\n\n\n

|0i |0i<\/p>\n\n\n\n

|0i |1i<\/p>\n\n\n\n

|0i |0i<\/p>\n\n\n\n

|1i<\/p>\n\n\n\n

\u2022 \u2022 \u2022<\/p>\n\n\n\n

FIGURE 8.6: Analysis of circuit for the Bernstein\u2013Vazirani algorithm for a =<\/p>\n\n\n\n

11010.<\/p>\n\n\n\n

The solution is therefore the circuit of Figure 8.6, whose output directly<\/p>\n\n\n\n

reads out the bits of a.<\/p>\n\n\n\n

The algorithm thus gives an n-fold speedup over the classical case<\/p>\n","protected":false},"excerpt":{"rendered":"

We\u2019ll now look at algorithms that show more substantial speedups com- pared to classical ones. One such algorithm was invented by Umesh Vazirani and his student Ethan Bernstein in 1993 [11]. This algorithm identi\ufb01es a linear Boolean function in one query of the oracle. The problem: given a function evaluator for f : {0, 1} […]<\/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-4086","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\/4086","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=4086"}],"version-history":[{"count":1,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4086\/revisions"}],"predecessor-version":[{"id":4087,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4086\/revisions\/4087"}],"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=4086"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4086"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4086"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}