ترجمه مقاله مدار جمع کننده با بیت نقلی موج گونه کوانتومی

 

 

یک مدار جمع کننده جدید با بیت نقلی موج گونه کوانتومی

 

A new quantum ripple-carry addition circuit

 

چکیده

ما در اینجا یک مدار جمع کننده جدید کوانتومی با بیت نقلی و عمق خطی ارائه می دهیم. مدارهای الحاقی قبلی بطورخطی نیازمند کیوبیت های جانبی بودند؛ جمع کننده جدید ما تنها از یک کیوبیت جانبی واحد استفاده می کند؛ همچنین، مدار ما دارای عمق پایین تر و مدخل کمتر نسبت به جمع کننده های با بیت نقلی موج گونه می باشد.  

 

سفارش ترجمه تخصصی مهندسی برق

 

مقدمه

  

ما یک مدار کوانتومی جدیدی بمنظور افزاینده ارائه می دهیم. این مدار مبتنی بر رویکردی با بیت نقلی موج گونه می باشد که در آن ما با بیت های مرتبه پایین درونداد شروع می کنیم و مسیر خودمان را به سمت بیت های با مرتبه بالا ادامه می دهیم. از آنجایی که محاسبات ما می بایست برگشت پذیر باشد، در نتیجه ما مسیر خودمان را از بیت های با مرتبه بالا به سمت بیت های با مرتبه پایین به انجام می رسانیم. یک جمع کننده با بیت نقلی موج گونه قبلا توسط ودرال، بارنکو و اکرت (4) مطرح شده است. مدارآنها دارای     دو عدد nبیتی بعنوان درونداد می باشد که مجموع موجود در مکان را محاسبه می کند و یک بیت واحد (بیت بالای مجموع کل) برونداد می کند. آنها همچنین کیوبیتهای ابتدایی n-O و یا ancillae را مستلزم می سازند.

 

 

 

مدار ما از این جهت دارای تفاوت می باشد که آن نیازمند تنها یک ancilla می باشد. همچنین عمق واندازه مدار کوچکتر می باشد. جمع کننده VBE متشکل از گیت های 4n +O(1) CNOT (کنترل شده-NOT) و گیت های توفولی 4n + O(1) (کنترل دوبرابر-NOT)، با همانندی کمتری می باشد. مدار ما از گیت های توفولی 2n + O(1) ، گیت های 5n + O(1) CNOT، و منفی های 2n + O(1)  استفاده می کند؛ عمق نیز برابر با 2n + O(1) می باشد.     

 

 

 

 

 

 

 

 

 

جزء اصلی جمع کننده جدید یک مدار می باشد که اکثریت سه بیت موجود در مکان را مورد محاسبه قرار می دهد. ما این مدار، و یک نسخه ساده از جمع کننده  در بخش 2 را ارائه می کنیم. ما سپس یک نسخه بهینه شده در بخش 3 ارائه می کنیم. بمنظور مشاهده یک نسخه شبه برنامه از جمع کننده به شکل 5 مراجعه کنید و برای یک نسخه تصویری به شکل 6 مراجعه کنید.

 

 ما در بخش 4 به بحث در رابطه با چندین متغیر جمع کننده می پردازیم: که انجام دهنده پیمانه جمع 2n با استفاده از یک بیت نقلی ورودی و محاسبه کننده تنها بیت بالای مجموع کل می باشد. این متغیر آخری بمنظور ایجاد یک قیاسگر ممکن است تغییر پیدا کند. پیچیدگی های این متغیرها در جدول 1 موجود در صفحه 6 بطور مختصر بیان گردیده است.

 

2- ایده اصلی

هدف ما محاسبه مجموع دو تعداد n بیتی a و b می باشد. اینطور بنویسید، a = an−1 · · · a0، که a0 در آن بیت پایین ترین مرتبه می باشد، و بهمین نحو، بنویسید که b = bn−1 · · · b0. ما از Ai و Bi استفاده می کنیم تا به مکانهای حافظه در جایی که ai و bi از ابتدا ذخیره گردیده اند اشاره کنیم.

