الگوریتم‌های کوانتومی مرسوم برای حل مسائل بهینه‌سازی ترکیبی (COP) با محدودیت‌هایی در زمان عملکرد رایانه‌های کوانتومی امکان‌پذیر نیستند. برای پرداختن به این موضوع، محققان یک الگوریتم جدید به نام الگوریتم کوانتومی برنامه‌ریزی شده تغییرات پس از پردازش ایجاد کرده‌اند. تازگی این الگوریتم نوآورانه در استفاده از تکنیک پس پردازش همراه با زمان‌بندی متغیر برای دستیابی به راه‌حل‌های با کیفیت بالا برای COPها در زمان کوتاه نهفته است.
مسائل بهینه‌سازی ترکیبی (COPs) در بسیاری از زمینه‌های مختلف مانند لجستیک، مدیریت زنجیره تامین، یادگیری ماشین، طراحی مواد و کشف دارو، از جمله برای یافتن راه‌حل بهینه برای مسائل پیچیده کاربرد دارند. این مشکلات معمولاً با استفاده از رایانه‌های کلاسیک از نظر محاسباتی بسیار فشرده هستند و بنابراین حل COPها با استفاده از رایانه‌های کوانتومی توجه قابل توجهی را هم از طرف دانشگاه و هم از صنعت به خود جلب کرده است.
کامپیوترهای کوانتومی از ویژگی کوانتومی برهم نهی با استفاده از کیوبیت‌های تخصصی استفاده می‌کنند که می‌تواند در تعداد بی‌نهایت و در عین حال حاوی حالت‌های 0 یا 1 یا هر ترکیبی از این دو وجود داشته باشد تا به سرعت مسائل بزرگ را حل کند. با این حال، زمانی که COPها شامل محدودیت‌ها می‌شوند، الگوریتم‌های کوانتومی معمولی مانند آنیل کوانتومی آدیاباتیک برای به دست آوردن یک راه‌حل تقریباً بهینه در زمان عملکرد رایانه‌های کوانتومی تلاش می‌کنند. پیشرفت‌های اخیر در فناوری کوانتومی منجر به تولید دستگاه‌هایی مانند آنیل‌کننده‌های کوانتومی و دستگاه‌های کوانتومی نوع دروازه‌ای شده است که بسترهای مناسبی را برای حل COP فراهم می‌کنند. متأسفانه، آنها مستعد نویز هستند، که کاربرد آنها را برای الگوریتم‌های کوانتومی با هزینه‌های محاسباتی کم محدود می‌کند.
برای مقابله با این چالش، استادیار Tatsuhiko Shirai و پروفسور Nozomu Togawa از دپارتمان علوم کامپیوتر و مهندسی ارتباطات در دانشگاه Waseda در ژاپن اخیراً یک الگوریتم کوانتومی برنامه‌ریزی متغیر پس از پردازش (pVSQA) پیشگامانه توسعه داده‌اند. “دو روش اصلی برای حل COP با دستگاه‌های کوانتومی، زمان‌بندی تغییرات و پس پردازش است. الگوریتم ما زمان‌بندی تغییرات را با یک روش پس پردازش ترکیب می‌کند که راه‌حل‌های غیرقابل اجرا را به راه‌حل‌های عملی تبدیل می‌کند و به ما امکان می‌دهد به راه‌حل‌های تقریباً بهینه برای COPهای محدود برسیم. دکتر شیرایی توضیح می دهد که هم آنیل کننده های کوانتومی و هم کامپیوترهای کوانتومی مبتنی بر گیت. مطالعه آنها در ژورنال IEEE Transactions on Quantum Engineering در 13 مارس 2024 منتشر شد.
الگوریتم نوآورانه pVSQA از یک دستگاه کوانتومی برای تولید یک حالت کوانتومی متغیر از طریق محاسبات کوانتومی استفاده می کند. سپس از این برای تولید یک تابع توزیع احتمال استفاده می‌شود که شامل تمام راه‌حل‌های امکان‌پذیر و غیرممکن است که در محدوده محدودیت‌های COP هستند. سپس، روش پس پردازش، راه‌حل‌های غیرممکن را به راه‌حل‌های عملی تبدیل می‌کند و توزیع احتمال را تنها با راه‌حل‌های امکان‌پذیر باقی می‌گذارد. سپس یک کامپیوتر کلاسیک برای محاسبه مقدار انتظار انرژی تابع هزینه با استفاده از این توزیع احتمال جدید استفاده می شود. تکرار این محاسبه منجر به یک راه حل تقریباً بهینه می شود.
محققان عملکرد این الگوریتم را با استفاده از یک شبیه ساز و دستگاه های کوانتومی واقعی مانند یک آنیل کوانتومی و یک دستگاه کوانتومی نوع دروازه تجزیه و تحلیل کردند. آزمایش‌ها نشان داد که pVSQA در یک زمان از پیش تعیین‌شده در شبیه‌ساز به عملکرد تقریباً بهینه‌ای دست می‌یابد و از الگوریتم‌های کوانتومی معمولی بدون پس‌پردازش در دستگاه‌های کوانتومی واقعی بهتر عمل می‌کند.
دکتر شیرایی کاربردهای بالقوه این الگوریتم را برجسته می‌کند و می‌گوید: برای رسیدگی به مسائل مختلف اجتماعی به تحولات اجتماعی شدید نیاز مبرم دارد. از نمونه‌های آن می‌توان به تحقق جامعه‌ای بدون کربن برای حل مسائل مربوط به تغییرات اقلیمی و تحقق اهداف توسعه پایدار برای رفع آن اشاره کرد. مسائلی مانند افزایش تقاضای انرژی و کمبود مواد غذایی حل موثر مسائل بهینه سازی ترکیبی در مرکز دستیابی به این تحولات است نقش مهمی در تحقق این تحولات اجتماعی درازمدت دارد.”
در نتیجه، این مطالعه یک گام مهم رو به جلو برای استفاده از رایانه‌های کوانتومی برای حل COP است، که نویدبخش رسیدگی به مشکلات پیچیده دنیای واقعی در حوزه‌های مختلف است.
مرجع
نویسنده: Tatsuhiko Shirai1 و نوزومو توگاوا1
وابستگی ها: گروه علوم کامپیوتر و مهندسی ارتباطات، دانشگاه Waseda
درباره دانشگاه واسدا
دانشگاه Waseda واقع در قلب توکیو، یک دانشگاه تحقیقاتی خصوصی پیشرو است که از سال 1882 به تعالی دانشگاهی، تحقیقات نوآورانه و مشارکت مدنی در سطح محلی و جهانی اختصاص یافته است. از جمله نه نخست وزیر و بسیاری از رهبران در تجارت، علم و فناوری، ادبیات، ورزش و فیلم. Waseda با مؤسسات تحقیقاتی خارج از کشور همکاری قوی دارد و متعهد به پیشبرد تحقیقات پیشرفته و توسعه رهبرانی است که می توانند در حل مسائل اجتماعی پیچیده و جهانی مشارکت کنند. این دانشگاه در راستای اهداف توسعه پایدار (SDGs) که در سال 2015 توسط سازمان ملل متحد به تصویب رسید، دستیابی به پردیس کربن صفر تا سال 2032 را هدف گذاری کرده است.
برای کسب اطلاعات بیشتر در مورد دانشگاه Waseda، مراجعه کنید
درباره استادیار Tatsuhiko Shirai
Tatsuhiko Shirai در حال حاضر استادیار گروه کامپیوتر و مهندسی ارتباطات در دانشگاه Waseda در ژاپن است. او فوق لیسانس و دکتری خود را گرفت. در فیزیک از دانشگاه توکیو در سال 2013 و 2016 به ترتیب. در سال 2022، او جایزه مقاله عالی SLDM Research Group را دریافت کرد. زمینه های تحقیقاتی او شامل الگوریتم های کوانتومی، سیستم های باز کوانتومی و محاسبات کوانتومی است. او عضو انجمن فیزیکی ژاپن است.
