حل سودوکو با افزایش قدرت کوانتومی

منتشر‌شده در: towardsdatascience به تاریخ ۵ مارس ۲۰۲۱
لینک منبع: Solving Sudoku with a Quantum Power-Up

امروز ما از یک حلال کوانتومی برای حل کردن سودوکو استفاده خواهیم کرد.

حتی بهتر: ما از بازی سودوکو برای محک زدن آخرین معماری حلال کوانتومی قابل‌دسترس عمومی استفاده خواهیم کرد. به این ترتیب، ما می‌دانیم که چه زمانی، زمان سرمایه‌گذاری در این فن‌آوری جدید فرا رسیده‌است.

اما یک حلال کوانتومی چیست؟

من نمی‌خواهم توضیح بدهم که چند نفر قبلا چه کار کرده‌اند و می‌توانند بهتر عمل کنند. بنابراین من برای شما لینک‌هایی با برخی توضیحات عالی در پایین فراهم می‌کنم، و در حال حاضر فقط فرضیات پایه که ما نیاز داریم را بیان می‌کنم:

• از حلال کوانتومی می‌توان برای حل مسائل بهینه‌سازی ترکیبی گسسته (که سودوکو زیر‌مجموعه آن است) استفاده کرد.
• با استفاده از جادوی مکانیک کوانتومی، حلال کوانتومی می‌تواند از نظر تئوری (بسیار) سریع‌تر از کامپیوترهای کلاسیک باشد.
• تولید‌کننده حلال کوانتومی، D-Wave، اسناد و یک API عمومی در دسترس (D-Wave Leap) را فراهم می‌کند که ما می‌توانیم برای حل پرسش خود از آن استفاده کنیم.

چگونه هدف حل یک آزمون سودوکو را تدوین کنیم؟

یک بازی سودوکو را می‌توان به سادگی به صورت ماتریسی بیان کرد که شامل اعداد همراه با یک مجموعه ساده از قوانین است.

فرض کنید که ما یک مجموعه ۹ * ۹ سودوکو داریم، که نشان می‌دهد صفحه به عنوان یک ماتریس با محدود کردن ماتریس به ۹ردیف و ۹ ستون شامل تنها اعداد از ۱ تا ۹ انجام می‌شود.

سپس می‌توانیم مجموعه قوانین سودوکو را به صورت زیر تعریف کنیم:

• هر ردیف باید شامل تمام اعداد از ۱ تا ۹ باشد.
• هر ستون باید تمام اعداد ۱ تا ۹ را در خود جای دهد.
• هر مربع باید شامل تمام اعداد از ۱ تا ۹ باشد.

اینها اساسا همه قوانینی هستند که ما نیاز داریم. خیلی ساده است، نه؟ اگر ما اکنون اطمینان حاصل کنیم که همه این قوانین حفظ می‌شوند، در حالی که اعداد را در نظر می‌گیریم، در نهایت یک راه‌حل سودوکو معتبر خواهیم داشت!

مطالعه مقاله چگونه رایانش کوانتومی می‌تواند آینده را تغییر دهد؟ توصیه می‌شود.

محدودیت‌های (ریاضی) چیست؟

مشکل فرمول‌بندی محدودیت‌ها در حال حاضر برای سخت‌افزار بهینه‌سازی غیر‌کوانتومی (که حلال دیجیتال نامیده می‌شود) در یک سری Top-Coder-Challenge حل شده است، بنابراین ما از قبل با مشکل زمان‌بر بودن زمان شروع مواجه شده‌ایم.

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

حال بیایید نگاهی سریع به محدودیت‌هایی که نیاز داریم بیندازیم:

این محدودیت اول نتیجه ابعاد برای هر عدد ممکنی است که ما درست قبل از آن معرفی کردیم. سلول یا «cell» مجموعه‌ای است که شامل تمام تاپل‌های ترکیبات سطری و ستونی است. محدودیت‌های ۲-۴ تنها قواعد سودکو هستند که در ابتدا درست تعریف کردیم.

