<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-runtime-version="1" data-block-type="vertical" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@vertical+block@Reversible_two-four-three_swap" data-has-score="False" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Reversible two-four-three swap</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.370.1x+1T2018+type@html+block@Classical_Reversible_Boolean_Circuits">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-runtime-version="1" data-block-type="html" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@html+block@Classical_Reversible_Boolean_Circuits" data-has-score="False" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><big class="xxlarge">Classical Reversible Boolean Circuits</big></p><p>
The problems explore the construction of several useful reversible circuits, using primitive reversible gates. </p><p>
For each problem, please enter a text description of the gates to apply, with one gate per line. Allowed gates include NOT, <a href="https://en.wikipedia.org/wiki/Controlled_NOT_gate" target="_blank">CNOT</a>, <a href="https://en.wikipedia.org/wiki/Toffoli_gate" target="_blank">Toffoli</a>, and <a href="https://en.wikipedia.org/wiki/Fredkin_gate" target="_blank">Fredkin</a> gates. These are some examples of how you can specify gates and which bits they act upon: <br/></p><center><table class="tabular" cellspacing="0" style="table-layout:auto"><tr><td style="text-align:center; border:none"><tt class="tt">not(a)</tt></td><td style="text-align:left; border:none">
NOT on a </td></tr><tr><td style="text-align:center; border:none"><tt class="tt">cnot(a,b)</tt></td><td style="text-align:left; border:none">
CNOT with control a and target b </td></tr><tr><td style="text-align:center; border:none"><tt class="tt">swap(c,d)</tt></td><td style="text-align:left; border:none">
swap on c,d </td></tr><tr><td style="text-align:center; border:none"><tt class="tt">fredkin(a,b,c)</tt></td><td style="text-align:left; border:none">
Fredkin with control a and targets b,c </td></tr><tr><td style="text-align:center; border:none"><tt class="tt">toffoli(c,a,b)</tt></td><td style="text-align:left; border:none">
Toffoli with controls c,a and target b </td></tr></table></center><p>
These correspond to the following schematic drawing of the gates: <center><img src="/assets/courseware/v1/33207d912920caa09b74cc9a0b53937d/asset-v1:MITx+8.370.1x+1T2018+type@asset+block/images_fig_reversible_gates.png" width="500"/></center> </p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_four_input_cswap">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-runtime-version="1" data-block-type="problem" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_four_input_cswap" data-has-score="True" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_u1_1_four_input_cswap" class="problems-wrapper" role="group"
aria-labelledby="u1_1_four_input_cswap-problem-title"
data-problem-id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_four_input_cswap" data-url="/courses/course-v1:MITx+8.370.1x+1T2018/xblock/block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_four_input_cswap/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="u1_1_four_input_cswap-problem-title" aria-describedby="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_four_input_cswap-problem-progress" tabindex="-1">
Reversible two-four-three swap
</h3>
<div class="problem-progress" id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_four_input_cswap-problem-progress"></div>
<div class="problem">
<div>
<p>
Design a reversible circuit, using NOT, CNOT, Toffoli, and Fredkin gates, which acts on the four inputs [mathjaxinline]a, b, c, d[/mathjaxinline], to perform the operation [mathjaxinline]{\rm swap_{243}}(a,b,c,d)[/mathjaxinline] which swaps [mathjaxinline]b[/mathjaxinline] and [mathjaxinline]d[/mathjaxinline] if [mathjaxinline]a=0[/mathjaxinline], and swaps [mathjaxinline]c[/mathjaxinline] and [mathjaxinline]d[/mathjaxinline] if [mathjaxinline]a=1[/mathjaxinline]. Bit [mathjaxinline]a[/mathjaxinline] should be left unchanged. </p>
<p>
Note that you have 20 attempts, so you have some leeway with syntax mistakes. Most later problems will just provide 10. Work out your circuits in your own notebook and check carefully before entering; do not rely on random exploration to get the correct answer. </p>
<p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="textbox_u1_1_four_input_cswap_2_1" class="capa_inputtype textbox cminput">
<label class="sr problem-group-label" for="cm-textarea-u1_1_four_input_cswap_2_1">Code Editor</label>
<textarea rows="8" cols="80" name="input_u1_1_four_input_cswap_2_1" aria-label="python editor" aria-describedby="answer_u1_1_four_input_cswap_2_1" id="input_u1_1_four_input_cswap_2_1" tabindex="0" data-mode="python" data-tabsize="4" data-linenums="true"/>
<span class="cm-editor-exit-message capa-message" id="cm-editor-exit-message-u1_1_four_input_cswap_2_1">
Press ESC then TAB or click outside of the code editor to exit
</span>
<div class="grader-status" tabindex="-1">
<span class="status unanswered" id="status_u1_1_four_input_cswap_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p class="debug">unanswered</p>
</div>
<span id="answer_u1_1_four_input_cswap_2_1"/>
<div class="external-grader-message">
</div>
</div></div>
</p>
<p>
<div class="solution-span">
<span id="solution_u1_1_four_input_cswap_solution_1"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Reversible two-four-three swap" />
<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_u1_1_four_input_cswap" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_u1_1_four_input_cswap">
<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="u1_1_four_input_cswap-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="u1_1_four_input_cswap-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="u1_1_four_input_cswap-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.370.1x+1T2018+type@html+block@site_search_box001100">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-runtime-version="1" data-block-type="html" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@html+block@site_search_box001100" data-has-score="False" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<span><a href="/asset-v1:MITx+8.370.1x+1T2018+type@asset+block/NONE" id="dummy_course_static_link" style="display:none"/><a href="/courses/course-v1:MITx+8.370.1x+1T2018/jump_to_id/NONE" id="dummy_jump_link" style="display:none"/><script type="text/javascript">
(function(){
course_static_url = $('#dummy_course_static_link').attr('href').replace('/NONE', '');
jump_to_url = $('#dummy_jump_link').attr('href').replace('/NONE', '');
if (typeof String.prototype.startsWith != 'function') {
// see below for better implementation!
String.prototype.startsWith = function (str){
return this.indexOf(str) === 0;
};
}
if(typeof(String.prototype.trim) === "undefined")
{
String.prototype.trim = function()
{
return String(this).replace(/^\s+|\s+$/g, '');
};
}
var lb = String.fromCharCode(60);
var rb = String.fromCharCode(62);
var amp = String.fromCharCode(38);
var rlb = rb + lb;
var mke = function(x){ return lb + x + rb; }
go_to_search = function(){
// find search this module link
search_module_url = "";
$('div.course-index').find('nav').find('a').each(function(){
if ($(this).text().trim().startsWith("Search this course")){
search_module_url = $(this).attr('href');
console.log("search_module_url = ", search_module_url);
}
});
var sterm = $('#site-search-box').val();
// new_url = jump_to_url + "/Search_this_module/?q=" + sterm;
new_url = search_module_url + "?q=" + sterm;
console.log("sterm = ", sterm, " ; going to ", new_url);
window.location.href = new_url;
}
if (!$('#site-search-box').length){
$("nav.courseware").find("ol").append(lb + "section style='float:right'" + rlb + "input size='20'"
+ " id='site-search-box'"
+ rlb + "img src='" + course_static_url
+ "/images_search_glass.png'/" + rlb + "/input" + rlb + "/section" + rb);
}
$("#site-search-box").keypress(function(event) {
if (event.which == 13) {
event.preventDefault();
go_to_search();
}
});
// $('#site-search-box').bind("enterKey", go_to_search);
})();
var add_fix_transcript = function(){
if ($('div.wrap-instructor-info').length==0){
return;
}
$('div.xblock-student_view-video').each(function(key, vblock_e){
var vblock = $(vblock_e);
var vuid = vblock.data('usage-id').split('@');
var vid;
if (vuid.length==1){
vuid = vblock.data('usage-id').split(';_')
vid = vuid[5];
}else{
vid = vuid[2];
}
var mfnpre = vid.split("_video",1)[0];
var mfnid = mfnpre; // no periods
mfnpre = mfnpre.replace('8_370', '8.370'); // periods in gh filename
var lb = String.fromCharCode(60);
var rb = String.fromCharCode(62);
var mke = function(x){ return lb + x + rb; }
var ftid = "fix_transcript_" + mfnid;
if (!$('#' + ftid).length){
var html = lb + "span id='" + ftid + "' style='float:right'" + rb + lb + "a href='#'" + rb;
html += "contribute transcript fix" + mke("/a") + mke("/span");
console.log("html = ", html);
vblock.after(html)
}
$('#' + ftid).click(function(){
var cst = $('ol.subtitles').find('li.current');
var cindex = Number(cst.data('index'));
var gurl;
if (mfnpre.endsWith('_cq_sol')){
gurl = "https://github.com/mitocw/content-mit-8370x-cq-sol-subtitles/blob/master/";
}else{
gurl = "https://github.com/mitocw/content-mit-8370x-subtitles/blob/master/";
}
gurl += mfnpre + ".txt#L" + String(cindex + 10 + 1);
console.log("going to ", gurl);
window.open(gurl, "MITx 8.370x subtitle source");
});
});
}
try{
add_fix_transcript();
}
catch(err){
console.log(err);
}
try{
var rb = String.fromCharCode(62);
setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 3000);
setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 8000);
}
catch(err){
console.log(err);
}
</script></span>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-runtime-version="1" data-block-type="vertical" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@vertical+block@Controlled-controlled_swap" data-has-score="False" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Controlled-controlled swap</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_ccswap">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-runtime-version="1" data-block-type="problem" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_ccswap" data-has-score="True" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_u1_1_ccswap" class="problems-wrapper" role="group"
aria-labelledby="u1_1_ccswap-problem-title"
data-problem-id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_ccswap" data-url="/courses/course-v1:MITx+8.370.1x+1T2018/xblock/block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_ccswap/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="u1_1_ccswap-problem-title" aria-describedby="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_ccswap-problem-progress" tabindex="-1">
Controlled-controlled swap
</h3>
<div class="problem-progress" id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_ccswap-problem-progress"></div>
<div class="problem">
<div>
<p>
Design a reversible circuit, using NOT, CNOT, Toffoli, and Fredkin gates, which acts on the four inputs [mathjaxinline]a, b, c, d[/mathjaxinline], to swap [mathjaxinline]c[/mathjaxinline] and [mathjaxinline]d[/mathjaxinline] only when both [mathjaxinline]a=1[/mathjaxinline] and [mathjaxinline]b=1[/mathjaxinline]. You may use a fifth bit [mathjaxinline]e[/mathjaxinline], given as initialized to [mathjaxinline]e=0[/mathjaxinline], in your circuit; this bit must also end as [mathjaxinline]e=0[/mathjaxinline]. </p>
<p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="textbox_u1_1_ccswap_2_1" class="capa_inputtype textbox cminput">
<label class="sr problem-group-label" for="cm-textarea-u1_1_ccswap_2_1">Code Editor</label>
<textarea rows="8" cols="80" name="input_u1_1_ccswap_2_1" aria-label="python editor" aria-describedby="answer_u1_1_ccswap_2_1" id="input_u1_1_ccswap_2_1" tabindex="0" data-mode="python" data-tabsize="4" data-linenums="true"/>
<span class="cm-editor-exit-message capa-message" id="cm-editor-exit-message-u1_1_ccswap_2_1">
Press ESC then TAB or click outside of the code editor to exit
</span>
<div class="grader-status" tabindex="-1">
<span class="status unanswered" id="status_u1_1_ccswap_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p class="debug">unanswered</p>
</div>
<span id="answer_u1_1_ccswap_2_1"/>
<div class="external-grader-message">
</div>
</div></div>
</p>
<p>
<div class="solution-span">
<span id="solution_u1_1_ccswap_solution_1"/>
</div></p>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Controlled-controlled swap" />
<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_u1_1_ccswap" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_u1_1_ccswap">
<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="u1_1_ccswap-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="u1_1_ccswap-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="u1_1_ccswap-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.370.1x+1T2018+type@html+block@site_search_box001101">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-runtime-version="1" data-block-type="html" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@html+block@site_search_box001101" data-has-score="False" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<span><a href="/asset-v1:MITx+8.370.1x+1T2018+type@asset+block/NONE" id="dummy_course_static_link" style="display:none"/><a href="/courses/course-v1:MITx+8.370.1x+1T2018/jump_to_id/NONE" id="dummy_jump_link" style="display:none"/><script type="text/javascript">
(function(){
course_static_url = $('#dummy_course_static_link').attr('href').replace('/NONE', '');
jump_to_url = $('#dummy_jump_link').attr('href').replace('/NONE', '');
if (typeof String.prototype.startsWith != 'function') {
// see below for better implementation!
String.prototype.startsWith = function (str){
return this.indexOf(str) === 0;
};
}
if(typeof(String.prototype.trim) === "undefined")
{
String.prototype.trim = function()
{
return String(this).replace(/^\s+|\s+$/g, '');
};
}
var lb = String.fromCharCode(60);
var rb = String.fromCharCode(62);
var amp = String.fromCharCode(38);
var rlb = rb + lb;
var mke = function(x){ return lb + x + rb; }
go_to_search = function(){
// find search this module link
search_module_url = "";
$('div.course-index').find('nav').find('a').each(function(){
if ($(this).text().trim().startsWith("Search this course")){
search_module_url = $(this).attr('href');
console.log("search_module_url = ", search_module_url);
}
});
var sterm = $('#site-search-box').val();
// new_url = jump_to_url + "/Search_this_module/?q=" + sterm;
new_url = search_module_url + "?q=" + sterm;
console.log("sterm = ", sterm, " ; going to ", new_url);
window.location.href = new_url;
}
if (!$('#site-search-box').length){
$("nav.courseware").find("ol").append(lb + "section style='float:right'" + rlb + "input size='20'"
+ " id='site-search-box'"
+ rlb + "img src='" + course_static_url
+ "/images_search_glass.png'/" + rlb + "/input" + rlb + "/section" + rb);
}
$("#site-search-box").keypress(function(event) {
if (event.which == 13) {
event.preventDefault();
go_to_search();
}
});
// $('#site-search-box').bind("enterKey", go_to_search);
})();
var add_fix_transcript = function(){
if ($('div.wrap-instructor-info').length==0){
return;
}
$('div.xblock-student_view-video').each(function(key, vblock_e){
var vblock = $(vblock_e);
var vuid = vblock.data('usage-id').split('@');
var vid;
if (vuid.length==1){
vuid = vblock.data('usage-id').split(';_')
vid = vuid[5];
}else{
vid = vuid[2];
}
var mfnpre = vid.split("_video",1)[0];
var mfnid = mfnpre; // no periods
mfnpre = mfnpre.replace('8_370', '8.370'); // periods in gh filename
var lb = String.fromCharCode(60);
var rb = String.fromCharCode(62);
var mke = function(x){ return lb + x + rb; }
var ftid = "fix_transcript_" + mfnid;
if (!$('#' + ftid).length){
var html = lb + "span id='" + ftid + "' style='float:right'" + rb + lb + "a href='#'" + rb;
html += "contribute transcript fix" + mke("/a") + mke("/span");
console.log("html = ", html);
vblock.after(html)
}
$('#' + ftid).click(function(){
var cst = $('ol.subtitles').find('li.current');
var cindex = Number(cst.data('index'));
var gurl;
if (mfnpre.endsWith('_cq_sol')){
gurl = "https://github.com/mitocw/content-mit-8370x-cq-sol-subtitles/blob/master/";
}else{
gurl = "https://github.com/mitocw/content-mit-8370x-subtitles/blob/master/";
}
gurl += mfnpre + ".txt#L" + String(cindex + 10 + 1);
console.log("going to ", gurl);
window.open(gurl, "MITx 8.370x subtitle source");
});
});
}
try{
add_fix_transcript();
}
catch(err){
console.log(err);
}
try{
var rb = String.fromCharCode(62);
setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 3000);
setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 8000);
}
catch(err){
console.log(err);
}
</script></span>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-init="VerticalStudentView" data-runtime-version="1" data-block-type="vertical" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@vertical+block@Reversible_two-input_demultiplexer" data-has-score="False" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Reversible two-input demultiplexer</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_demux2">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-init="XBlockToXModuleShim" data-runtime-version="1" data-block-type="problem" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_demux2" data-has-score="True" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_u1_1_demux2" class="problems-wrapper" role="group"
aria-labelledby="u1_1_demux2-problem-title"
data-problem-id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_demux2" data-url="/courses/course-v1:MITx+8.370.1x+1T2018/xblock/block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_demux2/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="u1_1_demux2-problem-title" aria-describedby="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_demux2-problem-progress" tabindex="-1">
Reversible two-input demultiplexer
</h3>
<div class="problem-progress" id="block-v1:MITx+8.370.1x+1T2018+type@problem+block@u1_1_demux2-problem-progress"></div>
<div class="problem">
<div>
<p>
Design a reversible circuit, using NOT, CNOT, Toffoli, and Fredkin gates, which acts on the two arbitrary inputs [mathjaxinline]a, b[/mathjaxinline], and the two fixed inputs [mathjaxinline]c=0[/mathjaxinline], [mathjaxinline]d=0[/mathjaxinline], to produce four bits [mathjaxinline]a'[/mathjaxinline], [mathjaxinline]b'[/mathjaxinline], [mathjaxinline]c'[/mathjaxinline], [mathjaxinline]d'[/mathjaxinline] of output, where only the [mathjaxinline]n^{\rm th}[/mathjaxinline] output is [mathjaxinline]1[/mathjaxinline] (the others are all [mathjaxinline]0[/mathjaxinline]), and [mathjaxinline]n=2b + a[/mathjaxinline]. </p>
<p>
This is a two-input demultiplexer, and the output is a unary encoded value, sometimes otherwise known as <a href="https://en.wikipedia.org/wiki/One-hot" target="_blank">&#8220;one-hot encoding"</a> in the field of deep neural networks. </p>
<p>
<div class="hideshowbox">
<h4 onclick="hideshow(this);" style="margin: 0px">Hint<span class="icon-caret-down toggleimage"/></h4>
<div class="hideshowcontent">
<p>
Denoting the NOT of [mathjaxinline]a[/mathjaxinline] as [mathjaxinline]\bar{a}[/mathjaxinline], note that </p>
<table id="a0000000002" class="eqnarray" cellspacing="0" cellpadding="7" width="100%" style="table-layout:auto">
<tr id="a0000000003">
<td style="width:40%; border:none">&#160;</td>
<td style="vertical-align:middle; text-align:right; border:none">
[mathjaxinline]\displaystyle a'[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:center; border:none">
[mathjaxinline]\displaystyle =[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle \bar{a} \bar{b}[/mathjaxinline]
</td>
<td style="width:40%; border:none">&#160;</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.1)</td>
</tr>
<tr id="a0000000004">
<td style="width:40%; border:none">&#160;</td>
<td style="vertical-align:middle; text-align:right; border:none">
[mathjaxinline]\displaystyle b'[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:center; border:none">
[mathjaxinline]\displaystyle =[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle a\bar{b}[/mathjaxinline]
</td>
<td style="width:40%; border:none">&#160;</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.2)</td>
</tr>
<tr id="a0000000005">
<td style="width:40%; border:none">&#160;</td>
<td style="vertical-align:middle; text-align:right; border:none">
[mathjaxinline]\displaystyle c'[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:center; border:none">
[mathjaxinline]\displaystyle =[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle \bar{a}b[/mathjaxinline]
</td>
<td style="width:40%; border:none">&#160;</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.3)</td>
</tr>
<tr id="a0000000006">
<td style="width:40%; border:none">&#160;</td>
<td style="vertical-align:middle; text-align:right; border:none">
[mathjaxinline]\displaystyle d'[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:center; border:none">
[mathjaxinline]\displaystyle =[/mathjaxinline]
</td>
<td style="vertical-align:middle; text-align:left; border:none">
[mathjaxinline]\displaystyle ab \, .[/mathjaxinline]
</td>
<td style="width:40%; border:none">&#160;</td>
<td class="eqnnum" style="width:20%; border:none;text-align:right">(1.4)</td>
</tr>
</table>
<p>
Since these are all Boolean functions of the input, it would seem immediate how to compute these using Boolean logic functions. The trick here is that you're being asked to construct the circuit using reversible gates, consuming no additional inputs, and producing no extra garbage. This is known as an &#8220;in-place" reversible circuit. </p>
<p>
You should be able to do this using 11 gates. If you can do it with fewer, let the TA know! </p>
</div>
<p class="hideshowbottom" onclick="hideshow(this);" style="margin: 0px">
<a href="javascript: {return false;}">Show</a>
</p>
</div>
</p>
<p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="textbox_u1_1_demux2_2_1" class="capa_inputtype textbox cminput">
<label class="sr problem-group-label" for="cm-textarea-u1_1_demux2_2_1">Code Editor</label>
<textarea rows="8" cols="80" name="input_u1_1_demux2_2_1" aria-label="python editor" aria-describedby="answer_u1_1_demux2_2_1" id="input_u1_1_demux2_2_1" tabindex="0" data-mode="python" data-tabsize="4" data-linenums="true"/>
<span class="cm-editor-exit-message capa-message" id="cm-editor-exit-message-u1_1_demux2_2_1">
Press ESC then TAB or click outside of the code editor to exit
</span>
<div class="grader-status" tabindex="-1">
<span class="status unanswered" id="status_u1_1_demux2_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p class="debug">unanswered</p>
</div>
<span id="answer_u1_1_demux2_2_1"/>
<div class="external-grader-message">
</div>
</div></div>
</p>
<p>
<div class="solution-span">
<span id="solution_u1_1_demux2_solution_1"/>
</div></p>
<SCRIPT type="text/javascript" src="/assets/courseware/v1/631e447105fca1b243137b21b9ed6f90/asset-v1:MITx+8.370.1x+1T2018+type@asset+block/latex2edx.js"/>
<LINK type="text/css" rel="stylesheet" href="/assets/courseware/v1/daf81af0af57b85a105e0ed27b7873a0/asset-v1:MITx+8.370.1x+1T2018+type@asset+block/latex2edx.css"/>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Reversible two-input demultiplexer" />
<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_u1_1_demux2" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_u1_1_demux2">
<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="u1_1_demux2-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="u1_1_demux2-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="u1_1_demux2-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.370.1x+1T2018+type@html+block@html_site_search_box001101">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-init="XBlockToXModuleShim" data-runtime-version="1" data-block-type="html" data-graded="True" data-request-token="4657e326732611efbae10e3672a9417f" data-usage-id="block-v1:MITx+8.370.1x+1T2018+type@html+block@html_site_search_box001101" data-has-score="False" data-course-id="course-v1:MITx+8.370.1x+1T2018" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<span><a href="/asset-v1:MITx+8.370.1x+1T2018+type@asset+block/NONE" id="dummy_course_static_link" style="display:none"/><a href="/courses/course-v1:MITx+8.370.1x+1T2018/jump_to_id/NONE" id="dummy_jump_link" style="display:none"/><script type="text/javascript">
(function(){
course_static_url = $('#dummy_course_static_link').attr('href').replace('/NONE', '');
jump_to_url = $('#dummy_jump_link').attr('href').replace('/NONE', '');
if (typeof String.prototype.startsWith != 'function') {
// see below for better implementation!
String.prototype.startsWith = function (str){
return this.indexOf(str) === 0;
};
}
if(typeof(String.prototype.trim) === "undefined")
{
String.prototype.trim = function()
{
return String(this).replace(/^\s+|\s+$/g, '');
};
}
var lb = String.fromCharCode(60);
var rb = String.fromCharCode(62);
var amp = String.fromCharCode(38);
var rlb = rb + lb;
var mke = function(x){ return lb + x + rb; }
go_to_search = function(){
// find search this module link
search_module_url = "";
$('div.course-index').find('nav').find('a').each(function(){
if ($(this).text().trim().startsWith("Search this course")){
search_module_url = $(this).attr('href');
console.log("search_module_url = ", search_module_url);
}
});
var sterm = $('#site-search-box').val();
// new_url = jump_to_url + "/Search_this_module/?q=" + sterm;
new_url = search_module_url + "?q=" + sterm;
console.log("sterm = ", sterm, " ; going to ", new_url);
window.location.href = new_url;
}
if (!$('#site-search-box').length){
$("nav.courseware").find("ol").append(lb + "section style='float:right'" + rlb + "input size='20'"
+ " id='site-search-box'"
+ rlb + "img src='" + course_static_url
+ "/images_search_glass.png'/" + rlb + "/input" + rlb + "/section" + rb);
}
$("#site-search-box").keypress(function(event) {
if (event.which == 13) {
event.preventDefault();
go_to_search();
}
});
// $('#site-search-box').bind("enterKey", go_to_search);
})();
var add_fix_transcript = function(){
if ($('div.wrap-instructor-info').length==0){
return;
}
$('div.xblock-student_view-video').each(function(key, vblock_e){
var vblock = $(vblock_e);
var vuid = vblock.data('usage-id').split('@');
var vid;
if (vuid.length==1){
vuid = vblock.data('usage-id').split(';_')
vid = vuid[5];
}else{
vid = vuid[2];
}
var mfnpre = vid.split("_video",1)[0];
var mfnid = mfnpre; // no periods
mfnpre = mfnpre.replace('8_370', '8.370'); // periods in gh filename
var lb = String.fromCharCode(60);
var rb = String.fromCharCode(62);
var mke = function(x){ return lb + x + rb; }
var ftid = "fix_transcript_" + mfnid;
if (!$('#' + ftid).length){
var html = lb + "span id='" + ftid + "' style='float:right'" + rb + lb + "a href='#'" + rb;
html += "contribute transcript fix" + mke("/a") + mke("/span");
console.log("html = ", html);
vblock.after(html)
}
$('#' + ftid).click(function(){
var cst = $('ol.subtitles').find('li.current');
var cindex = Number(cst.data('index'));
var gurl;
if (mfnpre.endsWith('_cq_sol')){
gurl = "https://github.com/mitocw/content-mit-8370x-cq-sol-subtitles/blob/master/";
}else{
gurl = "https://github.com/mitocw/content-mit-8370x-subtitles/blob/master/";
}
gurl += mfnpre + ".txt#L" + String(cindex + 10 + 1);
console.log("going to ", gurl);
window.open(gurl, "MITx 8.370x subtitle source");
});
});
}
try{
add_fix_transcript();
}
catch(err){
console.log(err);
}
try{
var rb = String.fromCharCode(62);
setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 3000);
setTimeout(function(){ $('.math' + rb + 'span').css("border-left-color","transparent"); }, 8000);
}
catch(err){
console.log(err);
}
</script></span>
</div>
</div>
</div>
</div>
© All Rights Reserved