بررسی پیچیدگی محاسباتی مسائل فیزیک کوانتومی

۱. مقدمه

از زمان ارائه الگوریتم شور در سال ۱۹۹۴ برای تجزیه اعداد صحیح به عوامل اول، که پیامدهای عمیقی برای رمزنگاری کلید عمومی به همراه داشت، حوزه پیچیدگی محاسباتی کوانتومی به یکی از فعال‌ترین شاخه‌های علوم رایانه و فیزیک نظری تبدیل شده است. پرسش بنیادی این حوزه آن است که رایانه‌های کوانتومی چه مسائلی را می‌توانند به‌طور کارآمدتر از رایانه‌های کلاسیک حل کنند، و محدودیت‌های ذاتی محاسبات کوانتومی کدامند.

نظریه پیچیدگی محاسباتی کوانتومی، به‌عنوان زیرشاخه‌ای از نظریه پیچیدگی محاسباتی، به مطالعه کلاس‌های پیچیدگی تعریف‌شده بر پایه رایانه‌های کوانتومی و روابط میان آن‌ها با کلاس‌های کلاسیک می‌پردازد. دو کلاس پیچیدگی محوری در این حوزه، BQP و QMA هستند که به‌ترتیب آنالوگ کوانتومی کلاس‌های P و NP به‌شمار می‌آیند.

این مقاله به بررسی جامع پیچیدگی محاسباتی مسائل فیزیک کوانتومی می‌پردازد. ابتدا چارچوب نظری کلاس‌های پیچیدگی کوانتومی معرفی می‌شود، سپس مسئله هامیلتونی موضعی به‌عنوان یک مسئله QMA-کامل تحلیل می‌گردد. در ادامه، پیچیدگی پرس‌وجوی کوانتومی و شبیه‌سازی سیستم‌های کوانتومی بررسی شده و در نهایت، آخرین تحولات در زمینه برتری کوانتومی و چالش‌های موجود مورد بحث قرار می‌گیرد.

۲. کلاس‌های پیچیدگی کوانتومی

۲.۱. مروری بر کلاس‌های پیچیدگی کلاسیک

پیش از ورود به کلاس‌های کوانتومی، لازم است مفاهیم پایه کلاس‌های کلاسیک مرور شوند. کلاس P شامل مسائلی است که در زمان چندجمله‌ای بر روی یک ماشین تورینگ قطعی حل می‌شوند. کلاس NP مسائلی را در بر می‌گیرد که برای نمونه‌های «بله»، یک گواهی وجود دارد که صحت آن در زمان چندجمله‌ای قابل بررسی است. کلاس BPP نسخه احتمالاتی کلاس P است که در آن الگوریتم‌های تصادفی با احتمال خطای کراندار مجاز هستند.

۲.۲. کلاس BQP

کلاس BQP (زمان چندجمله‌ای کوانتومی با خطای کراندار) شامل مسائلی است که یک رایانه کوانتومی می‌تواند آن‌ها را با احتمال خطای کمتر از یک ثابت مشخص، در زمان چندجمله‌ای حل کند. از آنجا که یک مدار کوانتومی قادر به شبیه‌سازی مدار کلاسیک است، هر دو کلاس P و BPP زیرمجموعه BQP محسوب می‌شوند.

الگوریتم شور برای تجزیه اعداد صحیح، مشهورترین نمونه مسئله‌ای در BQP است که عضویت آن در P دانسته نشده است. این الگوریتم زمان حل مسئله را از مرتبه نمایی به مرتبه چندجمله‌ای کاهش می‌دهد، هرچند این سرعت‌بخشی با افزایش نیاز حافظه از O(1) به O(2²ⁿ) همراه است.

۲.۳. کلاس QMA و گونه‌های آن

کلاس QMA (مرلین و آرتور کوانتومی) تعمیم کوانتومی کلاس NP است. در این کلاس، برای نمونه‌های «بله»، یک گواهی کوانتومی (حالت کوانتومی) وجود دارد که یک رایانه کوانتومی می‌تواند آن را به‌طور کارآمد بررسی کند، و برای نمونه‌های «نه»، هیچ گواهی معتبری وجود ندارد. مسائل متعلق به QMA انتظار نمی‌رود حتی با رایانه کوانتومی به‌طور کارآمد حل شوند، مگر آنکه BQP = QMA باشد.

دو دهه پس از نخستین تعاریف «NP کوانتومی»، نظریه‌پردازان با واقعیتی مواجه‌اند که حاکی از وجود گونه‌های متعدد این کلاس است: QMA، QCMA، QMA₁، QMA(2)، StoqMA و NQP. کلاس QMA(2)، که در آن دو اثبات‌کننده کوانتومی غیردرهم‌تنیده حضور دارند، موقعیتی محوری اما کم‌فهم‌تر در نظریه پیچیدگی کوانتومی اشغال می‌کند.

۳. مسئله هامیلتونی موضعی: مسئله کامل QMA

۳.۱. تعریف صوری

