<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@vertical+block@Communication_complexity_I" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True"> <h2 class="hd hd-2 unit-title">Communication complexity I</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-ddj1"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-ddj1" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="problem" data-runtime-version="1" data-has-score="True" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_wk7-ddj1" class="problems-wrapper" role="group" aria-labelledby="wk7-ddj1-problem-title" data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-ddj1" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-ddj1/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="1" data-attempts-used="0" data-content=" &lt;h3 class=&#34;hd hd-3 problem-header&#34; id=&#34;wk7-ddj1-problem-title&#34; aria-describedby=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-ddj1-problem-progress&#34; tabindex=&#34;-1&#34;&gt; Distributed Deutsch-Jozsa &lt;/h3&gt; &lt;div class=&#34;problem-progress&#34; id=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-ddj1-problem-progress&#34;&gt;&lt;/div&gt; &lt;div class=&#34;problem&#34;&gt; &lt;div&gt; &lt;p&gt; If two parties Alice and Bob receive inputs [mathjaxinline]x,y[/mathjaxinline] respectively then the classical/quantum communication complexity of a function [mathjaxinline]f(x,y)[/mathjaxinline] taking values in [mathjaxinline]\{ 0,1\}[/mathjaxinline] is the minimum number of bits/qubits required to compute [mathjaxinline]f[/mathjaxinline] with error probability [mathjaxinline]\leq 1/3[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; The following problem provides an example of an exponential gap between quantum and classical communication complexity. &lt;/p&gt; &lt;p&gt; Alice and Bob are each given [mathjaxinline]N[/mathjaxinline]-bit inputs [mathjaxinline]x[/mathjaxinline] and [mathjaxinline]y[/mathjaxinline], which are promised to either satisfy [mathjaxinline]x=y[/mathjaxinline] or have the property that [mathjaxinline]x[/mathjaxinline] and [mathjaxinline]y[/mathjaxinline] differ in exactly [mathjaxinline]N/2[/mathjaxinline] bit positions. For simplicity, assume [mathjaxinline]N=2^ n[/mathjaxinline], for integer [mathjaxinline]n[/mathjaxinline]. They are asked to determine which is the case, using as little communication as possible. &lt;/p&gt; &lt;p&gt; It is known that the best possible deterministic classical protocol for exact solution of this problem requires at least [mathjaxinline]0.007N[/mathjaxinline] bits to be communicated. &lt;/p&gt; &lt;p&gt; On the other hand, the following protocol shows that only [mathjaxinline]n = \log _2 N[/mathjaxinline] qubits need be communicated. This exemplifies an exponentially large separation between classical and quantum communication complexities, for the problem. &lt;/p&gt; &lt;p&gt; Alice prepares the [mathjaxinline]n[/mathjaxinline]-qubit state &lt;/p&gt; &lt;table id=&#34;a0000000002&#34; class=&#34;eqnarray&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; width=&#34;100%&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr id=&#34;a0000000003&#34;&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td style=&#34;vertical-align:middle; text-align:right; border:none&#34;&gt; [mathjaxinline]\displaystyle |\psi \rangle = \frac{1}{\sqrt{N}} \sum _{k=0}^{N-1} (-1)^{x_ k} |k\rangle[/mathjaxinline] &lt;/td&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.1)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; using [mathjaxinline]x[/mathjaxinline] (where [mathjaxinline]x_ k[/mathjaxinline] denotes the [mathjaxinline]k^{th}[/mathjaxinline] bit of [mathjaxinline]x[/mathjaxinline]). She then sends [mathjaxinline]|\psi \rangle[/mathjaxinline] to Bob. &lt;/p&gt; &lt;p&gt; Bob applies the unitary operation &lt;/p&gt; &lt;table id=&#34;a0000000004&#34; class=&#34;eqnarray&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; width=&#34;100%&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr id=&#34;a0000000005&#34;&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td style=&#34;vertical-align:middle; text-align:right; border:none&#34;&gt; [mathjaxinline]\displaystyle U |k\rangle = (-1)^{y_ k} |k\rangle[/mathjaxinline] &lt;/td&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.2)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; to [mathjaxinline]|\psi \rangle[/mathjaxinline], then he applies a Hadamard gate to each qubit. The resulting state is &lt;/p&gt; &lt;table id=&#34;a0000000006&#34; class=&#34;eqnarray&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; width=&#34;100%&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr id=&#34;a0000000007&#34;&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td style=&#34;vertical-align:middle; text-align:right; border:none&#34;&gt; [mathjaxinline]\displaystyle |\phi \rangle = H^{\otimes n} U |\psi \rangle \, .[/mathjaxinline] &lt;/td&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.3)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; Finally, he measures [mathjaxinline]|\phi \rangle[/mathjaxinline], and declares that [mathjaxinline]x=y[/mathjaxinline] if and only if the measurement gives all zeros. &lt;/p&gt; &lt;p&gt; To understand why this works, complete the following expression giving [mathjaxinline]|\phi \rangle[/mathjaxinline]: &lt;/p&gt; &lt;span&gt; &lt;div class=&#34;wrapper-problem-response&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 1&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_wk7-ddj1_2_1&#34; class=&#34;capa_inputtype&#34;&gt; &lt;div class=&#34;drag_and_drop_problem_div&#34; id=&#34;drag_and_drop_div_wk7-ddj1_2_1&#34; data-plain-id=&#34;wk7-ddj1_2_1&#34;&gt; &lt;/div&gt; &lt;div class=&#34;drag_and_drop_problem_json&#34; id=&#34;drag_and_drop_json_wk7-ddj1_2_1&#34; style=&#34;display:none;&#34;&gt;{&#34;base_image&#34;: &#34;/assets/courseware/v1/f08c53b9bdc3fd9b16e6667547fcae99/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd.png&#34;, &#34;targets&#34;: [{&#34;id&#34;: &#34;1&#34;, &#34;y&#34;: &#34;91&#34;, &#34;w&#34;: &#34;101&#34;, &#34;x&#34;: &#34;85&#34;, &#34;h&#34;: &#34;71&#34;}, {&#34;id&#34;: &#34;2&#34;, &#34;y&#34;: &#34;1&#34;, &#34;w&#34;: &#34;101&#34;, &#34;x&#34;: &#34;318&#34;, &#34;h&#34;: &#34;71&#34;}, {&#34;id&#34;: &#34;3&#34;, &#34;y&#34;: &#34;1&#34;, &#34;w&#34;: &#34;100&#34;, &#34;x&#34;: &#34;602&#34;, &#34;h&#34;: &#34;71&#34;}], &#34;label_bg_color&#34;: &#34;rgb(222, 139, 238)&#34;, &#34;draggables&#34;: [{&#34;id&#34;: &#34;one&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/0b37297a2fac41975ffea89ee21e883a/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label1.png&#34;}, {&#34;id&#34;: &#34;two&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/00159969b6475ecc4ed05f9f2fbd6504/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label2.png&#34;}, {&#34;id&#34;: &#34;N&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/514a6665a46aa4a04b58ecc7f83dc63c/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label3.png&#34;}, {&#34;id&#34;: &#34;sN&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/54c71d72547d25f8269bd8ac6d417f38/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label4.png&#34;}, {&#34;id&#34;: &#34;n&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/a4669c1b0606a1a09c020c0740b5bc1d/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label5.png&#34;}, {&#34;id&#34;: &#34;xk&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/86a44f6b303b914e13aaeb39e3f5d899/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label6.png&#34;}, {&#34;id&#34;: &#34;yk&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/7b2718e47f0ea829cbb2b37b45218ba0/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label7.png&#34;}, {&#34;id&#34;: &#34;xkpyk&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/f1b8f3f62bc76ab8bc4dee8671a1db64/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label8.png&#34;}, {&#34;id&#34;: &#34;xkdyk&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/6e9d834d00617cfb4bb8926b20c971e3/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label9.png&#34;}, {&#34;id&#34;: &#34;jdk&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/1b93c5c09b0d8d09620b2719ef4498b8/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label10.png&#34;}, {&#34;id&#34;: &#34;jopk&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/0830614436e548da0a7df22b37e29118/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-ddj_wk7-ddj_dnd_label11.png&#34;}], &#34;one_per_target&#34;: &#34;true&#34;, &#34;target_outline&#34;: &#34;false&#34;}&lt;/div&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/static/js/capa/drag_and_drop.a31124208b9b.js&#34;/&gt; &lt;div class=&#34;unanswered&#34; id=&#34;status_wk7-ddj1_2_1&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_wk7-ddj1_2_1&#34; id=&#34;input_wk7-ddj1_2_1&#34; aria-describedby=&#34;answer_wk7-ddj1_2_1&#34; value=&#34;&#34; style=&#34;display:none;&#34;/&gt; &lt;p class=&#34;indicator-container drag-and-drop--status&#34; aria-describedby=&#34;input_wk7-ddj1_2_1&#34;&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_wk7-ddj1_2_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;/p&gt; &lt;p id=&#34;answer_wk7-ddj1_2_1&#34; class=&#34;answer&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_wk7-ddj1_solution_1&#34;/&gt; &lt;/div&gt;&lt;/span&gt; &lt;p&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_wk7-ddj1_solution_2&#34;/&gt; &lt;/div&gt;&lt;/p&gt; &lt;/div&gt; &lt;div class=&#34;action&#34;&gt; &lt;input type=&#34;hidden&#34; name=&#34;problem_id&#34; value=&#34;Distributed Deutsch-Jozsa&#34; /&gt; &lt;div class=&#34;submit-attempt-container&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;submit btn-brand&#34; data-submitting=&#34;Submitting&#34; data-value=&#34;Submit&#34; data-should-enable-submit-button=&#34;True&#34; aria-describedby=&#34;submission_feedback_wk7-ddj1&#34; &gt; &lt;span class=&#34;submit-label&#34;&gt;Submit&lt;/span&gt; &lt;/button&gt; &lt;div class=&#34;submission-feedback&#34; id=&#34;submission_feedback_wk7-ddj1&#34;&gt; &lt;span class=&#34;sr&#34;&gt;Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.&lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;problem-action-buttons-wrapper&#34;&gt; &lt;span class=&#34;problem-action-button-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;save problem-action-btn btn-default btn-small&#34; data-value=&#34;Save&#34;&gt; &lt;span class=&#34;icon fa fa-floppy-o&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span aria-hidden=&#34;true&#34;&gt;Save&lt;/span&gt; &lt;span class=&#34;sr&#34;&gt;Save your answer&lt;/span&gt; &lt;/button&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-gentle-alert is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-exclamation-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;wk7-ddj1-problem-title&#34;&gt; &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-save is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-save&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;wk7-ddj1-problem-title&#34;&gt;None &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification general notification-show-answer is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-info-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;wk7-ddj1-problem-title&#34;&gt;Answers are displayed within the problem &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;/div&gt; " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading&hellip;</span> </p> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box1xxxx"> <div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box1xxxx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="html" data-runtime-version="1" data-has-score="False" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "HTMLModule"} </script> <span><a href="/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/NONE" id="dummy_course_static_link" style="display:none"/><a href="/courses/course-v1:MITx+8.371.3x+2T2018/jump_to_id/NONE" id="dummy_jump_link" style="display:none"/><script type="text/javascript"> var add_site_search = function(){ course_static_url = $('#dummy_course_static_link').attr('href').replace('/NONE', ''); jump_to_url = $('#dummy_jump_link').attr('href').replace('/NONE', ''); if (typeof String.prototype.startsWith != 'function') { // see below for better implementation! String.prototype.startsWith = function (str){ return this.indexOf(str) === 0; }; } if(typeof(String.prototype.trim) === "undefined") { String.prototype.trim = function() { return String(this).replace(/^\s+|\s+$/g, ''); }; } var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var amp = String.fromCharCode(38); var rlb = rb + lb; var mke = function(x){ return lb + x + rb; } var search_module_url = ""; var get_search_module_ficus = function(){ var cid = $('div.xblock').data('course-id'); if (cid){ console.log("cid = ", cid); // search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/" + cid + "/courseware/welcome/Search_this_course/"; search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/courseware/welcome/Search_this_course/"; // automatically rewritten console.log("3. search_module_url = ", search_module_url); return; } var course_root_link = $('span.nav-item-course').find('a').attr('href'); if (course_root_link){ console.log("course_root_link = ", course_root_link); search_module_url = course_root_link.replace("course/", "courseware/welcome/Search_this_course/"); console.log("2. search_module_url = ", search_module_url); return } console.log("cannot determine search module url"); } var get_search_module = function(){ // find search this module link if (!($('div.course-index').length)){ return get_search_module_ficus(); } $('div.course-index').find('nav').find('a').each(function(){ if ($(this).text().trim().startsWith("Search this course")){ search_module_url = $(this).attr('href'); console.log("search_module_url = ", search_module_url); } }); } var go_to_search = function(){ get_search_module(); var sterm = $('#site-search-box').val(); // new_url = jump_to_url + "/Search_this_module/?q=" + sterm; new_url = search_module_url + "?q=" + sterm; console.log("sterm = ", sterm, " ; going to ", new_url); window.location.href = new_url; } if (!$('#site-search-box').length){ $("nav.courseware").find("ol").append(lb + "section style='float:right'" + rlb + "input size='20'" + " id='site-search-box'" + rlb + "img src='" + course_static_url + "/images_search_glass.png'/" + rlb + "/input" + rlb + "/section" + rb); } $("#site-search-box").keypress(function(event) { if (event.which == 13) { event.preventDefault(); go_to_search(); } }); // $('#site-search-box').bind("enterKey", go_to_search); var get = function(x){ return eval(x); } return {'course_static_url': course_static_url, 'jump_to_url': jump_to_url, 'go_to_search': go_to_search, 'get_search_module': get_search_module, 'get_search_module_ficus': get_search_module_ficus, 'get': get, } } var the_site_search = add_site_search(); var add_fix_transcript = function(){ if ($('div.wrap-instructor-info').length==0){ return; } $('div.xblock-student_view-video').each(function(key, vblock_e){ var vblock = $(vblock_e); var vuid = vblock.data('usage-id').split('@'); var vid; if (vuid.length==1){ vuid = vblock.data('usage-id').split(';_') vid = vuid[5]; }else{ vid = vuid[2]; } var mfnpre = vid.split("_video",1)[0]; var mfnid = mfnpre; // no periods mfnpre = mfnpre.replace('8_370', '8.370'); // periods in gh filename var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var mke = function(x){ return lb + x + rb; } var ftid = "fix_transcript_" + mfnid; if (!$('#' + ftid).length){ var html = lb + "span id='" + ftid + "' style='float:right'" + rb + lb + "a href='#'" + rb; html += "contribute transcript fix" + mke("/a") + mke("/span"); console.log("html = ", html); vblock.after(html) } $('#' + ftid).click(function(){ var cst = $('ol.subtitles').find('li.current'); var cindex = Number(cst.data('index')); var gurl; if (mfnpre.endsWith('_cq_sol')){ gurl = "https://github.com/mitocw/content-mit-8370x-cq-sol-subtitles/blob/master/"; }else{ gurl = "https://github.com/mitocw/content-mit-8370x-subtitles/blob/master/"; } gurl += mfnpre + ".txt#L" + String(cindex + 10 + 1); console.log("going to ", gurl); window.open(gurl, "MITx 8.370x subtitle source"); }); }); } try{ add_fix_transcript(); } catch(err){ console.log(err); } try{ var rb = String.fromCharCode(62); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 3000); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 8000); } catch(err){ console.log(err); } </script></span> </div> </div> </div> </div>

