به قلم: سیدسجاد کاهانی
قسمتِ قبلی را میتوانید از اینجا ببینید
مقالاتِ مختلفِ تئوری [۲] و عملی [۶]، به خاطرِ تفاوتِ دیدگاهها، معمولاً تعاریف و شروطِ مختلفی را برای برتریِ کوانتومی میگویند، اما به طورِ کلی، میتوان این دوشرط را بیان کرد که البته هرکدام قابلِ بحث هستند
محاسباتی طراحی و انجام شود که:
اگر مسئلهای عضوِ 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 یک متغیرِ تصادفیست پس p=Prⁱᵈᵉᵃˡ(q|U) نیز یک متغیرِ تصادفیست که تابعِ چگالیِ احتمالِ آن به شکلِ زیر است (پانویس ۷)
با این دوفرض، میتوانیم به این معادله برسیم
و این یعنی با دانستنِ مقدارِ Prⁱᵈᵉᵃˡ(q|U) و با نمونهبرداری از آن، به ازای Uها و qهای مختلف (برای SUتا مقدار از U و هرکدام با Sq مقدار از q)، طبقِ قانونِ اعدادِ بزرگ، تخمینی از F را به دست میآوریم.
و همانطور که پیشتر پارامتر F را تعریف کردهایم، احتمالِ سلامتِ آزمایش است، که معیاری از کیفیتِ انجامِ آزمایش است.
اما حساب کردنِ Prⁱᵈᵉᵃˡ(q|U) مستلزمِ شبیهسازیِ کاملِ مدار در کامپیوترِ معمولیست. این یعنی تا جایی که امکانِ شبیهسازیِ مسئله در کامپیوتر وجود دارد، میتوانیم آن را ارزیابی کنیم.
ولی داستان به همینجا ختم نمیشود. گوگل، ابتدا از طریقِ بررسیِ خطاها، پیشبینیِ اولیهای از کیفیتِ نمونهبرداری در شرایط مختلف (تعدادِ کیوبیتها و تعداد مراحل شرایط مسئله هستند) به دست میآورد. سپس، چند نوع مدارِ تصادفیِ سادهشده نیز طراحی میکند و در نهایت نشان میدهد که کیفیتِ مدارهای سادهشده با مدارِ اصلی با پیشبینی برابر است. سپس، با افزایشِ تعدادِ مراحل (سختتر کردنِ مسئله) مدارهای سادهشده همچنان منطبق بر شبیهسازیها هستند اما ارزیابیِ کیفیتِ مدارِ اصلی دیگر غیرممکن است و این یعنی به برتریِ کوانتومی دست پیدا کردهایم. [۳]
پانویس ۶. این توزیع که در ابتدا از دادههای یک آزمایش مربوط به نوسانهای واکنشهای هستهای به دست آمدهاست [۱۱] و بعدها در مسئلههای مختلفِ آشوبِ کوانتومی موردِ توجه قرار گرفته، با توجه به آشوبناکِ بودنِ این مسئله و نتایجِ شبیهسازیها [۶] برای حالتِ ایدهآلِ این آزمایش (با تعدادِ مراحلِ کافی) معتبر میباشد.
پانویس ۷. اینکه f(p) برای p > 1 مقداری بزرگتر از صفر دارد و این شاید نادرست به نظر برسد، اما در شرایطی که 2ᴺ ≫ 1 [۳]، این مقدار بسیار ناچیز و تقریباً برابر با صفر است. البته که این صحبت دقیق نیست و تنها برای تقریبِ ذهن است.
![شکلِ برتریِ کوانتومی در گزارشِ گوگل [۳]](https://files.virgool.io/upload/users/12096/posts/vs0058dgad1w/rvg6hzka2mco.png)
برای این قسمت لازم است با مفهومِ تانسور، ضربِ تانسوری، ضربِ ماتریسی و روشهای نمونهبرداری آشنا باشید. دانستنِ مفهومِ ضربِ تانسوری تقریباً حیاتیست، پس یوتوب را باز کنید.
یکی از قسمتهای جذاب و قابلِ فهمِ مسئله این است که چه کدی توی کامپیوترهای معمولیمان بزنیم که همین مسئله را (در ابعادِ کوچک) شبیهسازی کند؟
برای یک شبیهسازیِ کاملاً واقعی، پنج کیوبیت را در نظر بگیرید، که حالتِ آنها تشکیلِ یک بردارِ مختلط در فضای 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))
حالا به سراغِ دستورالعملِ گوگل برای مدارِ تصادفی میرویم.
![شکل ۱: الگوی گوگل در ایجادِ مدارِ تصادفی [۳]](https://files.virgool.io/upload/users/12096/posts/vs0058dgad1w/epf2wxgfatk5.png)
الگوی هر مرحله، یکی از حروف 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.
