کامپیوتر‌های کوانتومی

تو پست قبلی در مورد ماهیت یک سری مفهوم تو نظریه محاسبه نوشتم و تو این پست قراره در مورد کوانتوم و ماهیتش بنویسم.

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

محاسبات کوانتومی پایه‌اش qubit هست. الکترون‌ها تو اتم بیشتر حالت ابری دارن و تا وقتی که مستقیم observe نشن جای ثابتی ندارن و میشه احتمالاتی نگاهشون کرد. مثلا در اتمی که دو مدار داره الکترون میتونه به احتمال 0.3(یا هر عدد دیگه‌ای!) روی مدار اول و به احتمال 0.7 روی مدار دوم باشه. برای نمایش این احتمال مفهومی به اسم کت تعریف میشه، کت صفر یا |0> و کت یک یا |1> که نمایشی به فرم زیر در نظر گرفته میشه براشون a |0> + b |1> که a و b اعداد موهومی هستند که مجموع نرم دومشان ۱ می‌شود. به هر کدوم از این الکترون‌ها یک کیوبیت گفته می‌شود.

مدار‌های کوانتومی غالبا به این شیوه کار می‌کنند: یک مدار عادی ۰ یا ۱ تبدیل میشه به حالت کوانتومی (مدار ۱ با احتمال ۱۰۰% روی کت ۱ و مدار ۰ با احتمال ۱۰۰% روی کت ۰) و سپس از تعدادی گیت کوانتومی رد میشن. در نهایت باز به فرم کلاسیک تبدیل میشن تا خروجیشون قابل استفاده بشه.

ویژگی‌های جالبی تو حالت کوانتومی هست، مثلا شما نمی‌تونید یک جریان رو clone کنید. همچنین تمام گیت‌ها برگشت پذیر هستند. شاید از همه مهم‌تر این باشه که اگر observe کنید حالت داده رو- یعنی ببینید چه حالتی داره، داده collapse میشه و دیگه به حالت قبل بر نمی‌گرده.

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

• ماشین‌های کوانتومی داده‌هایشان می‌تواند در چند حالت متفاوت باشد، آن هم به صورت محدود
• ‏ماشین‌های نامعین وضعیتشان می‌تواند در چند حالت متفاوت باشد.

برای مثال تو ماشین کوانتومی همزمان میشه ۱۰ تا عدد رو تقسیم بر ۲ کرد ولی تو ماشین نامعین روی ۵ تاشون تقسیم بر ۲ میشه انجام داد و روی ۵ تای دیگه جمع با ۳ انجام بشه. اینجا کلاس محاسباتی جدیدی تعریف میشه به نام کلاس BQP، کلاس ماشین‌های خطی کوانتومی با خطای محدود. همونطوری که از اسمشون پیداست این ماشین‌ها با استفاده از قابلیت‌های کوانتومی و در زمان خطی کار می‌کنند و خطایشان ناچیز است. خطای ناچیز یعنی هر خطایی کمتر از ۱/۲. به عنوان مثال با استفاده از الگوریتم شور، مسئله تجزیه به اعداد اول عضو BQP میشه. تا الان میدونیم که P زیرمجموعه BQP و BQP خودش زیرمجموعه NP است ولی برابری یا نابرابری ان‌ها هنوز اثبات نشده.

اگه بخوایم بررسی کنیم، میشه به طور کلی گفت ماشین کوانتومی با n کیوبیت می‌تواند دو به توان n مقدار را با یک عملیات محاسبه کند(این ادعا دقیق نیست ولی از واقعیت دور نیست) و بنابراین با ماشین کوانتومی به اندازه کافی قوی رمز‌های کلاسیک مبتنی بر تجزیه رو به راحتی میشه شکست اما هنوز جای زیادی برای رمز‌هایی که اثبات شده متعلق به گروه NP-Complete هستن وجود داره.