<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@vertical+block@Communication_complexity_II" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True"> <h2 class="hd hd-2 unit-title">Communication complexity II</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-iproduct"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-iproduct" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="problem" data-runtime-version="1" data-has-score="True" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_wk7-iproduct" class="problems-wrapper" role="group" aria-labelledby="wk7-iproduct-problem-title" data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-iproduct" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-iproduct/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="2" data-attempts-used="0" data-content=" &lt;h3 class=&#34;hd hd-3 problem-header&#34; id=&#34;wk7-iproduct-problem-title&#34; aria-describedby=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-iproduct-problem-progress&#34; tabindex=&#34;-1&#34;&gt; Inner product &lt;/h3&gt; &lt;div class=&#34;problem-progress&#34; id=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-iproduct-problem-progress&#34;&gt;&lt;/div&gt; &lt;div class=&#34;problem&#34;&gt; &lt;div&gt; &lt;p&gt; What is the quantum communication complexity for the problem of computing (exactly) the inner product [mathjaxinline]x\cdot y[/mathjaxinline] between two [mathjaxinline]n[/mathjaxinline]-bit strings [mathjaxinline]x[/mathjaxinline] and [mathjaxinline]y[/mathjaxinline]? We can obtain a bound by assuming that a quantum protocol for this exists, and seeing what its existence implies about the ability to communicate qubits. &lt;/p&gt; &lt;p&gt; Let Alice be given [mathjaxinline]x[/mathjaxinline] and Bob be given [mathjaxinline]y[/mathjaxinline]. It can be shown that any exact quantum protocol (&amp;#8220;IP&#34;) for the inner product must allow Alice and Bob to perform the following unitary transformation: &lt;/p&gt; &lt;table id=&#34;a0000000010&#34; class=&#34;eqnarray&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; width=&#34;100%&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr id=&#34;a0000000011&#34;&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td style=&#34;vertical-align:middle; text-align:right; border:none&#34;&gt; [mathjaxinline]\displaystyle U_{IP} |x,y\rangle = (-1)^{x\cdot y} |x,y\rangle \, .[/mathjaxinline] &lt;/td&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.5)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; Suppose Alice starts with [mathjaxinline]|x\rangle[/mathjaxinline] and Bob starts with a uniform superposition over all possible [mathjaxinline]y[/mathjaxinline], i.e. the joint initial state is &lt;/p&gt; &lt;table id=&#34;a0000000012&#34; class=&#34;eqnarray&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; width=&#34;100%&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr id=&#34;a0000000013&#34;&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td style=&#34;vertical-align:middle; text-align:right; border:none&#34;&gt; [mathjaxinline]\displaystyle |\psi \rangle = \frac{1}{\sqrt{2^ n}} \sum _ y |x,y\rangle \, .[/mathjaxinline] &lt;/td&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.6)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; Suppose that Alice and Bob then apply [mathjaxinline]U_{IP}[/mathjaxinline], obtaining &lt;/p&gt; &lt;table id=&#34;a0000000014&#34; class=&#34;eqnarray&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; width=&#34;100%&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr id=&#34;a0000000015&#34;&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td style=&#34;vertical-align:middle; text-align:right; border:none&#34;&gt; [mathjaxinline]\displaystyle |\phi \rangle = \frac{1}{\sqrt{2^ n}} \sum _ y (-1)^{x\cdot y}|x,y\rangle \, .[/mathjaxinline] &lt;/td&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.7)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; Bob now applies a Hadamard operator to each of his [mathjaxinline]n[/mathjaxinline] qubits, and measures these qubits. What state does he obtain? &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]|\phi \rangle =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 1&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_wk7-iproduct_2_1&#34; class=&#34;text-input-dynamath capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;text-input-dynamath_data inline&#34; data-preprocessor=&#34;MathjaxPreprocessorForQM&#34;/&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/assets/courseware/v1/95fe583d41f010195cf50c9f61992d94/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_H.js&#34;/&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_wk7-iproduct_2_1&#34; id=&#34;input_wk7-iproduct_2_1&#34; aria-describedby=&#34;status_wk7-iproduct_2_1&#34; value=&#34;&#34; class=&#34;math&#34; size=&#34;70&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_wk7-iproduct_2_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_wk7-iproduct_2_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_wk7-iproduct_2_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;display_wk7-iproduct_2_1&#34; class=&#34;equation&#34;&gt;`{::}`&lt;/div&gt; &lt;textarea style=&#34;display:none&#34; id=&#34;input_wk7-iproduct_2_1_dynamath&#34; name=&#34;input_wk7-iproduct_2_1_dynamath&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; This result implies that the IP protocol can be used to communicate [mathjaxinline]m[/mathjaxinline] qubits of quantum information from Alice to Bob. What is [mathjaxinline]m[/mathjaxinline], in terms of [mathjaxinline]n[/mathjaxinline]? &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]m =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 2&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_wk7-iproduct_3_1&#34; class=&#34; capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_wk7-iproduct_3_1&#34; id=&#34;input_wk7-iproduct_3_1&#34; aria-describedby=&#34;status_wk7-iproduct_3_1&#34; value=&#34;&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_wk7-iproduct_3_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_wk7-iproduct_3_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_wk7-iproduct_3_1&#34; class=&#34;answer&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_wk7-iproduct_solution_1&#34;/&gt; &lt;/div&gt;&lt;/p&gt; &lt;/div&gt; &lt;div class=&#34;action&#34;&gt; &lt;input type=&#34;hidden&#34; name=&#34;problem_id&#34; value=&#34;Inner product&#34; /&gt; &lt;div class=&#34;submit-attempt-container&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;submit btn-brand&#34; data-submitting=&#34;Submitting&#34; data-value=&#34;Submit&#34; data-should-enable-submit-button=&#34;True&#34; aria-describedby=&#34;submission_feedback_wk7-iproduct&#34; &gt; &lt;span class=&#34;submit-label&#34;&gt;Submit&lt;/span&gt; &lt;/button&gt; &lt;div class=&#34;submission-feedback&#34; id=&#34;submission_feedback_wk7-iproduct&#34;&gt; &lt;span class=&#34;sr&#34;&gt;Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.&lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;problem-action-buttons-wrapper&#34;&gt; &lt;span class=&#34;problem-action-button-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;save problem-action-btn btn-default btn-small&#34; data-value=&#34;Save&#34;&gt; &lt;span class=&#34;icon fa fa-floppy-o&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span aria-hidden=&#34;true&#34;&gt;Save&lt;/span&gt; &lt;span class=&#34;sr&#34;&gt;Save your answer&lt;/span&gt; &lt;/button&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-gentle-alert is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-exclamation-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;wk7-iproduct-problem-title&#34;&gt; &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-save is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-save&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;wk7-iproduct-problem-title&#34;&gt;None &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification general notification-show-answer is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-info-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;wk7-iproduct-problem-title&#34;&gt;Answers are displayed within the problem &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;/div&gt; " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading&hellip;</span> </p> </div> </div> </div> </div> </div>

