<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@vertical+block@Decision_problems_and_factoring" data-block-type="vertical" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="False">
<h2 class="hd hd-2 unit-title">Decision problems and factoring</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF1">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF1" data-block-type="problem" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="True">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_ps4a_DF1" class="problems-wrapper" role="group"
aria-labelledby="ps4a_DF1-problem-title"
data-problem-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF1" data-url="/courses/course-v1:MITx+8.371.2x+2T2018/xblock/block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF1/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="ps4a_DF1-problem-title" aria-describedby="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF1-problem-progress" tabindex="-1">
DF. A decision version of the factoring problem
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF1-problem-progress"></div>
<div class="problem">
<div>
<p>
Factoring is a central problem in cryptography. For example, the security of RSA protocol is based on hardness of discrete logarithm which is closely related to factoring. We have seen that Shor's algorithm finds the factors of a number in polynomial time. In this problem we investigate a different question: if P = NP then can we find the factors of numbers in polynomial time? </p>
<p>
Note that P vs NP is a statement about decision problems (languages), and finding factors is not immediately a decision task. We first show that if we have a black box that computes the circuit satisfiability problem, then using polynomially many queries to this black box we can find the factors of an arbitrary integer. </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4a_DF1_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_ps4a_DF1_2_1" data-plain-id="ps4a_DF1_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_ps4a_DF1_2_1" style="display:none;">{"draggables": [{"target_fields": [], "label": "", "icon": "/assets/courseware/v1/5785f0ebb077b78efd69c0f597026c8a/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label1.png", "can_reuse": "true", "id": "textNPminuscomplete"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/17a1b36b2981f6f07aa6148d4784018c/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label2.png", "can_reuse": "true", "id": "textexponential"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/dedff9eefe377d8073e89ebddc867056/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label3.png", "can_reuse": "true", "id": "textinteger"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/4ea2aca9f93eacdc549cb7c7359bf6ac/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label4.png", "can_reuse": "true", "id": "textreduction"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/a6537bc46e5a926f4de783adae252857/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label5.png", "can_reuse": "true", "id": "textTuring"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/300b496e95dab9b90d1d3b82e7c58757/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label6.png", "can_reuse": "true", "id": "textnondeterministic"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/a0985ba1c51cd008bfb07b8a5fd52c7c/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label7.png", "can_reuse": "true", "id": "textdeterministic"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/6395b148ac5040c83a112f5812762f16/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label8.png", "can_reuse": "true", "id": "textinNP"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/de1e2018f54d47759f80e6c415ba1ea7/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label9.png", "can_reuse": "true", "id": "textcomplexityminusclass"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/f6c6c08cb8a9ada767779fbd52629b1e/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label10.png", "can_reuse": "true", "id": "textcircuitminussatisfiability"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/a5353001dc4266cd0a178b135e469675/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label11.png", "can_reuse": "true", "id": "textpolynomial"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/73124e64f6cb8cabfc77e4a6831ff6fd/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label12.png", "can_reuse": "true", "id": "textcircuit"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/ec9c4268e168a49f096181ca7003d726/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd_label13.png", "can_reuse": "true", "id": "A"}], "label_bg_color": "rgb(222, 139, 238)", "base_image": "/assets/courseware/v1/3eabbfa8eee74aac59e0040c89fed1c4/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF1_ps4a_DF1_dnd.png", "target_outline": "false", "targets": [{"w": "242", "y": "0", "x": "498", "id": "1", "h": "60"}, {"w": "242", "y": "78", "x": "454", "id": "5", "h": "60"}, {"w": "242", "y": "157", "x": "7", "id": "2", "h": "59"}, {"w": "241", "y": "235", "x": "192", "id": "3", "h": "59"}, {"w": "241", "y": "313", "x": "341", "id": "4", "h": "59"}], "one_per_target": "true"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_ps4a_DF1_2_1">
<input type="text" name="input_ps4a_DF1_2_1" id="input_ps4a_DF1_2_1" aria-describedby="answer_ps4a_DF1_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_ps4a_DF1_2_1">
<span class="status unanswered" id="status_ps4a_DF1_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_ps4a_DF1_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_ps4a_DF1_solution_1"/>
</div></span>
<p>
Factoring is a functional task, and so does not immediately correspond to a language . We will define the language DF (Decision-to-factoring) to consist of all pairs of positive integers [mathjaxinline]N:a[/mathjaxinline], such that [mathjaxinline]N = p q[/mathjaxinline], [mathjaxinline]1&lt; p &lt; q[/mathjaxinline] and [mathjaxinline]p \leq a[/mathjaxinline]. </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div id="inputtype_ps4a_DF1_3_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_ps4a_DF1_3_1" data-plain-id="ps4a_DF1_3_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_ps4a_DF1_3_1" style="display:none;">{"draggables": [{"target_fields": [], "label": "", "icon": "/assets/courseware/v1/347ba57d540f72642f86154648079f22/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label1.png", "can_reuse": "true", "id": "textexponential"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/d8b6ca1d59228289f0c02589ebd8a348/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label2.png", "can_reuse": "true", "id": "textTuring"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/3ac210f5ac57ac5539ab1edae0ffe588/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label3.png", "can_reuse": "true", "id": "textnondeterministic"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/f834471367d63997fc5681fd91baeacd/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label4.png", "can_reuse": "true", "id": "pleqa"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/73252d92f338812155a3534d9ef6d8f3/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label5.png", "can_reuse": "true", "id": "Na"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/6588e6347e2aa0d2a2673ed45e6d60b4/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label6.png", "can_reuse": "true", "id": "Np"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/55aad078fda1832fa1c2b72483be8815/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label7.png", "can_reuse": "true", "id": "textdeterministic"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/ef20a276ccc941e44b3c4fbd87145cb9/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label8.png", "can_reuse": "true", "id": "textpolynomial"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/f292cc94fc7d59bf21021feda0bed2ad/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label9.png", "can_reuse": "true", "id": "textcircuit"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/28314dc1891a3242df4300ca323abc00/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label10.png", "can_reuse": "true", "id": "A"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/ef6f2dd7d67052e14d491b77e6d9a6b1/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label11.png", "can_reuse": "true", "id": "fNa"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/fe51886afb2f22e0ddbca1bf4522a54b/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd_label12.png", "can_reuse": "true", "id": "fNp"}], "label_bg_color": "rgb(222, 139, 238)", "base_image": "/assets/courseware/v1/33d7b6927a7cc715378ccf96d31dd401/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_DF2_ps4a_DF2_dnd.png", "target_outline": "false", "targets": [{"w": "211", "y": "0", "x": "350", "id": "1", "h": "52"}, {"w": "211", "y": "68", "x": "23", "id": "2", "h": "52"}, {"w": "211", "y": "68", "x": "254", "id": "3", "h": "52"}, {"w": "211", "y": "137", "x": "44", "id": "4", "h": "51"}, {"w": "210", "y": "205", "x": "353", "id": "5", "h": "52"}, {"w": "211", "y": "273", "x": "476", "id": "14", "h": "52"}, {"w": "211", "y": "341", "x": "30", "id": "6", "h": "52"}, {"w": "211", "y": "341", "x": "528", "id": "15", "h": "52"}, {"w": "211", "y": "430", "x": "6", "id": "13", "h": "52"}], "one_per_target": "true"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_ps4a_DF1_3_1">
<input type="text" name="input_ps4a_DF1_3_1" id="input_ps4a_DF1_3_1" aria-describedby="answer_ps4a_DF1_3_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_ps4a_DF1_3_1">
<span class="status unanswered" id="status_ps4a_DF1_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_ps4a_DF1_3_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_ps4a_DF1_solution_2"/>
</div></span>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="DF. A decision version of the factoring problem" />
<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_ps4a_DF1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4a_DF1">
<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="ps4a_DF1-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="ps4a_DF1-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="ps4a_DF1-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.2x+2T2018+type@problem+block@ps4a_DF2">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF2" data-block-type="problem" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="True">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_ps4a_DF2" class="problems-wrapper" role="group"
aria-labelledby="ps4a_DF2-problem-title"
data-problem-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF2" data-url="/courses/course-v1:MITx+8.371.2x+2T2018/xblock/block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF2/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="ps4a_DF2-problem-title" aria-describedby="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF2-problem-progress" tabindex="-1">
DF. Factoring black box
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF2-problem-progress"></div>
<div class="problem">
<div>
<p>
We have secretly implemented an algorithm to solve the DF problem, but before you get too excited, note that it only works when [mathjaxinline]N=1111987117303[/mathjaxinline]. Use this to find a nontrivial factor of [mathjaxinline]N[/mathjaxinline]. In the box below you can enter [mathjaxinline]a[/mathjaxinline] and our black box tells you if [mathjaxinline]N:a[/mathjaxinline] is in DF. </p>
<p>
Input your queries here: </p>
<p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4a_DF2_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_ps4a_DF2_2_1" id="input_ps4a_DF2_2_1" aria-describedby="status_ps4a_DF2_2_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4a_DF2_2_1"/>
<span class="status unanswered" id="status_ps4a_DF2_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_DF2_2_1" class="answer"/>
</div>
</div></div>
</p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="DF. Factoring black box" />
<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_ps4a_DF2" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4a_DF2">
<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="ps4a_DF2-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="ps4a_DF2-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="ps4a_DF2-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.2x+2T2018+type@problem+block@ps4a_DF3">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF3" data-block-type="problem" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="True">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_ps4a_DF3" class="problems-wrapper" role="group"
aria-labelledby="ps4a_DF3-problem-title"
data-problem-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF3" data-url="/courses/course-v1:MITx+8.371.2x+2T2018/xblock/block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF3/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="ps4a_DF3-problem-title" aria-describedby="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF3-problem-progress" tabindex="-1">
DF. Example of reduction from factoring to decision problem
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DF3-problem-progress"></div>
<div class="problem">
<div>
<p>
Can you tell us the smallest factor of this number? </p>
<p>
Input your answer here: </p>
<p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4a_DF3_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_ps4a_DF3_2_1" id="input_ps4a_DF3_2_1" aria-describedby="status_ps4a_DF3_2_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4a_DF3_2_1"/>
<span class="status unanswered" id="status_ps4a_DF3_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_DF3_2_1" class="answer"/>
</div>
</div></div>
</p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="DF. Example of reduction from factoring to decision problem" />
<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_ps4a_DF3" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4a_DF3">
<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="ps4a_DF3-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="ps4a_DF3-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="ps4a_DF3-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>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@vertical+block@DQC1__The_one-clean-qubit_model" data-block-type="vertical" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="False">
<h2 class="hd hd-2 unit-title">DQC1. The one-clean-qubit model</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DQC1">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DQC1" data-block-type="problem" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="True">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_ps4a_DQC1" class="problems-wrapper" role="group"
aria-labelledby="ps4a_DQC1-problem-title"
data-problem-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DQC1" data-url="/courses/course-v1:MITx+8.371.2x+2T2018/xblock/block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DQC1/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="ps4a_DQC1-problem-title" aria-describedby="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DQC1-problem-progress" tabindex="-1">
DQC1. The one-clean-qubit model
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_DQC1-problem-progress"></div>
<div class="problem">
<div>
<p>
One of the intermediate models of quantum computation is the one-clean-qubit model. Suppose you have a quantum computer with [mathjaxinline]n[/mathjaxinline] qubits, but unfortunately we are only able to initialize one of the qubits into the [mathjaxinline]|{0}\rangle[/mathjaxinline] state, while the rest of the qubits are initialized in a maximally mixed state. Our measurements are also restricted, and we are able to measure only one qubit at the end of the circuit, say the first qubit. However, we are allowed to perform any polynomial length sequence of two-qubit gates, as in the normal quantum circuit model. Let the resulting [mathjaxinline]n[/mathjaxinline]-qubit unitary evolution be [mathjaxinline]U[/mathjaxinline]. </p>
<p>
Despite the limitations of this model, known as DQC1, is capable of estimating the normalized trace of [mathjaxinline]U[/mathjaxinline] (i.e. [mathjaxinline]\text {tr}(U)/\text {tr}(I)[/mathjaxinline]), which is a task that we do not know how to achieve with any classical poly-time algorithm. </p>
<ol class="enumerate">
<li value="1">
<p>
Suppose [mathjaxinline]U[/mathjaxinline] is a single-qubit unitary with all eigenvalues equal to +1 or -1. (This class includes Paulis but is more general.) Suppose we have access to a control-U operation. Call this [mathjaxinline]C_ U[/mathjaxinline]. Show how to use this, together with an ancilla qubit, to measure whether a given input state is in the [mathjaxinline]+1[/mathjaxinline] or the [mathjaxinline]-1[/mathjaxinline] eigenspace of [mathjaxinline]U[/mathjaxinline]. </p>
<p>
Let's say the ancilla qubit is qubit 0 and U acts on qubit 1. We will initialize the ancilla to be in state [mathjaxinline]|0\rangle[/mathjaxinline] and at the end of the circuit will measure the ancilla in the [mathjaxinline]Z[/mathjaxinline] basis. </p>
<p>
Enter your answer below, as a quantum circuit specified by a list of gates, e.g. [mathjaxinline]{\tt [ CU(0,1), H(1), X(0) ]}[/mathjaxinline]: <p style="display:inline">circuit =</p> <span><div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4a_DQC1_2_1" class=" capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_ps4a_DQC1_2_1" id="input_ps4a_DQC1_2_1" aria-describedby="status_ps4a_DQC1_2_1" value="" size="70"/>
<span class="trailing_text" id="trailing_text_ps4a_DQC1_2_1"/>
<span class="status unanswered" id="status_ps4a_DQC1_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_DQC1_2_1" class="answer"/>
</div>
</div></div></span> </p>
<p>
<div class="solution-span">
<span id="solution_ps4a_DQC1_solution_1"/>
</div></p>
</li>
<li value="2">
<p>
Suppose we apply the above circuit to the maximally mixed state I/2. Now suppose that [mathjaxinline]U[/mathjaxinline] is a general single-qubit unitary, i.e. with arbitrary eigenvalues. Let [mathjaxinline]\text {tr}(U)/\text {tr}(I) =x+iy[/mathjaxinline] for real numbers [mathjaxinline]x,y[/mathjaxinline]. What is the probability that the above measurement returns outcome 0? </p>
<p>
Express your answer in terms of [mathjaxinline]x[/mathjaxinline] and [mathjaxinline]y[/mathjaxinline]: </p>
<p>
<div class="inline" tabindex="-1" aria-label="Question 2" role="group"><div id="inputtype_ps4a_DQC1_3_1" class=" capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_ps4a_DQC1_3_1" id="input_ps4a_DQC1_3_1" aria-describedby="status_ps4a_DQC1_3_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_ps4a_DQC1_3_1"/>
<span class="status unanswered" id="status_ps4a_DQC1_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_DQC1_3_1" class="answer"/>
</div>
</div></div>
</p>
<p>
<div class="solution-span">
<span id="solution_ps4a_DQC1_solution_2"/>
</div></p>
</li>
<li value="3">
<p>
In part (b) we saw that the circuit in part (a) could be used to estimate the normalized trace of even a unitary that does not have [mathjaxinline]\pm 1[/mathjaxinline] eigenvalues. The same idea works for unitaries on more than one qubit. </p>
<p>
Let [mathjaxinline]V[/mathjaxinline] be the following 2-qubit circuit, where [mathjaxinline]U[/mathjaxinline] is an arbitrary 1-qubit gate. </p>
<p>
[mathjaxinline]{\tt [U(1), CNOT(1,2), U(2), CNOT(2,1)]}[/mathjaxinline] </p>
<p>
Construct a circuit that can be used to estimate [mathjaxinline]\text {tr}(V)/\text {tr}(I)[/mathjaxinline]: </p>
<p>
<p style="display:inline">circuit =</p>
<span>
<div class="inline" tabindex="-1" aria-label="Question 3" role="group"><div id="inputtype_ps4a_DQC1_4_1" class=" capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_ps4a_DQC1_4_1" id="input_ps4a_DQC1_4_1" aria-describedby="status_ps4a_DQC1_4_1" value="" size="70"/>
<span class="trailing_text" id="trailing_text_ps4a_DQC1_4_1"/>
<span class="status unanswered" id="status_ps4a_DQC1_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_DQC1_4_1" class="answer"/>
</div>
</div></div>
</span>
</p>
</li>
</ol>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="DQC1. The one-clean-qubit model" />
<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_ps4a_DQC1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4a_DQC1">
<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="ps4a_DQC1-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="ps4a_DQC1-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="ps4a_DQC1-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>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@vertical+block@Permanent_is_hard_on_average" data-block-type="vertical" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="False">
<h2 class="hd hd-2 unit-title">Permanent is hard on average</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent1">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent1" data-block-type="problem" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="True">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_ps4a_permanent1" class="problems-wrapper" role="group"
aria-labelledby="ps4a_permanent1-problem-title"
data-problem-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent1" data-url="/courses/course-v1:MITx+8.371.2x+2T2018/xblock/block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent1/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="ps4a_permanent1-problem-title" aria-describedby="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent1-problem-progress" tabindex="-1">
Average case complexity of the permanent polynomial - High-level strategy
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent1-problem-progress"></div>
<div class="problem">
<div>
<p>
In this problem we consider the BosonSampling model of computation, which uses many noninteracting single photons, and a random configuration of beamsplitters and phase-shifters. It has been conjectured that classical computers cannot sample from the output distribution that arises in this model, making this one of the main proposals for quantum supremacy in near-term devices. The output distribution of BosonSampling is closely related to the permanent function which we describe below. </p>
<p>
Let [mathjaxinline]A[/mathjaxinline] be an arbitrary [mathjaxinline]n \times n[/mathjaxinline] matrix. The permanent is the following polynomial in the entries of [mathjaxinline]A[/mathjaxinline]: </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]\text {Per} (A) = \sum _{\sigma \in S_ n} \prod _ i a_{i\sigma (i)}[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
It is similar to the determinant: </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]\text {Det} (A) = \sum _{\sigma \in S_ n}\text { sgn } (\sigma ) \prod _ i a_{i\sigma (i)}[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
except that it doesn't have the sign factor. Here [mathjaxinline]S_ n[/mathjaxinline] is the group of permutations over [mathjaxinline]n[/mathjaxinline] elements. </p>
<p>
Even though determinant is polynomial-time computable, permanent is [mathjaxinline]\# P[/mathjaxinline] hard [<a href="https://www.sciencedirect.com/science/article/pii/0304397579900446" target="_blank">Valiant 1979</a>]. This means that given a black box that can compute the permanent of an arbitrary [mathjaxinline]0,1[/mathjaxinline] matrix, one can count the number of solutions in an arbitrary NP problem. Because of Valiant's observation, we believe that there is no polynomial-time algorithm to compute the permanent in the worst case. It is also known that permanent of arbitrary complex matrices is [mathjaxinline]\# P[/mathjaxinline] hard even to approximate. </p>
<p>
In this problem we ask the following question: suppose we have an algorithm that approximates the permanent of a matrix for a small fraction of matrices, can we use this algorithm to compute the permanent of arbitrary 0,1 matrices? The importance of this question for us is that if such statement holds for the permanent of Gaussian matrices (matrices with i.i.d. Gaussian elements), then (assuming further numerical and complexity theoretic conjectures) this implies that a BosonSampling device is hard to simulate classically within total variation distance. While the Gaussian case is unknown, in this problem we consider a similar but provable result. </p>
<p>
Let [mathjaxinline]A[/mathjaxinline] be a matrix of size [mathjaxinline]n[/mathjaxinline] over a finite field of size [mathjaxinline]p[/mathjaxinline], where [mathjaxinline]p[/mathjaxinline] is a prime we will choose later. We want to show that if there exists an algorithm that computes the permanent exactly for a constant fraction of such matrices, then we can compute the permanent of all such matrices. Assume we have a black box that computes the permanent exactly for a [mathjaxinline]\geq 0.9[/mathjaxinline] fraction of matrices in [mathjaxinline]\mathbb {F}_ p^{n\times n}[/mathjaxinline]. Let [mathjaxinline]X, Y \in \mathbb {F}_ p^{n\times n}[/mathjaxinline]. We consider the function [mathjaxinline]q(t) = \text {Per} (X + t Y)[/mathjaxinline]. </p>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_ps4a_permanent1_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_ps4a_permanent1_2_1" data-plain-id="ps4a_permanent1_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_ps4a_permanent1_2_1" style="display:none;">{"draggables": [{"target_fields": [], "label": "", "icon": "/assets/courseware/v1/cf75f3fac28933ef6e2f36d9e4e1fc64/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label1.png", "can_reuse": "true", "id": "textindependent"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/268cb6769d74a27ae0e2c88272afb5f1/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label2.png", "can_reuse": "true", "id": "textpolynomial"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/db4eaab32de54346434637a98f7a203e/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label3.png", "can_reuse": "true", "id": "one"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/c00145a2a684fee1fcecb00ac60124af/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label4.png", "can_reuse": "true", "id": "n"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/f43469e8fb88c31e0d094f4a6a01e955/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label5.png", "can_reuse": "true", "id": "ntwo"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/548bb260c7ddb0995c9d9da747689a04/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label6.png", "can_reuse": "true", "id": "textlinear"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/cc6e51a2b52cabfb93c3e625956ab963/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label7.png", "can_reuse": "true", "id": "textuniform"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/149b8de3fb6bb835d9ba1912e2c6aced/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label8.png", "can_reuse": "true", "id": "textunivariate"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/f4468692add16ce16018bc5ccdd99491/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label9.png", "can_reuse": "true", "id": "qone"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/4cd3455e1a82e4fd5c2ab266aca2df9c/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label10.png", "can_reuse": "true", "id": "qzero"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/17cacd56f0c07eab97882f6c1bbf7915/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label11.png", "can_reuse": "true", "id": "zeronine"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/0f91bdaa41961a9827c0436e33ca4a98/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label12.png", "can_reuse": "true", "id": "twothree"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/caaa9d2b76f1a23a5781df46454814aa/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label13.png", "can_reuse": "true", "id": "zeroonepminusone"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/daf255ff7290de9e959755b992aa5bba/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label14.png", "can_reuse": "true", "id": "pminusonethree"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/9f71d0e653e6d5b4dd6f0e3c9f4ee272/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label15.png", "can_reuse": "true", "id": "zeroonep"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/208c1d083362043c1af54db60e650e32/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd_label16.png", "can_reuse": "true", "id": "pthree"}], "label_bg_color": "rgb(222, 139, 238)", "base_image": "/assets/courseware/v1/2f1f2e38b29cf60c22729aeef31f5297/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Perm_ps4a_Perm_dnd.png", "target_outline": "false", "targets": [{"w": "166", "y": "0", "x": "157", "id": "1", "h": "63"}, {"w": "165", "y": "0", "x": "350", "id": "2", "h": "63"}, {"w": "165", "y": "82", "x": "8", "id": "3", "h": "63"}, {"w": "165", "y": "164", "x": "558", "id": "4", "h": "62"}, {"w": "165", "y": "246", "x": "513", "id": "5", "h": "62"}, {"w": "165", "y": "387", "x": "102", "id": "6", "h": "62"}, {"w": "165", "y": "494", "x": "8", "id": "7", "h": "62"}], "one_per_target": "true"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_ps4a_permanent1_2_1">
<input type="text" name="input_ps4a_permanent1_2_1" id="input_ps4a_permanent1_2_1" aria-describedby="answer_ps4a_permanent1_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_ps4a_permanent1_2_1">
<span class="status unanswered" id="status_ps4a_permanent1_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_ps4a_permanent1_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_ps4a_permanent1_solution_1"/>
</div></span>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Average case complexity of the permanent polynomial - High-level strategy" />
<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_ps4a_permanent1" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4a_permanent1">
<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="ps4a_permanent1-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="ps4a_permanent1-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="ps4a_permanent1-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.2x+2T2018+type@problem+block@ps4a_permanent2">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent2" data-block-type="problem" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="True">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_ps4a_permanent2" class="problems-wrapper" role="group"
aria-labelledby="ps4a_permanent2-problem-title"
data-problem-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent2" data-url="/courses/course-v1:MITx+8.371.2x+2T2018/xblock/block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent2/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="ps4a_permanent2-problem-title" aria-describedby="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent2-problem-progress" tabindex="-1">
Average case complexity of the permanent polynomial - Calculations
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_permanent2-problem-progress"></div>
<div class="problem">
<div>
<p>
Let [mathjaxinline]M[/mathjaxinline] be the number of reliable [mathjaxinline]t[/mathjaxinline]'s. Using Markov's inequality [mathjaxinline]M[/mathjaxinline] is at least </p>
<p>
<div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_ps4a_permanent2_2_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4a_permanent2_2_1" id="input_ps4a_permanent2_2_1" data-input-id="ps4a_permanent2_2_1" value="" aria-describedby="status_ps4a_permanent2_2_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4a_permanent2_2_1"/>
<span class="status unanswered" id="status_ps4a_permanent2_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_permanent2_2_1" class="answer"/>
<div id="input_ps4a_permanent2_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>
with probability at least [mathjaxinline]2/3[/mathjaxinline] over the choice of [mathjaxinline]{Y}[/mathjaxinline]. Give the strongest bound here that can be obtained from Markov's inequality. <div class="solution-span">
<span id="solution_ps4a_permanent2_solution_1"/>
</div></p>
<p>
Fortunately using a theorem by Berlekamp and Welch we can reconstruct [mathjaxinline]q(0)[/mathjaxinline] from these noisy samples: Let [mathjaxinline]q[/mathjaxinline] be a polynomial of degree [mathjaxinline]d[/mathjaxinline] and suppose we have samples [mathjaxinline](x_1,y_1), \ldots , (x_ m, y_ m)[/mathjaxinline]. So long as more than [mathjaxinline](m+d)/2[/mathjaxinline] of these samples obey [mathjaxinline]y_ i = q(x_ i)[/mathjaxinline] we can reconstruct [mathjaxinline]q[/mathjaxinline]. </p>
<p>
Using the Berlekamp-Welch theorem, if we query [mathjaxinline]q(1), \ldots , q(p-1)[/mathjaxinline], then [mathjaxinline]p[/mathjaxinline] should be at least </p>
<p>
<div class="inline" tabindex="-1" aria-label="Question 2" role="group"><div id="formulaequationinput_ps4a_permanent2_3_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4a_permanent2_3_1" id="input_ps4a_permanent2_3_1" data-input-id="ps4a_permanent2_3_1" value="" aria-describedby="status_ps4a_permanent2_3_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4a_permanent2_3_1"/>
<span class="status unanswered" id="status_ps4a_permanent2_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_permanent2_3_1" class="answer"/>
<div id="input_ps4a_permanent2_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>
so that this reconstruction succeeds with probability [mathjaxinline]\geq 2/3[/mathjaxinline]. Give the smallest bound you can find from the Berklekamp-Welch theorem. <div class="solution-span">
<span id="solution_ps4a_permanent2_solution_2"/>
</div></p>
<p>
Using a <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_ps4a_permanent2_4_1">
<fieldset aria-describedby="status_ps4a_permanent2_4_1">
<div class="field">
<input type="radio" name="input_ps4a_permanent2_4_1" id="input_ps4a_permanent2_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="ps4a_permanent2_4_1-choice_1-label" for="input_ps4a_permanent2_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_ps4a_permanent2_4_1"> <text> logarithmic</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_ps4a_permanent2_4_1" id="input_ps4a_permanent2_4_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="ps4a_permanent2_4_1-choice_2-label" for="input_ps4a_permanent2_4_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_ps4a_permanent2_4_1"> <text> linear</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_ps4a_permanent2_4_1" id="input_ps4a_permanent2_4_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="ps4a_permanent2_4_1-choice_3-label" for="input_ps4a_permanent2_4_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_ps4a_permanent2_4_1"> <text> polynomial (and not linear)</text>
</label>
</div>
<div class="field">
<input type="radio" name="input_ps4a_permanent2_4_1" id="input_ps4a_permanent2_4_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="ps4a_permanent2_4_1-choice_4-label" for="input_ps4a_permanent2_4_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_ps4a_permanent2_4_1"> <text> exponential</text>
</label>
</div>
<span id="answer_ps4a_permanent2_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_ps4a_permanent2_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div> number of iterations in [mathjaxinline]n[/mathjaxinline] and taking the majority vote among the answers we can boost the probability of success to [mathjaxinline]1-1/\text {poly}(n)[/mathjaxinline]. </p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Average case complexity of the permanent polynomial - Calculations" />
<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_ps4a_permanent2" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4a_permanent2">
<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="ps4a_permanent2-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="ps4a_permanent2-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="ps4a_permanent2-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>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@vertical+block@PostBQP_in_PP" data-block-type="vertical" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="False">
<h2 class="hd hd-2 unit-title">PostBQP in PP</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_postbqp">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_postbqp" data-block-type="problem" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="True">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_ps4a_postbqp" class="problems-wrapper" role="group"
aria-labelledby="ps4a_postbqp-problem-title"
data-problem-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_postbqp" data-url="/courses/course-v1:MITx+8.371.2x+2T2018/xblock/block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_postbqp/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="9"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="ps4a_postbqp-problem-title" aria-describedby="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_postbqp-problem-progress" tabindex="-1">
PostBQP in PP: initialization
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@ps4a_postbqp-problem-progress"></div>
<div class="problem">
<div>
<p>
In this problem you will show that PP contains PostBQP. </p>
<p>
It turns out that a general quantum circuit [mathjaxinline]U[/mathjaxinline] on [mathjaxinline]n[/mathjaxinline] qubits can be written (up to a small error from the Solovay-Kitaev theorem) in terms of [mathjaxinline]H[/mathjaxinline],[mathjaxinline]Z[/mathjaxinline], [mathjaxinline]C_ Z[/mathjaxinline] (controlled-[mathjaxinline]Z[/mathjaxinline]) and [mathjaxinline]CC_ Z[/mathjaxinline] (controlled-controlled-[mathjaxinline]Z[/mathjaxinline]). Furthermore that we can assume without loss of generality that the circuit starts in the [mathjaxinline]|{0^ n}\rangle[/mathjaxinline] state and then applies a Hadamard gate on each qubit. </p>
<p>
We want to show that after [mathjaxinline]k[/mathjaxinline] (<em>not counting the first layer of Hadamards</em>) applications of Hadamard gates, as well as an arbitrary number of [mathjaxinline]Z[/mathjaxinline], [mathjaxinline]C_ Z[/mathjaxinline] and [mathjaxinline]CC_ Z[/mathjaxinline] gates, the quantum state takes the form </p>
<table id="a0000000004" class="equation" width="100%" cellspacing="0" cellpadding="7" style="table-layout:auto">
<tr id="eqn1p1">
<td class="equation" style="width:80%; border:none">[mathjax]U|{0^ n}\rangle = \sum _{x \in \{ 0,1\} ^ n}\sum _{y\in \{ 0,1\} ^ k} \frac{(-1)^{p(x,y)}}{2^{\frac{n+k}{2}}} |{x}\rangle [/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.1)</td>
</tr>
</table>
<p>
where [mathjaxinline]p(x,y)[/mathjaxinline] is a degree-3 polynomial over [mathjaxinline]{\mathbf{F_2}}[/mathjaxinline]. </p>
<p>
We will prove the result using induction on the number of gates after the initial layer of Hadamards. The base case of the induction is the circuit consisting solely of the initial layer of Hadamards. The output amplitudes of this circuit are (for any [mathjaxinline]x\in \{ 0,1\} ^ n[/mathjaxinline]) </p>
<p>
<p style="display:inline">[mathjaxinline]\langle {x}| H^{\otimes n} |{0^ n}\rangle =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_ps4a_postbqp_2_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4a_postbqp_2_1" id="input_ps4a_postbqp_2_1" data-input-id="ps4a_postbqp_2_1" value="" aria-describedby="status_ps4a_postbqp_2_1" size="20"/>
<span class="trailing_text" id="trailing_text_ps4a_postbqp_2_1"/>
<span class="status unanswered" id="status_ps4a_postbqp_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_postbqp_2_1" class="answer"/>
<div id="input_ps4a_postbqp_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>
<div class="solution-span">
<span id="solution_ps4a_postbqp_solution_1"/>
</div></p>
<p>
Now, for the inductive step, we will show how the action of gates in this gate set preserve the set of states appearing in (1.1). </p>
<p>
For simplicity we do this for a circuit acting on [mathjaxinline]3[/mathjaxinline] qubits. Let [mathjaxinline]H_0[/mathjaxinline] and [mathjaxinline]Z_0[/mathjaxinline] be Hadamard and [mathjaxinline]Z[/mathjaxinline] gates acting on the zeroth qubit (left most in the ket notation), [mathjaxinline]CZ_{0,1}[/mathjaxinline] be the controlled [mathjaxinline]Z[/mathjaxinline] gate acting on qubits [mathjaxinline]0[/mathjaxinline] and [mathjaxinline]1[/mathjaxinline] and [mathjaxinline]CCZ_{0,1,2}[/mathjaxinline] be the controlled controlled [mathjaxinline]Z[/mathjaxinline] gate acting on qubits [mathjaxinline]0,1,2[/mathjaxinline]. </p>
<p>
Now, after [mathjaxinline]N[/mathjaxinline] gates, including [mathjaxinline]k[/mathjaxinline] Hadamards, by the induction hypothesis, the state is </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]|{\psi _ N}\rangle = \sum _{x , y , z \in \{ 0,1\} } \sum _{w \in \{ 0,1\} ^ k} \frac{(-1)^{p(x,y,z ,w)}}{2^{(n+k)/2}} |{x,y,z}\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
where [mathjaxinline]p(x,y,z,w)[/mathjaxinline] is a degree-3 polynomial, i.e. a sum of terms that are product of a scalar and at most three of [mathjaxinline]x,y,z,w_1,\ldots ,w_ k[/mathjaxinline]. </p>
<p>
After the [mathjaxinline]k+1[/mathjaxinline] application of Hadamard (e.g.) on qubit 0, we can write: </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]|{\psi _{N}}\rangle \mapsto |{\psi _{N+1}}\rangle = \sum _{x , y , z \in \{ 0,1\} } \sum _{w \in \{ 0,1\} ^ k} \sum _{c \in \{ 0,1\} } \frac{(-1)^{p(c,y,z ; w) + \delta _ H (x,y,z,c)}}{2^{(n+k+1)/2}} |{x,y,z}\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
<p style="display:inline">[mathjaxinline]\delta _ H(x,y,z,c) =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 2" role="group"><div id="formulaequationinput_ps4a_postbqp_3_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4a_postbqp_3_1" id="input_ps4a_postbqp_3_1" data-input-id="ps4a_postbqp_3_1" value="" aria-describedby="status_ps4a_postbqp_3_1" size="20"/>
<span class="trailing_text" id="trailing_text_ps4a_postbqp_3_1"/>
<span class="status unanswered" id="status_ps4a_postbqp_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_postbqp_3_1" class="answer"/>
<div id="input_ps4a_postbqp_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>
<div class="solution-span">
<span id="solution_ps4a_postbqp_solution_2"/>
</div></p>
<p>
<p style="display:inline">The degree of [mathjaxinline]\delta _ H[/mathjaxinline] is </p>
<div class="inline" tabindex="-1" aria-label="Question 3" role="group"><div id="inputtype_ps4a_postbqp_4_1" class=" capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_ps4a_postbqp_4_1" id="input_ps4a_postbqp_4_1" aria-describedby="status_ps4a_postbqp_4_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4a_postbqp_4_1"/>
<span class="status unanswered" id="status_ps4a_postbqp_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_postbqp_4_1" class="answer"/>
</div>
</div></div>
</p>
<p>
<div class="solution-span">
<span id="solution_ps4a_postbqp_solution_3"/>
</div></p>
<p>
Similarly for [mathjaxinline]Z_0, CZ_{0,1}[/mathjaxinline] and [mathjaxinline]CCZ_{0,1,2}[/mathjaxinline] we get that </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]|{\psi _{N}}\rangle \mapsto |{\psi _{N+1}}\rangle = \sum _{x , y , z \in \{ 0,1\} } \sum _{w \in \{ 0,1\} ^ k} \frac{(-1)^{p(x,y,z ; w) + \delta (x,y,z)}}{2^{(n+k)/2}} |{x,y,z}\rangle[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<p>
what is [mathjaxinline]\delta[/mathjaxinline] for [mathjaxinline]Z_0, CZ_{0,1}[/mathjaxinline] and [mathjaxinline]CCZ_{0,1,2}[/mathjaxinline]? </p>
<p>
<p style="display:inline">[mathjaxinline]\delta _{Z}(x,y,z) =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 4" role="group"><div id="formulaequationinput_ps4a_postbqp_5_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4a_postbqp_5_1" id="input_ps4a_postbqp_5_1" data-input-id="ps4a_postbqp_5_1" value="" aria-describedby="status_ps4a_postbqp_5_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4a_postbqp_5_1"/>
<span class="status unanswered" id="status_ps4a_postbqp_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_postbqp_5_1" class="answer"/>
<div id="input_ps4a_postbqp_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 style="display:inline">and [mathjaxinline]\text {deg}(\delta _{Z}) =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 5" role="group"><div id="inputtype_ps4a_postbqp_6_1" class=" capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_ps4a_postbqp_6_1" id="input_ps4a_postbqp_6_1" aria-describedby="status_ps4a_postbqp_6_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4a_postbqp_6_1"/>
<span class="status unanswered" id="status_ps4a_postbqp_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_postbqp_6_1" class="answer"/>
</div>
</div></div>
</p>
<p>
<p style="display:inline">[mathjaxinline]\delta _{C_ Z}(x,y,z) =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 6" role="group"><div id="formulaequationinput_ps4a_postbqp_7_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4a_postbqp_7_1" id="input_ps4a_postbqp_7_1" data-input-id="ps4a_postbqp_7_1" value="" aria-describedby="status_ps4a_postbqp_7_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4a_postbqp_7_1"/>
<span class="status unanswered" id="status_ps4a_postbqp_7_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_postbqp_7_1" class="answer"/>
<div id="input_ps4a_postbqp_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 style="display:inline">and [mathjaxinline]\text {deg}(\delta _{C_ Z}) =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 7" role="group"><div id="inputtype_ps4a_postbqp_8_1" class=" capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_ps4a_postbqp_8_1" id="input_ps4a_postbqp_8_1" aria-describedby="status_ps4a_postbqp_8_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4a_postbqp_8_1"/>
<span class="status unanswered" id="status_ps4a_postbqp_8_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_postbqp_8_1" class="answer"/>
</div>
</div></div>
</p>
<p>
<p style="display:inline">[mathjaxinline]\delta _{C_ Z}(x,y,z) =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 8" role="group"><div id="formulaequationinput_ps4a_postbqp_9_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_ps4a_postbqp_9_1" id="input_ps4a_postbqp_9_1" data-input-id="ps4a_postbqp_9_1" value="" aria-describedby="status_ps4a_postbqp_9_1" size="10"/>
<span class="trailing_text" id="trailing_text_ps4a_postbqp_9_1"/>
<span class="status unanswered" id="status_ps4a_postbqp_9_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_postbqp_9_1" class="answer"/>
<div id="input_ps4a_postbqp_9_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 style="display:inline">and [mathjaxinline]\text {deg}(\delta _{CC_ Z}) =[/mathjaxinline]</p>
<div class="inline" tabindex="-1" aria-label="Question 9" role="group"><div id="inputtype_ps4a_postbqp_10_1" class=" capa_inputtype inline textline">
<div class="unanswered inline">
<input type="text" name="input_ps4a_postbqp_10_1" id="input_ps4a_postbqp_10_1" aria-describedby="status_ps4a_postbqp_10_1" value=""/>
<span class="trailing_text" id="trailing_text_ps4a_postbqp_10_1"/>
<span class="status unanswered" id="status_ps4a_postbqp_10_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_ps4a_postbqp_10_1" class="answer"/>
</div>
</div></div>
</p>
<p>
<div class="solution-span">
<span id="solution_ps4a_postbqp_solution_4"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="PostBQP in PP: initialization" />
<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_ps4a_postbqp" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_ps4a_postbqp">
<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="ps4a_postbqp-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="ps4a_postbqp-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="ps4a_postbqp-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.2x+2T2018+type@problem+block@problem_ps4a_postbqp">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+8.371.2x+2T2018" data-request-token="e225dfa9ed9111eeb91e16ffd59041e1" data-graded="True" data-usage-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@problem_ps4a_postbqp" data-block-type="problem" data-runtime-class="LmsRuntime" data-runtime-version="1" data-has-score="True">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_problem_ps4a_postbqp" class="problems-wrapper" role="group"
aria-labelledby="problem_ps4a_postbqp-problem-title"
data-problem-id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@problem_ps4a_postbqp" data-url="/courses/course-v1:MITx+8.371.2x+2T2018/xblock/block-v1:MITx+8.371.2x+2T2018+type@problem+block@problem_ps4a_postbqp/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="6"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="problem_ps4a_postbqp-problem-title" aria-describedby="block-v1:MITx+8.371.2x+2T2018+type@problem+block@problem_ps4a_postbqp-problem-progress" tabindex="-1">
PostBQP in PP: in action
</h3>
<div class="problem-progress" id="block-v1:MITx+8.371.2x+2T2018+type@problem+block@problem_ps4a_postbqp-problem-progress"></div>
<div class="problem">
<div>
<p>
One way of performing postselection is to measure two qubits at the one of the computation and to use the first one for the answer and the second one for the postselection flag. This means that if the measurement outcomes on the first two qubits are 00 then the algorithm outputs '0', if they are 10, then the algorithm outputs '1' and if they are 01 or 11 then the algorithm outputs '?'. The promise in a PostBQP problem is that conditioned on the second qubit being 0, the first qubit either has probability [mathjaxinline]\geq 2/3[/mathjaxinline] of being 0 or [mathjaxinline]\geq 2/3[/mathjaxinline] of being 1. We want to show that these cases can be distinguished by reducing to a problem in PP. Assume for simplicity that the circuit begins with the [mathjaxinline]|{0^ n}\rangle[/mathjaxinline] state. </p>
<p>
From the previous part, it follows that the probability of obtaining a particular [mathjaxinline]n[/mathjaxinline]-bit outcome string [mathjaxinline]x[/mathjaxinline] is </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]\Pr [x] = \left( \sum _{y \in \{ 0,1\} ^ k} \frac{(-1)^{p(x,y)}}{2^{k/2}} \right)^2 = \sum _{y, z \in \{ 0,1\} ^ k} \frac{(-1)^{p(x,y) + p(x,z)}}{2^{k}}[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
<span>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_problem_ps4a_postbqp_2_1" class="capa_inputtype">
<div class="drag_and_drop_problem_div" id="drag_and_drop_div_problem_ps4a_postbqp_2_1" data-plain-id="problem_ps4a_postbqp_2_1">
</div>
<div class="drag_and_drop_problem_json" id="drag_and_drop_json_problem_ps4a_postbqp_2_1" style="display:none;">{"draggables": [{"target_fields": [], "label": "", "icon": "/assets/courseware/v1/a9e231cfe25380397ead9e984aa90278/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Post2b_ps4a_Post2b_dnd_label1.png", "can_reuse": "true", "id": "zero"}, {"target_fields": [], "label": "", "icon": "/assets/courseware/v1/31a556a5b8e185c45645e9214cd5e63a/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Post2b_ps4a_Post2b_dnd_label2.png", "can_reuse": "true", "id": "one"}], "label_bg_color": "rgb(222, 139, 238)", "base_image": "/assets/courseware/v1/a5688e25723cf7c2be1177bcc04adeea/asset-v1:MITx+8.371.2x+2T2018+type@asset+block/images_ps4a_Post2b_ps4a_Post2b_dnd.png", "target_outline": "false", "targets": [{"w": "106", "y": "118", "x": "178", "id": "1", "h": "50"}, {"w": "106", "y": "118", "x": "332", "id": "3", "h": "50"}, {"w": "106", "y": "239", "x": "178", "id": "2", "h": "49"}, {"w": "106", "y": "239", "x": "332", "id": "4", "h": "49"}, {"w": "106", "y": "359", "x": "178", "id": "5", "h": "50"}], "one_per_target": "true"}</div>
<div class="script_placeholder" data-src="/static/js/capa/drag_and_drop.a31124208b9b.js"/>
<div class="unanswered" id="status_problem_ps4a_postbqp_2_1">
<input type="text" name="input_problem_ps4a_postbqp_2_1" id="input_problem_ps4a_postbqp_2_1" aria-describedby="answer_problem_ps4a_postbqp_2_1" value="" style="display:none;"/>
<p class="indicator-container drag-and-drop--status" aria-describedby="input_problem_ps4a_postbqp_2_1">
<span class="status unanswered" id="status_problem_ps4a_postbqp_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</p>
<p id="answer_problem_ps4a_postbqp_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_problem_ps4a_postbqp_solution_1"/>
</div></span>
<p>
Thus, to distinguish the '0' and '1' cases of a PostBQP machine, we can use the following algorithm: </p>
<ol class="enumerate">
<li value="1">
<p>
Pick [mathjaxinline]x_{3}, \dots , x_{n}, y, z[/mathjaxinline] uniformly at random, and evaluate </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]q(x_1) = \frac{(-1)^{p(x_1,0,x_3, \dots , x_ n, y) + p(x_1,0,x_3, \dots , x_ n, z)}}{2^ k}.[/mathjax]</td>
<td class="eqnnum" style="width:20%; border:none">&#160;</td>
</tr>
</table>
</li>
<li value="2">
<p>
If [mathjaxinline]q(0) &gt; q(1)[/mathjaxinline], then reject. If [mathjaxinline]q(0) &lt; q(1)[/mathjaxinline], then accept. If [mathjaxinline]q(0) = q(1)[/mathjaxinline], then accept with probability [mathjaxinline]1/2[/mathjaxinline]. </p>
</li>
</ol>
<p>
Note that [mathjaxinline]q(0)-q(1)[/mathjaxinline] can only take on a fixed set of values. Select all the values which can appear. <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_problem_ps4a_postbqp_3_1">
<fieldset aria-describedby="status_problem_ps4a_postbqp_3_1">
<div class="field">
<input type="checkbox" name="input_problem_ps4a_postbqp_3_1[]" id="input_problem_ps4a_postbqp_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="problem_ps4a_postbqp_3_1-choice_0-label" for="input_problem_ps4a_postbqp_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_problem_ps4a_postbqp_3_1"> <text>1</text>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_problem_ps4a_postbqp_3_1[]" id="input_problem_ps4a_postbqp_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="problem_ps4a_postbqp_3_1-choice_1-label" for="input_problem_ps4a_postbqp_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_problem_ps4a_postbqp_3_1"> <text>[mathjaxinline]2^{1-k}[/mathjaxinline]</text>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_problem_ps4a_postbqp_3_1[]" id="input_problem_ps4a_postbqp_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="problem_ps4a_postbqp_3_1-choice_2-label" for="input_problem_ps4a_postbqp_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_problem_ps4a_postbqp_3_1"> <text>[mathjaxinline]2^{-k}[/mathjaxinline]</text>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_problem_ps4a_postbqp_3_1[]" id="input_problem_ps4a_postbqp_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="problem_ps4a_postbqp_3_1-choice_3-label" for="input_problem_ps4a_postbqp_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_problem_ps4a_postbqp_3_1"> <text>0</text>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_problem_ps4a_postbqp_3_1[]" id="input_problem_ps4a_postbqp_3_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="problem_ps4a_postbqp_3_1-choice_4-label" for="input_problem_ps4a_postbqp_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_problem_ps4a_postbqp_3_1"> <text>[mathjaxinline]-2^{-k}[/mathjaxinline]</text>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_problem_ps4a_postbqp_3_1[]" id="input_problem_ps4a_postbqp_3_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="problem_ps4a_postbqp_3_1-choice_5-label" for="input_problem_ps4a_postbqp_3_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_problem_ps4a_postbqp_3_1"> <text>[mathjaxinline]-2^{1-k}[/mathjaxinline]</text>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_problem_ps4a_postbqp_3_1[]" id="input_problem_ps4a_postbqp_3_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="problem_ps4a_postbqp_3_1-choice_6-label" for="input_problem_ps4a_postbqp_3_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_problem_ps4a_postbqp_3_1"> <text>-1</text>
</label>
</div>
<span id="answer_problem_ps4a_postbqp_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_problem_ps4a_postbqp_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div> </p>
<p>
To show that this algorithm works, let us calculate the probability of acceptance. Let [mathjaxinline]A[/mathjaxinline] be the number of choices of [mathjaxinline]x_3, \dots x_ n, y, z[/mathjaxinline] for which [mathjaxinline]q(0) &gt;q(1)[/mathjaxinline], [mathjaxinline]B[/mathjaxinline] be the number of choices for which [mathjaxinline]q(0) &lt; q(1)[/mathjaxinline], and [mathjaxinline]C[/mathjaxinline] be the number for which they are equal. They sum to <p style="display:inline">[mathjaxinline]A+B+C =[/mathjaxinline]</p> <div class="inline" tabindex="-1" aria-label="Question 3" role="group"><div id="formulaequationinput_problem_ps4a_postbqp_4_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_problem_ps4a_postbqp_4_1" id="input_problem_ps4a_postbqp_4_1" data-input-id="problem_ps4a_postbqp_4_1" value="" aria-describedby="status_problem_ps4a_postbqp_4_1" size="20"/>
<span class="trailing_text" id="trailing_text_problem_ps4a_postbqp_4_1"/>
<span class="status unanswered" id="status_problem_ps4a_postbqp_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_problem_ps4a_postbqp_4_1" class="answer"/>
<div id="input_problem_ps4a_postbqp_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> <div class="solution-span">
<span id="solution_problem_ps4a_postbqp_solution_2"/>
</div></p>
<p>
Express the following quantities as functions of [mathjaxinline]A,B,C,k,n[/mathjaxinline]. We know that (for the PostBQP machine) <p style="display:inline">[mathjaxinline]\Pr [0] - \Pr [1] =[/mathjaxinline]</p> <div class="inline" tabindex="-1" aria-label="Question 4" role="group"><div id="formulaequationinput_problem_ps4a_postbqp_5_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_problem_ps4a_postbqp_5_1" id="input_problem_ps4a_postbqp_5_1" data-input-id="problem_ps4a_postbqp_5_1" value="" aria-describedby="status_problem_ps4a_postbqp_5_1" size="20"/>
<span class="trailing_text" id="trailing_text_problem_ps4a_postbqp_5_1"/>
<span class="status unanswered" id="status_problem_ps4a_postbqp_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_problem_ps4a_postbqp_5_1" class="answer"/>
<div id="input_problem_ps4a_postbqp_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">The probability that our simulation accepts is </p>
<div class="inline" tabindex="-1" aria-label="Question 5" role="group"><div id="formulaequationinput_problem_ps4a_postbqp_6_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_problem_ps4a_postbqp_6_1" id="input_problem_ps4a_postbqp_6_1" data-input-id="problem_ps4a_postbqp_6_1" value="" aria-describedby="status_problem_ps4a_postbqp_6_1" size="20"/>
<span class="trailing_text" id="trailing_text_problem_ps4a_postbqp_6_1"/>
<span class="status unanswered" id="status_problem_ps4a_postbqp_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_problem_ps4a_postbqp_6_1" class="answer"/>
<div id="input_problem_ps4a_postbqp_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"> and the probability that our simulation rejects is</p>
<div class="inline" tabindex="-1" aria-label="Question 6" role="group"><div id="formulaequationinput_problem_ps4a_postbqp_7_1" class="inputtype formulaequationinput" style="display:inline-block;vertical-align:top">
<div class="unanswered">
<input type="text" name="input_problem_ps4a_postbqp_7_1" id="input_problem_ps4a_postbqp_7_1" data-input-id="problem_ps4a_postbqp_7_1" value="" aria-describedby="status_problem_ps4a_postbqp_7_1" size="20"/>
<span class="trailing_text" id="trailing_text_problem_ps4a_postbqp_7_1"/>
<span class="status unanswered" id="status_problem_ps4a_postbqp_7_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_problem_ps4a_postbqp_7_1" class="answer"/>
<div id="input_problem_ps4a_postbqp_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>
Putting these together we see that the simulation accepts with probability [mathjaxinline]&lt;1/2[/mathjaxinline] when (for the PostBQP machine) [mathjaxinline]\Pr [0]&gt;\Pr [1][/mathjaxinline] and it accepts with probability [mathjaxinline]&gt;1/2[/mathjaxinline] when [mathjaxinline]\Pr [0]&lt;\Pr [1][/mathjaxinline]. Thus, the algorithm meets the correctness criteria for PP. </p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="PostBQP in PP: in action" />
<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_problem_ps4a_postbqp" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_problem_ps4a_postbqp">
<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="problem_ps4a_postbqp-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="problem_ps4a_postbqp-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="problem_ps4a_postbqp-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>
</div>
© All Rights Reserved