![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bgb0.png\")
<\/p>\n\n\n\nEven though the Bernstein\u2013Vazirani algorithm o\ufb00ers such a great speedup,<\/p>\n\n\n\n
the classical solution is still not exponential. Daniel Simon came up with an<\/p>\n\n\n\n
algorithm [65] in 1994 that is the \ufb01rst to demonstrate a dramatic exponential<\/p>\n\n\n\n
speedup over a hard classical problem, but the solution is probabilistic. This<\/p>\n\n\n\n
feature is characteristic of many quantum algorithms. Simon\u2019s problem also<\/p>\n\n\n\n
illustrates a class of problems that basically use Fourier transforms, in the<\/p>\n\n\n\n
form of the amplitudes of the output states that \u201cinterfere\u201d to give a large<\/p>\n\n\n\n
probability for the expected solution.<\/p>\n\n\n\n
The problem: Given a black box implementing a function<\/p>\n\n\n\n
f : {0, 1}<\/p>\n\n\n\n
n<\/p>\n\n\n\n
7\u2192 {0, 1}<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
such thatf(x \u2295 a) = f(x), a \u2208 [0, 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\u2212 1], (8.15)<\/p>\n\n\n\n
determine a with the minimum number of queries to the box.<\/p>\n\n\n\n
Example 8.3.1. The functions considered in Simon\u2019s algorithm can be thought<\/p>\n\n\n\n
of as \u201cperiodic\u201d under bitwise addition. For example, let\u2019s look at the 3-bit<\/p>\n\n\n\n
function<\/p>\n\n\n\n
x 000 001 010 011 100 101 110 111<\/p>\n\n\n\n
f(x) 3 2 2 3 1 4 4 1<\/p>\n\n\n\n
The \ufb01rst repetition is of the value f(1) = f(2). The \u201cperiod\u201d is therefore<\/p>\n\n\n\n
a = 001 \u2295 010 = 011 = 3. You can verify that all the other repetitions also<\/p>\n\n\n\n
satisfy the same condition.<\/p>\n\n\n\n
<\/p>\n\n\n\n
Quantum Algorithms 151<\/p>\n\n\n\n
The classical solution to this problem is hard, i.e., the number of runs<\/p>\n\n\n\n
of the function grows exponentially as the size of the input. We would query<\/p>\n\n\n\n
the oracle with successive values of n-bit numbers x until we found a repeated<\/p>\n\n\n\n
value for the output: f (x<\/p>\n\n\n\n
i<\/p>\n\n\n\n
) = f (x<\/p>\n\n\n\n
j<\/p>\n\n\n\n
). Then we could calculate a = x<\/p>\n\n\n\n
i<\/p>\n\n\n\n
\u2295 x<\/p>\n\n\n\n
j<\/p>\n\n\n\n
.<\/p>\n\n\n\n
However, a could be any one of 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
possible numbers. By the m<\/p>\n\n\n\n
th<\/p>\n\n\n\n
run,<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
m(m\u2212<\/p>\n\n\n\n
1) pairs have been compared and eliminated as possible a\u2019s. For reasonable<\/p>\n\n\n\n
chance of success, we need<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
m(m\u22121) \u2265 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
=\u21d2 a lower bound on the number<\/p>\n\n\n\n
of trials m = \u03a9(2<\/p>\n\n\n\n
n\/2<\/p>\n\n\n\n
), which is exponential in the number of bits.<\/p>\n\n\n\n
The quantum circuit (Figure 8.7) that solves this problem is essentially<\/p>\n\n\n\n
the same as the Deutsch\u2013Josza circuit except that the lower register is also<\/p>\n\n\n\n
expanded to n qubit, and initialized to |0i<\/p>\n\n\n\n
n<\/p>\n\n\n\n
(we dispense with the phase<\/p>\n\n\n\n
kickback).<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i |\u03c8<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i |\u03c8<\/p>\n\n\n\n
2<\/p>\n\n\n\n
i<\/p>\n\n\n\n
|0i<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\/<\/p>\n\n\n\n
n<\/p>\n\n\n\n
H<\/p>\n\n\n\n
\u2297n<\/p>\n\n\n\n
\/<\/p>\n\n\n\n
n<\/p>\n\n\n\n
U<\/p>\n\n\n\n
f<\/p>\n\n\n\n
H<\/p>\n\n\n\n
\u2297n<\/p>\n\n\n\n
\/<\/p>\n\n\n\n
n<\/p>\n\n\n\n
|0i<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\/<\/p>\n\n\n\n
n<\/p>\n\n\n\n
f(x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
)<\/p>\n\n\n\n
FIGURE 8.7: The circuit for the Simon algorithm.<\/p>\n\n\n\n
The input to the oracle gives us<\/p>\n\n\n\n
U<\/p>\n\n\n\n
f<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i \u2297 |0i = U<\/p>\n\n\n\n
f<\/p>\n\n\n\n
“<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
x=0<\/p>\n\n\n\n
|xi \u2297 |0i<\/p>\n\n\n\n
#<\/p>\n\n\n\n
=<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
x=0<\/p>\n\n\n\n
|xi \u2297 |f(x)i. (8.16)<\/p>\n\n\n\n
In order to analyze the solution, let us use the reverse of the principle of<\/p>\n\n\n\n
delayed measurement, and assume we measure the lower register after the<\/p>\n\n\n\n
action of U<\/p>\n\n\n\n
f<\/p>\n\n\n\n
. Let\u2019s denote the outcome by f (x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
), which is generated from<\/p>\n\n\n\n
two possible inputs x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
or x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
\u2295 a. The top register therefore collapses to a<\/p>\n\n\n\n
superposition of these two states alone:<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(|x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i + |x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
\u2295 ai) . (8.17)<\/p>\n\n\n\n
If we now apply H to each qubit in the upper register, we get<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
3<\/p>\n\n\n\n
i =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
y=0<\/p>\n\n\n\n
h<\/p>\n\n\n\n
(\u22121)<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
\u00b7y<\/p>\n\n\n\n
+ (\u22121)<\/p>\n\n\n\n
(x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
\u2295a)\u00b7y<\/p>\n\n\n\n
i<\/p>\n\n\n\n
|yi. (8.18)<\/p>\n\n\n\n
Now a \u00b7 y is either 0 or 1. If a \u00b7 y = 1, then the amplitude for |yi is zero and<\/p>\n\n\n\n
all those states do not occur in the output. Thus the only states that can be<\/p>\n\n\n\n
measured in the output are those for which the condition a \u00b7y = 0 is satis\ufb01ed.<\/p>\n\n\n\n
This is a binary algebraic equation with n unknowns (the bits of a). We can<\/p>\n\n\n\n
\ufb01nd a if we can obtain n independent equations, corresponding to n di\ufb00erent<\/p>\n\n\n\n
values of y. If we repeat the experiment until we have collected n distinct,<\/p>\n\n\n\n
<\/p>\n\n\n\n
152 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n
non-zero y\u2019s then we can solve for the bits of a. It is not guaranteed that we<\/p>\n\n\n\n
will get a distinct y on each run, so we may most probably have to run the<\/p>\n\n\n\n
oracle more than n times.<\/p>\n\n\n\n
To determine the complexity of this problem, we will need to estimate<\/p>\n\n\n\n
how the number of runs of the oracle scales with n. It can be shown (see Box<\/p>\n\n\n\n
8.3) that the number of times the oracle has to be queried is n + m where m<\/p>\n\n\n\n
doesn\u2019t depend on n. This algorithm is thus a sub-exponential solution to a<\/p>\n\n\n\n
classically hard problem.<\/p>\n\n\n\n
Box 8.1: Complexity Analysis for Simon\u2019s Algorithm<\/p>\n\n\n\n
As in many quantum algorithms, the analysis of why the algorithm is com-<\/p>\n\n\n\n
putationally more e\ufb03cient than the classical case involves a detailed math-<\/p>\n\n\n\n
ematical examination of the solution. In the case of Simon\u2019s algorithm, the<\/p>\n\n\n\n
output after measurement is an n-bit string y such that<\/p>\n\n\n\n
a \u00b7 y = a<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
y<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
\u2295 a<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
y<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
\u2295 \u00b7\u00b7\u00b7 \u2295 a<\/p>\n\n\n\n
1<\/p>\n\n\n\n
y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u2295 a<\/p>\n\n\n\n
0<\/p>\n\n\n\n
y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
= 0.<\/p>\n\n\n\n
We need to collect at least n \u22121 such distinct bit-strings in order to determine<\/p>\n\n\n\n
the coe\ufb03cients a. So we need to query the oracle at least n \u22121 times and need<\/p>\n\n\n\n
to \ufb01nd a lower bound on the probability of success.<\/p>\n\n\n\n
Suppose we ran the algorithm k times and got linearly independent y\u2019s.<\/p>\n\n\n\n
What\u2019s the probability that the next run gives a di\ufb00erent y? The minimum<\/p>\n\n\n\n
probability for this occurring is<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\u2212 2<\/p>\n\n\n\n
k<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
= 1 \u2212 2<\/p>\n\n\n\n
k\u2212n<\/p>\n\n\n\n
.<\/p>\n\n\n\n
So the probability of getting n \u2212 1 independent y\u2019s is just<\/p>\n\n\n\n
P =<\/p>\n\n\n\n
\ue012<\/p>\n\n\n\n
1 \u2212<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\ue013\ue012<\/p>\n\n\n\n
1 \u2212<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
\ue013<\/p>\n\n\n\n
. . .<\/p>\n\n\n\n
\ue012<\/p>\n\n\n\n
1 \u2212<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue013<\/p>\n\n\n\n
.<\/p>\n\n\n\n
Now notice that (1 \u2212 s)(1 \u2212 t) = 1 \u2212 (s + t) + st \u2265 1 \u2212 (s + t). So we have<\/p>\n\n\n\n
P \u2265<\/p>\n\n\n\n
1 \u2212<\/p>\n\n\n\n
n<\/p>\n\n\n\n
X<\/p>\n\n\n\n
i=1<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
i<\/p>\n\n\n\n
!<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u2265<\/p>\n\n\n\n
\ue012<\/p>\n\n\n\n
1 \u2212<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue013<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
4<\/p>\n\n\n\n
.<\/p>\n\n\n\n
This means that there is a \ufb01nite minimum probability with which we will<\/p>\n\n\n\n
succeed in n runs. To ensure success, we\u2019ll have to run the algorithm a few<\/p>\n\n\n\n
more times, independent of n, so that the number of runs is still O(n).<\/p>\n\n\n\n
The trick that makes the kind of algorithms considered so far work is that<\/p>\n\n\n\n
the output before measuring in the X basis has f(x)-dependent phases.<\/p>\n","protected":false},"excerpt":{"rendered":"
Even though the Bernstein\u2013Vazirani algorithm o\ufb00ers such a great speedup, the classical solution is still not exponential. Daniel Simon came up with an algorithm [65] in 1994 that is the \ufb01rst to demonstrate a dramatic exponential speedup over a hard classical problem, but the solution is probabilistic. This feature is characteristic of many quantum algorithms. […]<\/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-4088","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\/4088","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=4088"}],"version-history":[{"count":2,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4088\/revisions"}],"predecessor-version":[{"id":4585,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4088\/revisions\/4585"}],"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=4088"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4088"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4088"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}