ما a و b را در مکان مربوطه خواهیم افزود؛ در انتها، Bi حاوی si،بیت iام مجموع،  خواهد بود. یک مکان برونداد افزوده شده، Z، برای بیت بالای Sn وجود دارد.

ما رشته حامل را برای a و b بطور بازگشتی تعریف می کنیم: برای i ≥ 0، اینطور در نظر بگیرید، c0  = 0، و

 ci+1  = MAJ(ai, bi, ci). توجه داشته باشید که MAJ(ai , bi, ci) = aibi ⊕ aici ⊕ bici. ما سپس برای تمامی i < n، اینطور داریم si  = ai ⊕ bi ⊕ ci ، و همچنین sn  = cn. در یک جمع کننده با بیت نقلی موج گونه کلاسیک، ما هر ci را بترتیب مورد محاسبه قرار می دهیم، و مسیر خودمان از c1 به سمت cn  به انجام می رسانیم. در یک جمع کننده با بیت نقلی موج گونه برگشت پذیر، ما می بایست سپس بیت های نقلی را حذف کنیم و مسیر خودمان را به سمت عقب به انجام برسانیم.          

 

 

 

 

 

اولین جزء جمع کننده ما، که در شکل 1 ترسیم شده است، یک گیت می باشد که اکثریت سه بیت کارگذاشته را مورد محاسبه قرار می دهد. ما مدارهای خودمان را خارج از موارد منفی ، CNOTها، و گیت های توفولی  ایجاد می کنیم؛ در نمودار مداری ما، زمان از چپ به راست جریان می یابد. برای اکثریت بکار گرفته، ما دو CNOT اول و سپس یک توفولی را بکار می گیریم.

 

دومین جزء، که در شکل 2 ترسیم شده است، یک گیت UnMajority and Add  و یا UMA می باشد. ما دو گونه از این مورد را ارئه میکنیم، که هریک از آنها تابع یکسان را در کیوبیت ها مورد محاسبه قرار می دهد. اولین مورد بطور نظری ساده تر می باشد ولی دومین مورد همانندی های بیشتری را می پذیرد. 

 

 

 

تاثیر استفاده از این دو گیت باهم در شکل 3 نشان داده شده است. فرض کنید که ما تنها بیت نقلی ci را مورد محاسبه قرار داده ایم. ما گیت MAJ را بکار می گیریم، که ci+1 را در یک Ai می نویسد. ما سپس محاسبه خودمان را تداوم می دهیم. بعد از اینکه ما با استفاده از ci+1  این کار را انجام دادیم، گیت UMA را بکار می گیریم که ai به Ai  و ci  را به Ai−1 بازیابی می کند و si  را به Biمی نگارد.    

 

در ادامه ما میتوانیم گیت های MAJ و  UMA را بمنظور ایجاد یک جمع کننده با بیت نقلی موج گونه باهم بصورت زنجیروار مرتب کنیم. چنین جمع کننده ای در شکل 4 ترسیم گردیده است. ما یک Aancilla با برچسب X در اختیار داریم که از صفر شروع می شود. ما X را بصورتی مدنظر می گیریم که حاوی بیت نقلی اولیه c0 می باشد. بیت برونداد Z حاوی مقادیرکمی از Z در زمانی که مدار شروع می گردد می باشد و زمانی که مدار به انتها می رسد حاوی مقدار کمی از z ⊕ snمی باشد.   

 

3- توسعه مدار

ما میتوانیم عمق مدار اصلی شکل 4 را به چندین روش کاهش می دهیم. استفاده از گونه 3-CNOT از گیت UMA از شکل 2b ضروری می باشد.

اولین CNOTs از تمامی گیت های MAJ میتواند در یک برش زمانی واحد در ابتدا انجام پذیرد. به همین نحو، CNOTهای نهایی از تمامی گیت های UMA میتواند در یک برش زمانی واحد در انتها انجام پذیرد.

2 .  نیمه اول مدار را در نظر بگیرید: موج گونه MAJ. توفولی در انتهای iام گیت MAJ با دومین CNOT از گیت

 (i + 1)ام جابجا می گردد. اگر ما این دو گیت را برای هر i معاوضه کنیم، سپس عمق کاهش می یابد: توفولی iام گیت MAJ هم اکنون می تواند هماهنگ با دومین CNOT از گیت MAJ (i+2) ام انجام پذیرد.

