{"id":4072,"date":"2024-09-21T12:45:18","date_gmt":"2024-09-21T12:45:18","guid":{"rendered":"https:\/\/workhouse.sweetdishy.com\/?p=4072"},"modified":"2024-09-21T12:45:18","modified_gmt":"2024-09-21T12:45:18","slug":"quantum-function-evaluation","status":"publish","type":"post","link":"https:\/\/workhouse.sweetdishy.com\/index.php\/2024\/09\/21\/quantum-function-evaluation\/","title":{"rendered":"Quantum Function Evaluation"},"content":{"rendered":"\n

We\u2019ve taken the circuit analogy for quantum computation up to gates. Can<\/p>\n\n\n\n

we go further? Can we identify a set of universal gates, as we did for classical<\/p>\n\n\n\n

computation?<\/p>\n\n\n\n

Since a computation is essentially the evaluation of a function of the inputs,<\/p>\n\n\n\n

let\u2019s \ufb01rst \ufb01x what we mean by a quantum function evaluation. Consider a<\/p>\n\n\n\n

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

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

7\u2192 {0, 1}<\/p>\n\n\n\n

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

that takes an n-bit input x and produces an<\/p>\n\n\n\n

m-bit output f(x). A reversible implementation of this function would have<\/p>\n\n\n\n

an n + m-bit input and the same number of bits in the output. We will use<\/p>\n\n\n\n

this to de\ufb01ne the unitary operator implementing f (x).<\/p>\n\n\n\n

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

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

De\ufb01nition 7.1. A quantum function evaluator is a unitary operator U<\/p>\n\n\n\n

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

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

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

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

7\u2192 {0, 1}<\/p>\n\n\n\n

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

, such that<\/p>\n\n\n\n

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

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

|xi|yi = |xi|f(x) \u2295 yi. (7.23)<\/p>\n\n\n\n

This is essentially an f-controlled XOR gate (which is like an f-controlled<\/p>\n\n\n\n

NOT gate if m = 1), expressed in the circuit of Figure 7.15.<\/p>\n\n\n\n

|xi<\/p>\n\n\n\n

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

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

|xi<\/p>\n\n\n\n

|yi |f(x) \u2295 yi<\/p>\n\n\n\n

FIGURE 7.15: Quantum function evaluator.<\/p>\n\n\n\n

Here, |xi is an n-qubit basis state while |yi is an m-qubit one. Note that<\/p>\n\n\n\n

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

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

will be represented by an n + m square matrix. If the input lower register<\/p>\n\n\n\n

y = 0, then the output on the register is just f(x).<\/p>\n\n\n\n

Exercise 7.14. Show that U<\/p>\n\n\n\n

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

as de\ufb01ned in Equation 7.23 is unitary and therefore<\/p>\n\n\n\n

reversible.<\/p>\n\n\n\n

The important feature of a unitary transformation is not only that it admits<\/p>\n\n\n\n

an inverse, but also that it is linear. So it acts on superpositions thus:<\/p>\n\n\n\n

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

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

(c<\/p>\n\n\n\n

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

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

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

i + c<\/p>\n\n\n\n

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

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

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

i) |yi = c<\/p>\n\n\n\n

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

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

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

(|x<\/p>\n\n\n\n

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

i|yi) + c<\/p>\n\n\n\n

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

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

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

(|x<\/p>\n\n\n\n

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

i|yi) . (7.24)<\/p>\n\n\n\n

For instance, if the input is the uniform superposition of two qubits, the<\/p>\n\n\n\n

linearity of U<\/p>\n\n\n\n

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

means that<\/p>\n\n\n\n

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

f<\/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) |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|f(0)i + |1i|f (1)i) .<\/p>\n\n\n\n

The output is an entangled superposition state of both registers, containing<\/p>\n\n\n\n

both f(0) as well as f(1). This generalizes to multiple qubits as well. A uniform<\/p>\n\n\n\n

superposition of n qubits is the normalized sum of all 2<\/p>\n\n\n\n

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

possible n-qubit basis<\/p>\n\n\n\n

states |0i, |1i. . . |2<\/p>\n\n\n\n

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

\u2212 1i. So we have<\/p>\n\n\n\n

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

f<\/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<\/p>\n\n\n\n

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

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

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

m<\/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<\/p>\n\n\n\n

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

|f(x)i<\/p>\n\n\n\n

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

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

where the subscripts on the states indicate the dimensionality. The function<\/p>\n\n\n\n

has been evaluated in parallel on all inputs. This has been referred to as<\/p>\n\n\n\n

quantum parallelism. The catch is, however, that this superposition does<\/p>\n\n\n\n

not mean much to our classical minds, until we measure the output, upon<\/p>\n\n\n\n

which one of the answers is selected! We can never know all the f(x)\u2019s at<\/p>\n\n\n\n

once, nor can we clone the output and hope to learn f (x) by making repeated<\/p>\n\n\n\n

measurements of the output state.<\/p>\n\n\n\n

Nevertheless, this feature is enormously useful in designing quantum algo-<\/p>\n\n\n\n

rithms. One has to additionally choose clever modi\ufb01cations of the output such<\/p>\n\n\n\n

that the state containing the answer occurs with high amplitude. We will see<\/p>\n\n\n\n

this in action in the next chapters<\/p>\n","protected":false},"excerpt":{"rendered":"

We\u2019ve taken the circuit analogy for quantum computation up to gates. Can we go further? Can we identify a set of universal gates, as we did for classical computation? Since a computation is essentially the evaluation of a function of the inputs, let\u2019s \ufb01rst \ufb01x what we mean by a quantum function evaluation. Consider a […]<\/p>\n","protected":false},"author":1,"featured_media":4041,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[496],"tags":[],"class_list":["post-4072","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-quantum-gates-and-circuits"],"jetpack_featured_media_url":"https:\/\/workhouse.sweetdishy.com\/wp-content\/uploads\/2024\/09\/quantum-2.png","_links":{"self":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4072","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=4072"}],"version-history":[{"count":1,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4072\/revisions"}],"predecessor-version":[{"id":4073,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4072\/revisions\/4073"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media\/4041"}],"wp:attachment":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media?parent=4072"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4072"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4072"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}