برتریِ کوانتومی، قصهٔ مقالهٔ گوگل - قسمت دوم

به قلم: سیدسجاد کاهانی

قسمتِ قبلی را می‌توانید از این‌جا ببینید

برتریِ کوانتومی، یک برخوردِ‌ صادقانه و مهندسی

مقالاتِ مختلفِ تئوری [۲] و عملی [۶]، به خاطرِ تفاوتِ دیدگاه‌ها، معمولاً تعاریف و شروطِ مختلفی را برای برتریِ کوانتومی می‌گویند، اما به طورِ کلی، می‌توان این دوشرط را بیان کرد که البته هرکدام قابلِ بحث هستند

محاسباتی طراحی و انجام شود که:

• با یک کامپیوترِ کوانتومی قابلِ انجام باشد ولی با کامپیوترِ معمولی غیرِ قابلِ انجام باشد. (مثلاً زمانِ زیادی طول بکشد یا حافظهٔ زیادی لازم داشته‌باشد)
• جوابِ مسئله قابلِ ارزیابی باشد.

اگر مسئله‌ای عضوِ BQP باشد و در عینِ حال عضوِ NP باشد (و طبیعتاً عضوِ P نباشد)، به این معنی‌ست که مطمئنیم وقتی اندازهٔ مسئله از حدی بزرگ‌تر شود

کامپیوترهای کوانتومی آن را سریع‌تر حل می‌کنند و همچنین در زمانِ تقریباً کوتاهی می‌توانیم پاسخِ این مسئله را با یک کامپیوترِ معمولی ارزیابی کنیم.

پس احتمال می‌دهیم مسئله‌هایی از این دست نظیرِ «تجزیهٔ عدد به عواملِ اول» یکی از کاندیداهای خوب برای نمایشِ برتریِ کوانتومی باشند. اما در حقیقت، بیشترِ طرح‌هایی که برای نمایشِ برتریِ کوانتومی ارائه می‌شوند، روی مسئله‌های متفاوتی نظیرِ نمونه‌برداری از یک توزیع تمرکز دارند. چرا؟[۲]

• کامپیوترِ کوانتومیِ همه‌کارهٔ بدونِ نویزِ درست‌حسابی نداریم.
• فکر می‌کنیم که مسئلهٔ تولیدِ اعدادِ تصادفی خیلی‌خیلی سخت‌تر از یک تجزیهٔ عدد برای کامپیوترهای معمولی‌ست.
• البته که علایقِ فیزیک‌دانان در طرحِ این مسائل دخیل بوده‌است.

مسئلهٔ مدارِ تصادفی

یک مدارِ منطقیِ معمولی، یک تابعی‌ست که از ‭{0, 1}ᴺ‬ به ‭{0, 1}ᴹ‬ می‌رود. حالا یک مدارِ منطقیِ کوانتومی (که لزوماً برگشت‌پذیر هم هست) یک تبدیلِ خطیِ یکانی‌ست، در فضایی که پایه‌هایش ‭{0, 1}ᴺ‬، یعنی رشته‌های N-بیتی اند. به این فضا،‌ فضای N-کیوبیتی و به این مدار نیز مدارِ N-کیوبیتی یا گیت N-کیوبیتی می‌گوییم.

فرض کنید که حالتِ ⟨ψ₀| را به‌عنوانِ ورودی به مدارِ کوانتومیِ U داده‌ایم، سپس اندازه‌گیری‌ای کرده‌ایم که نتیجه‌ش یکی از اعدادِ 1 تا 2ᴺ مانندِ q است. احتمالِ هر خروجی را Prⁱᵈᵉᵃˡ(q|U) می‌نامیم.

همچنین در نظر بگیرید، برای ساختِ مدارِ U، مدارهای یک‌ورودی-یک‌خروجی و دوورودی-دوخروجی را به شکلِ تصادفی ترکیب کرده‌ایم. یعنی با ترکیب کردنِ تعدادی از مدارهای ساده و کوچک -که مشخص هستند-، با یک الگوی تصادفی، یک مدارِ تصادفیِ بزرگ ساخته‌ایم.

