{"id":4099,"date":"2024-09-21T14:43:16","date_gmt":"2024-09-21T14:43:16","guid":{"rendered":"https:\/\/workhouse.sweetdishy.com\/?p=4099"},"modified":"2024-09-21T14:43:16","modified_gmt":"2024-09-21T14:43:16","slug":"extension-to-multiple-solutions","status":"publish","type":"post","link":"https:\/\/workhouse.sweetdishy.com\/index.php\/2024\/09\/21\/extension-to-multiple-solutions\/","title":{"rendered":"Extension to multiple solutions"},"content":{"rendered":"\n

A simple extension to this algorithm works when the search criterion has<\/p>\n\n\n\n

multiple solutions. The oracle then gives an answer \u201cyes\u201d whenever any one<\/p>\n\n\n\n

of the M possible solutions is input. The Hilbert space then has a \u201csolution<\/p>\n\n\n\n

subspace\u201d M, spanned by M solution states. Let us denote by |\u03b2i the uniform<\/p>\n\n\n\n

superposition of all these vectors, and by |\u03b1i, its orthogonal complement.<\/p>\n\n\n\n

|\u03b2i =<\/p>\n\n\n\n

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

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

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

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

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

|xi, (8.81)<\/p>\n\n\n\n

|\u03b1i =<\/p>\n\n\n\n

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

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

N \u2212 M<\/p>\n\n\n\n

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

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

|xi. (8.82)<\/p>\n\n\n\n

In this situation, the input state is<\/p>\n\n\n\n

|\u03c8i =<\/p>\n\n\n\n

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

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

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

|\u03b2i +<\/p>\n\n\n\n

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

N \u2212 M<\/p>\n\n\n\n

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

|\u03b1i. (8.83)<\/p>\n\n\n\n

The angle \u03b8 is now given by<\/p>\n\n\n\n

sin \u03b8 = h\u03c8|\u03b2i =<\/p>\n\n\n\n

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

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

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

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

The operator<\/p>\n\n\n\n

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

O tags all of the M solutions with a \u2018\u2212\u2019 sign, and the Grover<\/p>\n\n\n\n

iterate is de\ufb01ned the same way as before. After p iterations we get the state<\/p>\n\n\n\n

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

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

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

|\u03c8i = cos[(2p + 1)\u03b8]|\u03b1i + sin[(2p + 1)\u03b8]|\u03b2i, (8.85)<\/p>\n\n\n\n

and the number of iterations required is nearly<\/p>\n\n\n\n

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

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

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

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

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

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

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

You should check for yourself that this works out.<\/p>\n\n\n\n

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

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

8.6.2 Quantum counting<\/p>\n\n\n\n

A fallout of the multiple search algorithm is the counting algorithm. Be-<\/p>\n\n\n\n

fore we know how many times to iterate, we need to know how many solutions<\/p>\n\n\n\n

M there are to the search criterion. Can we deduce a quantum algorithm for<\/p>\n\n\n\n

\ufb01nding M given U<\/p>\n\n\n\n

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

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

? The solution found by Brassard et al. [15], is a com-<\/p>\n\n\n\n

bination of Grover\u2019s search and Shor\u2019s phase estimation algorithms. The key<\/p>\n\n\n\n

point here is to note that the number of solutions is related to the eigenvalues<\/p>\n\n\n\n

of the operator<\/p>\n\n\n\n

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

G, which can also be expressed in the |\u03b1i-|\u03b2i basis as the 2-d<\/p>\n\n\n\n

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

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

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

cos \u03d5 \u2212sin \u03d5<\/p>\n\n\n\n

sin \u03d5 cos \u03d5<\/p>\n\n\n\n

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

where sin \u03d5 = 2<\/p>\n\n\n\n

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

M(N \u2212 M)<\/p>\n\n\n\n

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

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

The eigenvalues of this matrix are e<\/p>\n\n\n\n

\u00b1i\u03d5<\/p>\n\n\n\n

. We can therefore use the phase estima-<\/p>\n\n\n\n

tion algorithm to deduce \u03d5. We need to feed the algorithm with an eigenstate<\/p>\n\n\n\n

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

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

G. Now you can see for yourself that |\u03c8i is a linear superposition of the two<\/p>\n\n\n\n

eigenstates of<\/p>\n\n\n\n

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

G, so the circuit of Figure 8.18 will work to t bits of accuracy.<\/p>\n\n\n\n

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

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

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

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

QF T<\/p>\n\n\n\n

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

n + 1 qubits<\/p>\n\n\n\n

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

FIGURE 8.18: Circuit for quantum counting<\/p>\n","protected":false},"excerpt":{"rendered":"

A simple extension to this algorithm works when the search criterion has multiple solutions. The oracle then gives an answer \u201cyes\u201d whenever any one of the M possible solutions is input. The Hilbert space then has a \u201csolution subspace\u201d M, spanned by M solution states. Let us denote by |\u03b2i the uniform superposition of all […]<\/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-4099","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\/4099","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=4099"}],"version-history":[{"count":1,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4099\/revisions"}],"predecessor-version":[{"id":4100,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4099\/revisions\/4100"}],"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=4099"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4099"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4099"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}