مسئله هامیلتونی k-موضعی (که با k-LH نشان داده می‌شود) یک مسئله تصمیم‌گیری است که ورودی آن مجموعه‌ای از ماتریس‌های هرمیتی مثبت نیم‌معین با نرم کراندار است که هر یک حداکثر بر k کیوبیت عمل می‌کنند. هدف، تعیین این است که آیا کمینه مقدار ویژه هامیلتونی کل H = Σ H_i از یک آستانه مشخص کمتر است یا خیر.

این مسئله از نظر مفهومی مشابه مسئله MAX-k-SAT در نظریه NP-کاملی است؛ همان‌گونه که MAX-k-SAT برای k ≥ 2 یک مسئله NP-کامل است، مسئله k-LH نیز برای مقادیر مشابه k یک مسئله QMA-کامل به شمار می‌آید.

۳.۲. سیر تاریخی نتایج QMA-کاملی

قضیه اصلی کیتایف نشان می‌دهد که مسئله هامیلتونی ۵-موضعی QMA-کامل است. پس از آن، نتایج تدریجی‌تری به دست آمد:

• مسئله هامیلتونی ۳-موضعی QMA-کامل است.
• مسئله هامیلتونی ۲-موضعی نیز QMA-کامل است؛ نتیجه‌ای که از این نظر بهینه محسوب می‌شود که هامیلتونی ۱-موضعی به‌وضوح در کلاس P قرار دارد.
• مسئله هامیلتونی ۲-موضعی با برهم‌کنش‌های همسایه نزدیک روی شبکه مربعی دو‌بعدی نیز QMA-کامل است.

۳.۳. ساختار اثبات QMA-کاملی

اثبات عضویت مسئله هامیلتونی موضعی در کلاس QMA نسبتاً ساده است: گواهی، حالت پایه هامیلتونی است که انرژی آن با دقت چندجمله‌ای توسط الگوریتم تخمین فاز قابل محاسبه است. بخش دشوار اثبات، نشان دادن این است که هر مسئله در QMA را می‌توان به یک نمونه از هامیلتونی موضعی کاهش داد. هامیلتونی کدگذاری‌شده به شکل زیر است:

که در آن H_out خروجی مدار را جریمه می‌کند، H_in ورودی‌های نامعتبر را جریمه می‌کند، H_prop درستی انتشار زمانی را تضمین می‌کند و H_clock ترتیب زمانی صحیح گیت‌ها را حفظ می‌کند.

۴. پیچیدگی پرس‌وجوی کوانتومی

۴.۱. مدل پرس‌وجو

پیچیدگی پرس‌وجو یک مدل بنیادی برای تحلیل توان محاسباتی الگوریتم‌های کوانتومی است که تعداد پرس‌وجوهای لازم برای دسترسی به داده‌های ورودی را به‌عنوان معیار سنجش پیچیدگی در نظر می‌گیرد. در این چارچوب، الگوریتم‌های بنیادینی نظیر الگوریتم‌های دویچ-جوزا، جست‌وجوی گروور و سایمون به‌عنوان معیارهای سنجش توان محاسباتی کوانتومی مورد استفاده قرار می‌گیرند.

# جستجوی گروور برای یافتن یک عنصر متمایز در میان N عنصر
def grover_search(N, oracle):
    n = ceil(log2(N))
    state = uniform_superposition(n)   # |s⟩ = H^⊗n |0⟩
    iterations = floor(pi / 4 * sqrt(N))

    for _ in range(iterations):
        state = oracle(state)              # U_ω: علامت‌گذاری جواب
        state = diffusion(state)           # U_s: بازتاب حول میانگین

    return measure(state)                # اندازه‌گیری → جواب با احتمال بالا

۴.۲. روش‌های اثبات کران پایین

چهار روش اصلی برای اثبات کران‌های پایین در پیچیدگی پرس‌وجوی کوانتومی وجود دارد:

1. روش ترکیبی (Hybrid Method): با ترکیب محاسبات کلاسیک و کوانتومی، کران‌های پایین را اثبات می‌کند و دشواری مسئله را حتی با کمک کوانتومی نشان می‌دهد.
2. روش چندجمله‌ای (Polynomial Method): از تقریب‌های چندجمله‌ای توابع استفاده می‌کند و پیچیدگی مسئله را به درجه چندجمله‌ای موردنیاز مرتبط می‌سازد.
3. روش ثبت (Recording Method): اطلاعات به‌دست‌آمده از هر پرس‌وجو را دقیقاً ردیابی می‌کند تا حداقل تعداد پرس‌وجوهای لازم را تعیین کند.
4. روش حریف (Adversary Method): با ساختن «حریفانی» فرضی که اطلاعات آشکارشده توسط هر پرس‌وجو را کمینه می‌کنند، حداقل تعداد سؤالات لازم را به‌طور دقیق تعیین می‌کند.

۵. پیچیدگی شبیه‌سازی سیستم‌های کوانتومی

