توضیحات
عنوان فارسی: بهبود الگوریتم کوانتومی خروجی حساس برای ضرب ماتریس بولین
عنوان انگلیسی:
Improved Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication
چکیده
ما الگوریتم های کوانتومی جدید برای ضرب ماتریس بولیندر در هر دو مورد پیچیدگی زمان و تنظیمات پیچیدگی پرس و جو را ارائه کرده ایم. تا آنجا که به پیچیدگی زمانی مربوط می شود، نتایج ما نشان می دهد که محصول دو ماتریس N × N بولین را می توان بر روی یک کامپیوتر کوانتومی در زمان ( O (N3 / 2 + nℓ 3/4 محاسبه کرد، که در آن ℓ تعداد غیر صفر ورودی در محصول است، این عمل با بهبود الگوریتم کوانتومی خروجی-حساس Buhrmanو Spalek درزمان ( O (N3 / 2 √ ℓ اجرا می شود. این عمل با ساخت یک نسخه کوانتومی از یک الگوریتم اخیر توسط Lingas، با استفاده از تکنیک های کوانتومی مانند شمارش کوانتومی برای بهره برداری از پراکندگی ماتریس خروجی انجام می شود. تا آنجا که به بررسی پیچیدگی مربوط می شود، نتایج ما بهبود الگوریتم کوانتومی توسط Vassilevska ویلیامز و ویلیامز را بر اساس مشکل کاهش یافته برای مثلث بهبود می بخشد. یکی از کمک های اصلی که منجر به بهبود شد، ساخت یک الگوریتم کوانتومی برای پیدا کردن مثلث به خصوص برای گراف های سه جانبه که در کاهش نمایان می شوند، می باشد.
- مقدمه
1.1 سابقه و هدف ضرب ماتریس بولین، که در آن علاوه بر این به عنوان یک منطق OR و ضرب به عنوان یک منطق AND تفسیر می شود، یک مشکل اساسی در علم کامپیوتر است. الگوریتم های مورد استفاده در ضرب ماتریس بولین، در بسیاری از مناطق کاربردی شده اند و به عنوان مثال، برای ساخت الگوریتم های کارآمد برای محاسبه بسته شدن متعد یک گراف [11، 12، 20]، از به رسمیت شناختن زبان مستقل از متن [22، 26]، تشخیص اینکه اگر یک گراف شامل یک مثلث [15] باشد، حل تمام جفت های مشکلات مسیر [10، 13، 24، 25]، و یا بالا بردن سرعت وظایف داده کاوی [2]، استفاده می شود.این محصول از دو بولین N × N ماتریس های A و B می تواند در زمان (O (N3 محاسبه شود. بهترین الگوریتم شناخته شده توسط تفسیر ماتریس A و B به عنوان ماتریس عدد صحیح، محاسبه ماتریس عدد صحیح، و تبدیل ماتریس محصول به یک ماتریس بولین می باشد. با استفاده از الگوریتم های کوپر-اسمیت و وینوگراد [9] برای ضرب ماتریس صحیح، یک الگوریتم برای ماتریس بولین چند کاربردی با پیچیدگی زمانی(O (n2.376 به دست می آید. از لحاظ جبری بیشتر این ایده وجود دارد که بولین نیمه حلقه ای می تواند در حلقه عدد صحیح جاسازی شده، و ضرب ماتریسی می تواند سریع تر در یک حلقه با استفاده از خواص لغو انجام شود. این رویکرد، دارای چند ایراد کلی می باشد، یکی از اصلی ترین آنها این است که الگوریتم کوپراسمیت-وینوگراد را در عمل به سختی می توان پیاده سازی نمود. به همین دلیل، تلاش زیادی در درک اینکه آیا ضرب ماتریس بولی می تواند درزمان ( O (N3 توسط ترکیب الگوریتم های ایجاد شود، صورت پذیرفته است، به عنوان مثال، الگوریتم هایی که بر روی ماتریس یک محصول توسط حلقه ها متکی نیستند. یک دلیل شاید اساسی تر برای بررسی این سوال این است که یک الگوریتم ترکیبی سریع برای ضرب ماتریس بولین، احتمالا به نیمه حلقه نیاز دارد، به خصوص نیمه حلقه (دقیقه، +) مربوط به بسیاری از مسائل گراف وزن دار مانند تمام مسائل با جفت های کوتاه. متاسفانه، پیشرفت کمی در این مورد وجود داشته است. بهترین الگوریتم ترکیبی شناخته شده با پیچیدگی زمانی( O (N3 / log2.25 n) اخیرا توسط Bansal و ویلیامز کشف شده است که الگوریتم “چهار روس” [3] پیشنهاد شده در دهه گذشته را بهبود می بخشد.
توجه: برای دانلود فایل ورد ترجمه مقاله لطفا اقدام به خرید فایل نمایید.
دیدگاهها
هیچ دیدگاهی برای این محصول نوشته نشده است.