دانلود مقاله ترجمه شده نگاشت توابع باینری به یک کامپیوتر کوانتومی بی دررو عملی – ۲۰۱۰ IEEE

نگاشت توابع باینری به یک کامپیوتر کوانتومی بی دررو عملی

Mapping Binary Functions to a Practical Adiabatic Quantum Computer

چکیده

۱- مقدمه

۲- مقدمه ای بر محاسبات کوانتومی آدیاباتیک

۳- جمع تعمیم یافته حاصل ضرب ها

۴- یک مثال ساده

۵- الگوریتم نگاشت

۶- اثبات صحت و درستی الگوریتم نگاشت

۷- پیچیدگی الگوریتم

۸- مزایا و محاسن الگوریتم

۹- نتیجه گیری

چکیده

نگاشت کارآمد توابع دودویی (باینری) روی کامپیوترهای کوانتومی آدیاباتیک، یک مسئله مهم به حساب می آید، زیرا از مدارهای حاصله می توان به عنوان اوراکل در الگوریتم Grover استفاده نمود. این مقاله روشی برای نگاشت توابع دودویی روی شبکه دو بعدی کوبیت (بیت کوانتوم) با برهم کنش های نزدیک ترین همسایه مطرح می کند که در نمونه اولیه سیستم های D-Wave بکار برده شده است. این کار با نوشتن تابع دودویی به شکلی خاص انجام می شود. بدین طریق تابع دودویی با تبدیل هر گیت به همیلتونی ۳ محلی (موضعی) پیاده می شود. سپس این همیلتونی ۳ محلی به همیلتونی ۲ محلی تبدیل می شود که روی شبکه کوبیت ها، نگاشته می شود.

۱- مقدمه
محاسبات کوانتومی آدیاباتیک پارادایم محاسباتی امیدوارکننده ای است که سیستم های D-Wave ادعا می کنند آن را روی کامپیوتر کوانتومی اولیه پیاده کرده اند. یکی از مزایای محاسبات کوانتومی آدیاباتیک نسبت به مدل مدار محاسبات کوانتومی آن است که امکان ساخت عملیات های منطقی بولی غیر برگشت پذیر در تابع هملیتونی میسر می باشد در صورتی که در مدل مدار محاسبات کوانتومی، برای پیاده سازی عملیات های برگشت ناپذیر با استفاده از گیت های برگشت پذیر، کوبیت های (فرعی) ancilla بایستی اضافه شوند.بدین طریق محاسبات کوانتومی آدیاباتیک می تواند از روشهای موجود از سنتز منطقی کلاسیکی استفاده نماید اما نیازمند نگاشت مدارها با آرایه مستطیلی از کوبیت های بکاررفته در وسیله کوانتومی آدیاباتیک می باشد. نشان داده شده است که محاسبات کوانتومی آدیاباتیک، زمان چند جمله ای معادل مدل مدار محاسبات کوانتومی هستند. این بدان معناست که الگوریتم های کوانتومی آدیاباتیک می توانند به تسریع زمان چند جمله ای نسبت به مدل مدار محاسبات کوانتومی دست یابند. یک ورژن کوانتومی آدیاباتیک از الگوریتم Grover توصیه شده است که تسریع درجه دو نسبت به محاسبات کلاسیکی بدست آمده درمدل مدار محاسبات کوانتومی، حاصل می نماید. از آنجایی که ورژن های مدارو آدیاباتیک الگوریتم کوانتومی Grover برای شناسایی حالت های پایه مطلوب، بر یک اوراکل تکیه می کنند، در نتیجه ساخت این اوراکل به روش کارآمد به یک مسئله مهم تبدیل می شود. در مدل مدار محاسبات کوانتومی، اوراکل به شکل ماتریس یکه ظاهر می شود که علامت فاز هر حالت پایه نظیر راه حل را تغییر می دهد.

Abstract

Efficiently mapping binary functions to adiabatic quantum computers is an important problem because the resulting circuits can be used as oracles in Grover’s algorithm. This paper presents a method for mapping binary functions to a two-dimensional grid of qubits with nearest neighbor interactions which is used in a prototype from D-Wave Systems. This is done by writing the binary function in a special form. This allows the binary function to be implemented by converting each gate into a 3- local Hamiltonian. These 3-local Hamiltonians are then converted into two-local Hamiltonians which are mapped to the grid of qubits.

I- INTRODUCTION

Adiabatic quantum computation is a promising computational paradigm which D-Wave Systems claims to have implemented on a prototype quantum computer [4]. An advantage of adiabatic quantum computation over the circuit model of quantum computation is that it is possible to build non-reversible boolean logic operations into the Hamiltonian whereas in the circuit model of quantum computation additional ancilla qubits must be added to implement non-reversible operations using reversible gates. This allows adiabatic quantum computation to utilize existing methods from classical logic synthesis but requires circuits to be mapped to the rectangular array of qubits utilized in the adiabatic quantum device. Adiabatic quantum computation has been shown to be polynomial time equivalent to the circuit model of quantum computation [1]. This means that it may be possible for adiabatic quantum algorithms to achieve polynomial time speedups over their equivalents in the circuit model of quantum computation. An adiabatic quantum version of Grover’s algorithm [6] has been devised which provides the quadratic speedup over classical computation achieved in the circuit model of quantum computation [3]. Because both the circuit and adiabatic versions of Grover’s quantum algorithm [3] rely on an oracle to identify the desired basis states, constructing this oracle efficiently becomes an important problem.

تصویری از مقاله ترجمه و تایپ شده در نرم افزار ورد

نگاشت توابع باینری به یک کامپیوتر کوانتومی بی دررو عملی

Mapping Binary Functions to a Practical Adiabatic Quantum Computer