رایانش کوانتومی
پتانسیل

محاسبه فاکتورگیری عدد صحیح به وسیلهٔ یک رایانه معمولی برای اعداد صحیح بزرگ، در صورتی که این اعداد حاصل چند عدد اول هستند (بعنوان مثال حاصل ضرب ۲ عدد اول ۳۰۰ رقمی) غیرممکن است. در مقایسه، یک رایانه کوانتومی می‌تواند به صورت مؤثری مشکل پیدا کردن این عامل‌ها را با استفاده از الگوریتم Shore حل کند. این قابلیت رایانه کوانتومی را قادر می‌سازد بسیاری از سیستم‌های رمزنگاری امروزه را رمز گشایی کند، به این معنی که یک الگوریتم زمانی (در تعداد ارقام عدد صحیح) چند جمله‌ای برای حل مسئله وجود خواهد داشت. به ویژه مبنای بسیاری از رمزهای کلید عمومی متداول، مشکل بودن فاکتورگیری اعداد صحیح (یا مسائل الگوریتم مجزای مربوط که به سادگی با الگوریتم Shore قابل حل است) شامل حالتهای مختلف RSA می‌باشد. این روش‌ها برای ایمن کردن صفحات WEB، رمز کردن ایمیل و بسیاری انواع دیگر دیتا بکار می‌رود. شکستن این‌ها پیامدهای مهمی برای محرمانگی و امنیت الکترونیکی خواهد داشت.
با این حال بنظر نمی‌رسد سایر الگوریتم‌های رمزنگاری موجود با این الگوریتم‌ها شکسته شوند. برخی از الگوریتم‌های کلید عمومی بر مبنای مسائلی بجز فاکتورگیری اعداد صحیح و الگوریتم مجزا که الگوریتم Shore برای حل آن‌ها بکار می‌رود، مانند سیستم رمز McEliece مبتنی بر مسئله‌ای در تئوری کدینگ قابل حل باشند. سیستم‌های رمز Lattice نیز با رایانه‌های کوانتومی شکسته می‌شوند و یک الگوریتم زمانی چند جمله‌ای برای حل مسائل زیرگروه پنهان دو سطحی، که قابلیت شکستن بسیاری از رمزهای lattice را دارند، پیدا می‌کنند. ثابت شده که به‌کارگیری الگوریتم Grover برای شکستن الگوریتم متقارن (کلید مخفی) به روش حمله همه‌جانبه تقریباً نیاز به  2^{\frac {n}{2}} الگوریتم رمز زیرین دارد که در مقایسه با  2^{n} در حالت سنتی، به این معناست که طول کلید متقارن به صورت مؤثری نصف شده‌است. ۲۵۶–AES در برابر حمله‌ای که از الگوریتم Grover استفاده می‌کند همان میزان امنیت ۱۲۸-AES در برابر حملات همه‌جانبه سنتی دارد (ابعاد کلید را ببینید). رمزنگاری کوانتومی، برخی عملیات رمزنگاری کلید عمومی را به صورت بالقوه بهبود می‌بخشد. علاوه بر فاکتورگیری و الگوریتم‌های مجزا، الگوریتم‌های کوانتومی یک چند جمله‌ای سرعت بخش برای معروف‌ترین الگوریتم سنتی که برای بسیاری مسائل پیداشده، شامل شبیه‌سازی فرایندهای فیزیک کوانتومی در شیمی و فیزیک حالت جامد، تخمین چندجمله‌ای Jones و حل معادله Pell ارائه می‌کند.
هیچ استدلال ریاضی که نشان دهد الگوریتم سنتی سریع معادلی را نتوان یافت، پیدا نشده و بعید هم به نظر می‌رسد. برای برخی مسائل، رایانه‌های کوانتومی یک چند جمله‌ای سرعت بخش ارائه می‌کنند. معروف‌ترین نمونه آن، جستجوی پایگاه داده کوانتومی است که با استفاده از الگوریتم Grover با پرسش‌های کمتر از پایگاه داده نسبت به روش سنتی حل می‌شود. این مزیت قابل اثبات است. نمونه‌های متعددی از سرعت بخشی کوانتومی برای مسائل مربوط به کوئری‌ها مانند یافتن توابع دو- به- یک و برآورد NAND trees اثبات شده‌است.
مسئله‌ای را با ۴ خصوصیت در نظر بگیرید:
تنها راه برای حل مسئله حدس زدن مکرر و امتحان زدن آنهاست.
تعداد پاسخهای احتمالی برای امتحان کردن مساوی تعداد ورودی هاست.
همه پاسخ‌های احتمالی یک زمان را برای امتحان کردن نیاز دارند.
هیچ نشانه‌ای دربارهٔ اینکه کدام پاسخ بهتر است وجود ندارد؛ مقادیر به صورت اتفاقی تولید و به ترتیب خاصی امتحان می‌شوند.
مثالی از آن رمز عبوریاب است که تلاش می‌کند تا رمز عبور را برای یک فایل رمز شده حدس بزند (با در نظر گرفتن حداکثر طول ممکن برای رمز عبور).
برای مسائلی با ۴ خصوصیت فوق، زمان حل این مسئله برای رایانه کوانتومی، متناسب با جذر تعداد ورودی‌ها است. این سرعت را بسیار زیاد خواهد کرد و برخی مسائل را از سال‌ها به ثانیه‌ها خواهد رساند. از این رایانه‌های کوانتومی برای حمله به رمزهای متقارن مانند DES سه‌گانه و AES از طریق حدس زدن کلید مخفی استفاده می‌شود.
الگوریتم Grover همچنین برای سرعت بخشی درجه دوم در جستجوهای همه‌جانبه پاره‌ای از مسائل مانند NP-complete بکار می‌رود.
از آنجا که علوم شیمی و نانوتکنولوژی متکی بر درک سیستم‌های کوانتومی می‌باشند و این سیستم‌ها به روش سنتی قابل شبیه‌سازی نیستند، بسیاری بر این اعتقادند که شبیه‌سازی کوانتومی یکی از مهم‌ترین کاربردهای محاسبات کوانتومی است.
چالش‌های فنی بسیاری در ایجاد یک رایانه کوانتومی در ابعاد بزرگ وجود دارد؛ بنابراین انتظار می‌رود این رایانه‌ها مسائل را بسیار سریع‌تر حل کنند. David DiVincenzo از شرکت IBM، الزامات زیر را برای یک رایانه کوانتومی ذکر کرده‌است:
به لحاظ فیزیکی تعداد بیتهای کوانتومی قابل افزایش باشند؛
به بیتهای کوانتومی بتوان مقادیر دلخواه داد؛
Quantum gateها سریعتر از زمان ناهمدوسی باشند؛
Gate عمومی ایجاد کرد؛
بیتهای کوانتومی را بتوان به راحتی خواند.