estimation<\/p>\n\n\n\n
One version of Shor\u2019s algorithm is based on phase estimation. This appli-<\/p>\n\n\n\n
cation of the quantum Fourier transform is used to estimate the eigenvalue of<\/p>\n\n\n\n
a unitary operator, which is a phase:<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
U|ui = e<\/p>\n\n\n\n
i\u03b8<\/p>\n\n\n\n
|ui; \u03b8 = 2\u03c0\u03c6 (8.63)<\/p>\n\n\n\n
where \u03c6 is a fraction.<\/p>\n\n\n\n
As a preliminary to this algorithm, let\u2019s look at a toy version. Suppose you<\/p>\n\n\n\n
are given U and an eigenstate |ui. We have seen that the circuit of Figure 7.14<\/p>\n\n\n\n
simulates a measurement of U.<\/p>\n\n\n\n
|0i<\/p>\n\n\n\n
H<\/p>\n\n\n\n
\u2022<\/p>\n\n\n\n
H<\/p>\n\n\n\n
|ui<\/p>\n\n\n\n
U<\/p>\n\n\n\n
|ui<\/p>\n\n\n\n
Here,<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue000<\/p>\n\n\n\n
|0i + |1i<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
\u2297 |ui \u2192<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue000<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i\u03c6<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
\u2297 |ui. (8.64)<\/p>\n\n\n\n
If \u03c6 were a single bit, then you can see that the output is 0 if \u03c6 = 0.0 and 1<\/p>\n\n\n\n
if \u03c6 = 0.1. This circuit thus gives us the value in one run. But in general \u03c6<\/p>\n\n\n\n
will be several bits long. A measurement of the upper register in the H basis<\/p>\n\n\n\n
will yield a 0 or 1 with probabilities cos<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u03c0\u03c6 and sin<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u03c0\u03c6. A statistically large<\/p>\n\n\n\n
number of measurements will allow us to recover \u03c6 from the counts. But this<\/p>\n\n\n\n
is an ine\ufb03cient method.<\/p>\n\n\n\n
Note that the H transform on the upper register is the one-bit Fourier<\/p>\n\n\n\n
transform. In order to estimate \u03c6 to more bits of accuracy, we must have<\/p>\n\n\n\n
a qubit for each signi\ufb01cant \ufb01gure of \u03c6 and then perform an inverse Fourier<\/p>\n\n\n\n
transform, as shown in the circuit of Figure 8.13.<\/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
|ui \/<\/p>\n\n\n\n
n<\/p>\n\n\n\n
U<\/p>\n\n\n\n
U<\/p>\n\n\n\n
2<\/p>\n\n\n\n
. . .<\/p>\n\n\n\n
U<\/p>\n\n\n\n
2<\/p>\n\n\n\n
t\u22121<\/p>\n\n\n\n
|ui<\/p>\n\n\n\n
FIGURE 8.13: Circuit for phase estimation.<\/p>\n\n\n\n
Imagine \u03c6 upto t bits as<\/p>\n\n\n\n
\u03c6 = 0.\u03c6<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u03c6<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u00b7\u00b7\u00b7\u03c6<\/p>\n\n\n\n
t<\/p>\n\n\n\n
=<\/p>\n\n\n\n
\u03c6<\/p>\n\n\n\n
0<\/p>\n\n\n\n
2<\/p>\n\n\n\n
t<\/p>\n\n\n\n
, \u03c6<\/p>\n\n\n\n
0<\/p>\n\n\n\n
= \u03c6<\/p>\n\n\n\n
t<\/p>\n\n\n\n
\u03c6<\/p>\n\n\n\n
t\u22121<\/p>\n\n\n\n
\u00b7\u00b7\u00b7\u03c6<\/p>\n\n\n\n
1<\/p>\n\n\n\n
. (8.65)<\/p>\n\n\n\n
<\/p>\n\n\n\n
Quantum Algorithms 167<\/p>\n\n\n\n
Then we start with t working qubits in the input register, and use them to<\/p>\n\n\n\n
control gates of the form U<\/p>\n\n\n\n
2<\/p>\n\n\n\n
k<\/p>\n\n\n\n
. After the control gates, the output on the k<\/p>\n\n\n\n
th<\/p>\n\n\n\n
line is<\/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) \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
\ue010<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i2<\/p>\n\n\n\n
k<\/p>\n\n\n\n
\u03c6<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\ue011<\/p>\n\n\n\n
(8.66)<\/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
\ue010<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i(0.\u03c6<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u03c6<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u00b7\u00b7\u00b7\u03c6<\/p>\n\n\n\n
k<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\ue011<\/p>\n\n\n\n
. (8.67)<\/p>\n\n\n\n
You can see that just before the QFT gate, the state of the upper register is<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
t<\/p>\n\n\n\n
\ue000<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i\u03c6<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
\u2297<\/p>\n\n\n\n
\ue000<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
4\u03c0i\u03c6<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
\u2297 . . . \u2297<\/p>\n\n\n\n
\ue010<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i.2<\/p>\n\n\n\n
t<\/p>\n\n\n\n
\u03c6<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\ue011<\/p>\n\n\n\n
(8.68)<\/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
t<\/p>\n\n\n\n
2<\/p>\n\n\n\n
t<\/p>\n\n\n\n
\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0i\u03c6k<\/p>\n\n\n\n
|ki (8.69)<\/p>\n\n\n\n
This is just the QFT mod 2<\/p>\n\n\n\n
t<\/p>\n\n\n\n
of \u03c6<\/p>\n\n\n\n
0<\/p>\n\n\n\n
and an inverse Fourier transform will give<\/p>\n\n\n\n
you \u03c6<\/p>\n\n\n\n
0<\/p>\n\n\n\n
exact to t signi\ufb01cant \ufb01gures.<\/p>\n","protected":false},"excerpt":{"rendered":"
estimation One version of Shor\u2019s algorithm is based on phase estimation. This appli- cation of the quantum Fourier transform is used to estimate the eigenvalue of a unitary operator, which is a phase: \u02c6 U|ui = e i\u03b8 |ui; \u03b8 = 2\u03c0\u03c6 (8.63) where \u03c6 is a fraction. As a preliminary to this algorithm, let\u2019s […]<\/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-4094","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\/4094","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=4094"}],"version-history":[{"count":2,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4094\/revisions"}],"predecessor-version":[{"id":4588,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4094\/revisions\/4588"}],"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=4094"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4094"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4094"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}