3. ما میتوانیم یک انتقال مشابهی را در دومین نیمه مدار به انجام برسانیم. ما توفولی گیت UMA (i + 1)ام را با دومین CNOT گیت UMA iام مبادله میکنیم. مجددا، عمق کاهش می یابد: دومین CNOT از گیت UMA i ام میتواند هماهنگ با توفولی گیت UMA (i+2) ام انجام پذیرد.

 

4- ما میدانیم که c0  = 0 می باشد، از اینرو ما برای محاسبه c1  = a0b0 به یک گیت MAJ نیاز داریم. در عوض، ما c1را با یک توفولی واحد محاسبه می کنیم و آن را در ancilla خودمان ذخیره می کنیم. در انتهای مدار، ما این توفولی یکسان را خنثی می کنیم و سپس B0  را به s0  با یک CNOT واحد تنظیم می کنیم.

 

 

 

 

 

5. نوشتن cn  در An−1 ، کپی کردن آن در برونداد، و سپس حذف آن ناکارآمد می باشد. ما میتوانیم در عوض آن را مستقیما به برونداد بنویسیم. ما بخش مرکزی (دو توفولی و، دو CNOT و دو مورد منفی) را با یک توفولی و دو CNOT  جایگزین می سازیم. یکی از CNOT ها میتواند هماهنگ با سایر محاسبات انجام پذیرد.     

مدار با بیت نقلی موج گونه ما در شکل 5 تشریح گردیده است. ساختار مربوطه برای هر n بکار گرفته شده است، اما شبه برنامه در شکل 5 تنها برای n ≥ 4 دارای اعتبار می باشد. یک مدار نمونه برای n = 6  در شکل 6 ترسیم شده است. توجه داشته باشید که در شکل 4، ancilla حاوی c0 بوده و بالاترین سیم می باشد؛ در شکل 6، ancilla حاوی c1 بوده و سومین سیم از بالا می باشد.

 

 

4. موارد افزوده شده

ما هم اکنون گونه های مختلف جزئی تغییر یافته از جمع کننده با بیت نقلی موج گونه را مورد بحث قرار می دهیم:

•  پیمانه  2n: ما بیت بالا را مورد محاسبه قرار نمی دهیم.
• نقل (حامل) درآیند: ما ancilla c0 را یک بیت درونداد اضافی در نظر می گیریم.
• تنها بیت بالا: ما بیت بالا را مورد محاسبه قرار می دهیم، اما درونداد b را بازنویسی می کنیم. این مدار میتواند بمنظور ارائه یک قیاسگر سازگار گردد.

در هر مورد، مدار یک تغییرپذیری ساده ای از مدار مربوط به بخش 3 می باشد. تنها سوال مربوط به عمق و اندازه دقیق مدار می باشد. نتایج در جدول 1 بطور مختصر توضیح داده شده است. برای هر مدار، ما تعداد گیت های توفولی، تعداد گیت های CNOT، و عمق کلی را ارائه می کنیم. در هر مورد، تعداد برش های زمانی توفولی برابر با تعداد گیت های توفولی می باشد؛ برش های زمانی باقیمانده حاوی CNOT می باشد. برای جمع کننده VBE، مدار دارای برش های زمانی توفولی 3n-1 و برش های زمانی CNOT 3n-1 می باشد.

 

 

جدول1- خلاصه مدار، برای موارد n ≥ 3. اولین ستون نشان دهنده تابع مورد محاسبه قرار گرفته می باشد. دومین ستون مربوط به این موضوع می باشد که آیا ما یک بیت نقلی درآیند را بعنوان درونداد مدنظر میگیریم یا خیر. سپس ما تعداد درونداد، برونداد و بیت های ancilla، تعداد گیت های توفولی و CNOT، و عمق کلی را بصورت فهرست بیان می کنیم. ما موارد منفی را در زمان محاسبه اندازه و عمق مشمول نمی سازیم.

 

4.1- پیمانه افزوده 2n