۵.۱. چالش شبیه‌سازی کلاسیک

رایانه‌های کلاسیک با چالش‌های قابل‌توجهی در شبیه‌سازی دینامیک کوانتومی مواجه هستند، به‌ویژه در پیش‌بینی تحول حالت‌های کوانتومی به‌شدت درهم‌تنیده. دلیل اصلی این دشواری، رشد نمایی فضای حالت کوانتومی است. برای یک سیستم با N کیوبیت، فضای هیلبرت دارای 2^N بُعد است. به‌عنوان مثال، یک رایانه کلاسیک برای توصیف حالت یک سیستم ۴۰-کیوبیتی به ذخیره‌سازی 2⁴⁰ عدد نیاز دارد که بیش از ۱۳۰ گیگابایت حافظه را می‌طلبد.

۵.۲. الگوریتم واریاسیونی کوانتومی (VQE)

یکی از رویکردهای امیدبخش برای شبیه‌سازی سیستم‌های کوانتومی روی رایانه‌های کوانتومی نزدیک‌مدت، الگوریتم واریاسیونی کوانتومی ویژه‌مقدار (VQE) است که با بهینه‌سازی کلاسیک پارامترهای یک مدار کوانتومی پارامتری، انرژی حالت پایه را تقریب می‌زند:

def vqe(hamiltonian, ansatz, optimizer, initial_params):
    """تقریب انرژی حالت پایه با الگوریتم واریاسیونی کوانتومی"""
    params = initial_params

    def cost(p):
        # اجرای مدار پارامتری روی سخت‌افزار کوانتومی
        circuit = ansatz(p)
        state = run_quantum_circuit(circuit)
        # محاسبه امید ریاضی: ⟨ψ(p)|H|ψ(p)⟩
        return expectation_value(state, hamiltonian)

    while not converged:
        params = optimizer.step(cost, params)

    return cost(params), params

۵.۳. معیارهای «کوانتومیت» و شبیه‌پذیری کلاسیک

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

۶. برتری کوانتومی: وعده‌ها و چالش‌ها

۶.۱. تعریف برتری کوانتومی

هدف اصلی کاوش در محاسبات کوانتومی دستیابی به سرعت‌بخشی یا برتری کوانتومی است که توانایی حل مسائل را در محاسبات علمی افزایش می‌دهد. مفهوم «برتری کوانتومی نمایی» (EQA) نشان می‌دهد که هزینه کلاسیک حداقل به‌صورت نمایی در n افزایش می‌یابد، در حالی که هزینه کوانتومی فقط به‌صورت چندجمله‌ای رشد می‌کند.

۶.۲. چارچوب صوری برتری کوانتومی

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

۶.۳. آزمایش‌های برتری کوانتومی

در سال ۲۰۱۹، گوگل ادعای نخستین نمایش برتری کوانتومی را مطرح کرد. پردازنده سایکامور آن‌ها یک وظیفه محاسباتی را در حدود چند دقیقه انجام داد که به تخمین گوگل، انجام آن روی قدرتمندترین رایانه کلاسیک جهان حدود ۱۰٫۰۰۰ سال طول می‌کشید. برای یک نمایش قانع‌کننده برتری کوانتومی، وظیفه موردنظر باید سه معیار را برآورده کند: (i) حل کارآمد در یک آزمایش کوانتومی نزدیک‌مدت؛ (ii) دشواری کلاسیک اثبات‌شده؛ (iii) قابلیت تأیید کارآمد با رایانه کلاسیک.

۷. نتیجه‌گیری

نظریه پیچیدگی محاسباتی کوانتومی چارچوبی نظری برای درک مرزهای توان محاسباتی رایانه‌های کوانتومی فراهم می‌کند. کلاس‌های BQP و QMA به‌عنوان آنالوگ‌های کوانتومی کلاس‌های P و NP، تصویر دقیقی از آنچه رایانه‌های کوانتومی می‌توانند و نمی‌توانند انجام دهند، ارائه می‌دهند.

مهم‌ترین نتیجه این حوزه، QMA-کامل بودن مسئله هامیلتونی موضعی است که نشان می‌دهد حل دقیق مسائل عمومی فیزیک کوانتومی، نظیر یافتن انرژی حالت پایه سیستم‌های چندجسمی، حتی با رایانه‌های کوانتومی کامل نیز در حالت کلی غیرقابل حل کارآمد است.

با این حال، رایانه‌های کوانتومی در مسائل خاصی نظیر تجزیه اعداد صحیح، جست‌وجوی بدون ساختار و شبیه‌سازی سیستم‌های فیزیکی خاص، برتری قابل‌توجهی نسبت به رایانه‌های کلاسیک دارند. چالش‌های پیش‌رو شامل اثبات جدایی نمایی بین کلاس‌های BQP و BPP، تعیین روابط دقیق بین QMA و سایر کلاس‌های کوانتومی، و توسعه روش‌های تأییدپذیر برای آزمایش‌های برتری کوانتومی است.