محدودیت پنجم این است که اطمینان حاصل شود که الگوریتم شروع به تغییر اعدادی که در حال حاضر داده شده‌اند نمی‌کند. البته این برای یک انسان بدیهی است، اما یک کامپیوتر باید صراحتا بداند که چه کاری باید انجام دهد و چه کاری نباید انجام دهد. مجموع معادله زیر در یک مجموعه به نام «hint» تکرار می‌شود که شامل تمام سلول‌هایی است که در ابتدا داده شده‌اند.

با این حال، این محدودیت‌ها فرمتی که حلال کوانتومی بتواند آن را حل کند را ندارند. هنوز نه. ما باید محدودیت‌ها را به صورت یک QUBO (مساله بهینه‌سازی باینری غیرقانونی درجه دوم)، به منظور حل آن توسط حلال کوانتومی، مجددا فرمول‌بندی کنیم.
یک QUBO اساسا مجموعه‌ای از جملات خطی و درجه‌دوم را انتظار دارد، که نشان‌دهنده مشکل است.

یک راه برای تنظیم مجدد محدودیت‌های ما به عنوان یک QUBO، می‌تواند معرفی اصطلاحی به نام اصطلاح پنالتی باشد. با یک عبارت جریمه، ما رفتار «اشتباه» را جریمه می‌کنیم، بنابراین به نوعی الگوریتم را اجرا می‌کنیم تا بهترین راه‌حل را به ما بدهد.

اجازه دهید ابتدا ببینیم که این فرمولاسیون‌ها چگونه به نظر می‌رسند و بعد از آن کمی درباره آن‌ها صحبت می‌کنیم.

بسیاری از معادلات بالا از یک فاصله مربع ۱ استفاده می‌کنند، زیرا ما باید مطمئن شویم که هر عدد را تنها یک‌بار در هر ردیف و یک‌بار در هر ستون می‌توان انتخاب کرد. به این ترتیب بهترین راه‌حل، که حداقل است، و در مورد ما ۰ (به دلیل مربع بودن)، زمانی حاصل می‌شود که اعداد جمع‌شده زیر مجموع برابر با ۱ باشند.

منطق بیان مجدد محدودیت‌ها به عنوان یک تابع پنالتی، با راه‌حل بهینه که کمترین مقدار ممکن است، برای همه عبارات اعمال می‌شود.

اگر همه QUBOs ها را با هم ترکیب کنیم، تا تابع هدف نهایی برای حلال کوانتومی را به دست آوریم، در نهایت به این معادله می‌رسیم:

این تابع هدف منجر به یک ماتریس نهایی می‌شود که یک بازی سودوکو صحیح به عنوان یک راه‌حل بهینه دارد. در پایان، هر چیزی که حلال کوانتومی انجام می‌دهد، بهینه‌سازی گسسته است: یافتن یک مجموعه بهینه از مقادیر (راه‌حل) در یک فضای مساله گسسته ناشناخته. در این مرحله ما می‌توانیم با استفاده از QUBO و D-Wave Leap، یک جدول سودوکو را حل کنیم، که دسترسی رایگان به یک حلال کوانتومی: مزیت D-Wave با معماری پگاسوس ( Pegasus-Architecture) جدید را ارائه می‌دهد.

محدودیت‌های حلال کوانتومی

مشخص شده است که سخت‌افزار حلال کوانتومی هنوز برای حل کل این ربع سودوکو ۹*۹ کوچک است. برای من ممکن نبود که جایگذاری برای QUBO را در گراف سخت‌افزار D-Wave پیدا کنم، که یک گام ضروری قبل از نمونه‌برداری است.

با این حال، با نسخه کاهش‌یافته یک سودوکو ۴*۴ من می‌توانم یک جایگذاری معتبر پیدا کنم و بنابراین معیارهای عملکرد زیر را با این جدول با اندازه کوچک‌تر انجام خواهم داد.

ممکن است به مطالعه مقاله ۵ دلیل برای اینکه چرا باید از پایتون و AI در بازی‌سازی استفاده کرد! علاقمند باشید.