فرض کنید که ما میخواهیم a + b (mod 2n) را مورد محاسبه قرار دهیم؛ یعنی، ما نمی خواهیم بیت بالای cn را مورد محاسبه قرار دهیم. یک رویکرد بصورت زیر می باشد:

1. مرتبه پایین بیت های n-1 مربوط به a و  b را با استفاده از مدار بخش 3 بیفزایید. از Bn−1   بعنوان

 بیت برونداد استفاده کنید.

   2.  Set Bn−1 ⊕= An−1.

 

بعد از مرحله 1، ما بطور صحیحی s0  را از طریق sn−2 محاسبه کردیم، و bn−1  ⊕ cn−1  را در Bn−1  نوشته ایم.

سپس، در مرحله 2، برآورد sn−1 را تکمیل می کنیم. توجه داشته باشید که مرحله2 هماهنگ با برش زمانی نهایی مرحله 1 واقع می گردد.

برای n ≥ 3، این مدار حاوی توفولی های 2n – 3، CNOTهای 5n − 7  و موارد منفی 2n − 6  می باشد. عمق برابر با 2n + 2 می باشد: برش های زمانی توفولی 2n − 3  و 5 برش های زمانی CNOT.        

 

 

 

 

 

4.2- جمع با نقل درآیند

فرض کنید که ما میخواهیم یک بیت نقلی درآیند را در مدار جمع خودمان بپذیریم. ما بیت درونداد افزودنی y را داریم و a+b+y را مورد محاسبه قرار می دهیم.

ما مشاهده می کنیم که مدار بخش 2 قبلا این مسئله را حل کرده است؛ ما از y در مکان ancilla c0 استفاده می کنیم. ما سپس بطور صحیحی c1 مورد محاسبه قرار می دهیم و موج تداوم می یابد.

ما نمی توانیم از توسعه چهارم از بخش 3 استفاده کنیم، زیرا ما دیگر نمی توانیم فرض کنیم که بیت درآیند برابر با صفر باشد. اصلاحات دیگر هنوز بکار گرفته می شوند.

 

ما یک جمع کننده با بیت نقلی موج گونه را با نقل درآیند بدست آوردیم که شامل توفولی های 2n − 1 ، CNOTهای

5n + 1  و موارد منفی 2n-1 می باشد. برای مورد n ≥ 2، مدار دارای عمق 2n+6 می باشد: برش های زمانی توفولی 2n-1، و 7 برش زمانی CNOT.

ما میتوانیم همچنین تغییرپذیری نقل درآیند را برای مدار بخش 4.1 بکار بگیریم. برای مورد n ≥ 3، ما یک مدار با توفولی های 2n − 3 ، CNOTهای 5n − 3 ، و موارد منفی 2n − 4  بدست می آوریم. عمق برابر با 2n + 4 می باشد: برش های زمانی توفولی 2n − 3 ، و 7 برش زمانی CNOT.       

 

4.3- منحصرا بیت بالا

ما هم اکنون مسئله محاسبه منحصرا بیت بالا از مجموع  a + b را مدنظر قرار می دهیم. اولین نیمه از مدار همانند با اولین نیمه از جمع کننده ما از بخش 3 می باشد: زمانی که ما نقطه وسط را بدست می آوریم، در واقع بیت بالا نسبت به Z را نوشته ایم. هم اکنون، ما بسادگی اولین نیمه از مدار را به حالت اول باز می گردانیم. ما میتوانیم این را همراه با بکارگیری یک سری از گیت های MAJ که بدنبال یک توفولی و یک سری از گیت های MAJ−1  می باشد مشاهده کنیم.

برای مورد n ≥ 2، مدار منتج حاوی گیت های توفولی 2n − 1  و CNOTهای4n – 3  می باشد.عمق برابر با  2n + 3 می باشد: برش های زمانی توفولی 2n-1 و 4 برش زمانی CNOT.

ما میتوانیم مدار بیت بالا را با تغییرپذیری نقل درآیند که در بخش 4.2 مورد بحث قرار گرفت ترکیب کنیم. ما یک مدار با توفولی های 2n-1 و CNOTهای 4n+1 بدست می آوریم. برای n ≥ 2، عمق برابر با 2n+5 می باشد: برش های زمانی توفولی 2n-1 و 4 برش زمانی CNOT.

   