اگر به این مدارِ تصادفیِ U، ورودی‌ای بدهیم و خروجیِ آن را اندازه بگیریم، q عددی از توزیعی خاص خواهدبود. نمونه‌برداری از این توزیع، مسئلهٔ ماست.

شبیه‌سازیِ این فرایند و نمونه‌برداری از توزیعِ آن، توسطِ کامپیوترهای معمولی کارِ بسیار مشکلی خواهدبود. [۶] این به نظر می‌رسد که فوق‌العاده‌ است، اما باید به سؤالات پاسخ داد:

• از کجا مطمئنیم این کار برای یک کامپیوترِ معمولی به اندازهٔ کافی مشکل است. شاید فقط ما بلد نیستم.
• از کجا مطمئن شویم واقعاً کامپیوترِ کوانتومی‌مان درست کار می‌کند و نمونه‌ها واقعاً از توزیعِ مذکور هستند؟

در پاسخ به سؤالِ اول، باید صادقانه بگوییم که نمی‌دانیم. [۲] این بیشتر شبیهِ یک تحدی‌ست که ادعا می‌کنیم این محاسبات را هیچ‌کسی نمی‌تواند انجام دهد و باید منتظر بمانیم و شاید مردی از خویش برون آید و الگوریتمی نو دراندازد و کاری بکند.

پاسخ دادن به سؤالِ دوم اما چندان آسان نیست (بوی پیچاندن می‌آید)، پاسخ کوتاه این است که نمی‌توانیم مطمئن شویم [۱] و پاسخِ بلند خودش قصهٔ طولانی‌ای‌ست که در ادامه می‌گوییم.

و ارزیابی‌ش

برای این قسمت، لازم است که آمار و احتمال بلد باشید. تقریباً به اندازهٔ درسِ آمار و احتمال که به شکلِ مرسوم ارائه می‌شود.

اگر مدارِ تصادفیِ U که در قسمتِ قبل گفتیم، با احتمالِ F، با خطا عمل کند، آنگاه می‌توان این فرایند را به این صورت بیان کرد

که در Prᵉʳʳᵒʳ توزیعِ نتیجهٔ آزمایش درصورتِ بروزِ خطاست.

با دو فرضِ زیر می‌توان سنجه‌ای میزانِ خطا پیدا کرد.

• با توجه به این‌که این احتمالات ناشی از رخدادهای کوانتومی هستند خطاهایی که مدارهای مختلف رخ می‌دهند، در مجموعِ همهٔ مدارها، اریب نباشند و تقارنی نسبت به qها داشته‌باشند. یعنی به طورِ میانگین (برای همهٔ Uها) این توزیع، یکنواخت باشد. [۳]

• با توجه به شیوه‌ای که این مدارهای تصادفی را می‌سازیم، نتایجِ اندازه‌گیری از توزیعِ پورتر-توماس (پانویس ۶) تبعیت کند.

این توزیع بیان می‌کند که برای یک q دلخواه، U یک متغیرِ تصادفی‌ست پس p=Prⁱᵈᵉᵃˡ(q|U) نیز یک متغیرِ تصادفی‌ست که تابعِ چگالیِ احتمالِ آن به شکلِ زیر است (پانویس ۷)

با این دوفرض، می‌توانیم به این معادله برسیم

و این یعنی با دانستنِ مقدارِ Prⁱᵈᵉᵃˡ(q|U) و با نمونه‌برداری از آن، به ازای Uها و qهای مختلف (برای SUتا مقدار از U و هرکدام با Sq مقدار از q)، طبقِ قانونِ اعدادِ بزرگ، تخمینی از F را به دست می‌آوریم.

و همان‌طور که پیش‌تر پارامتر F را تعریف کرده‌ایم، احتمالِ سلامتِ آزمایش است، که معیاری از کیفیتِ انجامِ آزمایش است.

