Дізнайтеся що таке алгоритм Шора, який доводить, що квантові обчислення є надзвичайно потужніші за класичні способи.
Кожен, хто зацікавлений у вивченні квантових обчислень, не міг не чути про алгоритм факторизації Шора. Це один з небагатьох хрестоматійних квантових алгоритмів, що означає, що він залишається одним з рідкісних прикладів квантової обчислювальної переваги.
Іншими словами, алгоритм може обчислити щось квантово, що важче і повільніше обчислюється класично. Фактично, цей конкретний алгоритм може обчислити те, що з усіх практичних міркувань і цілей, наскільки ми знаємо, неможливо зробити класично в будь-якому корисному масштабі.
Що таке алгоритм Шора?
Алгоритм факторизації Шора виділяється серед інших алгоритмів. Для цього є дві причини.
По-перше, він може факторизувати числа експоненціально швидше, ніж будь-який відомий класичний алгоритм.
Хоча всі хрестоматійні квантові алгоритми мають обчислювальні переваги, Алгоритм Шора є одним з небагатьох елітних алгоритмів з експоненціальним прискоренням, а також одним з небагатьох елітних алгоритмів, що мають практичне застосування.
Цікаві факти про фізику: від квантової механіки до чорних дір
Найважливіше те, що його потенціал факторизації чисел за розумні часові рамки безпосередньо загрожує найпопулярнішим криптосистемам у світі.
Значення цього неможливо переоцінити. Шифрування RSA, що захищає фінансові транзакції по всьому світу, працює шляхом перемноження двох величезних простих чисел.
Прості числа не можна розділити на цілі числа, окрім самих себе і числа один. Їхні добутки настільки великі, що не існує жодного відомого способу ефективно розкласти їх на множники класичним способом.
Подумайте про факторизацію як про зворотне множення, визначаючи використовувані прості числа, що дозволяє несанкціоновано розшифровувати інтернет-повідомлення.
У цій статті блогу алгоритм, що обговорюється, іноді згадується як алгоритм факторизації Шора, а не просто алгоритм Шора, оскільки існує також квантовий код корекції помилок, що носить ім’я Шора, з однойменною назвою, який було відкрито внаслідок публікації алгоритму факторизації. Для цієї статті, щоб уникнути двозначності, знайте, що алгоритм Шора і алгоритм факторингу Шора відносяться до одного і того ж алгоритму.
Що таке алгоритм Шора в квантових обчисленнях?
Алгоритм факторизації Шора виніс квантові обчислення на увагу громадскості. Його загрози змусили національні уряди, цілі галузі та широку громадськість звернути увагу на цю відносно нову технологію.
Десятиліття потому цей алгоритм залишається еталоном квантових алгоритмів. Протягом тривалого часу докладаються значні зусилля для захисту глобальних фінансових систем, національної безпеки та всіх інших сфер використання криптографії, якщо вже на те пішло.
Що таке квантова фізика – простими словами?
Існує очевидна геополітична небезпека того, що будь-хто, особливо державний суб’єкт, розвине достатню квантову обчислювальну потужність для використання алгоритму Шора до того, як квантово-безпечні криптосистеми зможуть бути повсюдно розгорнуті.
Майже так само важливо, що алгоритм Шора привів до сучасних інвестицій мільярдів доларів у квантові технології, включаючи квантові обчислення. Через три десятиліття після відкриття алгоритму триває пошук інших практичних застосувань, для яких можна реалізувати експоненціальне прискорення.
Якщо принаймні один алгоритм може досягти цього, то, на думку вчених, мають бути й інші. Після всіх цих років найбільш вірогідні кандидати черпають ідеї з алгоритму Шора.
Що таке квантові комп’ютери? Скоро вони будуть у вас?
Як працює алгоритм Шора?
Факторизація чисел за алгоритмом Шора починається з вибору випадкового цілого числа, меншого за число, яке потрібно факторизувати. Потім класично розрахований найбільший спільний дільник (НСД) цих двох чисел, випадкового і шуканого, використовується для визначення того, чи не було вже випадково враховано шукане число. Для менших чисел це можливо. Для більших чисел може знадобитися суперкомп’ютер. А для чисел, які вважаються криптографічно захищеними, знадобиться квантовий комп’ютер.
Роль квантового комп’ютера полягає в тому, щоб визначити період числа, яке потрібно факторизувати. Результати обчислень визначають, чи потрібно перевіряти нове випадкове ціле число, чи вже знайдено шукані фактори. Після того, як цільове число було враховано, роль алгоритму Шора завершується
На високому рівні весь цей процес може здатися досить простим. І на високому рівні так воно і є. Однак, якщо детально пояснювати кожен крок, то його можна розбити на серію лекцій. Реалізація алгоритму може бути виконана після завершення короткого підручника, але повне розуміння алгоритму може зайняти багато годин навчання.
Як реалізується алгоритм Шора?
Алгоритм Шора не є простим у реалізації. Перш за все, алгоритм складається з трьох основних компонентів: один використовує класичні обчислення, один використовує квантові обчислення і ще один використовує класичні обчислення. Загалом, алгоритм має шість важливих кроків, як описано вище.
Однак, додаючи до цієї складності, квантовий компонент алгоритму факторингу Шора має чотири підкомпоненти, кожен з яких сам по собі міг би мати цілу статтю для пояснення. І хоча два з цих квантових підкомпонентів відносно просто пояснити, інші два є неймовірно важливими квантовими підпрограмами. Насправді, це, мабуть, дві найбільш значущі квантові підпрограми.
Один з найважливіших квантових підкомпонентів називається квантовою оцінкою фази (QPE). Важливо те, що вона виконує модулярну арифметику, необхідну для знаходження періоду числа, яке потрібно розкласти на множники. Іншими словами, саме звідси походить факторингова потужність алгоритму Шора.
Інший ключовий квантовий підкомпонент називається оберненим квантовим перетворенням Фур’є (iQFT). Простіше кажучи, iQFT бере квантовий результат модулярної арифметики, що безпосередньо передує йому, і перетворює його на класичну інформацію, яку можна отримати з квантової схеми за допомогою процесу, відомого як вимірювання.
Загалом, алгоритм факторизації Шора починається з кількох класичних кроків. Потім квантовий компонент знаходить період числа, яке потрібно розкласти на множники. Це робиться за допомогою квантової модулярної арифметики, результат якої перетворюється з квантової інформації в класичну, щоб її можна було використовувати. І, нарешті, є ще кілька класичних кроків.
Якщо відповідь не знайдено, і число, відповідно, не можна розкласти на множники, алгоритм у повному обсязі коригується і повторюється.
Скільки кубітів потрібно для алгоритму Шора?
Щоб відповісти на це питання, необхідно розрізняти фізичні та логічні кубіти. Всі сучасні кубіти – це фізичні кубіти. Вони надзвичайно “зашумлені”, тобто схильні до помилок. Результати квантових обчислень будь-якої значущості не дозволяють відрізнити правильні відповіді від неправильних. Кожне можливе рішення має однакову ймовірність бути правильним, що рівнозначно відсутності відповідей взагалі.
Саме тут у гру вступають логічні кубіти. Фізичні кубіти повинні бути з’єднані і структуровані таким чином, щоб вони разом забезпечували достатню корекцію помилок один для одного, щоб вважатися “відмовостійкими” разом. У цей момент ці колективи кубітів стають відомими як “логічні кубіти”, або іноді як “досконалі кубіти”.
Ці логічні кубіти є абстракціями. Сьогодні квантова схема з п’ятьма кубітами представляє п’ять дуже шумних, схильних до помилок фізичних кубітів. Розробники квантових алгоритмів найближчого майбутнього захочуть, щоб ці п’ять кубітів представляли логічні, відмовостійкі, безпомилкові кубіти.
Оцінки щодо того, скільки фізичних кубітів знадобиться для представлення одного логічного кубіта, різняться, але розумним числом для роботи є 1000. Більшість вважає, що квантовому комп’ютеру знадобиться близько 1000 фізичних кубітів для представлення одного логічного кубіта.
Щоб оцінити, наскільки це складно, найбільший квантовий комп’ютер на сьогодні має лише 127 фізичних кубітів. І хоча IBM має на меті представити 1000-кубітний пристрій до наступного року, це все ще лише 1000 фізичних кубітів. До створення першого логічного кубіта залишається ще багато роботи.
Оцінки кількості кубітів, необхідних для алгоритму факторингу Шора, значно різняться. По-перше, як вже зазначалося, необхідно розрізняти оцінки для логічних кубітів і оцінки для фізичних кубітів.
Залежно від цілей дослідника, кількість необхідних кубітів можна зменшити, пожертвувавши часом виконання та глибиною схеми. З іншого боку, кількість кубітів можна значно збільшити, зменшивши час виконання та глибину схеми. Відмінності полягають у тому, що менша кількість кубітів стане доступною швидше, тоді як найшвидший час виконання буде найбільш вигідним. Нижче наведено декілька оцінок.
У статті Девіда Бекмана, Амалавояла Н. Чарі, Шрікрішни Девабхактуні та Джона Прескілла “Ефективні мережі для квантового факторингу” від 1 серпня 1996 року автори підрахували, що факторизація K-бітового числа займе K3 часу і потребуватиме 5K+1 логічних кубітів.
Таким чином, факторизація 2,048-бітового числа, що означає злам RSA-шифрування, займе 8,6 мільярдів часу і потребуватиме 10,241 логічних кубітів, або приблизно 10 мільйонів фізичних кубітів. На жаль, незрозуміло, скільки часу займе 8,6 мільярдів, оскільки різні технології роботи з кубітами працюють з різною швидкістю.
Потім у статті Стефана Борегара “Схема для алгоритму Шора з використанням 2n+3 кубітів” від 21 лютого 2003 року автори підрахували, що для факторизації K-бітового числа знадобиться 2n+3 логічних кубітів. Таким чином, для факторизації 2048-бітового числа знадобиться лише 4099 логічних кубітів, або приблизно 4 мільйони фізичних кубітів. Знову ж таки, сьогодні не існує нульових логічних кубітів. Однак ця стаття все ж наблизила алгоритм факторизації Шора до реалізації.
Потім у книзі Архімеда Павлідіса та Дімітріса Гізопулоса “Швидка архітектура квантового модулярного піднесення до степеня для алгоритму факторизації Шора” (pp0649-0682), опублікованій у травні 2014 року, автори запропонували реалізацію 9n+2, додавши значну кількість кубітів для зменшення глибини схеми. Для розкриття 2048-бітного RSA-шифрування потрібно 18 434 логічних кубітів або приблизно 18 мільйонів фізичних кубітів.
Однією з причин мінімізації глибини схеми є те, що з часом кубіти втрачають “зв’язність”. Чим довше виконується схема, що частково визначається глибиною схеми, тим більше шуму може просочитися в систему і тим більше помилок може з’явитися в результатах. Навіть сьогодні одним із способів зменшити кількість помилок є мінімізація глибини коду.
Зовсім недавно, 13 квітня 2021 року, в статті під назвою “Як за 8 годин обчислити 2048-бітне ціле число RSA, використовуючи 20 мільйонів зашумлених кубітів”, автори Крейг Гідні та Мартін Екер підрахували, що для злому RSA-шифрування потрібно приблизно 20 000 логічних кубітів, або приблизно 20 мільйонів фізичних кубітів. Автори йдуть ще далі і оцінюють час виконання для своєї конфігурації лише у вісім годин.
Порівняйте це з оцінкою часу, необхідного найпотужнішим у світі суперкомп’ютерам для зламу шифрування RSA, що значно перевищує час життя людини, і потужність алгоритму Шору стає зрозумілою. Для інших оцінок кількості кубітів для алгоритму Шора, зверніться до посилань на цю статтю.
Знову ж таки, час роботи алгоритму Шора обернено пропорційний кількості доступних логічних кубітів. Він також залежить від використовуваної кубітової технології, оскільки різні квантові комп’ютери виконують операції з дуже різною швидкістю. Чим менше кубітів потрібно, тим довше буде працювати алгоритм, але тим швидше сучасні криптосистеми стають застарілими. І навпаки, чим більше кубітів, тим швидше сучасні криптосистеми будуть зламані. Але, на щастя, ці дні ще далекі.
Як запустити алгоритм Шора?
Ніяк.
Найбільше число, яке на сьогоднішній день вдалося обчислити за допомогою алгоритму Шора – 21. А найменше можливе число, яке можна обчислити за допомогою алгоритму – 15. Це дуже вузький діапазон з двох причин. По-перше, алгоритм Шора вимагає великої кількості кубітів, як було сказано вище, а великої кількості кубітів не існує.
По-друге, сучасні кубіти є “зашумленими”, що означає, що вони надзвичайно схильні до помилок. Глибина схеми, необхідна алгоритму, дає результати з такою кількістю помилок, що неможливо відрізнити правильні рішення від неправильних.
Іншими словами, RSA та інші потенційно вразливі криптосистеми безпечні. Поки що. NIST продовжує працювати над вибором пост-квантового стандарту, інакше відомого як “квантово-безпечний” стандарт, який, як ми сподіваємося, буде широко впроваджений задовго до того, як з’явиться достатньо відмовостійких кубітів, щоб реалізувати цю загрозу.
Незважаючи на тривалий період часу і роботу, яка проводиться для зменшення ризику, алгоритм факторизації Шора залишається таким же хорошим способом підвищення обізнаності про квантові обчислення сьогодні, як і тоді, коли він був вперше відкритий.
Керівники в усіх галузях повинні турбуватися про потенційні ризики для конфіденційних комунікацій і даних, і цей ризик є справжнім. Сподіваємось, що в процесі вони дізнаються про десятки інших потенційних варіантів використання квантових обчислень, які колись можуть принести значну користь їхнім підприємствам.
Джерело: https://www.classiq.io
