![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bgaa.png\")
<\/p>\n\n\n\nLet\u2019s start with 1-bit functions f : {0, 1} 7\u2192 {0, 1}. There are totally<\/p>\n\n\n\n
four possible functions, and evaluated on inputs 0 and 1 can give answers<\/p>\n\n\n\n
0 or 1. To actually determine which of these our black box is we need to<\/p>\n\n\n\n
query it with both inputs, whether classically or otherwise, and we obtain no<\/p>\n\n\n\n
<\/p>\n\n\n\n
Quantum Algorithms 145<\/p>\n\n\n\n
advantage using quantum computing. However, as David Deutsch [24] showed<\/p>\n\n\n\n
in 1985, it is possible to distinguish the function on the basis of some property,<\/p>\n\n\n\n
more e\ufb03ciently in the quantum case. The particular classi\ufb01cation Deutsch\u2019s<\/p>\n\n\n\n
algorithm considers is the following: they are either constant (C), i.e., f(0) =<\/p>\n\n\n\n
f(1), or balanced (B), i.e., the outputs contain an equal number of 0\u2019s and 1\u2019s<\/p>\n\n\n\n
(f(0) = f (1)).<\/p>\n\n\n\n
Example 8.1.1. For n > 1, functions need not fall into the classes C or B<\/p>\n\n\n\n
alone. For example, consider f<\/p>\n\n\n\n
1<\/p>\n\n\n\n
and f<\/p>\n\n\n\n
2<\/p>\n\n\n\n
de\ufb01ned by:<\/p>\n\n\n\n
f<\/p>\n\n\n\n
1<\/p>\n\n\n\n
:<\/p>\n\n\n\n
f(00) = 0<\/p>\n\n\n\n
f(01) = 1<\/p>\n\n\n\n
f(10) = 0<\/p>\n\n\n\n
f(11) = 1<\/p>\n\n\n\n
, f<\/p>\n\n\n\n
2<\/p>\n\n\n\n
:<\/p>\n\n\n\n
f(00) = 0<\/p>\n\n\n\n
f(01) = 1<\/p>\n\n\n\n
f(10) = 0<\/p>\n\n\n\n
f(11) = 0<\/p>\n\n\n\n
Here, f<\/p>\n\n\n\n
1<\/p>\n\n\n\n
is balanced while f<\/p>\n\n\n\n
2<\/p>\n\n\n\n
is neither constant nor balanced.<\/p>\n\n\n\n
Deutsch\u2019s algorithm<\/p>\n\n\n\n
1<\/p>\n\n\n\n
is formulated for the following problem. Although it<\/p>\n\n\n\n
might seem contrived, it is the \ufb01rst algorithm to demonstrate the principles<\/p>\n\n\n\n
of the new paradigm.<\/p>\n\n\n\n
The problem: given a black-box (oracle) that implements a 1-bit function<\/p>\n\n\n\n
f(x), how will you determine whether the function belongs to class C or to<\/p>\n\n\n\n
class B with a minimum number of runs of the black box (or equivalently,<\/p>\n\n\n\n
queries to the oracle)?<\/p>\n\n\n\n
Classically, it is clear that we have to run the machine twice, with inputs<\/p>\n\n\n\n
0 and 1.<\/p>\n\n\n\n
The Deutsch algorithm shows how this problem can be solved in just<\/p>\n\n\n\n
one run of the black box. The circuit is shown in Figure 8.3, that we will work<\/p>\n\n\n\n
through step by step.<\/p>\n\n\n\n
|0i<\/p>\n\n\n\n
H<\/p>\n\n\n\n
|+i<\/p>\n\n\n\n
U<\/p>\n\n\n\n
f<\/p>\n\n\n\n
H<\/p>\n\n\n\n
(<\/p>\n\n\n\n
0 7\u2192 C<\/p>\n\n\n\n
1 7\u2192 B<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
H<\/p>\n\n\n\n
|\u2212i<\/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
FIGURE 8.3: The Deutsch algorithm.<\/p>\n\n\n\n
Step 1: Supply as input the uniform superposition<\/p>\n\n\n\n
H|0i =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(|0i + |1i). (8.1)<\/p>\n\n\n\n
1<\/p>\n\n\n\n
The presentation given here is not the original one in [24] but an improved version<\/p>\n\n\n\n
<\/p>\n\n\n\n
<\/p>\n\n\n\n
146 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n
Step 2: On the bottom register, supply the state H|1i =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(|0i\u2212|1i). This is<\/p>\n\n\n\n
the crucial feature that introduces useful interference in the result. The reason<\/p>\n\n\n\n
for this will be clear when we evaluate the output of the black box. So the<\/p>\n\n\n\n
input state is<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
0<\/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
(|0i + |1i) \u2297<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(|0i \u2212 |1i)<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
[|00i \u2212 |01i + |10i \u2212 |11i] (8.2)<\/p>\n\n\n\n
Step 3: Run the function evaluator. The output is<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i = 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<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
h<\/p>\n\n\n\n
|0i|f(0)i \u2212 |0i|f (0)i + |1i|f(1)i \u2212 |1i|f(1)i<\/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
|0i<\/p>\n\n\n\n
h<\/p>\n\n\n\n
|f(0)i \u2212 |f (0)i<\/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
|1i<\/p>\n\n\n\n
h<\/p>\n\n\n\n
|f(1)i \u2212 |f (1)i<\/p>\n\n\n\n
i<\/p>\n\n\n\n
. (8.3)<\/p>\n\n\n\n
Step 4: Measure the top register in the X-basis. That is, change basis by<\/p>\n\n\n\n
applying the H gate on the \ufb01rst qubit and then measure it. Just before the<\/p>\n\n\n\n
measurement, the output state on both wires is<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
2<\/p>\n\n\n\n
i = H<\/p>\n\n\n\n
1<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
1<\/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
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
|0i<\/p>\n\n\n\n
h<\/p>\n\n\n\n
|f(0)i \u2212 |f (0)i + |f(1)i \u2212 |f(1)i<\/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
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
h<\/p>\n\n\n\n
|f(0)i \u2212 |f (0)i \u2212 |f(1)i + |f(1)i<\/p>\n\n\n\n
i<\/p>\n\n\n\n
(8.4)<\/p>\n\n\n\n
If the function is C, then f(0) = f(1) and the amplitude for |0i is 1 while<\/p>\n\n\n\n
that for |1i is 0. On the other hand, when f is B then f(0) = f(1) and<\/p>\n\n\n\n
the amplitude for |1i is 1 while that for |0iis 0. Thus a measurement of<\/p>\n\n\n\n
the output gives us the answer to the query with certainty. We have run the<\/p>\n\n\n\n
function evaluator only once. The quantum advantage has given us a double<\/p>\n\n\n\n
speedup in this case.<\/p>\n\n\n\n
The reason why this works is that Step 2 implements the so called \u201cphase<\/p>\n\n\n\n
kickback\u201d trick. If the state |\u2212i on the lower register fed into the black box,<\/p>\n\n\n\n
then the output acquires a phase that depends on f(x). This phase can e\ufb00ec-<\/p>\n\n\n\n
tively be regarded as attached to the state of the upper register.<\/p>\n\n\n\n
U<\/p>\n\n\n\n
f<\/p>\n\n\n\n
\ue014<\/p>\n\n\n\n
|xi \u2297<\/p>\n\n\n\n
(|0i \u2212 |1i)<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue015<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
|xi<\/p>\n\n\n\n
h<\/p>\n\n\n\n
|f(x)i \u2212 |f (x)i<\/p>\n\n\n\n
i<\/p>\n\n\n\n
=<\/p>\n\n\n\n
(<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
|xi(|0i + |1i) if f (x) = 0,<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
|xi(|1i \u2212 |0i) if f (x) = 1<\/p>\n\n\n\n
= (\u22121)<\/p>\n\n\n\n
f(x)<\/p>\n\n\n\n
|xi<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
[|0i \u2212 |1i] . (8.5)<\/p>\n\n\n\n
![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bgac.png\")
<\/p>\n\n\n\n
Quantum Algorithms 147<\/p>\n\n\n\n
The output is separable, with the lower register unchanged in state |\u2212i, while<\/p>\n\n\n\n
the upper register is e\ufb00ectively the input with an f(x)-dependent phase.<\/p>\n\n\n\n
With this e\ufb00ect, we can re-analyze the algorithm with the uniform super-<\/p>\n\n\n\n
position |xi =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(|0i + |1i) in the input register:<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(|0i + |1i)<\/p>\n\n\n\n
U<\/p>\n\n\n\n
f<\/p>\n\n\n\n
\u2212\u2212\u2192<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
h<\/p>\n\n\n\n
(\u22121)<\/p>\n\n\n\n
f(0)<\/p>\n\n\n\n
|0i + (\u22121)<\/p>\n\n\n\n
f(1)<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
i<\/p>\n\n\n\n
(8.6)<\/p>\n\n\n\n
H<\/p>\n\n\n\n
\u2212\u2192<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
h\ue010<\/p>\n\n\n\n
(\u22121)<\/p>\n\n\n\n
f(0)<\/p>\n\n\n\n
+ (\u22121)<\/p>\n\n\n\n
f(1)<\/p>\n\n\n\n
\ue011<\/p>\n\n\n\n
|0i<\/p>\n\n\n\n
+<\/p>\n\n\n\n
\ue010<\/p>\n\n\n\n
(\u22121)<\/p>\n\n\n\n
f(0)<\/p>\n\n\n\n
\u2212 (\u22121)<\/p>\n\n\n\n
f(1)<\/p>\n\n\n\n
\ue011<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
i<\/p>\n\n\n\n
(8.7)<\/p>\n\n\n\n
where it\u2019s obvious that a measurement gives |0i if f(x) is C and |1i if f(x)<\/p>\n\n\n\n
is B.<\/p>\n\n\n\n
8.1.1 Deutsch\u2013Josza algorithm<\/p>\n\n\n\n
The Deutsch algorithm was extended to n-bit functions by Josza and others<\/p>\n\n\n\n
in 1992 [26].<\/p>\n\n\n\n
The problem: Given an n \u2192 1 function f : {0, 1}<\/p>\n\n\n\n
n<\/p>\n\n\n\n
7\u2192 {0, 1} that is<\/p>\n\n\n\n
guaranteed to be either constant or balanced, \ufb01nd out which it is in a minimum<\/p>\n\n\n\n
number of runs.<\/p>\n\n\n\n
Classically, we would proceed by querying the oracle with each n-bit<\/p>\n\n\n\n
number. If we \ufb01nd an answer that is not equal to the previous one then we<\/p>\n\n\n\n
have a balanced function. In worst-case scenario, we might \ufb01nd the same f(x)<\/p>\n\n\n\n
until the half the possible inputs, i.e., after querying the function 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\/2 times.<\/p>\n\n\n\n
The answer to the next query would solve the problem. Thus we need to run<\/p>\n\n\n\n
the oracle at worst 2<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
+ 1 times: exponential in the number of bits of input.<\/p>\n\n\n\n
The quantum algorithm achieves the distinction in just one run! This<\/p>\n\n\n\n
is a dramatic speedup indeed. The circuit (Figure 8.4) is an n-qubit extension<\/p>\n\n\n\n
of that for the Deutsch problem:<\/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
|1i<\/p>\n\n\n\n
H<\/p>\n\n\n\n
FIGURE 8.4: The circuit for the Deutsch\u2013Josza algorithm.<\/p>\n\n\n\n
The input to the circuit is the uniform n-qubit superposition<\/p>\n\n\n\n
H<\/p>\n\n\n\n
\u2297n<\/p>\n\n\n\n
|0i<\/p>\n\n\n\n
n<\/p>\n\n\n\n
=<\/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
x=0<\/p>\n\n\n\n
|xi. (8.8)<\/p>\n","protected":false},"excerpt":{"rendered":"
Let\u2019s start with 1-bit functions f : {0, 1} 7\u2192 {0, 1}. There are totally four possible functions, and evaluated on inputs 0 and 1 can give answers 0 or 1. To actually determine which of these our black box is we need to query it with both inputs, whether classically or otherwise, and we […]<\/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-4084","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\/4084","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=4084"}],"version-history":[{"count":2,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4084\/revisions"}],"predecessor-version":[{"id":4584,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4084\/revisions\/4584"}],"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=4084"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4084"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4084"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}