اما حساب کردنِ Prⁱᵈᵉᵃˡ(q|U) مستلزمِ شبیه‌سازیِ کاملِ مدار در کامپیوترِ معمولی‌ست. این یعنی تا جایی که امکانِ شبیه‌سازیِ مسئله در کامپیوتر وجود دارد، می‌توانیم آن را ارزیابی کنیم.

ولی داستان به همین‌جا ختم نمی‌شود. گوگل، ابتدا از طریقِ بررسیِ خطاها، پیش‌بینیِ اولیه‌ای از کیفیتِ نمونه‌برداری در شرایط مختلف (تعدادِ کیوبیت‌ها و تعداد مراحل شرایط مسئله هستند) به دست می‌آورد. سپس، چند نوع مدارِ تصادفیِ ساده‌شده نیز طراحی می‌کند و در نهایت نشان می‌دهد که کیفیتِ مدارهای ساده‌شده با مدارِ اصلی با پیش‌بینی‌ برابر است. سپس، با افزایشِ تعدادِ مراحل (سخت‌تر کردنِ مسئله) مدارهای ساده‌شده همچنان منطبق بر شبیه‌سازی‌‌ها هستند اما ارزیابیِ کیفیتِ مدارِ اصلی دیگر غیرممکن است و این یعنی به برتریِ کوانتومی دست پیدا کرده‌ایم. [۳]

پانویس ۶. این توزیع که در ابتدا از داده‌های یک آزمایش مربوط به نوسان‌های واکنش‌های هسته‌ای به دست آمده‌است [۱۱] و بعدها در مسئله‌های مختلفِ آشوبِ کوانتومی موردِ توجه قرار گرفته، با توجه به آشوبناکِ بودنِ این مسئله و نتایجِ شبیه‌سازی‌ها [۶] برای حالتِ ایده‌آلِ این آزمایش (با تعدادِ مراحلِ کافی) معتبر می‌باشد.

پانویس ۷. این‌که f(p) برای p > 1 مقداری بزرگ‌تر از صفر دارد و این شاید نادرست به نظر برسد، اما در شرایطی که 2ᴺ ≫ 1 [۳]، این مقدار بسیار ناچیز و تقریباً برابر با صفر است. البته که این صحبت دقیق نیست و تنها برای تقریبِ ذهن است.

کازینوی مونته‌کارلو

برای این قسمت لازم است با مفهومِ تانسور، ضربِ تانسوری، ضربِ ماتریسی و روش‌های نمونه‌برداری آشنا باشید. دانستنِ مفهومِ ضربِ تانسوری تقریباً حیاتی‌ست، پس یوتوب را باز کنید.

یکی از قسمت‌های جذاب و قابلِ فهمِ مسئله این است که چه کدی توی کامپیوترهای معمولی‌مان بزنیم که همین مسئله را (در ابعادِ کوچک) شبیه‌سازی کند؟

برای یک شبیه‌سازیِ کاملاً واقعی، پنج کیوبیت را در نظر بگیرید، که حالتِ آن‌ها تشکیلِ یک بردارِ مختلط در فضای 2⁵-بعدی (یا یک تانسورِ 2⨯2⨯2⨯2⨯2) می‌دهد. فرض کنید حالتِ اولیهٔ این پنج کیوبیت ⟨00000| باشد، یعنی مقدارِ آن بردار برابرِ ‭(1, 0, ... 0)‬ خواهد بود.

در ساختارِ تانسوری، اگر بخواهیم یک گیتِ تک‌کیوبیتی را (که یه ماتریس 2⨯2 است) روی کیوبیتِ سوم اعمال کنیم، باید یک ضربِ ماتریسی برروی بعدِ سومِ تانسورِ حالتمان انجام دهیم. این کدِ واقعیِ پایتون همین‌ کار را می‌کند.

import numpy

state_shape = (2, 2, 2, 2, 2)
state = np.reshape(np.array([1] + 31 * [0]), state_shape)

# a valid quantum state must have norm = 1
assert(np.linalg.norm(state) == 1.0)

