<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@Generalized_Bernstein-Vazirani" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True">
<h2 class="hd hd-2 unit-title">Generalized Bernstein-Vazirani</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-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@ps4b-BV-1" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-BV-1" class="problems-wrapper" role="group"
aria-labelledby="ps4b-BV-1-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-1" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-1/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-BV-1-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-1-problem-progress" tabindex="-1">
Learning a linear function mod 3: classical lower bound
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-1-problem-progress"></div>
<div class="problem">
<div>
<p>
Suppose [mathjaxinline]f:\mathbb {Z}_3^ n \rightarrow \mathbb {Z}_3[/mathjaxinline] is a linear function, i.e. </p>
<table id="a0000000002" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]f(x) = x_1s_1 + \cdots + x_ ns_ n \bmod {3},[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
for some unknown [mathjaxinline]s \in \mathbb {Z}_3^ n[/mathjaxinline]. The goal is to find [mathjaxinline]s[/mathjaxinline]. Given a black box for [mathjaxinline]f[/mathjaxinline], how many classical queries are needed to determine [mathjaxinline]s[/mathjaxinline] with certainty? </p>
<p>
<p style="display:inline">Number of queries is </p>
<div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_ps4b-BV-1_2_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-BV-1_2_1" id="input_ps4b-BV-1_2_1" data-input-id="ps4b-BV-1_2_1" value="" aria-describedby="status_ps4b-BV-1_2_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4b-BV-1_2_1"/>
<span class="status unanswered" id="status_ps4b-BV-1_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-BV-1_2_1" class="answer"/>
<div id="input_ps4b-BV-1_2_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Learning a linear function mod 3: classical lower bound" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-BV-1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-BV-1">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-BV-1-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-BV-1-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-BV-1-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-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@ps4b-BV-2" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-BV-2" class="problems-wrapper" role="group"
aria-labelledby="ps4b-BV-2-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-2" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-2/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-BV-2-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-2-problem-progress" tabindex="-1">
Learning a linear function mod 3: math interlude
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-2-problem-progress"></div>
<div class="problem">
<div>
<p>
Find a number [mathjaxinline]z\in \mathbb {C}[/mathjaxinline] such that for any [mathjaxinline]n[/mathjaxinline]-bit string [mathjaxinline]u\in \{ 0,1,2\} ^ n[/mathjaxinline], </p>
<table id="a0000000003" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]\sum _{v\in \{ 0,1,2\} ^ n} z^{\langle u,v\rangle } = \begin{cases} 3^ n &amp; \text {if }u=0\\ 0 &amp; \text {otherwise}\end{cases}[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
<p style="display:inline">[mathjaxinline]z=[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4b-BV-2_2_1" class="text-input-dynamath capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_ps4b-BV-2_2_1" id="input_ps4b-BV-2_2_1" aria-describedby="status_ps4b-BV-2_2_1" value="" class="math" size="30"/>
<span class="trailing_text" id="trailing_text_ps4b-BV-2_2_1"/>
<span class="status unanswered" id="status_ps4b-BV-2_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-BV-2_2_1" class="answer"/>
<div id="display_ps4b-BV-2_2_1" class="equation">`{::}`</div>
<textarea style="display:none" id="input_ps4b-BV-2_2_1_dynamath" name="input_ps4b-BV-2_2_1_dynamath"/>
</div>
</div></div>
</p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Learning a linear function mod 3: math interlude" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-BV-2" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-BV-2">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-BV-2-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-BV-2-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-BV-2-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-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@ps4b-BV-3" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-BV-3" class="problems-wrapper" role="group"
aria-labelledby="ps4b-BV-3-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-3" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-3/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-BV-3-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-3-problem-progress" tabindex="-1">
Learning a linear function mod 3: quantum algorithm
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-BV-3-problem-progress"></div>
<div class="problem">
<div>
<p>
Let [mathjaxinline]U_ f[/mathjaxinline] denote a unitary implementing [mathjaxinline]f[/mathjaxinline], defined by </p>
<table id="a0000000004" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]U_ f |{x}\rangle |{y}\rangle = |{x}\rangle |{y + s\cdot x \bmod {3}}\rangle ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
for [mathjaxinline]x\in \{ 0,1,2\} ^ n, y\in \{ 0,1,2\}[/mathjaxinline]. </p>
<p>
Consider the following circuit using [mathjaxinline]U_ f[/mathjaxinline]. </p>
<center>
<img src="/assets/courseware/v1/b20b8f212c9ec66c931d004fe4d6296a/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps4b_bv-circuit.png" width="400"/>
</center>
<p>
For the right choice of input state [mathjaxinline]|{\psi }\rangle[/mathjaxinline], the output of the measurement will be [mathjaxinline]s[/mathjaxinline] with probability 1. The state [mathjaxinline]|{\psi }\rangle[/mathjaxinline] is a qutrit (i.e. belongs to [mathjaxinline]\mathbb {C}^3[/mathjaxinline]) but we will write the three basis states in binary, so 0,1,2 become [mathjaxinline]|{00}\rangle , |{01}\rangle ,|{10}\rangle[/mathjaxinline]. </p>
<p>
<p style="display:inline">[mathjaxinline]|\psi \rangle =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4b-BV-3_2_1" class="text-input-dynamath capa_inputtype inline textline">
<div class="text-input-dynamath_data inline" data-preprocessor="MathjaxPreprocessorForQM"/>
<div class="script_placeholder" data-src="/assets/courseware/v1/95fe583d41f010195cf50c9f61992d94/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/mathjax_preprocessor_for_QM_H.js"/>
<div class="unanswered inline">
<input type="text" name="input_ps4b-BV-3_2_1" id="input_ps4b-BV-3_2_1" aria-describedby="status_ps4b-BV-3_2_1" value="" class="math" size="50"/>
<span class="trailing_text" id="trailing_text_ps4b-BV-3_2_1"/>
<span class="status unanswered" id="status_ps4b-BV-3_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-BV-3_2_1" class="answer"/>
<div id="display_ps4b-BV-3_2_1" class="equation">`{::}`</div>
<textarea style="display:none" id="input_ps4b-BV-3_2_1_dynamath" name="input_ps4b-BV-3_2_1_dynamath"/>
</div>
</div></div>
</p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Learning a linear function mod 3: quantum algorithm" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-BV-3" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-BV-3">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-BV-3-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-BV-3-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-BV-3-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" 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="95ccc098885c11ef87990affec87671b" 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@Collision" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True">
<h2 class="hd hd-2 unit-title">Collision</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-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@ps4b-collision-1" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-collision-1" class="problems-wrapper" role="group"
aria-labelledby="ps4b-collision-1-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-1" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-1/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-collision-1-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-1-problem-progress" tabindex="-1">
Quantum algorithm to break hash functions
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-1-problem-progress"></div>
<div class="problem">
<div>
<p>
If we have [mathjaxinline]N[/mathjaxinline] items of which [mathjaxinline]M[/mathjaxinline] are marked then Grover's algorithm can find a marked item using [mathjaxinline]O(\sqrt{N/M})[/mathjaxinline] queries. (In this problem we will ignore the probability of error as well as the issue of whether [mathjaxinline]M[/mathjaxinline] is known.) Let [mathjaxinline][N]=\{ 1,2,\ldots ,N\}[/mathjaxinline]. </p>
<p>
In the collision problem we are given a black-box function [mathjaxinline]f:[N]\rightarrow S[/mathjaxinline] with the promise that [mathjaxinline]f[/mathjaxinline] is two-to-one, i.e. for any output [mathjaxinline]y[/mathjaxinline], there are exactly two inputs [mathjaxinline]x[/mathjaxinline] such that [mathjaxinline]f(x)=y[/mathjaxinline]. The goal of this problem is to find such a pair of inputs, i.e. [mathjaxinline]x_1\neq x_2[/mathjaxinline] such that [mathjaxinline]f(x_1)=f(x_2)[/mathjaxinline]. We call these &#8220;collisions." </p>
<p>
We will consider the following algorithm. </p>
<ul class="itemize">
<li>
<p>
Query [mathjaxinline]f(1),\ldots ,f(K)[/mathjaxinline]. </p>
</li>
<li>
<p>
If a collision is found, output it. </p>
</li>
<li>
<p>
If not, then use Grover's algorithm to search for [mathjaxinline]x_1\in \{ K+1,\ldots ,N\}[/mathjaxinline] such that [mathjaxinline]f(x_1)=f(x_2)[/mathjaxinline] for some [mathjaxinline]x_2 \in [K][/mathjaxinline]. </p>
</li>
</ul>
<p>
How many queries are needed by this algorithm to find a collision with high probability? </p>
<p>
<p style="display:inline"># of queries is</p>
<div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4b-collision-1_2_1" class=" capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_ps4b-collision-1_2_1" id="input_ps4b-collision-1_2_1" aria-describedby="status_ps4b-collision-1_2_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4b-collision-1_2_1"/>
<span class="status unanswered" id="status_ps4b-collision-1_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-collision-1_2_1" class="answer"/>
</div>
</div></div>
</p>
<p>
<div class="solution-span">
<span id="solution_ps4b-collision-1_solution_1"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum algorithm to break hash functions" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-collision-1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-collision-1">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-collision-1-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-collision-1-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-collision-1-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-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@ps4b-collision-2" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-collision-2" class="problems-wrapper" role="group"
aria-labelledby="ps4b-collision-2-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-2" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-2/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-collision-2-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-2-problem-progress" tabindex="-1">
Optimizing K
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-collision-2-problem-progress"></div>
<div class="problem">
<div>
<p>
The minimum number of queries is obtained by choosing [mathjaxinline]K[/mathjaxinline] proportional to [mathjaxinline]N^ a[/mathjaxinline] for some constant [mathjaxinline]a[/mathjaxinline]. </p>
<p>
<p style="display:inline">[mathjaxinline]a =[/mathjaxinline]</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4b-collision-2_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_ps4b-collision-2_2_1" id="input_ps4b-collision-2_2_1" aria-describedby="status_ps4b-collision-2_2_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4b-collision-2_2_1"/>
<span class="status unanswered" id="status_ps4b-collision-2_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-collision-2_2_1" class="answer"/>
</div>
</div></div>
</p>
<p>
The resulting query complexity is [mathjaxinline]O(N^ b)[/mathjaxinline] for some constant [mathjaxinline]b[/mathjaxinline]. </p>
<p>
<p style="display:inline">[mathjaxinline]b =[/mathjaxinline]</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div id="inputtype_ps4b-collision-2_3_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_ps4b-collision-2_3_1" id="input_ps4b-collision-2_3_1" aria-describedby="status_ps4b-collision-2_3_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4b-collision-2_3_1"/>
<span class="status unanswered" id="status_ps4b-collision-2_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-collision-2_3_1" class="answer"/>
</div>
</div></div>
</p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Optimizing K" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-collision-2" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-collision-2">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-collision-2-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-collision-2-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-collision-2-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box2xxxxx">
<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_box2xxxxx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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@Discrete_Log" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True">
<h2 class="hd hd-2 unit-title">Discrete Log</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-dlog">
<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-wk9-dlog" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-dlog" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-dlog-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-dlog" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-dlog/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="7"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-dlog-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-dlog-problem-progress" tabindex="-1">
Quantum algorithm for computing the discrete log
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-dlog-problem-progress"></div>
<div class="problem">
<div>
<p>
In this problem we will complete the discrete log algorithm from lecture. </p>
<p>
We are given a group [mathjaxinline]G = \langle g \rangle = \{ g^0, g^1, \ldots , g^{N-1}\}[/mathjaxinline]. Here [mathjaxinline]N=|G|[/mathjaxinline] is the smallest positive integer such that [mathjaxinline]g^ N=1[/mathjaxinline], and we do not require that [mathjaxinline]N[/mathjaxinline] be prime. We want to compute the discrete log of [mathjaxinline]x[/mathjaxinline], defined to be </p>
<table id="a0000000005" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]\ell = \log _ g(x) = \min \{ \alpha \geq 0 : g^\alpha = x\} .[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
We start the algorithm with the state </p>
<table id="a0000000006" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|{\mathbb {Z}_ N \times \mathbb {Z}_ N}\rangle = \frac{1}{N} \sum _{\alpha ,\beta \in \mathbb {Z}_ N} |{\alpha ,\beta }\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
and then compute [mathjaxinline]f(\alpha ,\beta ) = x^\alpha g^\beta = g^{\tilde f(\alpha ,\beta )}[/mathjaxinline] where <p style="display:inline">[mathjaxinline]\tilde f(\alpha ,\beta ) =[/mathjaxinline]</p> <div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_s12-wk9-dlog_2_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_s12-wk9-dlog_2_1" id="input_s12-wk9-dlog_2_1" data-input-id="s12-wk9-dlog_2_1" value="" aria-describedby="status_s12-wk9-dlog_2_1" size="20"/>
<span class="trailing_text" id="trailing_text_s12-wk9-dlog_2_1"/>
<span class="status unanswered" id="status_s12-wk9-dlog_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_s12-wk9-dlog_2_1" class="answer"/>
<div id="input_s12-wk9-dlog_2_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div></p>
<p>
When we discard the third register we are left with the state </p>
<table id="a0000000007" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|{L_\gamma }\rangle = \frac{1}{\sqrt N} \sum _{\alpha \in \mathbb {Z}_ N} |{\alpha , \gamma - \ell \alpha }\rangle .[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
Then we Fourier transform and obtain </p>
<table id="a0000000008" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax](F_{\mathbb {Z}_ N} \otimes F_{\mathbb {Z}_ N})|{L_\gamma }\rangle = A \sum _{\alpha ,\mu ,\nu \in \mathbb {Z}_ N} e^{2\pi iB} |{\mu ,\nu }\rangle ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
for values of [mathjaxinline]A,B[/mathjaxinline] that you should determine. </p>
<p>
<p style="display:inline">[mathjaxinline]A =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 2" role="group"><div id="formulaequationinput_s12-wk9-dlog_3_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_s12-wk9-dlog_3_1" id="input_s12-wk9-dlog_3_1" data-input-id="s12-wk9-dlog_3_1" value="" aria-describedby="status_s12-wk9-dlog_3_1" size="20"/>
<span class="trailing_text" id="trailing_text_s12-wk9-dlog_3_1"/>
<span class="status unanswered" id="status_s12-wk9-dlog_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_s12-wk9-dlog_3_1" class="answer"/>
<div id="input_s12-wk9-dlog_3_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
<p style="display:inline">[mathjaxinline]B =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 3" role="group"><div id="formulaequationinput_s12-wk9-dlog_4_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_s12-wk9-dlog_4_1" id="input_s12-wk9-dlog_4_1" data-input-id="s12-wk9-dlog_4_1" value="" aria-describedby="status_s12-wk9-dlog_4_1" size="20"/>
<span class="trailing_text" id="trailing_text_s12-wk9-dlog_4_1"/>
<span class="status unanswered" id="status_s12-wk9-dlog_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_s12-wk9-dlog_4_1" class="answer"/>
<div id="input_s12-wk9-dlog_4_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
Since the sum is over [mathjaxinline]\alpha ,\mu ,\nu[/mathjaxinline] and the ket only depends on [mathjaxinline]\mu ,\nu[/mathjaxinline] we can evaluate the sum over [mathjaxinline]\alpha[/mathjaxinline] and obtain </p>
<table id="a0000000009" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]C \sum _{\nu \in \mathbb {Z}_ N} e^{2\pi iD} |{E, \nu }\rangle ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
where you should calculate [mathjaxinline]C,D,E[/mathjaxinline]. <p style="display:inline">[mathjaxinline]C =[/mathjaxinline]</p> <div class="inline" tabindex="-1" aria-label="Question 4" role="group"><div id="formulaequationinput_s12-wk9-dlog_5_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_s12-wk9-dlog_5_1" id="input_s12-wk9-dlog_5_1" data-input-id="s12-wk9-dlog_5_1" value="" aria-describedby="status_s12-wk9-dlog_5_1" size="20"/>
<span class="trailing_text" id="trailing_text_s12-wk9-dlog_5_1"/>
<span class="status unanswered" id="status_s12-wk9-dlog_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_s12-wk9-dlog_5_1" class="answer"/>
<div id="input_s12-wk9-dlog_5_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div></p>
<p>
<p style="display:inline">[mathjaxinline]D =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 5" role="group"><div id="formulaequationinput_s12-wk9-dlog_6_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_s12-wk9-dlog_6_1" id="input_s12-wk9-dlog_6_1" data-input-id="s12-wk9-dlog_6_1" value="" aria-describedby="status_s12-wk9-dlog_6_1" size="20"/>
<span class="trailing_text" id="trailing_text_s12-wk9-dlog_6_1"/>
<span class="status unanswered" id="status_s12-wk9-dlog_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_s12-wk9-dlog_6_1" class="answer"/>
<div id="input_s12-wk9-dlog_6_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
<p style="display:inline">[mathjaxinline]E =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 6" role="group"><div id="formulaequationinput_s12-wk9-dlog_7_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_s12-wk9-dlog_7_1" id="input_s12-wk9-dlog_7_1" data-input-id="s12-wk9-dlog_7_1" value="" aria-describedby="status_s12-wk9-dlog_7_1" size="20"/>
<span class="trailing_text" id="trailing_text_s12-wk9-dlog_7_1"/>
<span class="status unanswered" id="status_s12-wk9-dlog_7_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_s12-wk9-dlog_7_1" class="answer"/>
<div id="input_s12-wk9-dlog_7_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
Finally we measure and from [mathjaxinline]E,\nu[/mathjaxinline] we try to calculate [mathjaxinline]\ell[/mathjaxinline]. Do we now have enough information to determine [mathjaxinline]\ell[/mathjaxinline]? <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 7" role="group"><div class="choicegroup capa_inputtype" id="inputtype_s12-wk9-dlog_8_1">
<fieldset aria-describedby="status_s12-wk9-dlog_8_1">
<div class="field">
<input type="radio" name="input_s12-wk9-dlog_8_1" id="input_s12-wk9-dlog_8_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="s12-wk9-dlog_8_1-choice_1-label" for="input_s12-wk9-dlog_8_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_s12-wk9-dlog_8_1"> <text> Yes, for any value of [mathjaxinline]\nu[/mathjaxinline].</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_s12-wk9-dlog_8_1" id="input_s12-wk9-dlog_8_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="s12-wk9-dlog_8_1-choice_2-label" for="input_s12-wk9-dlog_8_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_s12-wk9-dlog_8_1"> <text> Yes, if [mathjaxinline]\nu \neq 0[/mathjaxinline]</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_s12-wk9-dlog_8_1" id="input_s12-wk9-dlog_8_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="s12-wk9-dlog_8_1-choice_3-label" for="input_s12-wk9-dlog_8_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_s12-wk9-dlog_8_1"> <text> Yes, if [mathjaxinline]\text {gcd}(\nu ,N)=1[/mathjaxinline].</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_s12-wk9-dlog_8_1" id="input_s12-wk9-dlog_8_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="s12-wk9-dlog_8_1-choice_4-label" for="input_s12-wk9-dlog_8_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_s12-wk9-dlog_8_1"> <text> Yes, if [mathjaxinline]\nu =1[/mathjaxinline].</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_s12-wk9-dlog_8_1" id="input_s12-wk9-dlog_8_1_choice_5" class="field-input input-radio" value="choice_5"/><label id="s12-wk9-dlog_8_1-choice_5-label" for="input_s12-wk9-dlog_8_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_s12-wk9-dlog_8_1"> <text> Yes, if [mathjaxinline]\nu[/mathjaxinline] satisfies some condition not listed here.</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_s12-wk9-dlog_8_1" id="input_s12-wk9-dlog_8_1_choice_6" class="field-input input-radio" value="choice_6"/><label id="s12-wk9-dlog_8_1-choice_6-label" for="input_s12-wk9-dlog_8_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_s12-wk9-dlog_8_1"> <text> No, a single run never has enough information. Multiple runs are necessary.</text>
</label>
</div>
<span id="answer_s12-wk9-dlog_8_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_s12-wk9-dlog_8_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div> </p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum algorithm for computing the discrete log" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-dlog" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-dlog">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-dlog-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-dlog-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-dlog-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</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="95ccc098885c11ef87990affec87671b" 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@Hidden_Parabola" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True">
<h2 class="hd hd-2 unit-title">Hidden Parabola</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@Hidden_Parabola_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@Hidden_Parabola_html" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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>
Suppose we are given a black-box function [mathjaxinline]f: \mathbb {Z}_ p^2\rightarrow S[/mathjaxinline] satisfying the promise that </p><table id="a0000000010" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]f(x_1,y_1)=f(x_2,y_2) \quad \Longleftrightarrow \quad \alpha x_1^2 + \beta x_1 - y_1 = \alpha x_2^2 + \beta x_2 - y_2,[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
for some unknown [mathjaxinline]\alpha ,\beta \in \mathbb {Z}_ p[/mathjaxinline]. This means that the level sets of [mathjaxinline]f[/mathjaxinline] are the parabolas </p><table id="a0000000011" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto"><tr><td class="equation" style="width:80%; border:none">[mathjax]P_{\alpha ,\beta ,\gamma } := \{ (x,y)\in \mathbb {Z}_ p^2 : y = \alpha ^2 x + \beta x + \gamma \}[/mathjax]</td><td class="eqnnum" style="width:20%; border:none"> </td></tr></table><p>
as [mathjaxinline]\gamma[/mathjaxinline] ranges over [mathjaxinline]\mathbb {Z}_ p[/mathjaxinline]. Given the ability to query [mathjaxinline]f[/mathjaxinline], the hidden parabola problem asks us to determine the values of [mathjaxinline]\alpha[/mathjaxinline] and [mathjaxinline]\beta[/mathjaxinline]. </p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-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@ps4b-parabola-1" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-parabola-1" class="problems-wrapper" role="group"
aria-labelledby="ps4b-parabola-1-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-1" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-1/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-parabola-1-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-1-problem-progress" tabindex="-1">
Hidden Parabola - Analogue of coset states
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-1-problem-progress"></div>
<div class="problem">
<div>
<p>
Suppose that we query [mathjaxinline]f[/mathjaxinline] on the superposition </p>
<table id="a0000000012" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]\frac1p \sum _{x,y \in \mathbb {Z}_ p} |{x,y}\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
and then we discard the register storing the value of [mathjaxinline]f[/mathjaxinline]. The resulting quantum state looks like: <span><div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4b-parabola-1_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_ps4b-parabola-1_2_1" data-plain-id="ps4b-parabola-1_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_ps4b-parabola-1_2_1" style="display:none;">{"base_image": "/assets/courseware/v1/3302b7df0318e6605e14c25694411e36/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps4b_parabola_ps4b_parabola_dnd.png", "targets": [{"id": "3", "y": "0", "w": "186", "x": "40", "h": "46"}, {"id": "2", "y": "52", "w": "186", "x": "242", "h": "46"}, {"id": "4", "y": "167", "w": "186", "x": "93", "h": "45"}, {"id": "1", "y": "219", "w": "186", "x": "294", "h": "45"}, {"id": "5", "y": "167", "w": "186", "x": "528", "h": "45"}], "label_bg_color": "rgb(222, 139, 238)", "draggables": [{"id": "x", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/bb0c40c84fd9905561e7178d97a2a44c/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps4b_parabola_ps4b_parabola_dnd_label1.png"}, {"id": "gamma", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/f628b01fde897d2e410eb48ce1939ffc/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps4b_parabola_ps4b_parabola_dnd_label2.png"}, {"id": "alphabetagamma", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/30b1cfb37ff75c8c65992d6431405b44/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps4b_parabola_ps4b_parabola_dnd_label3.png"}, {"id": "fraconep", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/87541b73d9595c23de160836b974cc2a/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps4b_parabola_ps4b_parabola_dnd_label4.png"}, {"id": "fraconesqrtp", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/8e9b835922e5ea10d044eba411cd5a98/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps4b_parabola_ps4b_parabola_dnd_label5.png"}, {"id": "alphaxtwoplusbetax", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/15df91da345ae4fa53bea6a995a2150c/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps4b_parabola_ps4b_parabola_dnd_label6.png"}, {"id": "alphaxtwoplusbetaxplusgamma", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/b86cdc94aafde1535d77eaa539e58f66/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps4b_parabola_ps4b_parabola_dnd_label7.png"}], "one_per_target": "true", "target_outline": "false"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_ps4b-parabola-1_2_1">
<input type="text" name="input_ps4b-parabola-1_2_1" id="input_ps4b-parabola-1_2_1" aria-describedby="answer_ps4b-parabola-1_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_ps4b-parabola-1_2_1">
<span class="status unanswered" id="status_ps4b-parabola-1_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_ps4b-parabola-1_2_1" class="answer"/>
</div>
</div></div><div class="solution-span">
<span id="solution_ps4b-parabola-1_solution_1"/>
</div></span></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Hidden Parabola - Analogue of coset states" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-parabola-1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-parabola-1">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-1-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-1-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-1-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-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@ps4b-parabola-2" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-parabola-2" class="problems-wrapper" role="group"
aria-labelledby="ps4b-parabola-2-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-2" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-2/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="7"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-parabola-2-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-2-problem-progress" tabindex="-1">
Hidden Parabola - After Fourier transform
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-2-problem-progress"></div>
<div class="problem">
<div>
<p>
Now define [mathjaxinline]T_ a[/mathjaxinline] such that [mathjaxinline]T_ a |{x}\rangle = |{x+a}\rangle[/mathjaxinline] Then </p>
<table id="a0000000013" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax](I \otimes T_ a)|{P_{\alpha , \beta , \gamma }}\rangle = |{P_{\alpha ', \beta ', \gamma '}}\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
Such that: <p style="display:inline">[mathjaxinline]\alpha ' =[/mathjaxinline]</p> <div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_ps4b-parabola-2_2_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-2_2_1" id="input_ps4b-parabola-2_2_1" data-input-id="ps4b-parabola-2_2_1" value="" aria-describedby="status_ps4b-parabola-2_2_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-2_2_1"/>
<span class="status unanswered" id="status_ps4b-parabola-2_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-2_2_1" class="answer"/>
<div id="input_ps4b-parabola-2_2_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div> </p>
<p>
<p style="display:inline">[mathjaxinline]\beta ' =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 2" role="group"><div id="formulaequationinput_ps4b-parabola-2_3_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-2_3_1" id="input_ps4b-parabola-2_3_1" data-input-id="ps4b-parabola-2_3_1" value="" aria-describedby="status_ps4b-parabola-2_3_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-2_3_1"/>
<span class="status unanswered" id="status_ps4b-parabola-2_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-2_3_1" class="answer"/>
<div id="input_ps4b-parabola-2_3_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
<p style="display:inline">[mathjaxinline]\gamma ' =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 3" role="group"><div id="formulaequationinput_ps4b-parabola-2_4_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-2_4_1" id="input_ps4b-parabola-2_4_1" data-input-id="ps4b-parabola-2_4_1" value="" aria-describedby="status_ps4b-parabola-2_4_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-2_4_1"/>
<span class="status unanswered" id="status_ps4b-parabola-2_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-2_4_1" class="answer"/>
<div id="input_ps4b-parabola-2_4_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
Now suppose we conjugate [mathjaxinline]\rho[/mathjaxinline] by [mathjaxinline]I \otimes T_ a[/mathjaxinline] to get the state [mathjaxinline]\rho '[/mathjaxinline]. What value would you expect for [mathjaxinline]\rho '[/mathjaxinline]? <p style="display:inline">[mathjaxinline]\rho ' =[/mathjaxinline]</p> <div class="inline" tabindex="-1" aria-label="Question 4" role="group"><div id="formulaequationinput_ps4b-parabola-2_5_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-2_5_1" id="input_ps4b-parabola-2_5_1" data-input-id="ps4b-parabola-2_5_1" value="" aria-describedby="status_ps4b-parabola-2_5_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-2_5_1"/>
<span class="status unanswered" id="status_ps4b-parabola-2_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-2_5_1" class="answer"/>
<div id="input_ps4b-parabola-2_5_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div> </p>
<p>
Using the observation you made in the above evaluations we can conclude that if we apply a quantum Fourier transform over [mathjaxinline]\mathbb {Z}_ p[/mathjaxinline] on the second register we obtain the state </p>
<table id="a0000000014" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]\frac{1}{D} \sum _{x,w,k\in \mathbb {Z}_ p} |{x,k}\rangle \langle {w,k}| \omega _ p^{k(\alpha \lambda _ A + \beta \lambda _ B)}[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
<p style="display:inline">[mathjaxinline]D =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 5" role="group"><div id="formulaequationinput_ps4b-parabola-2_6_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-2_6_1" id="input_ps4b-parabola-2_6_1" data-input-id="ps4b-parabola-2_6_1" value="" aria-describedby="status_ps4b-parabola-2_6_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-2_6_1"/>
<span class="status unanswered" id="status_ps4b-parabola-2_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-2_6_1" class="answer"/>
<div id="input_ps4b-parabola-2_6_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
<p style="display:inline">[mathjaxinline]\lambda _ A =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 6" role="group"><div id="formulaequationinput_ps4b-parabola-2_7_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-2_7_1" id="input_ps4b-parabola-2_7_1" data-input-id="ps4b-parabola-2_7_1" value="" aria-describedby="status_ps4b-parabola-2_7_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-2_7_1"/>
<span class="status unanswered" id="status_ps4b-parabola-2_7_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-2_7_1" class="answer"/>
<div id="input_ps4b-parabola-2_7_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
<p style="display:inline">[mathjaxinline]\lambda _ B =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 7" role="group"><div id="formulaequationinput_ps4b-parabola-2_8_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-2_8_1" id="input_ps4b-parabola-2_8_1" data-input-id="ps4b-parabola-2_8_1" value="" aria-describedby="status_ps4b-parabola-2_8_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-2_8_1"/>
<span class="status unanswered" id="status_ps4b-parabola-2_8_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-2_8_1" class="answer"/>
<div id="input_ps4b-parabola-2_8_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Hidden Parabola - After Fourier transform" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-parabola-2" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-parabola-2">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-2-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-2-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-2-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-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@ps4b-parabola-3" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-parabola-3" class="problems-wrapper" role="group"
aria-labelledby="ps4b-parabola-3-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-3" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-3/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-parabola-3-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-3-problem-progress" tabindex="-1">
Hidden Parabola - Measure second register
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-3-problem-progress"></div>
<div class="problem">
<div>
<p>
Now suppose that we measure the register that we have applied quantum Fourier transform on. The resulting state is </p>
<p><div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_ps4b-parabola-3_2_1">
<fieldset aria-describedby="status_ps4b-parabola-3_2_1">
<div class="field">
<input type="radio" name="input_ps4b-parabola-3_2_1" id="input_ps4b-parabola-3_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="ps4b-parabola-3_2_1-choice_1-label" for="input_ps4b-parabola-3_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_ps4b-parabola-3_2_1"> <text> pure</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_ps4b-parabola-3_2_1" id="input_ps4b-parabola-3_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="ps4b-parabola-3_2_1-choice_2-label" for="input_ps4b-parabola-3_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_ps4b-parabola-3_2_1"> <text> mixed</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_ps4b-parabola-3_2_1" id="input_ps4b-parabola-3_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="ps4b-parabola-3_2_1-choice_3-label" for="input_ps4b-parabola-3_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_ps4b-parabola-3_2_1"> <text> sometimes pure and sometimes mixed</text>
</label>
</div>
<span id="answer_ps4b-parabola-3_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_ps4b-parabola-3_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div> and is equal to </p>
<table id="a0000000015" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|{\varphi _ k}\rangle = \frac{1}{\sqrt p} \sum _{x \in \mathbb {Z}_ p} \omega _ p^{k \lambda }|{x}\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
where [mathjaxinline]\lambda[/mathjaxinline] is equal to </p>
<p>
<p style="display:inline">[mathjaxinline]\lambda =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 2" role="group"><div id="formulaequationinput_ps4b-parabola-3_3_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-3_3_1" id="input_ps4b-parabola-3_3_1" data-input-id="ps4b-parabola-3_3_1" value="" aria-describedby="status_ps4b-parabola-3_3_1" size="40"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-3_3_1"/>
<span class="status unanswered" id="status_ps4b-parabola-3_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-3_3_1" class="answer"/>
<div id="input_ps4b-parabola-3_3_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Hidden Parabola - Measure second register" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-parabola-3" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-parabola-3">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-3-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-3-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-3-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-4">
<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@ps4b-parabola-4" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-parabola-4" class="problems-wrapper" role="group"
aria-labelledby="ps4b-parabola-4-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-4" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-4/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-parabola-4-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-4-problem-progress" tabindex="-1">
Hidden Parabola - Two copies
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-4-problem-progress"></div>
<div class="problem">
<div>
<p>
Now suppose that we had applied all the steps from the previous parts twice. We would expect to get the following state: </p>
<table id="a0000000016" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|{\varphi _ k}\rangle \otimes |{\varphi _ l}\rangle = \frac1p \sum _{x,w\in \mathbb {Z}_ p} \omega _ p^{\alpha A + \beta B}|{x,w}\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
where [mathjaxinline]A,B[/mathjaxinline] are functions of [mathjaxinline]k,l,x,w[/mathjaxinline]. </p>
<p>
<p style="display:inline">[mathjaxinline]A =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_ps4b-parabola-4_2_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-4_2_1" id="input_ps4b-parabola-4_2_1" data-input-id="ps4b-parabola-4_2_1" value="" aria-describedby="status_ps4b-parabola-4_2_1" size="20"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-4_2_1"/>
<span class="status unanswered" id="status_ps4b-parabola-4_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-4_2_1" class="answer"/>
<div id="input_ps4b-parabola-4_2_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
<p style="display:inline">[mathjaxinline]B =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 2" role="group"><div id="formulaequationinput_ps4b-parabola-4_3_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-4_3_1" id="input_ps4b-parabola-4_3_1" data-input-id="ps4b-parabola-4_3_1" value="" aria-describedby="status_ps4b-parabola-4_3_1" size="20"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-4_3_1"/>
<span class="status unanswered" id="status_ps4b-parabola-4_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-4_3_1" class="answer"/>
<div id="input_ps4b-parabola-4_3_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
Since [mathjaxinline]A,B[/mathjaxinline] are explicit and efficiently computable functions of [mathjaxinline]k,l,x,w[/mathjaxinline] we can store them in two new registers. This yields the state </p>
<table id="a0000000017" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]\frac1p \sum _{x,w\in \mathbb {Z}_ p} \omega _ p^{\alpha A + \beta B}|{x,w,A,B}\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Hidden Parabola - Two copies" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-parabola-4" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-parabola-4">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-4-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-4-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-4-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-5" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-8">
<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@ps4b-parabola-8" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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_ps4b-parabola-8" class="problems-wrapper" role="group"
aria-labelledby="ps4b-parabola-8-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-8" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-8/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4b-parabola-8-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-8-problem-progress" tabindex="-1">
Hidden Parabola - Inverse QFT
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@ps4b-parabola-8-problem-progress"></div>
<div class="problem">
<div>
<p>
After erasing the first two registers we are left with the state </p>
<table id="a0000000018" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|{\psi }\rangle = \frac{1}{|S|} \sum _{(A,B)\in S} \omega _ p^{\alpha A + \beta B} |{A,B}\rangle ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
where [mathjaxinline]S[/mathjaxinline] is the set of [mathjaxinline](A,B)[/mathjaxinline] that can arise as solutions to the quadratic equations that you found above. </p>
<p>
We will now apply [mathjaxinline]F_{\mathbb {Z}_ p}^\dagger \otimes F_{\mathbb {Z}_ p}^\dagger[/mathjaxinline] and measure. </p>
<p>
Pretend for the moment that our state were actually </p>
<table id="a0000000019" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|{\psi _{\text {ideal}}}\rangle = \frac{1}{p} \sum _{A,B\in \mathbb {Z}_ p} \omega _ p^{\alpha A + \beta B} |{A,B}\rangle .[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
Then [mathjaxinline]F_{\mathbb {Z}_ p}^\dagger \otimes F_{\mathbb {Z}_ p}^\dagger |{\psi _{\text {ideal}}}\rangle = |{a,b}\rangle[/mathjaxinline]. What are [mathjaxinline]a[/mathjaxinline] and [mathjaxinline]b[/mathjaxinline]? </p>
<p>
<p style="display:inline">[mathjaxinline]a =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_ps4b-parabola-8_2_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-8_2_1" id="input_ps4b-parabola-8_2_1" data-input-id="ps4b-parabola-8_2_1" value="" aria-describedby="status_ps4b-parabola-8_2_1" size="20"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-8_2_1"/>
<span class="status unanswered" id="status_ps4b-parabola-8_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-8_2_1" class="answer"/>
<div id="input_ps4b-parabola-8_2_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
<p style="display:inline">[mathjaxinline]b =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 2" role="group"><div id="formulaequationinput_ps4b-parabola-8_3_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4b-parabola-8_3_1" id="input_ps4b-parabola-8_3_1" data-input-id="ps4b-parabola-8_3_1" value="" aria-describedby="status_ps4b-parabola-8_3_1" size="20"/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-8_3_1"/>
<span class="status unanswered" id="status_ps4b-parabola-8_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-8_3_1" class="answer"/>
<div id="input_ps4b-parabola-8_3_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
</p>
<p>
Since we are actually measuring [mathjaxinline]F_{\mathbb {Z}_ p}^\dagger \otimes F_{\mathbb {Z}_ p}^\dagger |{\psi }\rangle[/mathjaxinline], we only obtain these outcomes with some probability [mathjaxinline]P[/mathjaxinline]. As [mathjaxinline]p[/mathjaxinline] becomes large, [mathjaxinline]P[/mathjaxinline] approaches <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div id="inputtype_ps4b-parabola-8_4_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_ps4b-parabola-8_4_1" id="input_ps4b-parabola-8_4_1" aria-describedby="status_ps4b-parabola-8_4_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4b-parabola-8_4_1"/>
<span class="status unanswered" id="status_ps4b-parabola-8_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4b-parabola-8_4_1" class="answer"/>
</div>
</div></div>. </p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Hidden Parabola - Inverse QFT" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ps4b-parabola-8" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4b-parabola-8">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-8-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-8-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="ps4b-parabola-8-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-6" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box4xx">
<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_box4xx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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@Factoring_using_feedback_introduction" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True">
<h2 class="hd hd-2 unit-title">Factoring using feedback: introduction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback">
<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-wk9-factoring-feedback" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback-problem-progress" tabindex="-1">
Quantum factoring as a feedback process
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback-problem-progress"></div>
<div class="problem">
<div>
<p>
Shor's quantum factoring algorithm was independently (re-)discovered by Alexei Kitaev, working in Russia. Kitaev's formulation allows for an interesting observation of how quantum factoring can be viewed as a feedback process, involving quantum control and optimal estimation, as we explore in this problem. </p>
<p>
Let [mathjaxinline]N[/mathjaxinline] be a composite number we wish to factor, and choose some [mathjaxinline]y[/mathjaxinline] coprime to [mathjaxinline]N[/mathjaxinline]. Define the unitary transform [mathjaxinline]U[/mathjaxinline] to be </p>
<table id="a0000000020" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]U |{m}\rangle = |{m y \, {\rm mod}\, N}\rangle \, ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.1)</td>
</tr>
</table>
<p>
where the state lives in an [mathjaxinline]2^ L[/mathjaxinline] dimensional Hilbert space of [mathjaxinline]L = \left\lceil {\log _2 N}\right\rceil[/mathjaxinline] qubits. </p>
<p>
Let [mathjaxinline]\phi _ k = k/r[/mathjaxinline], and [mathjaxinline]r[/mathjaxinline] be the order of [mathjaxinline]y[/mathjaxinline], i.e. the smallest integer such that [mathjaxinline]y^ r\, {\rm mod}\, N = 1[/mathjaxinline]. </p>
<p>
Complete the following expression for the eigenstates of [mathjaxinline]U[/mathjaxinline]: </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_s12-wk9-factoring-feedback_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_s12-wk9-factoring-feedback_2_1" data-plain-id="s12-wk9-factoring-feedback_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_s12-wk9-factoring-feedback_2_1" style="display:none;">{"base_image": "/assets/courseware/v1/ddc3fcd197efffebade48c3aad81c431/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eig_wk5-factoring-eig_dnd.png", "targets": [{"id": "1", "y": "58", "w": "100", "x": "100", "h": "71"}, {"id": "2", "y": "1", "w": "100", "x": "276", "h": "71"}], "label_bg_color": "rgb(222, 139, 238)", "draggables": [{"id": "one", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/490c934bfaad07f8459dc6ecbf76a883/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eig_wk5-factoring-eig_dnd_label1.png"}, {"id": "two", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/ef798b1959f96b350dacd5842ef2f80b/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eig_wk5-factoring-eig_dnd_label2.png"}, {"id": "sr", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/eda2fc98ac3b35e653415d07a0bbf6d6/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eig_wk5-factoring-eig_dnd_label3.png"}, {"id": "srx", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/7facce4a50756a14dea1247b693e6b85/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eig_wk5-factoring-eig_dnd_label4.png"}, {"id": "evalx", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/046a2ab8e5955a00b772593c2a651066/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eig_wk5-factoring-eig_dnd_label5.png"}, {"id": "eval", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/c9e7e66b54b30d7f0b14e2e874860213/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eig_wk5-factoring-eig_dnd_label6.png"}, {"id": "evalxx", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/bfeeb507f4796d683253a1a02eae0207/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eig_wk5-factoring-eig_dnd_label7.png"}], "one_per_target": "true", "target_outline": "false"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_s12-wk9-factoring-feedback_2_1">
<input type="text" name="input_s12-wk9-factoring-feedback_2_1" id="input_s12-wk9-factoring-feedback_2_1" aria-describedby="answer_s12-wk9-factoring-feedback_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_s12-wk9-factoring-feedback_2_1">
<span class="status unanswered" id="status_s12-wk9-factoring-feedback_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_s12-wk9-factoring-feedback_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback_solution_1"/>
</div></span>
<p>
Let [mathjaxinline]|{\lambda _ k}\rangle[/mathjaxinline] denote an eigenstate of [mathjaxinline]U[/mathjaxinline]. Complete the following expression giving the eigenvalue of this state: </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div id="inputtype_s12-wk9-factoring-feedback_3_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_s12-wk9-factoring-feedback_3_1" data-plain-id="s12-wk9-factoring-feedback_3_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_s12-wk9-factoring-feedback_3_1" style="display:none;">{"base_image": "/assets/courseware/v1/6771170bc8c49c37275dd3a6c94f7d7e/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eigv_wk5-factoring-eigv_dnd.png", "targets": [{"id": "1", "y": "1", "w": "139", "x": "121", "h": "71"}], "label_bg_color": "rgb(222, 139, 238)", "draggables": [{"id": "evalx", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/d555e8cd4534633866bb552ade08cb95/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eigv_wk5-factoring-eigv_dnd_label1.png"}, {"id": "eval", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/c56fd865321f41230594b8f35ed8f6a7/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eigv_wk5-factoring-eigv_dnd_label2.png"}, {"id": "evalxx", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/4bda92ce5d5ed1a4e5e6d8c27563da10/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eigv_wk5-factoring-eigv_dnd_label3.png"}, {"id": "evalm", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/3ec3d2d8787ed13c824c48173797e6cf/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eigv_wk5-factoring-eigv_dnd_label4.png"}, {"id": "evalxm", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/732d3f10544120f9dd0e7f794a19cf12/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eigv_wk5-factoring-eigv_dnd_label5.png"}, {"id": "evalmxx", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/414b11792159cb1da9ae0bffc2cbf36f/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-eigv_wk5-factoring-eigv_dnd_label6.png"}], "one_per_target": "true", "target_outline": "false"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_s12-wk9-factoring-feedback_3_1">
<input type="text" name="input_s12-wk9-factoring-feedback_3_1" id="input_s12-wk9-factoring-feedback_3_1" aria-describedby="answer_s12-wk9-factoring-feedback_3_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_s12-wk9-factoring-feedback_3_1">
<span class="status unanswered" id="status_s12-wk9-factoring-feedback_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_s12-wk9-factoring-feedback_3_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback_solution_2"/>
</div></span>
<p>
From number theory it is known that for a randomly chosen [mathjaxinline]y[/mathjaxinline], with probability greater than 50%, from [mathjaxinline]r[/mathjaxinline] a factor of [mathjaxinline]N[/mathjaxinline] can be found. Factoring [mathjaxinline]N[/mathjaxinline] can thus be reduced to finding [mathjaxinline]r[/mathjaxinline]. The calculation here indicates that finding [mathjaxinline]r[/mathjaxinline] is equivalent to finding an eigenvalue of [mathjaxinline]U[/mathjaxinline]. </p>
<p>
We consider next a circuit by which this may be accomplished. </p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring as a feedback process" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2">
<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-wk9-factoring-feedback2" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback2" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback2-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback2-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-problem-progress" tabindex="-1">
Quantum factoring as a feedback process II
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-problem-progress"></div>
<div class="problem">
<div>
<p>
Consider this quantum circuit: </p>
<center>
<img src="/assets/courseware/v1/aa2aed976f9aa9170d311c3f48ddd1a8/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps9-kitaev-factoring.png" width="400"/>
</center>
<p>
This is one step of a Kitaev factoring algorithm, in which the top wire carries an ancilla qubit, and the bottom (thick) wire carries the main [mathjaxinline]L[/mathjaxinline] qubit state. Let the initial input state into the controlled-[mathjaxinline]U[/mathjaxinline] gate be [mathjaxinline]|{\psi _0}\rangle = |{\lambda }\rangle[/mathjaxinline], an eigenstate with eigenvalue [mathjaxinline]\phi[/mathjaxinline]. </p>
<p>
The state [mathjaxinline]|\chi \rangle[/mathjaxinline] of the system just before the measurement can be expressed as </p>
<table id="a0000000021" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|\chi \rangle = |A\rangle \otimes |\lambda \rangle \, ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.2)</td>
</tr>
</table>
<p>
where [mathjaxinline]|A\rangle[/mathjaxinline] is the &#8220;ancilla" qubit which is measured. </p>
<p>
Complete the following expression for the ancilla qubit state: </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_s12-wk9-factoring-feedback2_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_s12-wk9-factoring-feedback2_2_1" data-plain-id="s12-wk9-factoring-feedback2_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_s12-wk9-factoring-feedback2_2_1" style="display:none;">{"base_image": "/assets/courseware/v1/70382af896b6797a9d09b2cb7d1f4559/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancilla_wk5-factoring-ancilla_dnd.png", "targets": [{"id": "1", "y": "9", "w": "139", "x": "186", "h": "71"}, {"id": "2", "y": "9", "w": "138", "x": "414", "h": "71"}], "label_bg_color": "rgb(222, 139, 238)", "draggables": [{"id": "xphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/3e6d5c7c9eead8ccc685e1e2abecd4a8/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancilla_wk5-factoring-ancilla_dnd_label1.png"}, {"id": "xmphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/2d9191a27556da5f44f984770d08c017/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancilla_wk5-factoring-ancilla_dnd_label2.png"}, {"id": "cphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/3a027972a90d167f5cbffd88bbc3780b/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancilla_wk5-factoring-ancilla_dnd_label3.png"}, {"id": "sphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/6a8a8e05e9809d6ed79aad3addbfff38/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancilla_wk5-factoring-ancilla_dnd_label4.png"}, {"id": "msphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/91596fd9e9dc64ec400a50a90e5ee8d0/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancilla_wk5-factoring-ancilla_dnd_label5.png"}], "one_per_target": "true", "target_outline": "false"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_s12-wk9-factoring-feedback2_2_1">
<input type="text" name="input_s12-wk9-factoring-feedback2_2_1" id="input_s12-wk9-factoring-feedback2_2_1" aria-describedby="answer_s12-wk9-factoring-feedback2_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_s12-wk9-factoring-feedback2_2_1">
<span class="status unanswered" id="status_s12-wk9-factoring-feedback2_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_s12-wk9-factoring-feedback2_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback2_solution_1"/>
</div></span>
<p>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback2_solution_2"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring as a feedback process II" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback2" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback2">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback3">
<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-wk9-factoring-feedback3" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback3" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback3-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback3" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback3/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback3-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback3-problem-progress" tabindex="-1">
Quantum factoring as a feedback process III
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback3-problem-progress"></div>
<div class="problem">
<div>
<p>
What is the probability [mathjaxinline]p_0[/mathjaxinline] that the ancilla is measured to be [mathjaxinline]0[/mathjaxinline]? </p>
<p>
Please enter your result using [mathjaxinline]{\tt cos}[/mathjaxinline] or [mathjaxinline]{\tt sin}[/mathjaxinline] functions, in terms of [mathjaxinline]\phi[/mathjaxinline]. Enter [mathjaxinline]\phi[/mathjaxinline] as [mathjaxinline]{\tt phi}[/mathjaxinline], and use <tt class="tt">^</tt> for exponentiation. </p>
<p>
<p style="display:inline">[mathjaxinline]p_0 =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_s12-wk9-factoring-feedback3_2_1" class="text-input-dynamath capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_s12-wk9-factoring-feedback3_2_1" id="input_s12-wk9-factoring-feedback3_2_1" aria-describedby="status_s12-wk9-factoring-feedback3_2_1" value="" class="math" size="70"/>
<span class="trailing_text" id="trailing_text_s12-wk9-factoring-feedback3_2_1"/>
<span class="status unanswered" id="status_s12-wk9-factoring-feedback3_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_s12-wk9-factoring-feedback3_2_1" class="answer"/>
<div id="display_s12-wk9-factoring-feedback3_2_1" class="equation">`{::}`</div>
<textarea style="display:none" id="input_s12-wk9-factoring-feedback3_2_1_dynamath" name="input_s12-wk9-factoring-feedback3_2_1_dynamath"/>
</div>
</div></div>
</p>
<p>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback3_solution_1"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring as a feedback process III" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback3" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback3">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback3-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback3-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback3-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box2xxxxxx">
<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_box2xxxxxx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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@Factoring_using_feedback_repetition" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True">
<h2 class="hd hd-2 unit-title">Factoring using feedback: repetition</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1">
<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-wk9-factoring-feedback1" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback1" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback1-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback1-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-problem-progress" tabindex="-1">
Quantum factoring by feedback: repetition
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-problem-progress"></div>
<div class="problem">
<div>
<p>
This problem continues the study of Kitaev's factoring algorithm, as posed in the previous problem. </p>
<p>
Let [mathjaxinline]N[/mathjaxinline] be a composite number we wish to factor, and choose some [mathjaxinline]y[/mathjaxinline] coprime to [mathjaxinline]N[/mathjaxinline]. For [mathjaxinline]U[/mathjaxinline] defined as </p>
<table id="a0000000026" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]U |{m}\rangle = |{m y \, {\rm mod}\, N}\rangle \, ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.6)</td>
</tr>
</table>
<p>
we have that its eigenstates [mathjaxinline]|\lambda _ k\rangle[/mathjaxinline] have eigenvalues [mathjaxinline]e^{-2\pi i \phi _ k}[/mathjaxinline] with [mathjaxinline]\phi _ k = k/r[/mathjaxinline]. The goal of the factoring algorithm is to determine [mathjaxinline]r[/mathjaxinline], or equivalently, [mathjaxinline]k/r[/mathjaxinline]. </p>
<p>
The starting point of Kitaev's algorithm is this quantum circuit: </p>
<center>
<img src="/assets/courseware/v1/aa2aed976f9aa9170d311c3f48ddd1a8/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps9-kitaev-factoring.png" width="400"/>
</center>
<p>
Here, we show that we can obtain an estimate of [mathjaxinline]k/r[/mathjaxinline] by repetition, and measurement of the number [mathjaxinline]n[/mathjaxinline] of ancilla qubits measured to be [mathjaxinline]0[/mathjaxinline], via the conditional probabilty distribution [mathjaxinline]p(k|n)[/mathjaxinline]. </p>
<p>
The above scheme would not be very useful if we already knew enough to be able to generate an eigenstate at the outset to feed into the system! What happens if we do not start with an eigenstate, and instead have the input state </p>
<table id="a0000000027" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|{\psi _0}\rangle = |{1}\rangle = \frac{1}{\sqrt{r}}\sum _{k=0}^{r-1} |{\lambda _ k}\rangle \, ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.7)</td>
</tr>
</table>
<p>
which is an equally weighted superposition of eigenstates? </p>
<p>
Note that [mathjaxinline]|{1}\rangle[/mathjaxinline] is simple to generate. Also, recall that [mathjaxinline]\phi _ k = k/r[/mathjaxinline]. </p>
<p>
The output state after one trial, with this superposition as input (instead of [mathjaxinline]|\lambda \rangle[/mathjaxinline]), may be written as </p>
<table id="a0000000028" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|{\chi }\rangle = \frac{1}{\sqrt{r}}\sum _{k=0}^{r-1} |{A_ k}\rangle |{\lambda _ k}\rangle \, ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.8)</td>
</tr>
</table>
<p>
where [mathjaxinline]|A_ k\rangle[/mathjaxinline] is the state of the ancilla qubit. </p>
<p>
Complete the following expression for [mathjaxinline]|A_ k\rangle[/mathjaxinline]. </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_s12-wk9-factoring-feedback1_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_s12-wk9-factoring-feedback1_2_1" data-plain-id="s12-wk9-factoring-feedback1_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_s12-wk9-factoring-feedback1_2_1" style="display:none;">{"base_image": "/assets/courseware/v1/a5bd5ea45e81fe85157834a6eacbedb9/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancillak_wk5-factoring-ancillak_dnd.png", "targets": [{"id": "1", "y": "9", "w": "138", "x": "201", "h": "71"}, {"id": "2", "y": "9", "w": "139", "x": "428", "h": "71"}], "label_bg_color": "rgb(222, 139, 238)", "draggables": [{"id": "xphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/2557cf8358afa5421ec3a158dd4f7230/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancillak_wk5-factoring-ancillak_dnd_label1.png"}, {"id": "xmphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/e43491516eedd1d2dcee90faad35ac98/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancillak_wk5-factoring-ancillak_dnd_label2.png"}, {"id": "cphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/5e7c81c2be97656e5b691a6779c90577/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancillak_wk5-factoring-ancillak_dnd_label3.png"}, {"id": "sphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/46184e0aa24b7d4c6c7ec41ce60a3521/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancillak_wk5-factoring-ancillak_dnd_label4.png"}, {"id": "msphi", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/1461eed050adc6898e41cfc9d99b89d9/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-ancillak_wk5-factoring-ancillak_dnd_label5.png"}], "one_per_target": "true", "target_outline": "false"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_s12-wk9-factoring-feedback1_2_1">
<input type="text" name="input_s12-wk9-factoring-feedback1_2_1" id="input_s12-wk9-factoring-feedback1_2_1" aria-describedby="answer_s12-wk9-factoring-feedback1_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_s12-wk9-factoring-feedback1_2_1">
<span class="status unanswered" id="status_s12-wk9-factoring-feedback1_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_s12-wk9-factoring-feedback1_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback1_solution_1"/>
</div></span>
<p>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback1_solution_2"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring by feedback: repetition" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback1">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-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@s12-wk9-factoring-feedback1-2" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback1-2" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback1-2-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-2" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-2/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback1-2-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-2-problem-progress" tabindex="-1">
Quantum factoring by feedback: repetition II
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-2-problem-progress"></div>
<div class="problem">
<div>
<p>
After the first trial, the state [mathjaxinline]|\psi _1\rangle[/mathjaxinline] is <em>fed back</em> in as the input, in place of [mathjaxinline]|\psi _0\rangle[/mathjaxinline]. This is repeated for a total of [mathjaxinline]t[/mathjaxinline] trials. </p>
<p>
Suppose the [mathjaxinline]t[/mathjaxinline] ancilla qubits are not measured. The overall state of the system with [mathjaxinline]t[/mathjaxinline] ancilla qubits would then be </p>
<table id="a0000000032" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]|\chi _ t\rangle = \frac{1}{\sqrt{r}} \sum _ k |A_ k\rangle ^{\otimes t} |\lambda _ k\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.11)</td>
</tr>
</table>
<p>
Keep in mind that the states [mathjaxinline]|\lambda _ k\rangle[/mathjaxinline] are orthogonal to each other, being distinct eigenstates of [mathjaxinline]U[/mathjaxinline]. </p>
<p>
Now suppose the [mathjaxinline]t[/mathjaxinline] ancilla qubits are measured, with [mathjaxinline]n[/mathjaxinline] bits being found to be [mathjaxinline]0[/mathjaxinline] (and [mathjaxinline]t-n[/mathjaxinline] bits found to be [mathjaxinline]1[/mathjaxinline]). This gives information about [mathjaxinline]k[/mathjaxinline], since [mathjaxinline]n[/mathjaxinline] and [mathjaxinline]k[/mathjaxinline] are correlated to each other. We can appreciate this fact by studying the joint probability distribution [mathjaxinline]p(k,n)[/mathjaxinline], obtained from [mathjaxinline]|\chi _ t\rangle[/mathjaxinline]. </p>
<p>
Complete the following expression for [mathjaxinline]p(k,n)[/mathjaxinline]: </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_s12-wk9-factoring-feedback1-2_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_s12-wk9-factoring-feedback1-2_2_1" data-plain-id="s12-wk9-factoring-feedback1-2_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_s12-wk9-factoring-feedback1-2_2_1" style="display:none;">{"base_image": "/assets/courseware/v1/f2d28ea075148e225e46344bda47dec7/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-pkn_wk5-factoring-pkn_dnd.png", "targets": [{"id": "1", "y": "52", "w": "69", "x": "106", "h": "64"}, {"id": "2", "y": "0", "w": "183", "x": "250", "h": "65"}, {"id": "3", "y": "0", "w": "183", "x": "450", "h": "65"}], "label_bg_color": "rgb(222, 139, 238)", "draggables": [{"id": "two", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/9f03818d8eb12debbb288b031719c24e/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-pkn_wk5-factoring-pkn_dnd_label1.png"}, {"id": "r", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/3f7a347d7821c14adee49dc24838c67e/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-pkn_wk5-factoring-pkn_dnd_label2.png"}, {"id": "sr", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/e6845b9ee064cfd270aa4c6b8f4ff2c5/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-pkn_wk5-factoring-pkn_dnd_label3.png"}, {"id": "coskrtn", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/82c2cebc7ab0514d9e49c0aca2052176/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-pkn_wk5-factoring-pkn_dnd_label4.png"}, {"id": "coskr", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/0647b46949350fb47450095babbc4ea4/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-pkn_wk5-factoring-pkn_dnd_label5.png"}, {"id": "sinkr", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/1f7fe53a522bd3f34e693bbde075a303/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-pkn_wk5-factoring-pkn_dnd_label6.png"}, {"id": "sinkrn", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/507979ef33273db0860c5dc173316db5/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-pkn_wk5-factoring-pkn_dnd_label7.png"}], "one_per_target": "true", "target_outline": "false"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_s12-wk9-factoring-feedback1-2_2_1">
<input type="text" name="input_s12-wk9-factoring-feedback1-2_2_1" id="input_s12-wk9-factoring-feedback1-2_2_1" aria-describedby="answer_s12-wk9-factoring-feedback1-2_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_s12-wk9-factoring-feedback1-2_2_1">
<span class="status unanswered" id="status_s12-wk9-factoring-feedback1-2_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_s12-wk9-factoring-feedback1-2_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback1-2_solution_1"/>
</div></span>
<p>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback1-2_solution_2"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring by feedback: repetition II" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback1-2" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback1-2">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-2-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-2-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-2-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-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@s12-wk9-factoring-feedback1-3" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback1-3" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback1-3-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-3" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-3/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback1-3-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-3-problem-progress" tabindex="-1">
Quantum factoring by feedback: repetition III
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-3-problem-progress"></div>
<div class="problem">
<div>
<p>
From the joint distribution [mathjaxinline]p(k,n)[/mathjaxinline] we can find the marginal distribution p(n) = &#8721;_k=0^r-1 p(k,n) and use that to compute the conditional distribution [mathjaxinline]p(k|n)=p(k,n)/p(n)[/mathjaxinline] by Bayes rule. </p>
<p>
Ideally, this would give a nice closed-form expression for [mathjaxinline]p(k|n)[/mathjaxinline]. However, a nice expression for the summation in the expression for [mathjaxinline]p(n)[/mathjaxinline] is unknown (can you find one?). Also, we are mostly interested in the dependence of [mathjaxinline]p(k|n)[/mathjaxinline] on [mathjaxinline]k[/mathjaxinline]. This may be uncovererd by splitting [mathjaxinline]p(k|n)[/mathjaxinline] into parts which depend on [mathjaxinline]k[/mathjaxinline], and parts which depend only on [mathjaxinline]t[/mathjaxinline] and [mathjaxinline]n[/mathjaxinline], ie: </p>
<table id="a0000000036" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]p(k|n) = f(t,n) q(t,n,k) \, .[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.14)</td>
</tr>
</table>
<p>
We may approximate [mathjaxinline]f(t,n)[/mathjaxinline] as </p>
<table id="a0000000037" class="eqnarray" cellspacing="0" cellpadding="7" width="100%" style="table-layout:auto">
<tr id="a0000000038">
<td style="width:40%; border:none">&#160;</td>
<td style="vertical-align:middle; text-align:right; border:none">
[mathjaxinline]\displaystyle f(t,n)[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:center; border:none">
[mathjaxinline]\displaystyle =[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle \frac{1}{r}{t \choose n} \frac{1}{p(n)}[/mathjaxinline]
</td>
<td style="width:40%; border:none">&#160;</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.15)</td>
</tr>
<tr id="a0000000039">
<td style="width:40%; border:none">&#160;</td>
<td style="vertical-align:middle; text-align:right; border:none">
&#160;
</td>
<td style="vertical-align:middle; text-align:center; border:none">
[mathjaxinline]\displaystyle \approx[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle \frac{1}{r}{t \choose n} \frac{-1+e^{8(1+t^{-1})}}{e^{(4-8n)/t} \left(e^8+e^{16n/t}\right) \sinh (4/t)} \, .[/mathjaxinline]
</td>
<td style="width:40%; border:none">&#160;</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.16)</td>
</tr>
</table>
<p>
Complete the following expression for [mathjaxinline]q(t,n,k)[/mathjaxinline]. </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_s12-wk9-factoring-feedback1-3_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_s12-wk9-factoring-feedback1-3_2_1" data-plain-id="s12-wk9-factoring-feedback1-3_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_s12-wk9-factoring-feedback1-3_2_1" style="display:none;">{"base_image": "/assets/courseware/v1/197ec984987d2b43c6800f837b690264/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-qtnk_wk5-factoring-qtnk_dnd.png", "targets": [{"id": "1", "y": "1", "w": "211", "x": "161", "h": "74"}, {"id": "2", "y": "1", "w": "210", "x": "393", "h": "74"}], "label_bg_color": "rgb(222, 139, 238)", "draggables": [{"id": "coskrtn", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/b6461c21c4fd7f224836e8b7ee2a9ff6/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-qtnk_wk5-factoring-qtnk_dnd_label1.png"}, {"id": "coskr", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/8b7e02952b112e52739f960166675733/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-qtnk_wk5-factoring-qtnk_dnd_label2.png"}, {"id": "sinkr", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/041347ca7029d069b648372c318be66b/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-qtnk_wk5-factoring-qtnk_dnd_label3.png"}, {"id": "sinkrn", "target_fields": [], "can_reuse": "", "label": "", "icon": "/assets/courseware/v1/06d2b8f18bbe6e40efd93c411af0fd33/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-qtnk_wk5-factoring-qtnk_dnd_label4.png"}], "one_per_target": "true", "target_outline": "false"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_s12-wk9-factoring-feedback1-3_2_1">
<input type="text" name="input_s12-wk9-factoring-feedback1-3_2_1" id="input_s12-wk9-factoring-feedback1-3_2_1" aria-describedby="answer_s12-wk9-factoring-feedback1-3_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_s12-wk9-factoring-feedback1-3_2_1">
<span class="status unanswered" id="status_s12-wk9-factoring-feedback1-3_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_s12-wk9-factoring-feedback1-3_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback1-3_solution_1"/>
</div></span>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring by feedback: repetition III" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback1-3" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback1-3">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-3-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-3-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-3-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-4">
<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-wk9-factoring-feedback1-4" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback1-4" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback1-4-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-4" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-4/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback1-4-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-4-problem-progress" tabindex="-1">
Quantum factoring by feedback: repetition IV
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-4-problem-progress"></div>
<div class="problem">
<div>
<p>
Let us define [mathjaxinline]\bar{p}(k|n) = f(t,n,k)[/mathjaxinline]. Plot this distribution as a function of [mathjaxinline]k[/mathjaxinline], for a variety of values for [mathjaxinline]n[/mathjaxinline] and [mathjaxinline]t[/mathjaxinline]. Prove to yourself that the peaks have widths which decrease as [mathjaxinline]1/t[/mathjaxinline]. </p>
<p>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback1-4_solution_1"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring by feedback: repetition IV" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback1-4" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback1-4">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-4-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-4-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-4-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-5">
<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-wk9-factoring-feedback1-5" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback1-5" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback1-5-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-5" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-5/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback1-5-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-5-problem-progress" tabindex="-1">
Quantum factoring by feedback: repetition V
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback1-5-problem-progress"></div>
<div class="problem">
<div>
<p>
Helpful insight is gained by a numerical example. Try running this algorithm for [mathjaxinline]N=143[/mathjaxinline], [mathjaxinline]y=5[/mathjaxinline], and [mathjaxinline]r=20[/mathjaxinline], and plot [mathjaxinline]p(k|n)[/mathjaxinline] for a sequence of values of [mathjaxinline]t[/mathjaxinline]. </p>
<p>
The critical quantity is the convergence rate of our knowledge of the eigenvalue, [mathjaxinline]k/r[/mathjaxinline]. How fast does this uncertainty decrease, as a function of [mathjaxinline]t[/mathjaxinline]? </p>
<p>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback1-5_solution_1"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring by feedback: repetition V" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback1-5" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback1-5">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-5-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-5-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback1-5-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-5" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box3xxxxx">
<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_box3xxxxx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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@Factoring_using_feedback_convergence" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" data-block-type="vertical" data-runtime-version="1" data-has-score="False" data-graded="True">
<h2 class="hd hd-2 unit-title">Factoring using feedback: convergence</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-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@s12-wk9-factoring-feedback2-1" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback2-1" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback2-1-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-1" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-1/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback2-1-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-1-problem-progress" tabindex="-1">
Quantum factoring by feedback: convergence
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-1-problem-progress"></div>
<div class="problem">
<div>
<p>
This problem continues the study of Kitaev's factoring algorithm, as posed in the previous two problems. </p>
<p>
Let [mathjaxinline]N[/mathjaxinline] be a composite number we wish to factor, and choose some [mathjaxinline]y[/mathjaxinline] coprime to [mathjaxinline]N[/mathjaxinline]. For [mathjaxinline]U[/mathjaxinline] defined as </p>
<table id="a0000000051" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]U |{m}\rangle = |{m y \, {\rm mod}\, N}\rangle \, ,[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.25)</td>
</tr>
</table>
<p>
we have that its eigenstates [mathjaxinline]|\lambda _ k\rangle[/mathjaxinline] have eigenvalues [mathjaxinline]e^{-2\pi i \phi _ k}[/mathjaxinline] with [mathjaxinline]\phi _ k = k/r[/mathjaxinline]. The goal of the factoring algorithm is to determine [mathjaxinline]r[/mathjaxinline], or equivalently, [mathjaxinline]k/r[/mathjaxinline]. </p>
<p>
The starting point of Kitaev's algorithm is this quantum circuit: </p>
<center>
<img src="/assets/courseware/v1/aa2aed976f9aa9170d311c3f48ddd1a8/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps9-kitaev-factoring.png" width="400"/>
</center>
<p>
with which we can obtain an estimate of [mathjaxinline]k/r[/mathjaxinline] by repetition, and measurement of the number [mathjaxinline]n[/mathjaxinline] of ancilla qubits measured to be [mathjaxinline]0[/mathjaxinline], via the conditional probabilty distribution [mathjaxinline]p(k|n)[/mathjaxinline]. However, this initial version of the algorithm converges slowly. </p>
<p>
One of the inefficiencies of the scheme analyzed in the previous problem is the fact that even after the system has converged into a perfect eigenstate, the measurement result from each iteration can still vary quite randomly. That is, once [mathjaxinline]k[/mathjaxinline] has converged to a fixed value, we still obtain a zero with a probability which can be significant. </p>
<p>
Ideally, we would like arrange the output distribution so as to maximize the mutual information between each measurement and the unknown eigenvalue [mathjaxinline]\phi _ k[/mathjaxinline]. Kitaev's algorithm takes a step in that direction by modifying the above quantum circuit to become: </p>
<center>
<img src="/assets/courseware/v1/5aaeb784df6cfeffac066cf8db77ce7e/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_ps9-kitaev-factoring-with-feedback-Up.png" width="600"/>
</center>
<p>
Note that an additional component is added in the control path, a [mathjaxinline]\theta[/mathjaxinline] box, which implements the transform </p>
<table id="a0000000052" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr>
<td class="equation" style="width:80%; border:none">[mathjax]\left[ \begin{array}{cc}{1}&amp; {0}\\ {0}&amp; {e^{2\pi i\theta }}\end{array}\right][/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.26)</td>
</tr>
</table>
<p>
on the control bit, where [mathjaxinline]\theta[/mathjaxinline] is a classically determined angle, provided by a classical control apparatus. </p>
<p>
Operation of this circuit is very similar to the previous scenario: an initial state [mathjaxinline]|{\psi _0}\rangle[/mathjaxinline] is prepared and fed into the lower loop. This state will continually circulate, and eventually converges into an eigenstate of the system. </p>
<p>
The difference now is that depending on the accumulated sequence of measurement results, we can estimate the state of the system and change [mathjaxinline]\theta[/mathjaxinline] accordingly to bias future measurement outputs so that they have low entropy. Another variable which can be classically controlled by feedback is [mathjaxinline]x[/mathjaxinline], the power of [mathjaxinline]U[/mathjaxinline] which is applied by the controlled-[mathjaxinline]U^ x[/mathjaxinline] gate. </p>
<p>
Analyze how this circuit works in detail, by following the state around one iteration of the loop, assuming it starts initially with an eigenstate input, [mathjaxinline]|{0}\rangle |{\lambda _ k}\rangle[/mathjaxinline], obtaining [mathjaxinline]|A_\theta \rangle \otimes |\lambda _ k\rangle[/mathjaxinline] as the pre-measurement output from a single trial. Also assume for simplicity that [mathjaxinline]p=1[/mathjaxinline]. </p>
<p>
Complete the following expression for [mathjaxinline]|A_\theta \rangle[/mathjaxinline]. </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_s12-wk9-factoring-feedback2-1_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_s12-wk9-factoring-feedback2-1_2_1" data-plain-id="s12-wk9-factoring-feedback2-1_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_s12-wk9-factoring-feedback2-1_2_1" style="display:none;">{"base_image": "/assets/courseware/v1/bef24f0fa569121cb0ee864a2cfd468f/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-atheta_wk5-factoring-atheta_dnd.png", "targets": [{"id": "1", "y": "7", "w": "158", "x": "315", "h": "75"}, {"id": "3", "y": "60", "w": "79", "x": "554", "h": "75"}, {"id": "2", "y": "229", "w": "158", "x": "321", "h": "74"}, {"id": "4", "y": "282", "w": "80", "x": "559", "h": "74"}], "label_bg_color": "rgb(222, 139, 238)", "draggables": [{"id": "tpkor", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/e80ca0a49716a245377efbbdde344242/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-atheta_wk5-factoring-atheta_dnd_label1.png"}, {"id": "tmkor", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/df21193fdc4466442608361beb394a7a/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-atheta_wk5-factoring-atheta_dnd_label2.png"}, {"id": "t", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/2923dbdfc6f0e7ae672b552b82b23c59/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-atheta_wk5-factoring-atheta_dnd_label3.png"}, {"id": "kor", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/0fd2ba1fe24feb7a510d54ae5d31d1d4/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-atheta_wk5-factoring-atheta_dnd_label4.png"}, {"id": "kz", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/885880dc9b5a03a105078779206a690b/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-atheta_wk5-factoring-atheta_dnd_label5.png"}, {"id": "ko", "target_fields": [], "can_reuse": "true", "label": "", "icon": "/assets/courseware/v1/69190457d798d0a1ac1036f9641edac6/asset-v1:MITx+8.371.3x+2T2018+type@asset+block/images_wk5-factoring-atheta_wk5-factoring-atheta_dnd_label6.png"}], "one_per_target": "true", "target_outline": "false"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_s12-wk9-factoring-feedback2-1_2_1">
<input type="text" name="input_s12-wk9-factoring-feedback2-1_2_1" id="input_s12-wk9-factoring-feedback2-1_2_1" aria-describedby="answer_s12-wk9-factoring-feedback2-1_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_s12-wk9-factoring-feedback2-1_2_1">
<span class="status unanswered" id="status_s12-wk9-factoring-feedback2-1_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_s12-wk9-factoring-feedback2-1_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback2-1_solution_1"/>
</div></span>
<p>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback2-1_solution_2"/>
</div></p>
<p>
Note that if we choose [mathjaxinline]\theta = \phi _ k[/mathjaxinline] then [mathjaxinline]p_0 = 1[/mathjaxinline]. This is good, because then a measurement of [mathjaxinline]1[/mathjaxinline], being an unlikely event (if our estimator is correct), would give us a relatively large amount of information about the error [mathjaxinline]|\theta - \phi _ k|[/mathjaxinline]. </p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring by feedback: convergence" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback2-1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback2-1">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-1-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-1-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-1-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-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@s12-wk9-factoring-feedback2-2" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback2-2" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback2-2-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-2" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-2/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback2-2-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-2-problem-progress" tabindex="-1">
Quantum factoring by feedback: convergence II
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-2-problem-progress"></div>
<div class="problem">
<div>
<p>
Coming up with a good estimator model is nontrivial, especially since the system changes non-deterministically each time a measurement is performed. In particular, when feedback is performed, the expression we obtained for [mathjaxinline]p(k|n)[/mathjaxinline] is no longer a good estimate of the state, since the evolution now becomes a function of the record of prior measurement results! </p>
<p>
Construct an algorithm for updating [mathjaxinline]\theta[/mathjaxinline] based on the measurement record obtained, using the idea that [mathjaxinline]\{ f_0,f_1,\ldots \}[/mathjaxinline] is a model (series of functions of [mathjaxinline]\phi[/mathjaxinline]) of what we expect the system's conditional probability distribution for [mathjaxinline]\phi _ k[/mathjaxinline] to look like. Append new multiplicative terms to this function after each iteration, depending on the measurement results obtained. </p>
<p>
Evaluate your algorithm, for example, using a trial run with parameters [mathjaxinline]N=143[/mathjaxinline], [mathjaxinline]y=5[/mathjaxinline], [mathjaxinline]r=20[/mathjaxinline]. </p>
<p>
<div class="solution-span">
<span id="solution_s12-wk9-factoring-feedback2-2_solution_1"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring by feedback: convergence II" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback2-2" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback2-2">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-2-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-2-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-2-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-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@s12-wk9-factoring-feedback2-3" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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-wk9-factoring-feedback2-3" class="problems-wrapper" role="group"
aria-labelledby="s12-wk9-factoring-feedback2-3-problem-title"
data-problem-id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-3" data-url="/courses/course-v1:MITx+8.371.3x+2T2018/xblock/block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-3/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="s12-wk9-factoring-feedback2-3-problem-title" aria-describedby="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-3-problem-progress" tabindex="-1">
Quantum factoring by feedback: convergence III
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.3x+2T2018+type@problem+block@s12-wk9-factoring-feedback2-3-problem-progress"></div>
<div class="problem">
<div>
<p>
The procedure suggested in the last step is somewhat unstable in practice, because the estimator for [mathjaxinline]\theta[/mathjaxinline] is very bad at early times. An improved solution would be to estimate [mathjaxinline]\theta[/mathjaxinline] based on a running average of [mathjaxinline]\phi[/mathjaxinline], or from the frequency of occurance of [mathjaxinline]0[/mathjaxinline]. Ideally, you would want something like a Kalman filter. Try to derive an optimal estimation procedure for this feedback based quantum factoring algorithm, and compare your result with Shor's algorithm. What [mathjaxinline]\theta[/mathjaxinline] update rule would you need to be able to obtain the quantum Fourier transform circuit? </p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Quantum factoring by feedback: convergence III" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_s12-wk9-factoring-feedback2-3" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_s12-wk9-factoring-feedback2-3">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save">
<span class="icon fa fa-floppy-o" aria-hidden="true"></span>
<span aria-hidden="true">Save</span>
<span class="sr">Save your answer</span>
</button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-3-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-3-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="s12-wk9-factoring-feedback2-3-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+8.371.3x+2T2018+type@html+block@html_site_search_box4xxx">
<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_box4xxx" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+8.371.3x+2T2018" data-request-token="95ccc098885c11ef87990affec87671b" 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>
© All Rights Reserved