Sunnyvale، کالیفرنیا - 26 اکتبر 2022 - NTT Research اعلام کرد که یک دانشمند از آن آزمایشگاه رمزنگاری و امنیت اطلاعات (CIS). و همکار از آزمایشگاه انفورماتیک اجتماعی NTT (SIL) مقاله راهگشایی در مورد مزیت کوانتومی نوشته است. این مقاله برای ارائه در سمپوزیوم سالانه IEEE در مبانی علوم کامپیوتر (FOCS) که از 31 اکتبر تا نوامبر برگزار می شود، انتخاب شد. 3 در دنور
نویسندگان همکار مقاله با عنوان «مزیت کوانتومی قابل تأیید بدون ساختاردکتر تاکاشی یاماکاوا، محقق برجسته در NTT SIL و دکتر مارک ژاندری، دانشمند ارشد در تحقیقات NTT آزمایشگاه CIS این کار تا حدی در دانشگاه پرینستون انجام شد، جایی که دکتر یاماکاوا یک محقق پژوهشی مدعو بود و دکتر ژاندری نیز به عنوان استادیار علوم کامپیوتر خدمت می کند.
موضوع مزیت کوانتومی (یا افزایش سرعت کوانتومی) به انواع مشکلاتی که رایانههای کوانتومی میتوانند سریعتر از رایانههای کلاسیک یا غیرکوانتومی حل کنند و اینکه چقدر سریعتر هستند، مربوط میشود. مسائل مورد بحث معمولاً به عنوان کلاس زمان چند جمله ای غیر قطعی (NP) توصیف می شوند. چقدر مزیت می تواند تا حد زیادی متفاوت باشد. یک کامپیوتر کوانتومی ممکن است بتواند یک مشکل خاص را در یک دقیقه یا یک ثانیه حل کند که یک کامپیوتر کلاسیک در هفته یا احتمالاً زمان نمایی غیرقابل تصوری را می طلبد. در این مقاله، نویسندگان به چالش تأیید این برتری، و انجام کارآمد آن می پردازند. تا به امروز، نشان دادن مزیت کوانتومی شامل "ساختار" یا ارتباطات رفت و برگشتی بین دو یا چند طرف بوده است. پیشرفت مقاله Yamakawa و Zhandry برای نشان دادن یک مشکل سخت NP است که در آن تأیید بدون ساختار امکان پذیر است.
دکتر اسکات آرونسون، پروفسور علوم کامپیوتر دانشگاه تگزاس در آستین، که در مورد یک نسخه اولیه اظهار نظر کرد، گفت: "این اولین باری است که ما یک سرعت کوانتومی نمایی برای یک مشکل جستجوی NP را می بینیم، که فقط به یک اوراکل تصادفی نیاز دارد." این مقاله طی کارگاهی در 13 ژوئن 2022 در موسسه تئوری محاسبات سیمونز. یاماکاوا و ژاندری تنها با نیاز به یک اوراکل تصادفی، یعنی یک جعبه سیاه نظری که پاسخهای تصادفی را به هر پرس و جو تولید میکند، مشکل خود را بر اساس مفروضات محاسباتی بدون ساختار ایجاد کردند. به این ترتیب، مشکل آنها بیشتر با توابع یک طرفه به جای توابع ساختاریافته، مانند آنهایی که در رمزنگاری کلید عمومی یافت می شود، هماهنگ می شود. آن تراز یک طرفه تأیید کارآمد را تسهیل می کند.
کازوهیرو گومی گفت: «دیدن رمزنگاران وابسته به NTT که در تحقیقاتی همکاری میکنند که یک بار دیگر شایستگی برچسب «دستیابی به موفقیت» را دارد، به ویژه در مقالهای که درک ما از محاسبات کوانتومی را غنیتر میکند، یکی دیگر از حوزههای تمرکز ما در NTT Research است، هیجانانگیز است. ، رئیس و مدیرعامل NTT Research. تبریک و آرزوی بهترین ها برای همه شرکت کنندگان در این کنفرانس معتبر IEEE.
مشکل جستجوی NP که یاماکاوا و ژاندری ابداع کردند، یک مشکل دو در یک بود که مستلزم یافتن 1) یک رشته n-نماد است که یک کلمه رمز از یک کد تصحیح خطای داده شده است، و 2) یک رشته n-نماد که در آن هر کدام نماد در زیر اوراکل تصادفی به صفر نگاشت می شود. هر مشکل به طور جداگانه آسان است. اما یافتن یک رشته از نمادها که هم رمز و هم نقشه صفر باشد، حداقل به صورت کلاسیک بسیار دشوارتر است. دکتر ژاندری گفت: "اگر کوانتومی هستید، می توانید این را در زمان چند جمله ای حل کنید، اما اگر کلاسیک هستید، حداقل اگر در این مدل جعبه سیاه هستید، به زمان نمایی نیاز دارید." از سوی دیگر، با توجه به یک راه حل بالقوه، تأیید آن با بررسی اینکه آیا به طور جداگانه هر یک از دو مشکل را حل می کند، ساده است. توجه داشته باشید که، همانطور که برای یک مقاله برای FOCS مناسب است، این کار پایه یا اساسی است. همانطور که در سخنرانی دکتر آرونسون در موسسه سیمونز اشاره شد (در این تحقیق NTT بحث شد مقاله وبلاگآرگومان Yamakawa-Zhandry در دستهای از افزایشها قرار میگیرد که میتوان آنها را به آسانی به صورت ریاضی بررسی کرد، اما به این زودی توسط یک کامپیوتر کوانتومی واقعی نشان داده نمیشود. با این حال، فراتر از طرح راستیآزمایی مسیرشکن، این مقاله به چیز جدیدی در مورد میزان سرعت کوانتومی نیز اشاره میکند.
«قبل از کارمان، نمونههایی از مزیت کوانتومی برای مسائل NP، مانند فاکتورگیری یا در تنظیمات جعبه سیاه، یافتن دوره داشتیم. اما معلوم شد که الگوریتم کوانتومی زیربنای همه این مثالها اساساً دورهیابی بوده است – اگرچه نشان دادن نحوه اعمال دورهیابی برای این نمونهها اغلب بیاهمیت بود.» دکتر ژاندری گفت. مقاله ما نشان می دهد که حداقل مورد دومی وجود دارد. شما میتوانید با خوشبینانه آن را به این صورت تعبیر کنید که امید وجود دارد که مزیت کوانتومی گستردهتر از آن چیزی باشد که قبلاً فکر میکردیم.»
با حمایت کمیته فنی انجمن کامپیوتر IEEE در مبانی ریاضی محاسبات (TCMF)، FOCS یک کنفرانس پیشرو در زمینه علوم کامپیوتر نظری است. فراخوان مقالات برای FOCS 2022، شصت و سومین گردهمایی سالانه، محاسبات کوانتومی را به عنوان یکی از 63 حوزه عمومی مورد علاقه ذکر کرد. مقاله Yamakawa-Zhandry قرار است در 17 اکتبر 31 در ساعت 2022:10 صبح به وقت MT ارائه شود. برای کسب اطلاعات بیشتر و ثبت نام در این رویداد به آدرس زیر مراجعه کنید FOCS 2022 وب سایت.