توجه به این نکته ضرورت دارد که جمع کننده نقل موج گونه ما میتواند به آسانی به یک کاهشگر مبدل گردد. اینکه ما از حسابگر تک مکمل و یا جفت مکمل استفاده کنیم، ما مشخصات زیر را دریم

a − b = (a′ + b)′

جایی که ′  اشاره به مکمل سازی بیتی دارد. بنابراین، ما میتوانیم با افزودن دو برش زمانی کم کنیم:

     مکمل a در ابتدا، و مکمل a و s در انتها.

اگر ما این ایده کاهش را با محاسبه کننده بیت بالای این بخش ترکیب کنیم، ما یک قیاسگر بدست می آوریم: ما بیت بالای a-b را محاسبه میکنیم، که تنها در صورتی که a کوچکتر از b باشد برابر با 1 است

 

 

 

 

5- نتیجه گیری

یک مسئله مشخص و جالب توجه ایجاد یک مدار جمع مطلوب می باشد.بویژه، اگر یک مدار جمع برگشت پذیر تنها از یک ancilla استفاده کند، آیا آن می بایست دارای عمق خطی باشد؟  یک جمع کننده عمقی-لگاریتمی با استفاده از 2n ancilla ایجاد گردیده است {3}؛ بطور کلی تر، برای هر k > 0، ما میتوانیم یک خانواده ای از مدارها با استفاده از n/k ancilla با عمق O ایجاد کنیم (k + log n). آیا یک خانواده مدار جمع عمقی-لگاریتمی با استفاده از تنها یک تعداد ثابت از ancilla وجود دارد؟ در غیر اینصورت، آیا ما میتوانیم یک محدوده پایین تری در عمق را اثبات کنیم؟

 

 

یک نوع از جمع کننده با بیت نقلی موج گونه پیشنهاد عدم استفاده از ancilla را کرده است {1}. این مدار

نیازمند این می باشد که بیت برونداد تا میزان صفر مقداردهی اولیه گردد. ما نمی دانیم که آیا میتوانیم عمق خطی را بدون ancilla و بدون این محدودیت در بیت برونداد بیفزاییم.       

 

این موضوع جالب توجه خواهد بود که جمع کننده با بیت نقلی موج گونه این مقاله را با جمع کننده انتقالی مورد مقایسه قرار دهیم.(2).

هردو مدار دارای عمق خطی می باشند. این موضوع نامشخص می باشد که اجرای کدام جمع کننده بطور عملی آسانتر خواهد بود؛ جواب بستگی به ارزش های نسبی گیت های توفولی و جابجایی های کنترل شده دارد. این موضوع شناخته شده می باشد که گیت توفولی ممکن است از 5 چرخش کنترل شده ایجاد گردد. بنابراین یک شخص ممکن است انتظار این را داشته باشد که عمق یگانی کنترل شده از جمع کننده با بیت نقلی موج گونه ما برابر با 10n+O(1) باشد. در حقیقت، توفولی ها میتوانند اشتراک داشته باشند؛ عمق مربوطه تنها 6n-2 می باشد. یک مثال با n=5 در شکل 7 ترسیم شده است.

 

 

 

 

 

ما همچنین میتوانیم ارزش افزودن یک کمیت کلاسیک به یک کمیت کوانتوم را مد نظر بگیریم. ما در حافظه کوانتوم خودمان تعداد nبیتی اندکی را داریم، و میخواهیم تا یک تعداد ثابت nبیتی (معروف به زمان کامپایل) را به آن بیفزاییم.  جمع کننده با بیت نقلی ما در یان زمینه ساده تر از این نمی گردد؛ ما هنوز می بایست از بیت های کوانتوم n بمنظور ذخیره کردن افزوده کلاسیک استفاده کنیم. از سویی دیگر، جمع کننده انتقالی به میزان زیادی منفعت خواهد برد؛ اطلاعات کلاسیک نمی بایست در حافظه کوانتوم ذخیره گردد، و چرخش های کنترل شده با چرخش های شناخته شده و ثابت جایگزین می گردند. در این زمینه، جمع کننده انتقالی برتر به نظر می رسد.