gate = np.matrix([[0, 1j], [-1j, 0]])

# a valid quantum gate must be unitary (maintains norm)
assert(np.all(np.matmul(gate.H, gate) == np.identity(2)))

# apply gate on 3th qubit (2nd if we start from 0) 
np.tensordot(gate, state, axes=(1, 2))

حالا به سراغِ دستورالعملِ گوگل برای مدارِ تصادفی می‌رویم.

• به ازای هرکدام از کیوبیت‌ها، به شکلِ تصادفی یکی از سه گیتِ ‭√X, √Y, √W‬ (پانویس ۸) را انتخاب می‌کنیم و اعمال می‌کنیم. اگر در مرحلهٔ پیش یکی از این سه‌گیت را روی این گیت اثر داده‌ایم، از انتخاب‌هایمان حذفش می‌کنیم و از بینِ دو گیتِ باقی‌مانده یکی را برمی‌گزینیم.
• مطابقِ الگوی هرمرحله، برروی زوج کیوبیت‌های مشخص‌شده توسط الگو، گیتِ دوکیوبیتی‌ای را که fSim(π/2, π/6) نام دارد، اعمال می‌کنیم. این گیت نسبت به دوکیوبیت متقارن است. (پانویس ۹)

الگوی هر مرحله، یکی از حروف A تا H می‌تواند باشد که مشخص می‌کند که برروی کدام زوج کیوبیت‌ها این گیتِ دوکیوبیتی اثر کند (درج شده در جدول ۱). دنبالهٔ الگوی مرحله‌ها در این موردِ شبیه‌سازیِ ما عبارتِ تکرارشوندهٔ ABCDCDAB است.[۳]

مقدارِ ماتریسِ این گیت‌ها به این ترتیب است:

در مرحلهٔ آخر، تنها گیتِ یک‌کیوبیتی اعمال می‌کنیم و سپس به سراغِ اندازه‌گیری می‌رویم.

برای اندازه‌گیریِ این بردارِ حالت که به شکلِ 2⨯2⨯2⨯2⨯2 است، برای هرمؤلفهٔ آن که v باشد داریم ‭|v|²‬ احتمالِ رخدادِ رشته‌بیتِ مربوط به آن مؤلفه است. حالا کافی‌ست از این توزیع نمونه‌هایی را برداریم و پارامترِ F را که در قسمتِ قبل معرفی کردیم برای آن‌ها محاسبه کنیم.

و در نهایت، با کدِ زیر می‌خواهیم صد بار، با شش مرحله مدارهای تصادفی‌ای بسازیم و هربار با ده‌بار نمونه‌برداری از خروجی، پارامترِ F را تخمین بزنیم.

import numpy as np
from random import choice

n = 5
cycles = 6
state_shape = (2, 2, 2, 2, 2)

# define single-qubit gates
xsqrt = np.array([[1, -1j], [-1j, 1]]) / np.sqrt(2)
ysqrt = np.array([[1, -1], [1, 1]]) / np.sqrt(2)
wsqrt = np.array([[1, -np.sqrt(1j)], [np.sqrt(-1j), 1]]) / np.sqrt(2)

single_gates = [xsqrt, ysqrt, wsqrt]

# define double-qubit gates
double_gate = np.array([[1, 0, 0, 0], \
                        [0, 0, -1j, 0], \
                        [0, -1j, 0, 0], \
                        [0, 0, 0, np.exp(1j * np.pi/6)]])
double_gate = np.reshape(double_gate, (2, 2, 2, 2))

# double-qubit gate pattern (from shape) ABCDCDAB
pattern = [(1,2), (2,3), (0,2), (2,4), (0,2), (2,4), (1,2), (2,3)]

# sample from different 100 random circuits
samples_U = 100