محک زدن معیار حلال کوانتومی

بعد از زمانی که برای محاسبه مورد نیاز است، معیار دیگری که به طور گسترده مورد استفاده قرار می‌گیرد احتمال موفقیت نامیده می‌شود. از آنجایی که حلال کوانتومی به صورت ابتکاری کار می‌کند، نتیجه معتبر تضمین نشده است. احتمال موفقیت تنها نسبت راه‌حل‌های صحیح با توجه به تمام محاسبات است. بسته به پیچیدگی مساله، احتمال موفقیت می‌تواند کاملا به سرعت کاهش یابد، به این معنی که تنها یک‌بار در یک زمان، آنالایزر کوانتومی راه‌حل بهینه را پیدا می‌کند و در زمان‌های دیگر به راه‌حل‌های (کمی) بدتری منجر می‌شود. برای داشتن چیزی به عنوان یک مقایسه، ما از یک الگوریتم تبرید شبیه‌سازی‌شده (Simulated Annealing) بر روی یک کامپیوتر کلاسیک استفاده می‌کنیم. حلال شبیه‌سازی‌شده ویژگی‌های زیادی را با حلال کوانتومی به اشتراک می‌گذارد.

حتی با این آزمایش بزرگ‌ترین تفاوت بین الگوریتم کلاسیک و کوانتومی در حال حاضر قابل‌مشاهده است. در حالی که حلال کوانتومی برای رسیدن به یک راه‌حل به زمان تقریبا ثابتی (۲۰ μs برای هر نمونه‌برداری) نیاز دارد، زمانی که الگوریتم کلاسیک نیاز دارد می‌تواند تغییر کند. علاوه بر این، به نظر می‌رسد که حلال کوانتومی، در هر صورت، سریع‌تر از CPU کامپیوترهای خانگی من است.

احتمال موفقیت تصویر متفاوتی را ترسیم می‌کند. در حالی که فرآیند شبیه‌سازی‌شده تقریبا همیشه راه‌حل دقیق را پیدا می‌کند، حلال کوانتومی این کار را تنها در ۱٪ از مراحل نمونه‌گیری انجام می‌دهد. این دقیقا دلیل این است که چرا ما هنگام محاسبه یک راه‌حل - به خصوص با سخت‌افزار کوانتومی به نمونه‌برداری نیاز داریم. اگرچه، ۱٪ به نظر یک نرخ بسیار بدی می‌رسد، اما اگر نمونه‌برداری، مثلا ۱۰۰۰اجرا، زمان ثابتی را در اندازه ثانیه بگیرد، بیش از حد کافی است - و یک راه‌حل معتبر معمولا تمام چیزی است که ما نیاز داریم.

نتیجه‌گیری

تجزیه و تحلیل مزیت حلال کوانتومی نشان می‌دهد که D-Wave ارائه مشکلات به سیستم خود را بسیار ساده کرده‌است. اگرچه سخت‌افزار برای حل مسائل بزرگ هنوز کوچک است، در حال حاضر کاربردهای جالب زیادی وجود دارد، که می‌تواند زمانی که اندازه مساله کاهش می‌یابد بررسی شود. علاوه بر این، ممکن است استفاده از یک رویکرد ترکیبی امکان‌پذیر باشد - یعنی: مساله را به یک بخش محاسباتی کلاسیک قابل محاسبه آسان تقسیم کنید و تنها بخش محاسباتی سخت‌تر را برای حلال کوانتومی برون‌سپاری کنید.

امیدوارم تجربه کوچک من بتواند به شما لذت سرمایه‌گذاری کمی از وقت شما برای شیرجه زدن در این فصل بسیار جالب از علوم کامپیوتر، ریاضیات و فیزیک را نشان دهد.

شما می‌تواند تمام کدهای ایجاد شده را در GitHub پیدا کند.

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

مقالات لینک‌شده در این متن می‌توانند به صورت رایگان با استفاده از مقاله‌خوان ترجمیار به فارسی مطالعه شوند.