در سال 1994، یک ریاضیدان کشف کرد که چگونه یک کامپیوتر کوانتومی کاری انجام دهد که هیچ کامپیوتر کلاسیک معمولی قادر به انجام آن نیست. این کار نشان داد که، در اصل، یک ماشین مبتنی بر قوانین مکانیک کوانتومی می‌تواند به طور موثر تعداد زیادی را به فاکتورهای اصلی خود بشکند - این کار برای یک کامپیوتر کلاسیک آنقدر دشوار است که اساس امنیت اینترنت امروزی را تشکیل می‌دهد.
موجی از خوش بینی به دنبال داشت. شاید، محققان فکر می‌کردند، ما بتوانیم الگوریتم‌های کوانتومی را اختراع کنیم که بتواند طیف وسیعی از مسائل مختلف را حل کند.
اما پیشرفت متوقف شد. گفت: "این مسیر کمی بد بوده است." رایان اودانل از دانشگاه کارنگی ملون مردم می‌گفتند، این شگفت‌انگیز است، من مطمئن هستم که ما انواع الگوریتم‌های شگفت‌انگیز دیگر را به دست خواهیم آورد. جواب منفی." دانشمندان فقط برای یک دسته محدود از مشکلات از درون یک مجموعه استاندارد، سرعت های چشمگیر را کشف کردند NP نامیده می شود، به این معنی که آنها راه حل های قابل تأیید کارآمدی داشتند - مانند فاکتورینگ.
نزدیک به سه دهه همین بود. سپس در ماه آوریل، محققان اختراع یک نوع اساسی جدید از مسئله است که یک کامپیوتر کوانتومی باید قادر به حل آن به صورت تصاعدی سریعتر از یک کامپیوتر کلاسیک باشد. این شامل محاسبه ورودی های یک فرآیند پیچیده ریاضی است که صرفاً بر اساس خروجی های درهم ریخته آن است. این که آیا مشکل به تنهایی باقی می ماند یا اولین مشکل در مرزهای جدید بسیاری دیگر است، هنوز مشخص نشده است.
گفت: "احساس هیجان وجود دارد." وینود وایکونتاناتان، دانشمند کامپیوتر در موسسه فناوری ماساچوست. بسیاری از مردم به این فکر می کنند که چه چیز دیگری در آنجا وجود دارد.
دانشمندان کامپیوتر سعی می کنند با مطالعه مدل های ریاضی که آنها را نشان می دهند بفهمند که کامپیوترهای کوانتومی چه کاری را بهتر انجام می دهند. اغلب، آنها مدلی از یک کامپیوتر کوانتومی یا کلاسیک را با یک ماشین محاسبه ایده آل به نام اوراکل جفت می کنند. اوراکل ها مانند توابع ساده ریاضی یا برنامه های کامپیوتری هستند که یک ورودی را می گیرند و یک خروجی از پیش تعیین شده را بیرون می اندازند. آنها ممکن است رفتار تصادفی داشته باشند، اگر ورودی در محدوده تصادفی خاصی قرار گیرد (مثلاً 12 تا 67) "بله" و اگر اینطور نباشد "نه" را خروجی می دهند. یا ممکن است دوره ای باشند، به طوری که ورودی بین 1 تا 10 "بله" را برمی گرداند، 11 تا 20 "نه" را نشان می دهد، 21 تا 30 دوباره "بله" را تولید می کند و غیره.
فرض کنید شما یکی از این اوراکل های دوره ای را دارید و دوره را نمی دانید. تنها کاری که می توانید انجام دهید این است که اعداد آن را تغذیه کنید و ببینید چه خروجی هایی دارد. با این محدودیت ها، یک کامپیوتر با چه سرعتی می تواند دوره را پیدا کند؟ در سال 1993، دانیل سیمون، در آن زمان در دانشگاه مونترال، دریافت که یک الگوریتم کوانتومی می تواند پاسخ یک مسئله نزدیک به هم را به طور نمایی سریعتر از هر الگوریتم کلاسیک محاسبه کند.
نتیجه به سایمون امکان داد تا یکی از اولین نکاتی را که می توان انتظار برتری چشمگیر کامپیوترهای کوانتومی را داشت، تعیین کرد. اما زمانی که او مقاله خود را به یک کنفرانس پیشرو ارسال کرد، رد شد. با این حال، این مقاله یکی از اعضای جوان کمیته برنامه کنفرانس را مورد توجه قرار داد - پیتر شور، که در آن زمان در آزمایشگاه های بل در نیوجرسی بود. شور در ادامه متوجه شد که می‌تواند الگوریتم سایمون را برای محاسبه دوره یک اوراکل، در صورت وجود، تطبیق دهد. سپس متوجه شد که می‌تواند یک بار دیگر الگوریتم را تطبیق دهد تا معادله‌ای را حل کند که رفتاری مشابه یک اوراکل دوره‌ای دارد: معادله‌ای که فاکتورگیری را توصیف می‌کند، که دوره‌ای است.
نتیجه شور تاریخی بود. الگوریتم کوانتومی که او کشف کرد می‌تواند به سرعت اعداد غول‌پیکر را به عوامل اول تشکیل‌دهنده آنها تبدیل کند، کاری که هیچ الگوریتم کلاسیک شناخته‌شده‌ای نمی‌تواند انجام دهد. در سال های بعد، محققان الگوریتم های کوانتومی کارآمد دیگری را کشف کردند. برخی از آنها، مانند الگوریتم Shor، حتی مزیت نمایی را ارائه کردند، اما هیچ کس نتوانست یک مزیت کوانتومی چشمگیر را در هر مسئله NP که دوره ای نبود، اثبات کند.
این کمبود پیشرفت باعث شد تا دو دانشمند کامپیوتر، اسکات آرونسون از دانشگاه تگزاس، آستین، و آندریس آمباینیس از دانشگاه لتونی، برای انجام یک مشاهده. اثبات مزیت کوانتومی همیشه وابسته به اوراکل هایی به نظر می رسید که دارای نوعی ساختار غیرتصادفی مانند تناوب بودند. در سال 2009، آنها حدس زد که نمی‌توان سرعت‌های چشمگیری در مسائل NP که تصادفی یا بدون ساختار بودند، وجود داشت. هیچ کس نتوانست استثنا پیدا کند.
حدس آنها قدرت رایانه های کوانتومی را محدود می کند. اما فقط گفت که هیچ افزایش سرعت چشمگیری برای نوع خاصی از مشکلات NP بدون ساختار وجود ندارد - آنهایی که پاسخ‌های بله یا خیر دارند. اگر مشکلی شامل یافتن پاسخ‌های کمی و خاص‌تر باشد که به عنوان مشکل جستجو شناخته می‌شود، حدس اعمال نمی‌شود.
با توجه به این موضوع، محققان تاکاشی یاماکاوا از آزمایشگاه های انفورماتیک اجتماعی NTT و مارک ژاندری از تحقیقات NTT و دانشگاه پرینستون تصمیم گرفتند که یک مشکل جستجوی خاص را آزمایش کنند که در سال 2005 توسط اودد رگو.
مجموعه ای از پره های هواشناسی را تصور کنید که همگی در یک جهت هستند. به هر یک از آنها یک تکان دهید، سپس اجازه دهید یک باد تند بر جهت آنها تأثیر بگذارد. رگو می خواست بر اساس جهت گیری های نهایی خود مشخص کند که در ابتدا همه به کجا اشاره کردند. مشکلاتی مانند این «یادگیری با خطا» نامیده می‌شوند، زیرا ضربه و باد مانند یک منبع خطای تصادفی در جهت اصلی عمل می‌کنند. شواهدی وجود دارد که حل آن برای هر دو الگوریتم کلاسیک و کوانتومی دشوار است.
یاماکاوا و ژاندری تنظیمات را بهینه کردند. آنها قدرت ضربه های شروع کننده را تغییر دادند و آنها را قابل پیش بینی تر کردند. آنها همچنین باعث شدند که باد توسط یک اوراکل تصادفی تعیین شود به طوری که در موارد خاص تصادفی تر و در موارد دیگر کاملاً خاموش بود.
با این تغییرات، محققان کشف کردند که یک الگوریتم کوانتومی می تواند به طور موثر جهت اولیه را پیدا کند. آنها همچنین ثابت کردند که هر الگوریتم کلاسیک باید با یک عامل نمایی کندتر باشد. مانند Shor، آنها سپس الگوریتم خود را برای حل یک نسخه واقعی از مسئله، که اوراکل را با یک معادله ریاضی واقعی جایگزین می‌کند، تطبیق دادند.
دانشمندان کامپیوتر هنوز در حال کار برای درک و ایجاد مشکل هستند. Vaikuntanathan آن را با دیگری مقایسه می‌کند که هنگام فشرده‌سازی داده‌ها به وجود می‌آید: هنگامی که اطلاعات در حال فشرده شدن هستند، دو بیت می‌توانند به طور تصادفی در یک مکان فشرده شوند و آنها را بازنویسی کنند. مشکل پیش بینی این برخوردها از قبل، به طوری که بتوانید از آنها اجتناب کنید، شباهت هایی دارد. او گفت: «این یک دسته از مشکلات است که اساساً به این شکل است. "شاید بتوان این مشکلات را به صورت کوانتومی حل کرد."
این امید وجود داشت که مشکل ساختار نیافته ای مانند مشکل جدید حتی در نسخه های نوپای امروزی کامپیوترهای کوانتومی قابل حل باشد و بدین وسیله وسیله ای برای آزمایش آنها فراهم شود. تصور این بود که مشکلات بدون ساختار ممکن است منابع کمتری برای برنامه‌نویسی نیاز داشته باشند، یا حساسیت کمتری نسبت به نویز داشته باشند، زیرا از قبل تصادفی هستند. اما تا کنون، مشکل جدید هنوز برای کامپیوترهای کوانتومی موجود بسیار پیشرفته به نظر می رسد. «مشکل عجیبی است. آرونسون گفت: فکر نمی‌کردم آن را تعریف کنم. اما در نگاهی به گذشته، ویژگی‌های بسیار خوبی دارد.»
نتیجه اولین مثال از مزیت کوانتومی چشمگیر در یک مسئله NP بدون ساختار را ارائه می دهد. آیا ممکن است بسیاری از مسائل دیگر وجود داشته باشد که جهان کوانتومی از عملاً غیر قابل حل به حل شدنی تبدیل شود؟ اکنون دلایل بیشتری برای این فکر کردن وجود دارد.
اودانل می‌گوید: «این تا حدودی باورهای ما را در مورد انواع مشکلاتی که رایانه‌های کوانتومی می‌توانند در آنها خوب عمل کنند، زیر و رو کرده است».
