Останнім часом я бачив набагато більше галасу навколо квантових комп'ютерів на X, тому подумав, що зроблю довгий пост про них. Резюме: Я не вірю, що квантові обчислення з'являться найближчим часом. Я думаю, це тому, що за багато років не було досягнуто прогресу в найпростішій проблемі, для якої можуть бути використані квантові комп'ютери, а саме факторингу. Рекорд квантового факторингу знаходиться близько числа 15 (так, 15, 3 x 5!) вже десять років, і останнім часом очевидного прогресу не відбулося. Мої міркування наведені нижче. Я збираюся розкласти все по поличках для людей, які не дуже розбираються в математиці або інформатиці, але це все одно може налякати людей з математичними фобіями. Розкладання великих чисел на множники представляє інтерес тому, що кілька важливих криптографічних алгоритмів залежать від того, що для розкладання досить великого числа на його прості множники за допомогою звичайних комп'ютерів потрібно дуже багато часу. Ви можете розкласти невелике число (скажімо, 21) вручну дуже швидко, просто спробуйте розділити його на числа, що починаються з 2, потім 3 і так далі, і ви швидко знайдете, що 21 дорівнює 3 x 7. Однак це не працює для дійсно великих чисел, тому що простір всіх чисел, які вам потрібно спробувати, стає занадто великим. Якби ви могли розкладати числа на множники довжиною близько 1200 десяткових цифр (не число 1200, яке має чотири цифри, а числа з 1200 цифр!), ви могли б зламати багато криптографічних систем, які цікавлять людей, але ніхто не знає, як це зробити досить швидко на звичайному комп'ютері. (Досить швидко означає «до того, як згорять усі зірки на небі».) Кілька років тому Пітер Шор показав, що за допомогою квантових комп'ютерів можна (принаймні теоретично) дуже швидко розкладати числа на множники. Факторинг з використанням алгоритму Шора є, на мою думку, найочевиднішим еталоном для квантових обчислень, який важко підробити. У 2016 році число 15 (не 15-значне число, а число 15!) вперше було враховано (очевидно, у 3 x 5) у чистій, неперевіреній демонстрації алгоритму Шора. Це крихітна цифра, але це був початок. (Існують деякі суперечки про те, чи було число 21 також враховано в нефальсифікованій демонстрації алгоритму Шора, чи ні.) Але знову ж таки, 15 – це двозначне число. Ми хочемо врахувати числа в тисячах цифр, щоб мати можливість зламати криптографічні системи. Однак, починаючи з 2016 року, більші цифри не були враховані при чистих демонстраціях алгоритму Шора. (Деякі люди стверджували, що вони розкладали більші числа на множники за допомогою алгоритму Шора, але вони завжди використовували трюки, які вимагали, щоб вони вже знали фактори, щоб зробити це, і налаштувати квантовий комп'ютер з тим, що рівносильно попередньому знанню відповіді, що насправді не є суть. Я шукаю *нефальсифіковані* демонстрації.) Ми довго чекали, коли хтось продемонструє факторинг навіть трохи більшого числа, ніж 15. Можна було б сподіватися, що в цьому питанні може бути стабільний прогрес, коли хтось розкладе на множники (скажімо) число, наприклад, 77 (7 x 11), потім одне, наприклад, 323 (17 x 19), потім щось тисячі, і так далі. Однак ніхто не продемонстрував машину, яка може зробити щось краще, ніж число 15 (яке дитина може врахувати в голові на 3 і 5 в моменти), і цей рекорд стоїть дуже довго. Отже, принаймні щодо цієї базової проблеми, яку легко пояснити, у квантових обчисленнях не спостерігається стабільного прогресу. У нас було багато галасу, багато людей демонстрували квантові комп'ютери, які нібито використовують алгоритми, які не є такими очевидно чистими демонстраціями, але ми нічого не бачили за довгий час щодо факторингу. Я вірю, що відбувся реальний прогрес у квантових обчисленнях, коли ми почнемо бачити більші числа, враховані в чистих, несфальсифікованих демонстраціях алгоритму Шора. Я вважаю, що ми досягли справжнього прогресу, коли можемо робити чотиризначні числа після коми, тобто числа в тисячах. Навіть демонстрація чогось, що може зробити набагато більше двозначне число, ніж 15, буде вітатися. Однак жодна машина, яка може це зробити, насправді не знаходиться на найближчому горизонті. Тепер, щоб вміти розбивати коди, потрібні машини, які можуть обробляти числа з тисячами цифр, але ми ще не маємо в полі зору навіть тризначних чисел (або навіть більшості двозначних чисел). Отже, мій особистий орієнтир полягає в тому, що я бачу хоча б невеликий прогрес у цьому питанні. Передзвоніть мені, коли у нас з'являться квантові комп'ютери, які можуть успішно розкладати (скажімо) 323 на множники, в чистій, неперевіреній демонстрації алгоритму Шора, який оброблятиме будь-яке складене число подібного розміру. До того часу я не думаю, що це викликає великий інтерес, принаймні для мене.

(До речі, я не хочу створювати враження, що я вважаю квантові обчислення неможливими або щось подібне. Я просто кажу, що з моєї точки зору недавній прогрес не був очевидним, і ми все ще далекі від вирішення простих проблем, таких як розкладання чисел на множники з його допомогою.)

До речі, це також не означає, що такі компанії, як Google, дурні, проводячи чисті дослідження в галузі квантових обчислень. Я вважаю, що над цим варто працювати. Це просто не має якогось неминучого практичного застосування. Можливо, АНБ або інші подібні організації досягли більш значного прогресу в цій проблемі, ніж відкритий науковий світ, але очевидно, що це не та інформація, до якої я був би причетний. Нарешті, це не означає, що дослідження постквантових криптографічних алгоритмів є поганою ідеєю.

У своєму оригінальному пості зверху я уникнув згадки про те, наскільки серйозними є проблеми з масштабуванням. В основному я просто концентрувався на тому, що нічого з масштабування насправді не відбулося. І щоб бути впевненим, в якийсь момент дуже можливо, що речі для виправлення помилок почнуть з'являтися. Але масштабування до факторингу серйозних цифр не відбудеться наступного дня.

@defendtheworld Так чи інакше, знову ж таки: я почну вірити, коли побачу, що технологія переходить від факторингу 15. І так, це означає, що величезна кількість роботи вже буде виконана, але це також залишить величезний обсяг роботи, який ще належить виконати.