# list of F values
fs = []
for _ in range(samples_U):
  last_applied_gate = [None] * n
  
  # define input state
  state = np.reshape(np.array([1] + 31 * [0]), state_shape)
  
  # iterate over cycles
  for c in range(cycles):
    # iterate over qubits to apply single gates 
    for i in range(n):
      # apply a random gate on ith qubit
      gate = choice([g for g in single_gates if np.all(g != last_applied_gate[i])])
      state = np.tensordot(gate, state, axes=(1, i))
    # apply double-qubit gate
    state = np.tensordot(double_gate, state, axes=((2,3), pattern[c % len(pattern)]))
  
  # last half cycle
  for i in range(n):
    gate = choice([g for g in single_gates if np.all(g != last_applied_gate[i])])
    state = np.tensordot(gate, state, axes=(1, i))
  
  # let's dice!
  ps = (abs(state)**2).flatten()
  # number of samples from output of this circuit
  samples_q = 10
  for _ in range(samples_q):
    fs.append(2**n * np.random.choice(ps, p=ps) - 1)

print('F = ', np.mean(fs), '±', np.std(fs) / np.sqrt(len(fs) - 1))

نتیجهٔ اجرای این کد، برای من این شد، انتظار داشتیم چند بشود؟

F = 0.98 ± 0.05

بعد از این اتفاق‌ها آی‌بی‌ام ادعا کرده که برتریِ کوانتومی رخ نداده و این محاسبات را می‌توان در طیِ دو روز با یک سوپرکامپیوتر انجام داد. [۱۰]

(امروز که این نوشته تمام شد سالگردِ مرتضی کیوان بود. کاشکی به جای این‌ها، فقط می‌نشستیم و یادی از او می‌کردیم)

برای دیدنِ کدها و فایل پی‌دی‌اف گزارش این‌جا را ببینید

پانویس ۸. مهم نیست این رادیکال‌ها و نامگذاری‌ها چه معنی‌ای می‌دهند و چه دلیلی دارند، ما می‌دانیم هر گیتِ تک‌کیوبیتی، یک ماتریسِ 2⨯2 است و تنها مقدارِ این ماتریس‌ها را بدانیم.

پانویس ۹. یک گیت دوکیوبیتی یک تبدیلِ خطی برروی فضای 2⨯2بعدی‌ست. به عبارتِ دیگر، یک ماتریسِ 4⨯4 است.

مراجع و منابع و مآخذ و غیره

[1] Scott Aaronson. Scott's Supreme Quantum Supremacy FAQ. url: https://www.scottaaronson.com/blog/?p=4317 (visited on 10/19/2019).

[2] Scott Aaronson and Lijie Chen. "Complexity-theoretic foundations of quantum supremacy experiments". In: Proceedings of the 32nd Computational Complexity Conference. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 2017, p. 22.

[3] Frank Arute et al. "Quantum supremacy using a programmable superconducting processor". In: Nature 574.7779 (2019), pp. 505-510.

[4] Charles H Bennett et al. "Strengths and weaknesses of quantum computing". In: SIAM Journal on Computing 26.5 (1997), pp. 1510-1523.

[5] Ethan Bernstein and Umesh Vazirani. "Quantum complexity theory". In: SIAM Journal on Computing 26.5 (1997), pp. 1411-1473.

[6] Sergio Boixo et al. "Characterizing quantum supremacy in near-term devices". In: Nature Physics 14.6 (2018), p. 595.

[7] David Deutsch. "Quantum theory, the Church-Turing principle and the universal quantum computer". In: Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400.1818 (1985), pp. 97-117.

[8] Oded Goldreich. "In a world of P= BPP". In: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer, 2011, pp. 191-232.

[9] Abstruse Goose. Schrödinger's Infinitesimal Miscalculation. url: https://abstrusegoose.com/6 (visited on 10/06/2019).

[10] Edwin Pednault et al. Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits. 2019. arXiv: 1910.09534 [quant-ph].

[11] Charles E Porter and Robert G Thomas. "Fluctuations of nuclear reaction widths". In: Physical Review 104.2 (1956), pp. 483–491.

[12] Erwin Schrödinger. "Die gegenwärtige Situation in der Quantenmechanik". In: Naturwissenschaften 23.49 (1935), pp. 823-828.