<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@vertical+block@Communication_complexity_III" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True"> <h2 class="hd hd-2 unit-title">Communication complexity III</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-intersection1"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-intersection1" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="problem" data-runtime-version="1" data-has-score="True" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_wk7-intersection1" class="problems-wrapper" role="group" aria-labelledby="wk7-intersection1-problem-title" data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-intersection1" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-intersection1/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="1" data-attempts-used="0" data-content=" &lt;h3 class=&#34;hd hd-3 problem-header&#34; id=&#34;wk7-intersection1-problem-title&#34; aria-describedby=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-intersection1-problem-progress&#34; tabindex=&#34;-1&#34;&gt; The intersection problem &lt;/h3&gt; &lt;div class=&#34;problem-progress&#34; id=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@wk7-intersection1-problem-progress&#34;&gt;&lt;/div&gt; &lt;div class=&#34;problem&#34;&gt; &lt;div&gt; &lt;p&gt; Suppose Alice and Bob are given [mathjaxinline]n[/mathjaxinline]-bit strings [mathjaxinline]x[/mathjaxinline] and [mathjaxinline]y[/mathjaxinline], respectively, and asked if there is any [mathjaxinline]k[/mathjaxinline] such that [mathjaxinline]x_ k=y_ k[/mathjaxinline] (i.e. the two bit strings have a common [mathjaxinline]1[/mathjaxinline] at the same bit string position [mathjaxinline]k[/mathjaxinline]). &lt;/p&gt; &lt;p&gt; It is a well-known result of classical communication complexity that classical bounded-error protocols for this &amp;#8220;intersection problem&#34; need about [mathjaxinline]n[/mathjaxinline] bits of communication. &lt;/p&gt; &lt;p&gt; On the other hand, here is a quantum protocol which solves the problem using [mathjaxinline]O(\sqrt{n} \log _2 n)[/mathjaxinline] qubits of communication, based on a distributed version of Grover&#39;s algorithm. &lt;/p&gt; &lt;p&gt; Recall that Grover&#39;s algorithm involves the search for an index [mathjaxinline]j[/mathjaxinline] such that [mathjaxinline]z_ j=1[/mathjaxinline] in an [mathjaxinline]n[/mathjaxinline]-bit string [mathjaxinline]z[/mathjaxinline] held by an oracle. The oracle performs a unitary operation &lt;/p&gt; &lt;table id=&#34;a0000000016&#34; class=&#34;eqnarray&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; width=&#34;100%&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr id=&#34;a0000000017&#34;&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td style=&#34;vertical-align:middle; text-align:right; border:none&#34;&gt; [mathjaxinline]\displaystyle O_ z |k\rangle = (-1)^{z_ k} |k\rangle \, .[/mathjaxinline] &lt;/td&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.8)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; The algorithm is given by applying the Grover iterate &lt;/p&gt; &lt;table id=&#34;a0000000018&#34; class=&#34;eqnarray&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; width=&#34;100%&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr id=&#34;a0000000019&#34;&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td style=&#34;vertical-align:middle; text-align:right; border:none&#34;&gt; [mathjaxinline]\displaystyle G = H^{\otimes \log _2 n} O_0 H^{\otimes \log _2 n} O_ z[/mathjaxinline] &lt;/td&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.9)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; [mathjaxinline]O(\sqrt{n})[/mathjaxinline] times to the initial state [mathjaxinline]\sum _ k |k\rangle /\sqrt{n}[/mathjaxinline], then measuring, to obtain [mathjaxinline]j[/mathjaxinline] with high probability. &lt;/p&gt; &lt;p&gt; The intersection problem can be viewed as an instance of the search problem solved by Grover&#39;s algorithm, wherein [mathjaxinline]z = x\wedge y[/mathjaxinline], the bit-wise AND of [mathjaxinline]x[/mathjaxinline] and [mathjaxinline]y[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; Alice can do all the steps of the Grover algorithm herself, except the oracle operation [mathjaxinline]O_ z[/mathjaxinline]. That must involve Bob. &lt;/p&gt; &lt;p&gt; To apply [mathjaxinline]O_ z[/mathjaxinline] to a state &lt;/p&gt; &lt;table id=&#34;a0000000020&#34; class=&#34;eqnarray&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; width=&#34;100%&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr id=&#34;a0000000021&#34;&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td style=&#34;vertical-align:middle; text-align:right; border:none&#34;&gt; [mathjaxinline]\displaystyle |\phi \rangle = \sum _{k=0}^{n-1} \alpha _ k |k\rangle \, ,[/mathjaxinline] &lt;/td&gt; &lt;td style=&#34;width:40%; border:none&#34;&gt;&amp;#160;&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.10)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; Alice appends an ancilla qubit [mathjaxinline]|0\rangle[/mathjaxinline] and performs the simple unitary transform [mathjaxinline]U_{\rm Alice} |k, 0\rangle = |k, x_ k\rangle[/mathjaxinline], generated using her knowledge of [mathjaxinline]x[/mathjaxinline]. She then sends this state to Bob, who performs [mathjaxinline]U_{\rm Bob}[/mathjaxinline], then returns the qubits to Alice. Alice then applies [mathjaxinline]U^{\dagger }_{\rm Alice}[/mathjaxinline] to remove the ancilla qubit, obtaining [mathjaxinline]O_ z |\phi \rangle[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; Complete the following expression which specifies [mathjaxinline]U_{\rm Bob}[/mathjaxinline] such that the protocol works as described: &lt;/p&gt; &lt;span&gt; &lt;div class=&#34;wrapper-problem-response&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 1&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_wk7-intersection1_2_1&#34; class=&#34;capa_inputtype&#34;&gt; &lt;div class=&#34;drag_and_drop_problem_div&#34; id=&#34;drag_and_drop_div_wk7-intersection1_2_1&#34; data-plain-id=&#34;wk7-intersection1_2_1&#34;&gt; &lt;/div&gt; &lt;div class=&#34;drag_and_drop_problem_json&#34; id=&#34;drag_and_drop_json_wk7-intersection1_2_1&#34; style=&#34;display:none;&#34;&gt;{&#34;base_image&#34;: &#34;/assets/courseware/v1/6800dbc0fc6f95fe7f07308a0848bf70/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd.png&#34;, &#34;targets&#34;: [{&#34;id&#34;: &#34;1&#34;, &#34;y&#34;: &#34;1&#34;, &#34;w&#34;: &#34;101&#34;, &#34;x&#34;: &#34;225&#34;, &#34;h&#34;: &#34;71&#34;}, {&#34;id&#34;: &#34;2&#34;, &#34;y&#34;: &#34;34&#34;, &#34;w&#34;: &#34;101&#34;, &#34;x&#34;: &#34;361&#34;, &#34;h&#34;: &#34;71&#34;}, {&#34;id&#34;: &#34;3&#34;, &#34;y&#34;: &#34;34&#34;, &#34;w&#34;: &#34;100&#34;, &#34;x&#34;: &#34;495&#34;, &#34;h&#34;: &#34;71&#34;}], &#34;label_bg_color&#34;: &#34;rgb(222, 139, 238)&#34;, &#34;draggables&#34;: [{&#34;id&#34;: &#34;i&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/59a247a6836a8a3989fef4e9c641c867/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label1.png&#34;}, {&#34;id&#34;: &#34;j&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/3b6bde87684e715fdb43116ce53aad41/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label2.png&#34;}, {&#34;id&#34;: &#34;k&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/b483447814ce93d0db3e247509bfdf96/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label3.png&#34;}, {&#34;id&#34;: &#34;xi&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/e534fa063eccdb7a0c3bc2323548f9aa/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label4.png&#34;}, {&#34;id&#34;: &#34;xj&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/c8e46ea6a3d7070cb8e1bfa2ec261b0d/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label5.png&#34;}, {&#34;id&#34;: &#34;yi&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/5b2273b12ac9b4fde09666dd8c9ba2ec/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label6.png&#34;}, {&#34;id&#34;: &#34;yj&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/10e31783e75ea6bc7cde5b668f264b4e/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label7.png&#34;}, {&#34;id&#34;: &#34;xandy&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/6a3f409bc6a03d83cc7385a3e741b25e/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label8.png&#34;}, {&#34;id&#34;: &#34;jandy&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/c99de2e02833ec497e1881bef25639dc/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label9.png&#34;}, {&#34;id&#34;: &#34;xjandy&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/5868329eefa0af410ba1556af35590d5/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label10.png&#34;}, {&#34;id&#34;: &#34;xiandy&#34;, &#34;target_fields&#34;: [], &#34;can_reuse&#34;: &#34;&#34;, &#34;label&#34;: &#34;&#34;, &#34;icon&#34;: &#34;/assets/courseware/v1/55507e41c03fd6ee6d1da357b2cced10/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk7-intersection_wk7-intersection_dnd_label11.png&#34;}], &#34;one_per_target&#34;: &#34;true&#34;, &#34;target_outline&#34;: &#34;false&#34;}&lt;/div&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/static/js/capa/drag_and_drop.a31124208b9b.js&#34;/&gt; &lt;div class=&#34;unanswered&#34; id=&#34;status_wk7-intersection1_2_1&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_wk7-intersection1_2_1&#34; id=&#34;input_wk7-intersection1_2_1&#34; aria-describedby=&#34;answer_wk7-intersection1_2_1&#34; value=&#34;&#34; style=&#34;display:none;&#34;/&gt; &lt;p class=&#34;indicator-container drag-and-drop--status&#34; aria-describedby=&#34;input_wk7-intersection1_2_1&#34;&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_wk7-intersection1_2_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;/p&gt; &lt;p id=&#34;answer_wk7-intersection1_2_1&#34; class=&#34;answer&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_wk7-intersection1_solution_1&#34;/&gt; &lt;/div&gt;&lt;/span&gt; &lt;p&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_wk7-intersection1_solution_2&#34;/&gt; &lt;/div&gt;&lt;/p&gt; &lt;/div&gt; &lt;div class=&#34;action&#34;&gt; &lt;input type=&#34;hidden&#34; name=&#34;problem_id&#34; value=&#34;The intersection problem&#34; /&gt; &lt;div class=&#34;submit-attempt-container&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;submit btn-brand&#34; data-submitting=&#34;Submitting&#34; data-value=&#34;Submit&#34; data-should-enable-submit-button=&#34;True&#34; aria-describedby=&#34;submission_feedback_wk7-intersection1&#34; &gt; &lt;span class=&#34;submit-label&#34;&gt;Submit&lt;/span&gt; &lt;/button&gt; &lt;div class=&#34;submission-feedback&#34; id=&#34;submission_feedback_wk7-intersection1&#34;&gt; &lt;span class=&#34;sr&#34;&gt;Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.&lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;problem-action-buttons-wrapper&#34;&gt; &lt;span class=&#34;problem-action-button-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;save problem-action-btn btn-default btn-small&#34; data-value=&#34;Save&#34;&gt; &lt;span class=&#34;icon fa fa-floppy-o&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span aria-hidden=&#34;true&#34;&gt;Save&lt;/span&gt; &lt;span class=&#34;sr&#34;&gt;Save your answer&lt;/span&gt; &lt;/button&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-gentle-alert is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-exclamation-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;wk7-intersection1-problem-title&#34;&gt; &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-save is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-save&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;wk7-intersection1-problem-title&#34;&gt;None &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification general notification-show-answer is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-info-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;wk7-intersection1-problem-title&#34;&gt;Answers are displayed within the problem &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;/div&gt; " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading&hellip;</span> </p> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box3xxxx"> <div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box3xxxx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="html" data-runtime-version="1" data-has-score="False" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "HTMLModule"} </script> <span><a href="/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/NONE" id="dummy_course_static_link" style="display:none"/><a href="/courses/course-v1:MITx+8.371.3x+2T2018/jump_to_id/NONE" id="dummy_jump_link" style="display:none"/><script type="text/javascript"> var add_site_search = function(){ course_static_url = $('#dummy_course_static_link').attr('href').replace('/NONE', ''); jump_to_url = $('#dummy_jump_link').attr('href').replace('/NONE', ''); if (typeof String.prototype.startsWith != 'function') { // see below for better implementation! String.prototype.startsWith = function (str){ return this.indexOf(str) === 0; }; } if(typeof(String.prototype.trim) === "undefined") { String.prototype.trim = function() { return String(this).replace(/^\s+|\s+$/g, ''); }; } var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var amp = String.fromCharCode(38); var rlb = rb + lb; var mke = function(x){ return lb + x + rb; } var search_module_url = ""; var get_search_module_ficus = function(){ var cid = $('div.xblock').data('course-id'); if (cid){ console.log("cid = ", cid); // search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/" + cid + "/courseware/welcome/Search_this_course/"; search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/courseware/welcome/Search_this_course/"; // automatically rewritten console.log("3. search_module_url = ", search_module_url); return; } var course_root_link = $('span.nav-item-course').find('a').attr('href'); if (course_root_link){ console.log("course_root_link = ", course_root_link); search_module_url = course_root_link.replace("course/", "courseware/welcome/Search_this_course/"); console.log("2. search_module_url = ", search_module_url); return } console.log("cannot determine search module url"); } var get_search_module = function(){ // find search this module link if (!($('div.course-index').length)){ return get_search_module_ficus(); } $('div.course-index').find('nav').find('a').each(function(){ if ($(this).text().trim().startsWith("Search this course")){ search_module_url = $(this).attr('href'); console.log("search_module_url = ", search_module_url); } }); } var go_to_search = function(){ get_search_module(); var sterm = $('#site-search-box').val(); // new_url = jump_to_url + "/Search_this_module/?q=" + sterm; new_url = search_module_url + "?q=" + sterm; console.log("sterm = ", sterm, " ; going to ", new_url); window.location.href = new_url; } if (!$('#site-search-box').length){ $("nav.courseware").find("ol").append(lb + "section style='float:right'" + rlb + "input size='20'" + " id='site-search-box'" + rlb + "img src='" + course_static_url + "/images_search_glass.png'/" + rlb + "/input" + rlb + "/section" + rb); } $("#site-search-box").keypress(function(event) { if (event.which == 13) { event.preventDefault(); go_to_search(); } }); // $('#site-search-box').bind("enterKey", go_to_search); var get = function(x){ return eval(x); } return {'course_static_url': course_static_url, 'jump_to_url': jump_to_url, 'go_to_search': go_to_search, 'get_search_module': get_search_module, 'get_search_module_ficus': get_search_module_ficus, 'get': get, } } var the_site_search = add_site_search(); var add_fix_transcript = function(){ if ($('div.wrap-instructor-info').length==0){ return; } $('div.xblock-student_view-video').each(function(key, vblock_e){ var vblock = $(vblock_e); var vuid = vblock.data('usage-id').split('@'); var vid; if (vuid.length==1){ vuid = vblock.data('usage-id').split(';_') vid = vuid[5]; }else{ vid = vuid[2]; } var mfnpre = vid.split("_video",1)[0]; var mfnid = mfnpre; // no periods mfnpre = mfnpre.replace('8_370', '8.370'); // periods in gh filename var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var mke = function(x){ return lb + x + rb; } var ftid = "fix_transcript_" + mfnid; if (!$('#' + ftid).length){ var html = lb + "span id='" + ftid + "' style='float:right'" + rb + lb + "a href='#'" + rb; html += "contribute transcript fix" + mke("/a") + mke("/span"); console.log("html = ", html); vblock.after(html) } $('#' + ftid).click(function(){ var cst = $('ol.subtitles').find('li.current'); var cindex = Number(cst.data('index')); var gurl; if (mfnpre.endsWith('_cq_sol')){ gurl = "https://github.com/mitocw/content-mit-8370x-cq-sol-subtitles/blob/master/"; }else{ gurl = "https://github.com/mitocw/content-mit-8370x-subtitles/blob/master/"; } gurl += mfnpre + ".txt#L" + String(cindex + 10 + 1); console.log("going to ", gurl); window.open(gurl, "MITx 8.370x subtitle source"); }); }); } try{ add_fix_transcript(); } catch(err){ console.log(err); } try{ var rb = String.fromCharCode(62); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 3000); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 8000); } catch(err){ console.log(err); } </script></span> </div> </div> </div> </div>

<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@vertical+block@Dihedral_Hidden_Subgroup_Problem_and_QFT" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True"> <h2 class="hd hd-2 unit-title">Dihedral Hidden Subgroup Problem and QFT</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@Dihedral_Hidden_Subgroup_Problem_and_QFT_html"> <div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@Dihedral_Hidden_Subgroup_Problem_and_QFT_html" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="html" data-runtime-version="1" data-has-score="False" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "HTMLModule"} </script> <p> We will revisit the hidden subgroup problem (HSP) on the dihedral group [mathjaxinline]D_ N[/mathjaxinline] which can be thought of as [mathjaxinline]\{ s^ x r^ a : s \in \mathbb {Z}_ N, r\in \mathbb {Z}_2\}[/mathjaxinline] where [mathjaxinline]s,r[/mathjaxinline] satisfy [mathjaxinline]s^ N = r^2 = srsr =1[/mathjaxinline]. In lecture we used the quantum Fourier transform (QFT) over the cyclic group [mathjaxinline]\mathbb {Z}_ N[/mathjaxinline], while in this problem we will use the QFT over [mathjaxinline]D_ N[/mathjaxinline]. </p><p> Recall that the QFT for a group [mathjaxinline]G[/mathjaxinline] is defined in terms of its set of irreps (irreducible representations) [mathjaxinline]\hat G[/mathjaxinline]. If [mathjaxinline]\sigma \in \hat G[/mathjaxinline] then let [mathjaxinline]d_\sigma[/mathjaxinline] denote its dimension. Then </p><table id="a0000000022" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]F_ G = \sum _{g \in G} \sum _{\sigma \in \hat G} \sum _{i=0}^{d_\sigma -1} \sum _{j=0}^{d_\sigma -1} \sqrt{\frac{d_\sigma }{|G|}} \sigma (g)_{i,j} |{\sigma ,i,j}\rangle \langle {g}|.[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p> It turns out that for [mathjaxinline]D_ N[/mathjaxinline] the set of irreps [mathjaxinline]\widehat{D_ N}[/mathjaxinline] is as follows. There are two one-dimensional irreps, [mathjaxinline]\sigma _{\text {triv}}[/mathjaxinline] and [mathjaxinline]\sigma _{\text {sign}}[/mathjaxinline] with </p><table id="a0000000023" class="eqnarray" cellspacing="0" cellpadding="7" width="100%" style="table-layout:auto"><tr id="a0000000024"><td style="width:40%; border:none"> </td><td style="vertical-align:middle; text-align:right; border:none"> [mathjaxinline]\displaystyle \sigma _{\text {triv}}(s) = 1[/mathjaxinline] </td><td style="vertical-align:middle; text-align:center; border:none">   </td><td style="vertical-align:middle; text-align:left; border:none"> [mathjaxinline]\displaystyle \sigma _{\text {triv}}(r) = 1[/mathjaxinline] </td><td style="width:40%; border:none"> </td><td class="eqnnum" style="width:20%; border:none"> </td></tr><tr id="a0000000025"><td style="width:40%; border:none"> </td><td style="vertical-align:middle; text-align:right; border:none"> [mathjaxinline]\displaystyle \sigma _{\text {sign}}(s)= 1[/mathjaxinline] </td><td style="vertical-align:middle; text-align:center; border:none">   </td><td style="vertical-align:middle; text-align:left; border:none"> [mathjaxinline]\displaystyle \sigma _{\text {sign}}(r) = -1.[/mathjaxinline] </td><td style="width:40%; border:none"> </td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p> If we assume that [mathjaxinline]N[/mathjaxinline] is odd, then there are also [mathjaxinline](N-1)/2[/mathjaxinline] two-dimensional irreps [mathjaxinline]\sigma _1, \ldots , \sigma _{(N-1)/2}[/mathjaxinline] with </p><table id="a0000000026" class="eqnarray" cellspacing="0" cellpadding="7" width="100%" style="table-layout:auto"><tr id="a0000000027"><td style="width:40%; border:none"> </td><td style="vertical-align:middle; text-align:right; border:none"> [mathjaxinline]\displaystyle \sigma _ j(s)[/mathjaxinline] </td><td style="vertical-align:middle; text-align:center; border:none"> [mathjaxinline]\displaystyle = \begin{pmatrix} e^{2\pi i j/N}&amp; 0 \\ 0 &amp; e^{-2\pi i j/N} \end{pmatrix} .[/mathjaxinline] </td><td style="vertical-align:middle; text-align:center; border:none">   </td><td style="vertical-align:middle; text-align:center; border:none"> [mathjaxinline]\displaystyle \sigma _ j(r)[/mathjaxinline] </td><td style="vertical-align:middle; text-align:left; border:none"> [mathjaxinline]\displaystyle = \begin{pmatrix} 0 &amp; 1 \\ 1 &amp; 0 \end{pmatrix}[/mathjaxinline] </td><td style="width:40%; border:none"> </td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p> We will consider the HSP with hidden subgroup [mathjaxinline]H = \{ 1, s^ yr\}[/mathjaxinline] for some unknown [mathjaxinline]y\in \mathbb {Z}_ N[/mathjaxinline]. </p> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-1"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-1" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="problem" data-runtime-version="1" data-has-score="True" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_ps5a-DHSP-1" class="problems-wrapper" role="group" aria-labelledby="ps5a-DHSP-1-problem-title" data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-1" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-1/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="4" data-attempts-used="0" data-content=" &lt;h3 class=&#34;hd hd-3 problem-header&#34; id=&#34;ps5a-DHSP-1-problem-title&#34; aria-describedby=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-1-problem-progress&#34; tabindex=&#34;-1&#34;&gt; Dihedral HSP and QFT &lt;/h3&gt; &lt;div class=&#34;problem-progress&#34; id=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-1-problem-progress&#34;&gt;&lt;/div&gt; &lt;div class=&#34;problem&#34;&gt; &lt;div&gt; &lt;p&gt; Suppose that we prepare the state [mathjaxinline](2N)^{-1/2}\sum _{g\in D_ N} |{g}\rangle |{f(g)}\rangle[/mathjaxinline], discard the second register, apply [mathjaxinline]F_{D_ N}[/mathjaxinline] and measure [mathjaxinline]\sigma[/mathjaxinline], obtaining outcome [mathjaxinline]\sigma _ j[/mathjaxinline]. We are left with a two-qubit state, which we denote [mathjaxinline]|{\varphi _ j}\rangle[/mathjaxinline], and which you should calculate. You may assume that after discarding the second register we are left with the coset state [mathjaxinline]|{s^ xH}\rangle[/mathjaxinline]. Your answer may depend on [mathjaxinline]j,x,y,N[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]|\varphi _ j\rangle =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 1&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_ps5a-DHSP-1_2_1&#34; class=&#34;text-input-dynamath capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;text-input-dynamath_data inline&#34; data-preprocessor=&#34;MathjaxPreprocessorForQM&#34;/&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/assets/courseware/v1/95fe583d41f010195cf50c9f61992d94/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_H.js&#34;/&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_ps5a-DHSP-1_2_1&#34; id=&#34;input_ps5a-DHSP-1_2_1&#34; aria-describedby=&#34;status_ps5a-DHSP-1_2_1&#34; value=&#34;&#34; class=&#34;math&#34; size=&#34;50&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_ps5a-DHSP-1_2_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-1_2_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_ps5a-DHSP-1_2_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;display_ps5a-DHSP-1_2_1&#34; class=&#34;equation&#34;&gt;`{::}`&lt;/div&gt; &lt;textarea style=&#34;display:none&#34; id=&#34;input_ps5a-DHSP-1_2_1_dynamath&#34; name=&#34;input_ps5a-DHSP-1_2_1_dynamath&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_ps5a-DHSP-1_solution_1&#34;/&gt; &lt;/div&gt;&lt;/p&gt; &lt;p&gt; Recall that the algorithm in lecture applied [mathjaxinline]F_{\mathbb {Z}_ N}[/mathjaxinline], measured, and upon obtaining outcome [mathjaxinline]k[/mathjaxinline], yielded the state [mathjaxinline]|{\psi _ k}\rangle = (|{0}\rangle + e^{2\pi iky}|{1}\rangle )/\sqrt{2}[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; There is a procedure that will transform [mathjaxinline]|{\varphi _ j}\rangle[/mathjaxinline] into [mathjaxinline]|{\psi _ k}\rangle[/mathjaxinline] for some distribution over [mathjaxinline]k[/mathjaxinline] that depends on [mathjaxinline]j[/mathjaxinline]. If we start with a known value of [mathjaxinline]j[/mathjaxinline] then this yields a known value of [mathjaxinline]k[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; What is that procedure? &lt;div class=&#34;wrapper-problem-response&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 2&#34; role=&#34;group&#34;&gt;&lt;div class=&#34;choicegroup capa_inputtype&#34; id=&#34;inputtype_ps5a-DHSP-1_3_1&#34;&gt; &lt;fieldset aria-describedby=&#34;status_ps5a-DHSP-1_3_1&#34;&gt; &lt;div class=&#34;field&#34;&gt; &lt;input type=&#34;radio&#34; name=&#34;input_ps5a-DHSP-1_3_1&#34; id=&#34;input_ps5a-DHSP-1_3_1_choice_1&#34; class=&#34;field-input input-radio&#34; value=&#34;choice_1&#34;/&gt;&lt;label id=&#34;ps5a-DHSP-1_3_1-choice_1-label&#34; for=&#34;input_ps5a-DHSP-1_3_1_choice_1&#34; class=&#34;response-label field-label label-inline&#34; aria-describedby=&#34;status_ps5a-DHSP-1_3_1&#34;&gt; &lt;text&gt; Measure the first qubit.&lt;/text&gt; &lt;/label&gt; &lt;/div&gt; &lt;div class=&#34;field&#34;&gt; &lt;input type=&#34;radio&#34; name=&#34;input_ps5a-DHSP-1_3_1&#34; id=&#34;input_ps5a-DHSP-1_3_1_choice_2&#34; class=&#34;field-input input-radio&#34; value=&#34;choice_2&#34;/&gt;&lt;label id=&#34;ps5a-DHSP-1_3_1-choice_2-label&#34; for=&#34;input_ps5a-DHSP-1_3_1_choice_2&#34; class=&#34;response-label field-label label-inline&#34; aria-describedby=&#34;status_ps5a-DHSP-1_3_1&#34;&gt; &lt;text&gt; Measure the second qubit.&lt;/text&gt; &lt;/label&gt; &lt;/div&gt; &lt;div class=&#34;field&#34;&gt; &lt;input type=&#34;radio&#34; name=&#34;input_ps5a-DHSP-1_3_1&#34; id=&#34;input_ps5a-DHSP-1_3_1_choice_3&#34; class=&#34;field-input input-radio&#34; value=&#34;choice_3&#34;/&gt;&lt;label id=&#34;ps5a-DHSP-1_3_1-choice_3-label&#34; for=&#34;input_ps5a-DHSP-1_3_1_choice_3&#34; class=&#34;response-label field-label label-inline&#34; aria-describedby=&#34;status_ps5a-DHSP-1_3_1&#34;&gt; &lt;text&gt; CNOT from first to second qubit, then measure second qubit.&lt;/text&gt; &lt;/label&gt; &lt;/div&gt; &lt;div class=&#34;field&#34;&gt; &lt;input type=&#34;radio&#34; name=&#34;input_ps5a-DHSP-1_3_1&#34; id=&#34;input_ps5a-DHSP-1_3_1_choice_4&#34; class=&#34;field-input input-radio&#34; value=&#34;choice_4&#34;/&gt;&lt;label id=&#34;ps5a-DHSP-1_3_1-choice_4-label&#34; for=&#34;input_ps5a-DHSP-1_3_1_choice_4&#34; class=&#34;response-label field-label label-inline&#34; aria-describedby=&#34;status_ps5a-DHSP-1_3_1&#34;&gt; &lt;text&gt; CNOT from second to first qubit, then measure first qubit.&lt;/text&gt; &lt;/label&gt; &lt;/div&gt; &lt;div class=&#34;field&#34;&gt; &lt;input type=&#34;radio&#34; name=&#34;input_ps5a-DHSP-1_3_1&#34; id=&#34;input_ps5a-DHSP-1_3_1_choice_5&#34; class=&#34;field-input input-radio&#34; value=&#34;choice_5&#34;/&gt;&lt;label id=&#34;ps5a-DHSP-1_3_1-choice_5-label&#34; for=&#34;input_ps5a-DHSP-1_3_1_choice_5&#34; class=&#34;response-label field-label label-inline&#34; aria-describedby=&#34;status_ps5a-DHSP-1_3_1&#34;&gt; &lt;text&gt; Something else.&lt;/text&gt; &lt;/label&gt; &lt;/div&gt; &lt;span id=&#34;answer_ps5a-DHSP-1_3_1&#34;/&gt; &lt;/fieldset&gt; &lt;div class=&#34;indicator-container&#34;&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-1_3_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; To know [mathjaxinline]k[/mathjaxinline] do we need the outcome of the measurement? &lt;div class=&#34;wrapper-problem-response&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 3&#34; role=&#34;group&#34;&gt;&lt;div class=&#34;choicegroup capa_inputtype&#34; id=&#34;inputtype_ps5a-DHSP-1_4_1&#34;&gt; &lt;fieldset aria-describedby=&#34;status_ps5a-DHSP-1_4_1&#34;&gt; &lt;div class=&#34;field&#34;&gt; &lt;input type=&#34;radio&#34; name=&#34;input_ps5a-DHSP-1_4_1&#34; id=&#34;input_ps5a-DHSP-1_4_1_choice_1&#34; class=&#34;field-input input-radio&#34; value=&#34;choice_1&#34;/&gt;&lt;label id=&#34;ps5a-DHSP-1_4_1-choice_1-label&#34; for=&#34;input_ps5a-DHSP-1_4_1_choice_1&#34; class=&#34;response-label field-label label-inline&#34; aria-describedby=&#34;status_ps5a-DHSP-1_4_1&#34;&gt; &lt;text&gt; Yes&lt;/text&gt; &lt;/label&gt; &lt;/div&gt; &lt;div class=&#34;field&#34;&gt; &lt;input type=&#34;radio&#34; name=&#34;input_ps5a-DHSP-1_4_1&#34; id=&#34;input_ps5a-DHSP-1_4_1_choice_2&#34; class=&#34;field-input input-radio&#34; value=&#34;choice_2&#34;/&gt;&lt;label id=&#34;ps5a-DHSP-1_4_1-choice_2-label&#34; for=&#34;input_ps5a-DHSP-1_4_1_choice_2&#34; class=&#34;response-label field-label label-inline&#34; aria-describedby=&#34;status_ps5a-DHSP-1_4_1&#34;&gt; &lt;text&gt; No&lt;/text&gt; &lt;/label&gt; &lt;/div&gt; &lt;span id=&#34;answer_ps5a-DHSP-1_4_1&#34;/&gt; &lt;/fieldset&gt; &lt;div class=&#34;indicator-container&#34;&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-1_4_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;What value of [mathjaxinline]k[/mathjaxinline] do we obtain? If there are more than one possibility then write any one of them.&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 4&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_ps5a-DHSP-1_5_1&#34; class=&#34;text-input-dynamath capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;text-input-dynamath_data inline&#34; data-preprocessor=&#34;MathjaxPreprocessorForQM&#34;/&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/assets/courseware/v1/95fe583d41f010195cf50c9f61992d94/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_H.js&#34;/&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_ps5a-DHSP-1_5_1&#34; id=&#34;input_ps5a-DHSP-1_5_1&#34; aria-describedby=&#34;status_ps5a-DHSP-1_5_1&#34; value=&#34;&#34; class=&#34;math&#34; size=&#34;50&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_ps5a-DHSP-1_5_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-1_5_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_ps5a-DHSP-1_5_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;display_ps5a-DHSP-1_5_1&#34; class=&#34;equation&#34;&gt;`{::}`&lt;/div&gt; &lt;textarea style=&#34;display:none&#34; id=&#34;input_ps5a-DHSP-1_5_1_dynamath&#34; name=&#34;input_ps5a-DHSP-1_5_1_dynamath&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;/div&gt; &lt;div class=&#34;action&#34;&gt; &lt;input type=&#34;hidden&#34; name=&#34;problem_id&#34; value=&#34;Dihedral HSP and QFT&#34; /&gt; &lt;div class=&#34;submit-attempt-container&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;submit btn-brand&#34; data-submitting=&#34;Submitting&#34; data-value=&#34;Submit&#34; data-should-enable-submit-button=&#34;True&#34; aria-describedby=&#34;submission_feedback_ps5a-DHSP-1&#34; &gt; &lt;span class=&#34;submit-label&#34;&gt;Submit&lt;/span&gt; &lt;/button&gt; &lt;div class=&#34;submission-feedback&#34; id=&#34;submission_feedback_ps5a-DHSP-1&#34;&gt; &lt;span class=&#34;sr&#34;&gt;Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.&lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;problem-action-buttons-wrapper&#34;&gt; &lt;span class=&#34;problem-action-button-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;save problem-action-btn btn-default btn-small&#34; data-value=&#34;Save&#34;&gt; &lt;span class=&#34;icon fa fa-floppy-o&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span aria-hidden=&#34;true&#34;&gt;Save&lt;/span&gt; &lt;span class=&#34;sr&#34;&gt;Save your answer&lt;/span&gt; &lt;/button&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-gentle-alert is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-exclamation-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;ps5a-DHSP-1-problem-title&#34;&gt; &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-save is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-save&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;ps5a-DHSP-1-problem-title&#34;&gt;None &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification general notification-show-answer is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-info-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;ps5a-DHSP-1-problem-title&#34;&gt;Answers are displayed within the problem &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;/div&gt; " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading&hellip;</span> </p> </div> </div> </div> <div class="vert vert-2" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-2"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-2" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="problem" data-runtime-version="1" data-has-score="True" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_ps5a-DHSP-2" class="problems-wrapper" role="group" aria-labelledby="ps5a-DHSP-2-problem-title" data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-2" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-2/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="3" data-attempts-used="0" data-content=" &lt;h3 class=&#34;hd hd-3 problem-header&#34; id=&#34;ps5a-DHSP-2-problem-title&#34; aria-describedby=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-2-problem-progress&#34; tabindex=&#34;-1&#34;&gt; Dihedral HSP - one-dimensional irreps &lt;/h3&gt; &lt;div class=&#34;problem-progress&#34; id=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-2-problem-progress&#34;&gt;&lt;/div&gt; &lt;div class=&#34;problem&#34;&gt; &lt;div&gt; &lt;p&gt; For the algorithm using [mathjaxinline]F_{D_ N}[/mathjaxinline], what is the probability of obtaining the irrep labels [mathjaxinline]\sigma _{\text {triv}}[/mathjaxinline] and [mathjaxinline]\sigma _{\text {sign}}[/mathjaxinline]? &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]\text {Pr}[\sigma _{\text {triv}}]=[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 1&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;formulaequationinput_ps5a-DHSP-2_2_1&#34; class=&#34;inputtype formulaequationinput&#34; style=&#34;display:inline-block;vertical-align:top&#34;&gt; &lt;div class=&#34;unanswered&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_ps5a-DHSP-2_2_1&#34; id=&#34;input_ps5a-DHSP-2_2_1&#34; data-input-id=&#34;ps5a-DHSP-2_2_1&#34; value=&#34;&#34; aria-describedby=&#34;status_ps5a-DHSP-2_2_1&#34; size=&#34;20&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_ps5a-DHSP-2_2_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-2_2_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_ps5a-DHSP-2_2_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;input_ps5a-DHSP-2_2_1_preview&#34; class=&#34;equation&#34;&gt; \(\) &lt;img src=&#34;/static/images/spinner.bc34f953403f.gif&#34; class=&#34;loading&#34; alt=&#34;Loading&#34;/&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/static/js/capa/src/formula_equation_preview.b1967ab28c31.js&#34;/&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]\text {Pr}[\sigma _{\text {sign}}]=[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 2&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;formulaequationinput_ps5a-DHSP-2_3_1&#34; class=&#34;inputtype formulaequationinput&#34; style=&#34;display:inline-block;vertical-align:top&#34;&gt; &lt;div class=&#34;unanswered&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_ps5a-DHSP-2_3_1&#34; id=&#34;input_ps5a-DHSP-2_3_1&#34; data-input-id=&#34;ps5a-DHSP-2_3_1&#34; value=&#34;&#34; aria-describedby=&#34;status_ps5a-DHSP-2_3_1&#34; size=&#34;20&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_ps5a-DHSP-2_3_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-2_3_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_ps5a-DHSP-2_3_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;input_ps5a-DHSP-2_3_1_preview&#34; class=&#34;equation&#34;&gt; \(\) &lt;img src=&#34;/static/images/spinner.bc34f953403f.gif&#34; class=&#34;loading&#34; alt=&#34;Loading&#34;/&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/static/js/capa/src/formula_equation_preview.b1967ab28c31.js&#34;/&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; For the algorithm using [mathjaxinline]F_{\mathbb {Z}_ N}[/mathjaxinline], what is the state [mathjaxinline]|{\psi _{k=0}}\rangle[/mathjaxinline]? &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]|\psi _{k=0}\rangle =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 3&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_ps5a-DHSP-2_4_1&#34; class=&#34;text-input-dynamath capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;text-input-dynamath_data inline&#34; data-preprocessor=&#34;MathjaxPreprocessorForQM&#34;/&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/assets/courseware/v1/95fe583d41f010195cf50c9f61992d94/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_H.js&#34;/&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_ps5a-DHSP-2_4_1&#34; id=&#34;input_ps5a-DHSP-2_4_1&#34; aria-describedby=&#34;status_ps5a-DHSP-2_4_1&#34; value=&#34;&#34; class=&#34;math&#34; size=&#34;50&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_ps5a-DHSP-2_4_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-2_4_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_ps5a-DHSP-2_4_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;display_ps5a-DHSP-2_4_1&#34; class=&#34;equation&#34;&gt;`{::}`&lt;/div&gt; &lt;textarea style=&#34;display:none&#34; id=&#34;input_ps5a-DHSP-2_4_1_dynamath&#34; name=&#34;input_ps5a-DHSP-2_4_1_dynamath&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;/div&gt; &lt;div class=&#34;action&#34;&gt; &lt;input type=&#34;hidden&#34; name=&#34;problem_id&#34; value=&#34;Dihedral HSP - one-dimensional irreps&#34; /&gt; &lt;div class=&#34;submit-attempt-container&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;submit btn-brand&#34; data-submitting=&#34;Submitting&#34; data-value=&#34;Submit&#34; data-should-enable-submit-button=&#34;True&#34; aria-describedby=&#34;submission_feedback_ps5a-DHSP-2&#34; &gt; &lt;span class=&#34;submit-label&#34;&gt;Submit&lt;/span&gt; &lt;/button&gt; &lt;div class=&#34;submission-feedback&#34; id=&#34;submission_feedback_ps5a-DHSP-2&#34;&gt; &lt;span class=&#34;sr&#34;&gt;Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.&lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;problem-action-buttons-wrapper&#34;&gt; &lt;span class=&#34;problem-action-button-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;save problem-action-btn btn-default btn-small&#34; data-value=&#34;Save&#34;&gt; &lt;span class=&#34;icon fa fa-floppy-o&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span aria-hidden=&#34;true&#34;&gt;Save&lt;/span&gt; &lt;span class=&#34;sr&#34;&gt;Save your answer&lt;/span&gt; &lt;/button&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-gentle-alert is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-exclamation-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;ps5a-DHSP-2-problem-title&#34;&gt; &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-save is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-save&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;ps5a-DHSP-2-problem-title&#34;&gt;None &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification general notification-show-answer is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-info-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;ps5a-DHSP-2-problem-title&#34;&gt;Answers are displayed within the problem &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;/div&gt; " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading&hellip;</span> </p> </div> </div> </div> <div class="vert vert-3" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-3"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-3" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="problem" data-runtime-version="1" data-has-score="True" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_ps5a-DHSP-3" class="problems-wrapper" role="group" aria-labelledby="ps5a-DHSP-3-problem-title" data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-3" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-3/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="4" data-attempts-used="0" data-content=" &lt;h3 class=&#34;hd hd-3 problem-header&#34; id=&#34;ps5a-DHSP-3-problem-title&#34; aria-describedby=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-3-problem-progress&#34; tabindex=&#34;-1&#34;&gt; Dihedral HSP - decomposition &lt;/h3&gt; &lt;div class=&#34;problem-progress&#34; id=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps5a-DHSP-3-problem-progress&#34;&gt;&lt;/div&gt; &lt;div class=&#34;problem&#34;&gt; &lt;div&gt; &lt;p&gt; Let [mathjaxinline]\sigma _{j\otimes k} := \sigma _ j \otimes \sigma _ k[/mathjaxinline]. What are [mathjaxinline]\sigma _{j\otimes k}(r)[/mathjaxinline] and[mathjaxinline]\sigma _{j\otimes k}(s)[/mathjaxinline]? To express the matrix [mathjaxinline]\begin{pmatrix} a &amp;amp; b &amp;amp; c &amp;amp; d\\ e &amp;amp; f &amp;amp; g &amp;amp; h \\ i &amp;amp; j &amp;amp; k &amp;amp; l \\ m &amp;amp; n &amp;amp; o &amp;amp; p \end{pmatrix}[/mathjaxinline] you should write [mathjaxinline][[a,b,c,d], [e,f,g,h], [i,j,k,l], [m,n,o,p]][/mathjaxinline]. &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]\sigma _{j\otimes k}(r) =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 1&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_ps5a-DHSP-3_2_1&#34; class=&#34;text-input-dynamath capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;text-input-dynamath_data inline&#34; data-preprocessor=&#34;MathjaxPreprocessorForQM&#34;/&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/assets/courseware/v1/95fe583d41f010195cf50c9f61992d94/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_H.js&#34;/&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_ps5a-DHSP-3_2_1&#34; id=&#34;input_ps5a-DHSP-3_2_1&#34; aria-describedby=&#34;status_ps5a-DHSP-3_2_1&#34; value=&#34;&#34; class=&#34;math&#34; size=&#34;50&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_ps5a-DHSP-3_2_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-3_2_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_ps5a-DHSP-3_2_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;display_ps5a-DHSP-3_2_1&#34; class=&#34;equation&#34;&gt;`{::}`&lt;/div&gt; &lt;textarea style=&#34;display:none&#34; id=&#34;input_ps5a-DHSP-3_2_1_dynamath&#34; name=&#34;input_ps5a-DHSP-3_2_1_dynamath&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]\sigma _{j\otimes k}(s) =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 2&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_ps5a-DHSP-3_3_1&#34; class=&#34;text-input-dynamath capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;text-input-dynamath_data inline&#34; data-preprocessor=&#34;MathjaxPreprocessorForQM&#34;/&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/assets/courseware/v1/95fe583d41f010195cf50c9f61992d94/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_H.js&#34;/&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_ps5a-DHSP-3_3_1&#34; id=&#34;input_ps5a-DHSP-3_3_1&#34; aria-describedby=&#34;status_ps5a-DHSP-3_3_1&#34; value=&#34;&#34; class=&#34;math&#34; size=&#34;50&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_ps5a-DHSP-3_3_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-3_3_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_ps5a-DHSP-3_3_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;display_ps5a-DHSP-3_3_1&#34; class=&#34;equation&#34;&gt;`{::}`&lt;/div&gt; &lt;textarea style=&#34;display:none&#34; id=&#34;input_ps5a-DHSP-3_3_1_dynamath&#34; name=&#34;input_ps5a-DHSP-3_3_1_dynamath&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; It turns out that [mathjaxinline]\sigma _{j\otimes k}[/mathjaxinline] is equivalent to the representation [mathjaxinline]\sigma _{l+m} \oplus \sigma _{l-m}[/mathjaxinline]. (Equivalence of representations was defined in class.) What are [mathjaxinline]l,m?[/mathjaxinline] &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]l=[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 3&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_ps5a-DHSP-3_4_1&#34; class=&#34;text-input-dynamath capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;text-input-dynamath_data inline&#34; data-preprocessor=&#34;MathjaxPreprocessorForQM&#34;/&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/assets/courseware/v1/95fe583d41f010195cf50c9f61992d94/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_H.js&#34;/&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_ps5a-DHSP-3_4_1&#34; id=&#34;input_ps5a-DHSP-3_4_1&#34; aria-describedby=&#34;status_ps5a-DHSP-3_4_1&#34; value=&#34;&#34; class=&#34;math&#34; size=&#34;50&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_ps5a-DHSP-3_4_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-3_4_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_ps5a-DHSP-3_4_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;display_ps5a-DHSP-3_4_1&#34; class=&#34;equation&#34;&gt;`{::}`&lt;/div&gt; &lt;textarea style=&#34;display:none&#34; id=&#34;input_ps5a-DHSP-3_4_1_dynamath&#34; name=&#34;input_ps5a-DHSP-3_4_1_dynamath&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]m=[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 4&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_ps5a-DHSP-3_5_1&#34; class=&#34;text-input-dynamath capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;text-input-dynamath_data inline&#34; data-preprocessor=&#34;MathjaxPreprocessorForQM&#34;/&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/assets/courseware/v1/95fe583d41f010195cf50c9f61992d94/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_H.js&#34;/&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_ps5a-DHSP-3_5_1&#34; id=&#34;input_ps5a-DHSP-3_5_1&#34; aria-describedby=&#34;status_ps5a-DHSP-3_5_1&#34; value=&#34;&#34; class=&#34;math&#34; size=&#34;50&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_ps5a-DHSP-3_5_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_ps5a-DHSP-3_5_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_ps5a-DHSP-3_5_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;display_ps5a-DHSP-3_5_1&#34; class=&#34;equation&#34;&gt;`{::}`&lt;/div&gt; &lt;textarea style=&#34;display:none&#34; id=&#34;input_ps5a-DHSP-3_5_1_dynamath&#34; name=&#34;input_ps5a-DHSP-3_5_1_dynamath&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; Such a decomposition of a tensor product of irreps is known as a Clebsch-Gordan transformation. At the same time, we see that the irrep indices [mathjaxinline]j,k[/mathjaxinline] transform in a way similar to what happened with the Kuperberg sieve algorithm that was presented in lecture. This is an indication that the sieve algorithm can be reinterpreted in representation-theoretic terms. Thinking about it this way has been useful to researchers in finding versions of the Kuperberg sieve (also known as a Clebsch-Gordan sieve) for the &lt;a href=&#34;https://arxiv.org/abs/quant-ph/0612107&#34; target=&#34;_blank&#34;&gt;Heisenberg group&lt;/a&gt;, the &lt;a href=&#34;https://arxiv.org/abs/quant-ph/0609138&#34; target=&#34;_blank&#34;&gt;symmetric group&lt;/a&gt;, and &lt;a href=&#34;https://arxiv.org/abs/0808.0174&#34; target=&#34;_blank&#34;&gt;product groups&lt;/a&gt;. &lt;/p&gt; &lt;/div&gt; &lt;div class=&#34;action&#34;&gt; &lt;input type=&#34;hidden&#34; name=&#34;problem_id&#34; value=&#34;Dihedral HSP - decomposition&#34; /&gt; &lt;div class=&#34;submit-attempt-container&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;submit btn-brand&#34; data-submitting=&#34;Submitting&#34; data-value=&#34;Submit&#34; data-should-enable-submit-button=&#34;True&#34; aria-describedby=&#34;submission_feedback_ps5a-DHSP-3&#34; &gt; &lt;span class=&#34;submit-label&#34;&gt;Submit&lt;/span&gt; &lt;/button&gt; &lt;div class=&#34;submission-feedback&#34; id=&#34;submission_feedback_ps5a-DHSP-3&#34;&gt; &lt;span class=&#34;sr&#34;&gt;Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.&lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;problem-action-buttons-wrapper&#34;&gt; &lt;span class=&#34;problem-action-button-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;save problem-action-btn btn-default btn-small&#34; data-value=&#34;Save&#34;&gt; &lt;span class=&#34;icon fa fa-floppy-o&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span aria-hidden=&#34;true&#34;&gt;Save&lt;/span&gt; &lt;span class=&#34;sr&#34;&gt;Save your answer&lt;/span&gt; &lt;/button&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-gentle-alert is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-exclamation-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;ps5a-DHSP-3-problem-title&#34;&gt; &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-save is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-save&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;ps5a-DHSP-3-problem-title&#34;&gt;None &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification general notification-show-answer is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-info-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;ps5a-DHSP-3-problem-title&#34;&gt;Answers are displayed within the problem &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;/div&gt; " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading&hellip;</span> </p> </div> </div> </div> <div class="vert vert-4" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box2xxxx"> <div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box2xxxx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="html" data-runtime-version="1" data-has-score="False" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "HTMLModule"} </script> <span><a href="/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/NONE" id="dummy_course_static_link" style="display:none"/><a href="/courses/course-v1:MITx+8.371.3x+2T2018/jump_to_id/NONE" id="dummy_jump_link" style="display:none"/><script type="text/javascript"> var add_site_search = function(){ course_static_url = $('#dummy_course_static_link').attr('href').replace('/NONE', ''); jump_to_url = $('#dummy_jump_link').attr('href').replace('/NONE', ''); if (typeof String.prototype.startsWith != 'function') { // see below for better implementation! String.prototype.startsWith = function (str){ return this.indexOf(str) === 0; }; } if(typeof(String.prototype.trim) === "undefined") { String.prototype.trim = function() { return String(this).replace(/^\s+|\s+$/g, ''); }; } var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var amp = String.fromCharCode(38); var rlb = rb + lb; var mke = function(x){ return lb + x + rb; } var search_module_url = ""; var get_search_module_ficus = function(){ var cid = $('div.xblock').data('course-id'); if (cid){ console.log("cid = ", cid); // search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/" + cid + "/courseware/welcome/Search_this_course/"; search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/courseware/welcome/Search_this_course/"; // automatically rewritten console.log("3. search_module_url = ", search_module_url); return; } var course_root_link = $('span.nav-item-course').find('a').attr('href'); if (course_root_link){ console.log("course_root_link = ", course_root_link); search_module_url = course_root_link.replace("course/", "courseware/welcome/Search_this_course/"); console.log("2. search_module_url = ", search_module_url); return } console.log("cannot determine search module url"); } var get_search_module = function(){ // find search this module link if (!($('div.course-index').length)){ return get_search_module_ficus(); } $('div.course-index').find('nav').find('a').each(function(){ if ($(this).text().trim().startsWith("Search this course")){ search_module_url = $(this).attr('href'); console.log("search_module_url = ", search_module_url); } }); } var go_to_search = function(){ get_search_module(); var sterm = $('#site-search-box').val(); // new_url = jump_to_url + "/Search_this_module/?q=" + sterm; new_url = search_module_url + "?q=" + sterm; console.log("sterm = ", sterm, " ; going to ", new_url); window.location.href = new_url; } if (!$('#site-search-box').length){ $("nav.courseware").find("ol").append(lb + "section style='float:right'" + rlb + "input size='20'" + " id='site-search-box'" + rlb + "img src='" + course_static_url + "/images_search_glass.png'/" + rlb + "/input" + rlb + "/section" + rb); } $("#site-search-box").keypress(function(event) { if (event.which == 13) { event.preventDefault(); go_to_search(); } }); // $('#site-search-box').bind("enterKey", go_to_search); var get = function(x){ return eval(x); } return {'course_static_url': course_static_url, 'jump_to_url': jump_to_url, 'go_to_search': go_to_search, 'get_search_module': get_search_module, 'get_search_module_ficus': get_search_module_ficus, 'get': get, } } var the_site_search = add_site_search(); var add_fix_transcript = function(){ if ($('div.wrap-instructor-info').length==0){ return; } $('div.xblock-student_view-video').each(function(key, vblock_e){ var vblock = $(vblock_e); var vuid = vblock.data('usage-id').split('@'); var vid; if (vuid.length==1){ vuid = vblock.data('usage-id').split(';_') vid = vuid[5]; }else{ vid = vuid[2]; } var mfnpre = vid.split("_video",1)[0]; var mfnid = mfnpre; // no periods mfnpre = mfnpre.replace('8_370', '8.370'); // periods in gh filename var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var mke = function(x){ return lb + x + rb; } var ftid = "fix_transcript_" + mfnid; if (!$('#' + ftid).length){ var html = lb + "span id='" + ftid + "' style='float:right'" + rb + lb + "a href='#'" + rb; html += "contribute transcript fix" + mke("/a") + mke("/span"); console.log("html = ", html); vblock.after(html) } $('#' + ftid).click(function(){ var cst = $('ol.subtitles').find('li.current'); var cindex = Number(cst.data('index')); var gurl; if (mfnpre.endsWith('_cq_sol')){ gurl = "https://github.com/mitocw/content-mit-8370x-cq-sol-subtitles/blob/master/"; }else{ gurl = "https://github.com/mitocw/content-mit-8370x-subtitles/blob/master/"; } gurl += mfnpre + ".txt#L" + String(cindex + 10 + 1); console.log("going to ", gurl); window.open(gurl, "MITx 8.370x subtitle source"); }); }); } try{ add_fix_transcript(); } catch(err){ console.log(err); } try{ var rb = String.fromCharCode(62); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 3000); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 8000); } catch(err){ console.log(err); } </script></span> </div> </div> </div> </div>

<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@vertical+block@Classical_and_quantum_entropy_I" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True"> <h2 class="hd hd-2 unit-title">Classical and quantum entropy I</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-entropy"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-entropy" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="problem" data-runtime-version="1" data-has-score="True" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_s12-wk10-entropy" class="problems-wrapper" role="group" aria-labelledby="s12-wk10-entropy-problem-title" data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-entropy" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-entropy/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="5" data-attempts-used="0" data-content=" &lt;h3 class=&#34;hd hd-3 problem-header&#34; id=&#34;s12-wk10-entropy-problem-title&#34; aria-describedby=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-entropy-problem-progress&#34; tabindex=&#34;-1&#34;&gt; Exercises with entropy &lt;/h3&gt; &lt;div class=&#34;problem-progress&#34; id=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-entropy-problem-progress&#34;&gt;&lt;/div&gt; &lt;div class=&#34;problem&#34;&gt; &lt;div&gt; &lt;p&gt; &lt;span/&gt; &lt;/p&gt; &lt;p&gt; With three games remaining in the baseball season, the Reds and the Giants are tied for first place. Depending on the outcomes of the final three games, which are played against other teams, either the Reds or the Giants will win the championship or they will tie. &lt;/p&gt; &lt;ol class=&#34;enumerate&#34;&gt; &lt;li value=&#34;1&#34;&gt; &lt;p&gt; Assume that each of the remaining games played by the contending teams are won or lost with probability [mathjaxinline]1/2[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; Let [mathjaxinline]R[/mathjaxinline] be a random variable whose outcomes are { win, lose, tie} for the Reds. &lt;/p&gt; &lt;p&gt; What are the probabilities of each of the three possible outcomes? Enter each result as a decimal number, correct to within 1%. &lt;/p&gt; &lt;ul class=&#34;itemize&#34;&gt; &lt;li&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]P(\hbox{win}) =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 1&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_s12-wk10-entropy_2_1&#34; class=&#34; capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_s12-wk10-entropy_2_1&#34; id=&#34;input_s12-wk10-entropy_2_1&#34; aria-describedby=&#34;status_s12-wk10-entropy_2_1&#34; value=&#34;&#34; size=&#34;30&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_s12-wk10-entropy_2_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_s12-wk10-entropy_2_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_s12-wk10-entropy_2_1&#34; class=&#34;answer&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;/li&gt; &lt;li&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]P(\hbox{lose}) =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 2&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_s12-wk10-entropy_3_1&#34; class=&#34; capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_s12-wk10-entropy_3_1&#34; id=&#34;input_s12-wk10-entropy_3_1&#34; aria-describedby=&#34;status_s12-wk10-entropy_3_1&#34; value=&#34;&#34; size=&#34;30&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_s12-wk10-entropy_3_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_s12-wk10-entropy_3_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_s12-wk10-entropy_3_1&#34; class=&#34;answer&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;/li&gt; &lt;li&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]P(\hbox{tie}) =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 3&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_s12-wk10-entropy_4_1&#34; class=&#34; capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_s12-wk10-entropy_4_1&#34; id=&#34;input_s12-wk10-entropy_4_1&#34; aria-describedby=&#34;status_s12-wk10-entropy_4_1&#34; value=&#34;&#34; size=&#34;30&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_s12-wk10-entropy_4_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_s12-wk10-entropy_4_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_s12-wk10-entropy_4_1&#34; class=&#34;answer&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;/li&gt; &lt;/ul&gt; &lt;p&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_s12-wk10-entropy_solution_1&#34;/&gt; &lt;/div&gt;&lt;/p&gt; &lt;/li&gt; &lt;li value=&#34;2&#34;&gt; &lt;p&gt; Compute the &lt;a href=&#34;http://en.wikipedia.org/wiki/Entropy_(information_theory)&#34; target=&#34;_blank&#34;&gt;entropy&lt;/a&gt; of [mathjaxinline]R[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; Express your answer in units of &lt;em&gt;bits&lt;/em&gt;, and give the result as a decimal number within 1% of the exact answer. &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]H(R) =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 4&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_s12-wk10-entropy_5_1&#34; class=&#34; capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_s12-wk10-entropy_5_1&#34; id=&#34;input_s12-wk10-entropy_5_1&#34; aria-describedby=&#34;status_s12-wk10-entropy_5_1&#34; value=&#34;&#34; size=&#34;30&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_s12-wk10-entropy_5_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_s12-wk10-entropy_5_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_s12-wk10-entropy_5_1&#34; class=&#34;answer&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;p&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_s12-wk10-entropy_solution_2&#34;/&gt; &lt;/div&gt;&lt;/p&gt; &lt;/li&gt; &lt;li value=&#34;3&#34;&gt; &lt;p&gt; Assume that the Giants win all three games against their feeble opponents. Compute the conditional entropy of the random variable whose outcomes are {win, lose, tie} for the Reds, given this assumption. &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]H(R) =[/mathjaxinline]&lt;/p&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 5&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_s12-wk10-entropy_6_1&#34; class=&#34; capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_s12-wk10-entropy_6_1&#34; id=&#34;input_s12-wk10-entropy_6_1&#34; aria-describedby=&#34;status_s12-wk10-entropy_6_1&#34; value=&#34;&#34; size=&#34;30&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_s12-wk10-entropy_6_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_s12-wk10-entropy_6_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_s12-wk10-entropy_6_1&#34; class=&#34;answer&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/p&gt; &lt;/li&gt; &lt;/ol&gt; &lt;p&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_s12-wk10-entropy_solution_3&#34;/&gt; &lt;/div&gt;&lt;/p&gt; &lt;/div&gt; &lt;div class=&#34;action&#34;&gt; &lt;input type=&#34;hidden&#34; name=&#34;problem_id&#34; value=&#34;Exercises with entropy&#34; /&gt; &lt;div class=&#34;submit-attempt-container&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;submit btn-brand&#34; data-submitting=&#34;Submitting&#34; data-value=&#34;Submit&#34; data-should-enable-submit-button=&#34;True&#34; aria-describedby=&#34;submission_feedback_s12-wk10-entropy&#34; &gt; &lt;span class=&#34;submit-label&#34;&gt;Submit&lt;/span&gt; &lt;/button&gt; &lt;div class=&#34;submission-feedback&#34; id=&#34;submission_feedback_s12-wk10-entropy&#34;&gt; &lt;span class=&#34;sr&#34;&gt;Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.&lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;problem-action-buttons-wrapper&#34;&gt; &lt;span class=&#34;problem-action-button-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;save problem-action-btn btn-default btn-small&#34; data-value=&#34;Save&#34;&gt; &lt;span class=&#34;icon fa fa-floppy-o&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span aria-hidden=&#34;true&#34;&gt;Save&lt;/span&gt; &lt;span class=&#34;sr&#34;&gt;Save your answer&lt;/span&gt; &lt;/button&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-gentle-alert is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-exclamation-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;s12-wk10-entropy-problem-title&#34;&gt; &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-save is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-save&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;s12-wk10-entropy-problem-title&#34;&gt;None &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification general notification-show-answer is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-info-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;s12-wk10-entropy-problem-title&#34;&gt;Answers are displayed within the problem &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;/div&gt; " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading&hellip;</span> </p> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box1xxxxx"> <div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box1xxxxx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="html" data-runtime-version="1" data-has-score="False" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "HTMLModule"} </script> <span><a href="/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/NONE" id="dummy_course_static_link" style="display:none"/><a href="/courses/course-v1:MITx+8.371.3x+2T2018/jump_to_id/NONE" id="dummy_jump_link" style="display:none"/><script type="text/javascript"> var add_site_search = function(){ course_static_url = $('#dummy_course_static_link').attr('href').replace('/NONE', ''); jump_to_url = $('#dummy_jump_link').attr('href').replace('/NONE', ''); if (typeof String.prototype.startsWith != 'function') { // see below for better implementation! String.prototype.startsWith = function (str){ return this.indexOf(str) === 0; }; } if(typeof(String.prototype.trim) === "undefined") { String.prototype.trim = function() { return String(this).replace(/^\s+|\s+$/g, ''); }; } var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var amp = String.fromCharCode(38); var rlb = rb + lb; var mke = function(x){ return lb + x + rb; } var search_module_url = ""; var get_search_module_ficus = function(){ var cid = $('div.xblock').data('course-id'); if (cid){ console.log("cid = ", cid); // search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/" + cid + "/courseware/welcome/Search_this_course/"; search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/courseware/welcome/Search_this_course/"; // automatically rewritten console.log("3. search_module_url = ", search_module_url); return; } var course_root_link = $('span.nav-item-course').find('a').attr('href'); if (course_root_link){ console.log("course_root_link = ", course_root_link); search_module_url = course_root_link.replace("course/", "courseware/welcome/Search_this_course/"); console.log("2. search_module_url = ", search_module_url); return } console.log("cannot determine search module url"); } var get_search_module = function(){ // find search this module link if (!($('div.course-index').length)){ return get_search_module_ficus(); } $('div.course-index').find('nav').find('a').each(function(){ if ($(this).text().trim().startsWith("Search this course")){ search_module_url = $(this).attr('href'); console.log("search_module_url = ", search_module_url); } }); } var go_to_search = function(){ get_search_module(); var sterm = $('#site-search-box').val(); // new_url = jump_to_url + "/Search_this_module/?q=" + sterm; new_url = search_module_url + "?q=" + sterm; console.log("sterm = ", sterm, " ; going to ", new_url); window.location.href = new_url; } if (!$('#site-search-box').length){ $("nav.courseware").find("ol").append(lb + "section style='float:right'" + rlb + "input size='20'" + " id='site-search-box'" + rlb + "img src='" + course_static_url + "/images_search_glass.png'/" + rlb + "/input" + rlb + "/section" + rb); } $("#site-search-box").keypress(function(event) { if (event.which == 13) { event.preventDefault(); go_to_search(); } }); // $('#site-search-box').bind("enterKey", go_to_search); var get = function(x){ return eval(x); } return {'course_static_url': course_static_url, 'jump_to_url': jump_to_url, 'go_to_search': go_to_search, 'get_search_module': get_search_module, 'get_search_module_ficus': get_search_module_ficus, 'get': get, } } var the_site_search = add_site_search(); var add_fix_transcript = function(){ if ($('div.wrap-instructor-info').length==0){ return; } $('div.xblock-student_view-video').each(function(key, vblock_e){ var vblock = $(vblock_e); var vuid = vblock.data('usage-id').split('@'); var vid; if (vuid.length==1){ vuid = vblock.data('usage-id').split(';_') vid = vuid[5]; }else{ vid = vuid[2]; } var mfnpre = vid.split("_video",1)[0]; var mfnid = mfnpre; // no periods mfnpre = mfnpre.replace('8_370', '8.370'); // periods in gh filename var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var mke = function(x){ return lb + x + rb; } var ftid = "fix_transcript_" + mfnid; if (!$('#' + ftid).length){ var html = lb + "span id='" + ftid + "' style='float:right'" + rb + lb + "a href='#'" + rb; html += "contribute transcript fix" + mke("/a") + mke("/span"); console.log("html = ", html); vblock.after(html) } $('#' + ftid).click(function(){ var cst = $('ol.subtitles').find('li.current'); var cindex = Number(cst.data('index')); var gurl; if (mfnpre.endsWith('_cq_sol')){ gurl = "https://github.com/mitocw/content-mit-8370x-cq-sol-subtitles/blob/master/"; }else{ gurl = "https://github.com/mitocw/content-mit-8370x-subtitles/blob/master/"; } gurl += mfnpre + ".txt#L" + String(cindex + 10 + 1); console.log("going to ", gurl); window.open(gurl, "MITx 8.370x subtitle source"); }); }); } try{ add_fix_transcript(); } catch(err){ console.log(err); } try{ var rb = String.fromCharCode(62); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 3000); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 8000); } catch(err){ console.log(err); } </script></span> </div> </div> </div> </div>

<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@vertical+block@Classical_and_quantum_entropy_II" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True"> <h2 class="hd hd-2 unit-title">Classical and quantum entropy II</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-vn-entropy"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-vn-entropy" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="problem" data-runtime-version="1" data-has-score="True" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_s12-wk10-vn-entropy" class="problems-wrapper" role="group" aria-labelledby="s12-wk10-vn-entropy-problem-title" data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-vn-entropy" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-vn-entropy/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="1" data-attempts-used="0" data-content=" &lt;h3 class=&#34;hd hd-3 problem-header&#34; id=&#34;s12-wk10-vn-entropy-problem-title&#34; aria-describedby=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-vn-entropy-problem-progress&#34; tabindex=&#34;-1&#34;&gt; Von Neumann entropy of a qubit &lt;/h3&gt; &lt;div class=&#34;problem-progress&#34; id=&#34;block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk10-vn-entropy-problem-progress&#34;&gt;&lt;/div&gt; &lt;div class=&#34;problem&#34;&gt; &lt;div&gt; &lt;p&gt; Let [mathjaxinline]\rho[/mathjaxinline] be a single qubit state (a density matrix), and recall the Bloch sphere representation &lt;/p&gt; &lt;table id=&#34;a0000000056&#34; class=&#34;equation&#34; width=&#34;100%&#34; cellspacing=&#34;0&#34; cellpadding=&#34;7&#34; style=&#34;table-layout:auto&#34;&gt; &lt;tr&gt; &lt;td class=&#34;equation&#34; style=&#34;width:80%; border:none&#34;&gt;[mathjax]\rho = \frac{I + \sum _{k=1}^3 r_ k \sigma _ k}{2} \, ,[/mathjax]&lt;/td&gt; &lt;td class=&#34;eqnnum&#34; style=&#34;width:20%; border:none;text-align:right&#34;&gt;(1.32)&lt;/td&gt; &lt;/tr&gt; &lt;/table&gt; &lt;p&gt; where [mathjaxinline]\sigma _ k[/mathjaxinline] are the three Pauli matrices. &lt;/p&gt; &lt;p&gt; Express [mathjaxinline]S(\rho ) = -{\rm tr}(\rho \log \rho )[/mathjaxinline] in terms of [mathjaxinline]\vec{r} = (r_ x, r_ y, r_ z)[/mathjaxinline] and the binary entropy function [mathjaxinline]H(p) = -p \log p - (1-p) \log (1-p)[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; Enter your response using [mathjaxinline]{\tt H(\cdots )}[/mathjaxinline] for the binary entropy function, [mathjaxinline]{\tt rx}[/mathjaxinline], [mathjaxinline]{\tt ry}[/mathjaxinline], [mathjaxinline]{\tt rz}[/mathjaxinline], for the components of [mathjaxinline]\vec{r}[/mathjaxinline], and [mathjaxinline]{\tt r}[/mathjaxinline] for [mathjaxinline]|\vec{r}|[/mathjaxinline]. A valid entry would thus be [mathjaxinline]{\tt 1+H(rx)+H(r)}[/mathjaxinline]. &lt;/p&gt; &lt;p&gt; &lt;p style=&#34;display:inline&#34;&gt;[mathjaxinline]S(\rho ) =[/mathjaxinline]&lt;/p&gt; &lt;span&gt; &lt;div class=&#34;inline&#34; tabindex=&#34;-1&#34; aria-label=&#34;Question 1&#34; role=&#34;group&#34;&gt;&lt;div id=&#34;inputtype_s12-wk10-vn-entropy_2_1&#34; class=&#34;text-input-dynamath capa_inputtype inline textline&#34;&gt; &lt;div class=&#34;text-input-dynamath_data inline&#34; data-preprocessor=&#34;MathjaxPreprocessorForQM&#34;/&gt; &lt;div class=&#34;script_placeholder&#34; data-src=&#34;/assets/courseware/v1/dc8916af8ae257e4388dae38f570cb8b/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_subtext.js&#34;/&gt; &lt;div class=&#34;unanswered inline&#34;&gt; &lt;input type=&#34;text&#34; name=&#34;input_s12-wk10-vn-entropy_2_1&#34; id=&#34;input_s12-wk10-vn-entropy_2_1&#34; aria-describedby=&#34;status_s12-wk10-vn-entropy_2_1&#34; value=&#34;&#34; class=&#34;math&#34; size=&#34;70&#34;/&gt; &lt;span class=&#34;trailing_text&#34; id=&#34;trailing_text_s12-wk10-vn-entropy_2_1&#34;/&gt; &lt;span class=&#34;status unanswered&#34; id=&#34;status_s12-wk10-vn-entropy_2_1&#34; data-tooltip=&#34;Not yet answered.&#34;&gt; &lt;span class=&#34;sr&#34;&gt;unanswered&lt;/span&gt;&lt;span class=&#34;status-icon&#34; aria-hidden=&#34;true&#34;/&gt; &lt;/span&gt; &lt;p id=&#34;answer_s12-wk10-vn-entropy_2_1&#34; class=&#34;answer&#34;/&gt; &lt;div id=&#34;display_s12-wk10-vn-entropy_2_1&#34; class=&#34;equation&#34;&gt;`{::}`&lt;/div&gt; &lt;textarea style=&#34;display:none&#34; id=&#34;input_s12-wk10-vn-entropy_2_1_dynamath&#34; name=&#34;input_s12-wk10-vn-entropy_2_1_dynamath&#34;/&gt; &lt;/div&gt; &lt;/div&gt;&lt;/div&gt; &lt;/span&gt; &lt;/p&gt; &lt;p&gt; &lt;div class=&#34;solution-span&#34;&gt; &lt;span id=&#34;solution_s12-wk10-vn-entropy_solution_1&#34;/&gt; &lt;/div&gt;&lt;/p&gt; &lt;/div&gt; &lt;div class=&#34;action&#34;&gt; &lt;input type=&#34;hidden&#34; name=&#34;problem_id&#34; value=&#34;Von Neumann entropy of a qubit&#34; /&gt; &lt;div class=&#34;submit-attempt-container&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;submit btn-brand&#34; data-submitting=&#34;Submitting&#34; data-value=&#34;Submit&#34; data-should-enable-submit-button=&#34;True&#34; aria-describedby=&#34;submission_feedback_s12-wk10-vn-entropy&#34; &gt; &lt;span class=&#34;submit-label&#34;&gt;Submit&lt;/span&gt; &lt;/button&gt; &lt;div class=&#34;submission-feedback&#34; id=&#34;submission_feedback_s12-wk10-vn-entropy&#34;&gt; &lt;span class=&#34;sr&#34;&gt;Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.&lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;problem-action-buttons-wrapper&#34;&gt; &lt;span class=&#34;problem-action-button-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;save problem-action-btn btn-default btn-small&#34; data-value=&#34;Save&#34;&gt; &lt;span class=&#34;icon fa fa-floppy-o&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span aria-hidden=&#34;true&#34;&gt;Save&lt;/span&gt; &lt;span class=&#34;sr&#34;&gt;Save your answer&lt;/span&gt; &lt;/button&gt; &lt;/span&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-gentle-alert is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-exclamation-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;s12-wk10-vn-entropy-problem-title&#34;&gt; &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification warning notification-save is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-save&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;s12-wk10-vn-entropy-problem-title&#34;&gt;None &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;div class=&#34;notification general notification-show-answer is-hidden&#34; tabindex=&#34;-1&#34;&gt; &lt;span class=&#34;icon fa fa-info-circle&#34; aria-hidden=&#34;true&#34;&gt;&lt;/span&gt; &lt;span class=&#34;notification-message&#34; aria-describedby=&#34;s12-wk10-vn-entropy-problem-title&#34;&gt;Answers are displayed within the problem &lt;/span&gt; &lt;div class=&#34;notification-btn-wrapper&#34;&gt; &lt;button type=&#34;button&#34; class=&#34;btn btn-default btn-small notification-btn review-btn sr&#34;&gt;Review&lt;/button&gt; &lt;/div&gt; &lt;/div&gt; &lt;/div&gt; " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading&hellip;</span> </p> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box1xxxxxx"> <div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box1xxxxxx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="f8c19530886011ef87990affec87671b" data-block-type="html" data-runtime-version="1" data-has-score="False" data-graded="True"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "HTMLModule"} </script> <span><a href="/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/NONE" id="dummy_course_static_link" style="display:none"/><a href="/courses/course-v1:MITx+8.371.3x+2T2018/jump_to_id/NONE" id="dummy_jump_link" style="display:none"/><script type="text/javascript"> var add_site_search = function(){ course_static_url = $('#dummy_course_static_link').attr('href').replace('/NONE', ''); jump_to_url = $('#dummy_jump_link').attr('href').replace('/NONE', ''); if (typeof String.prototype.startsWith != 'function') { // see below for better implementation! String.prototype.startsWith = function (str){ return this.indexOf(str) === 0; }; } if(typeof(String.prototype.trim) === "undefined") { String.prototype.trim = function() { return String(this).replace(/^\s+|\s+$/g, ''); }; } var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var amp = String.fromCharCode(38); var rlb = rb + lb; var mke = function(x){ return lb + x + rb; } var search_module_url = ""; var get_search_module_ficus = function(){ var cid = $('div.xblock').data('course-id'); if (cid){ console.log("cid = ", cid); // search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/" + cid + "/courseware/welcome/Search_this_course/"; search_module_url = "/courses/course-v1:MITx+8.371.3x+2T2018/courseware/welcome/Search_this_course/"; // automatically rewritten console.log("3. search_module_url = ", search_module_url); return; } var course_root_link = $('span.nav-item-course').find('a').attr('href'); if (course_root_link){ console.log("course_root_link = ", course_root_link); search_module_url = course_root_link.replace("course/", "courseware/welcome/Search_this_course/"); console.log("2. search_module_url = ", search_module_url); return } console.log("cannot determine search module url"); } var get_search_module = function(){ // find search this module link if (!($('div.course-index').length)){ return get_search_module_ficus(); } $('div.course-index').find('nav').find('a').each(function(){ if ($(this).text().trim().startsWith("Search this course")){ search_module_url = $(this).attr('href'); console.log("search_module_url = ", search_module_url); } }); } var go_to_search = function(){ get_search_module(); var sterm = $('#site-search-box').val(); // new_url = jump_to_url + "/Search_this_module/?q=" + sterm; new_url = search_module_url + "?q=" + sterm; console.log("sterm = ", sterm, " ; going to ", new_url); window.location.href = new_url; } if (!$('#site-search-box').length){ $("nav.courseware").find("ol").append(lb + "section style='float:right'" + rlb + "input size='20'" + " id='site-search-box'" + rlb + "img src='" + course_static_url + "/images_search_glass.png'/" + rlb + "/input" + rlb + "/section" + rb); } $("#site-search-box").keypress(function(event) { if (event.which == 13) { event.preventDefault(); go_to_search(); } }); // $('#site-search-box').bind("enterKey", go_to_search); var get = function(x){ return eval(x); } return {'course_static_url': course_static_url, 'jump_to_url': jump_to_url, 'go_to_search': go_to_search, 'get_search_module': get_search_module, 'get_search_module_ficus': get_search_module_ficus, 'get': get, } } var the_site_search = add_site_search(); var add_fix_transcript = function(){ if ($('div.wrap-instructor-info').length==0){ return; } $('div.xblock-student_view-video').each(function(key, vblock_e){ var vblock = $(vblock_e); var vuid = vblock.data('usage-id').split('@'); var vid; if (vuid.length==1){ vuid = vblock.data('usage-id').split(';_') vid = vuid[5]; }else{ vid = vuid[2]; } var mfnpre = vid.split("_video",1)[0]; var mfnid = mfnpre; // no periods mfnpre = mfnpre.replace('8_370', '8.370'); // periods in gh filename var lb = String.fromCharCode(60); var rb = String.fromCharCode(62); var mke = function(x){ return lb + x + rb; } var ftid = "fix_transcript_" + mfnid; if (!$('#' + ftid).length){ var html = lb + "span id='" + ftid + "' style='float:right'" + rb + lb + "a href='#'" + rb; html += "contribute transcript fix" + mke("/a") + mke("/span"); console.log("html = ", html); vblock.after(html) } $('#' + ftid).click(function(){ var cst = $('ol.subtitles').find('li.current'); var cindex = Number(cst.data('index')); var gurl; if (mfnpre.endsWith('_cq_sol')){ gurl = "https://github.com/mitocw/content-mit-8370x-cq-sol-subtitles/blob/master/"; }else{ gurl = "https://github.com/mitocw/content-mit-8370x-subtitles/blob/master/"; } gurl += mfnpre + ".txt#L" + String(cindex + 10 + 1); console.log("going to ", gurl); window.open(gurl, "MITx 8.370x subtitle source"); }); }); } try{ add_fix_transcript(); } catch(err){ console.log(err); } try{ var rb = String.fromCharCode(62); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 3000); setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 8000); } catch(err){ console.log(err); } </script></span> </div> </div> </div> </div>