Вимірювання обчислювальної вартості

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

Як відправна точка, розглянь наступний рисунок із попереднього уроку, який представляє дуже високорівневу абстракцію обчислення.

Саме обчислення можна моделювати або описувати різними способами: програмою на Python, машиною Тюрінга, булевою схемою або квантовою схемою. Ми зосередимось на схемах (як булевих, так і квантових).

Кодування та довжина вхідних даних

Почнімо з вхідних і вихідних даних обчислювальної задачі, які ми вважатимемо бінарними рядками. Можна використовувати різні символи, але для простоти ми обмежимося бінарними рядками на вході та виході. За допомогою бінарних рядків можна кодувати різноманітні об'єкти, що стосуються задач, які нас цікавлять: числа, вектори, матриці, графи, а також списки цих та інших об'єктів.

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

Число	Двійкове кодування	Довжина
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

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

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

Число	Унарне кодування	Лексикографічне кодування
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(У цій таблиці символ $\varepsilon$ позначає порожній рядок, що не містить жодного символу і має довжину, рівну нулю. Природно, щоб уникнути очевидної плутанини, ми використовуємо спеціальний символ $\varepsilon$ для позначення порожнього рядка, а не буквально нічого не пишемо.)

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

Наприклад, кількість бітів, необхідних для запису невід'ємного цілого числа $N$ у двійковому записі, що іноді позначається $\operatorname{lg}(N),$ визначається за такою формулою.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

Якщо ми використовуємо двійковий запис для кодування вхідних даних задачі цілочисельного факторизації, то довжина вхідних даних для числа $N$ дорівнює $\operatorname{lg}(N).$ Зауваж зокрема, що довжина (або розмір) вхідних даних $N$ — це не саме $N$; для великих $N$ двійковий запис займає значно менше бітів, ніж $N$.

З формально суворої точки зору, щоразу, коли ми розглядаємо обчислювальну задачу або завдання, слід мати на увазі, що обрано конкретну схему кодування для об'єктів, що подаються на вхід або виводяться на виході. Це дозволяє розглядати обчислення, що розв'язують цікаві задачі, абстрактно як перетворення з бінарних рядків-входів у бінарні рядки-виходи.

Деталі того, як об'єкти кодуються у вигляді бінарних рядків, неодмінно важливі для цих обчислень на певному рівні. Однак зазвичай ми не надто переймаємося цими деталями при аналізі обчислювальної вартості, щоб уникнути другорядних подробиць. Базова логіка полягає в тому, що ми очікуємо: обчислювальна вартість конвертації між «розумними» схемами кодування є незначною порівняно з вартістю розв'язання самої задачі. У тих випадках, де це не так, деталі можна (і слід) уточнити.

Наприклад, дуже просте обчислення конвертує між двійковим представленням невід'ємного цілого числа та його лексикографічним кодуванням (яке ми детально не пояснювали, але його можна вивести з наведеної таблиці). Тому обчислювальна вартість цілочисельної факторизації не зміниться суттєво, якщо ми вирішимо перейти від одного з цих кодувань до іншого для вхідних даних $N.$ З іншого боку, кодування невід'ємних цілих чисел в унарному записі призводить до експоненційного збільшення загальної кількості символів, і з цієї причини воно не вважається «розумною» схемою кодування.

Елементарні операції

Тепер розглянемо саме обчислення, зображене синім прямокутником на малюнку вище. Спосіб вимірювання обчислювальної вартості полягає у підрахунку кількості елементарних операцій, що потребує кожне обчислення. Інтуїтивно, елементарна операція — це операція, що залучає невелику фіксовану кількість бітів або кубітів і може бути виконана швидко й легко, наприклад обчислення І (AND) двох бітів. Натомість виклик функції factorint не можна розглядати як елементарну операцію.

Формально кажучи, конкретний вибір того, що є елементарною операцією, залежить від використовуваної обчислювальної моделі. Ми зосередимося на схемних моделях, зокрема на квантових і булевих схемах.

Універсальні набори вентилів

Для схемних моделей обчислень зазвичай кожен вентиль розглядається як елементарна операція. Це підводить до питання: які саме вентилі ми дозволяємо в наших схемах? Зосередившись зараз на квантових схемах, ми вже бачили в цій серії кілька вентилів: $X,$ $Y,$ $Z,$ $H,$ $S,$ та $T$, вентилі swap, керовані версії вентилів (зокрема controlled-NOT, Тоффолі та Фредкіна), а також вентилі, що представляють вимірювання в стандартному базисі. У контексті гри CHSH ми також побачили кілька додаткових вентилів обертання.

Ми також обговорювали вентилі запитів у контексті моделі запитів і бачили, що будь-яку унітарну операцію $U,$ яка діє на довільну кількість кубітів, можна вважати вентилем — але обидва ці варіанти ми відкинемо для цього обговорення. Ми не працюватимемо в моделі запитів (хоча реалізація вентилів запитів за допомогою елементарних операцій розглядається далі в уроці), а розгляд довільних унітарних вентилів, які можуть діяти на мільйони кубітів, як елементарних операцій не дає осмисленого або реалістичного поняття обчислювальної вартості.

Залишаючись у межах квантових вентилів, що оперують невеликою кількістю кубітів, один із підходів до визначення того, які з них вважати елементарними, — виробити точний критерій, але це не стандартний підхід і не той, який ми використаємо. Натомість ми просто робимо вибір.

Ось один стандартний вибір, який ми приймемо як типовий набір вентилів для квантових схем:

• Одно-кубітні унітарні вентилі з цього списку: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ та $T^{\dagger}$
• Вентилі controlled-NOT
• Вимірювання одного кубіта в стандартному базисі

Поширеною альтернативою є розгляд вентилів Тоффолі, Адамара та $S$ як елементарних, а також вимірювань у стандартному базисі. Іноді всі одно-кубітні вентилі розглядаються як елементарні, хоча це призводить до нереалістично потужної моделі, якщо не враховувати належним чином точність виконання вентилів.

Унітарні вентилі нашого типового набору утворюють так званий універсальний набір вентилів. Це означає, що можна наблизити будь-яку унітарну операцію на будь-якій кількості кубітів до будь-якого ступеня точності, використовуючи лише схеми зі цих вентилів. Щоб бути точним, визначення універсальності не висуває жодних вимог щодо вартості таких наближень, тобто кількості вентилів із нашого набору, що нам знадобляться. Справді, досить простий аргумент, що спирається на математичне поняття міри, показує: більшість унітарних операцій мають надзвичайно високу вартість. Доведення універсальності наборів квантових вентилів — непросте завдання і в цьому курсі не розглядається.

Для булевих схем ми вважатимемо елементарними операціями вентилі AND, OR, NOT та FANOUT. Насправді не потрібні одночасно AND і OR — за законами де Моргана можна перетворити один у інший, розмістивши NOT на всіх трьох вхідних/вихідних дротах, — але тим не менш типово та зручно допускати обидва. Вентилі AND, OR, NOT та FANOUT утворюють універсальний набір для детерміністичних обчислень, тобто будь-яку функцію з будь-якої фіксованої кількості вхідних бітів у будь-яку фіксовану кількість вихідних бітів можна реалізувати за допомогою цих вентилів.

Принцип відкладеного вимірювання

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

Зокрема, класичний біт у схемі ліворуч замінюється кубітом праворуч (ініціалізованим у стан $\vert 0\rangle$), а вимірювання у стандартному базисі замінюється вентилем controlled-NOT з подальшим вимірюванням нижнього кубіта в стандартному базисі. Суть у тому, що вимірювання у стандартному базисі в правій схемі можна зрушити аж до кінця схеми. Якщо класичний біт у лівій схемі пізніше використовується як керуючий біт, замість нього можна використовувати нижній кубіт із правої схеми, і загальний ефект буде тим самим. (Ми припускаємо, що класичний біт у лівій схемі не перезаписується після вимірювання іншим вимірюванням — але якби це відбувалося, завжди можна використати новий класичний біт, а не перезаписувати той, що використовувався для попереднього вимірювання.)

Розмір і глибина схем

Розмір схеми

Загальна кількість вентилів у схемі називається розміром цієї схеми. Отже, якщо вентилі в наших схемах представляють елементарні операції, розмір схеми відображає кількість необхідних елементарних операцій — або, іншими словами, її обчислювальну вартість. Ми пишемо $\operatorname{size}(C)$ для позначення розміру певної схеми $C.$

Наприклад, розглянь таку булеву схему для обчислення XOR двох бітів.

Розмір цієї схеми дорівнює 7, оскільки в ній є 7 вентилів загалом. (Операції FANOUT не завжди вважаються вентилями, але для цілей цього уроку ми рахуватимемо їх вентилями.)

Час, вартість і глибина схеми

Час — критично важливий ресурс або обмежуюча умова для обчислень. Наведені вище приклади, зокрема задача факторизації RSA1024, підкріплюють цю думку. Функція factorint не неспроможна факторизувати RSA1024 сама по собі — просто у нас немає достатньо часу, щоб дочекатися її завершення.

Поняття обчислювальної вартості як кількості елементарних операцій, необхідних для виконання обчислення, покликане бути абстрактним замінником часу, потрібного для реалізації обчислення. Кожна елементарна операція вимагає певного часу, і чим більше їх потребує обчислення, тим довше воно виконуватиметься — принаймні загалом. Заради простоти ми продовжуватимемо ставити знак рівності між обчислювальною вартістю і часом виконання алгоритмів.

Але зауваж, що розмір схеми не обов'язково безпосередньо відповідає часу її виконання. Наприклад, у нашій булевій схемі для обчислення XOR двох бітів два вентилі FANOUT можна виконати одночасно, так само як і два вентилі NOT, і два вентилі AND. Інший спосіб вимірювати ефективність схем — з урахуванням можливості розпаралелювання — це їхня глибина. Глибина — це мінімальна кількість шарів вентилів у схемі, де вентилі кожного шару діють на різних дротах. Еквівалентно, глибина схеми — це максимальна кількість вентилів на будь-якому шляху від вхідного до вихідного дроту. Для наведеної схеми, наприклад, глибина дорівнює 4.

Глибина схеми — один із способів формалізувати час роботи паралельних обчислень. Це просунута тема, і відомі дуже витончені конструкції схем, що мінімізують глибину для певних обчислень. Є також деякі захоплюючі невирішені питання щодо глибини схем. (Наприклад, мало що відомо про глибину схеми, необхідну для обчислення НСД.) Ми не будемо надто детально зупинятися на глибині схем у цій серії, хоча згадаємо кілька цікавих фактів у міру їх появи, але слід чітко визнати: розпаралелювання є потенційним джерелом обчислювальних переваг.

Призначення вартостей різним вентилям

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

Наприклад, як вже зазначалося, вентилі FANOUT часто вважаються безкоштовними для булевих схем — тобто ми можемо призначити вентилям FANOUT нульову вартість. Ще один приклад: коли ми працюємо в моделі запитів і рахуємо кількість звернень схеми до вхідної функції (у вигляді «чорного ящика»), ми фактично призначаємо одиничну вартість вентилям запитів і нульову вартість іншим вентилям, наприклад вентилям Адамара. Третій приклад: іноді ми призначаємо різну вартість вентилям залежно від складності їх реалізації, яка може варіюватися залежно від розглянутого обладнання.

Хоча всі ці варіанти мають сенс у різних контекстах, у цьому уроці ми залишимося простими і використовуватимемо розмір схеми як представлення обчислювальної вартості.

Вартість як функція від довжини вхідних даних

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

Сімейства схем

Вхідні дані для певної обчислювальної задачі можуть мати різну довжину, потенційно необмежено зростаючи. Кожна схема, з іншого боку, має фіксовану кількість вентилів і дротів. З цієї причини, коли ми думаємо про алгоритми в термінах схем, нам зазвичай потрібні нескінченно великі сімейства схем для представлення алгоритмів. Під сімейством схем ми розуміємо послідовність схем, що зростають у розмірі, що дозволяє обробляти дедалі більші вхідні дані.

Наприклад, уяви, що у нас є класичний алгоритм для цілочисельної факторизації, такий як той, що використовується у factorint. Як і всі класичні алгоритми, цей алгоритм можна реалізувати за допомогою булевих схем — але для цього нам знадобиться окрема схема для кожної можливої довжини вхідних даних. Якщо подивитися на отримані схеми для різних довжин вхідних даних, то буде видно, що їхні розміри природно зростають зі зростанням довжини вхідних даних — що відображає факт: факторизація 4-бітних цілих чисел значно простіша і потребує набагато менше елементарних операцій, ніж факторизація 1024-бітних.

Це приводить нас до представлення обчислювальної вартості алгоритму функцією $t,$ визначеною так, що $t(n)$ — це кількість вентилів у схемі, яка реалізує алгоритм для $n$-бітних вхідних даних. У формальніших термінах, алгоритм у моделі булевих схем описується послідовністю схем $\{C_1, C_2, C_3,\ldots\},$ де $C_n$ вирішує розглядувану задачу для $n$-бітних вхідних даних (або, у загальнішому випадку, для вхідних даних, розмір яких параметризовано деяким чином через $n$), і функція $t,$ що представляє вартість цього алгоритму, визначається як

$$t(n) = \operatorname{size}(C_n).$$

Для квантових схем ситуація подібна: для обробки дедалі довших вхідних рядків потрібні дедалі більші схеми.

Приклад: додавання цілих чисел

Для кращого пояснення розглянемо задачу додавання цілих чисел, яка значно простіша за цілочисельну факторизацію або навіть обчислення НСД.

Додавання цілих чисел

Вхід: цілі числа $N$ і $M$
Вихід: $N+M$

Як спроектувати булеві схеми для розв'язання цієї задачі?

Для простоти обмежимося випадком, коли $N$ і $M$ — невід'ємні цілі числа, представлені $n$-бітними рядками у двійковому записі. Дозволимо довільну кількість ведучих нулів у цих кодуваннях, щоб

$$0\leq N,M\leq 2^n - 1.$$

Виходом буде $(n+1)$-бітний двійковий рядок, що представляє суму — це максимальна кількість бітів, необхідних для запису результату.

Починаємо зі стандартного алгоритму додавання двійкових представлень, що є аналогом у базисі 2 того, як додавання викладають у початковій школі по всьому світу. Цей алгоритм можна реалізувати за допомогою булевих схем таким чином.

Починаючи з молодших бітів, можна обчислити їхній XOR, щоб визначити молодший біт суми. Потім обчислюємо біт перенесення, що є І (AND) двох молодших бітів $N$ і $M.$ Ці дві операції разом іноді називають напівсуматором.

Використовуючи схему XOR, яку ми вже бачили кілька разів, разом із вентилем AND і двома вентилями FANOUT, можна побудувати напівсуматор із 10 вентилів. Якщо з якоїсь причини ми вирішимо включити вентилі XOR до набору елементарних операцій, знадобиться 1 вентиль AND, 1 вентиль XOR і 2 вентилі FANOUT для побудови напівсуматора.

Переходячи до старших бітів, можна використати аналогічну процедуру, але цього разу враховуючи біт перенесення з кожної попередньої позиції в обчисленні. Каскадуючи два напівсуматори і беручи АБО (OR) бітів перенесення, що вони виробляють, можна створити так званий повний суматор.

Це потребує 21 вентиля загалом: 2 вентилі AND, 2 вентилі XOR (кожен потребує 7 вентилів для реалізації), один вентиль OR і 4 вентилі FANOUT.

Нарешті, каскадуючи повні суматори, отримуємо булеву схему для додавання невід'ємних цілих чисел. Наприклад, наступна схема обчислює суму двох 4-бітних цілих чисел.

Загалом для цього потрібно

$$21 (n-1) + 10 = 21 n - 11$$

вентилів. Якби ми вирішили включити вентилі XOR до набору елементарних операцій, знадобилося б $2n-1$ вентилів AND, $2n-1$ вентилів XOR, $n-1$ вентилів OR та $4n-2$ вентилів FANOUT, тобто $9n-5$ вентилів загалом. Якщо до того ж не рахувати вентилі FANOUT, виходить $5n-3$ вентиля.

Асимптотичне позначення

З одного боку, добре точно знати, скільки вентилів потрібно для виконання різних обчислень, як у прикладі додавання цілих чисел. Ці деталі важливі для фактичного побудови схем.

З іншого боку, якщо ми проводитимемо аналізи на такому рівні деталей для всіх обчислень, що нас цікавлять, зокрема для задач, значно складніших за додавання, ми дуже швидко загрузнемо в деталях. Щоб зберегти керованість і навмисно відсіяти другорядні деталі, при аналізі алгоритмів зазвичай використовують нотацію «O великого». За допомогою цього позначення можна виражати порядок зростання функцій.

Формально, маючи дві функції $g(n)$ і $h(n),$ ми пишемо $g(n) = O(h(n)),$ якщо існує позитивне дійсне число $c > 0$ і позитивне ціле число $n_0$ такі, що

$$g(n) \leq c\cdot h(n)$$

для всіх $n \geq n_0.$ Зазвичай $h(n)$ обирається якомога простим виразом, щоб позначення можна було використовувати для виявлення граничної поведінки функції у простій формі. Наприклад, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Це позначення досить прямолінійно поширюється на функції кількох аргументів. Наприклад, якщо маємо дві функції $g(n,m)$ і $h(n,m),$ визначені на позитивних цілих числах $n$ і $m,$ ми пишемо $g(n,m) = O(h(n,m)),$ якщо існує позитивне дійсне число $c > 0$ і позитивне ціле число $k_0$ такі, що

$$g(n,m) \leq c\cdot h(n,m)$$

за умови $n+m \geq k_0.$

Пов'язуючи це позначення з прикладом додавання невід'ємних цілих чисел, робимо висновок: існує сімейство булевих схем $\{C_1, C_2,\ldots,\},$ де $C_n$ складає два $n$-бітних невід'ємних цілих числа, такі, що $\operatorname{size}(C_n) = O(n).$ Це розкриває найсуттєвішу характеристику того, як вартість додавання масштабується з розміром вхідних даних: вона масштабується лінійно.

Також зауваж, що це не залежить від конкретної деталі — чи вважаємо ми вартість вентилів XOR одиничною або рівною 7. Загалом використання нотації «O великого» дозволяє робити заяви про обчислювальні вартості, нечутливі до таких низькорівневих деталей.

Більше прикладів

Ось ще кілька прикладів задач обчислювальної теорії чисел, починаючи з множення.

Множення цілих чисел

Вхід: цілі числа $N$ і $M$
Вихід: $NM$

Побудова булевих схем для цієї задачі складніша, ніж для задачі додавання — але, думаючи про стандартний алгоритм множення, можна отримати схеми розміром $O(n^2)$ для цієї задачі (якщо $N$ і $M$ обидва представлені $n$-бітними двійковими представленнями). Загальніше: якщо $N$ має $n$ бітів, а $M$ має $m$ бітів, то існують булеві схеми розміром $O(nm)$ для множення $N$ на $M.$

Насправді існують інші способи множення, що масштабуються краще. Наприклад, алгоритм множення Шенхаге–Штрассена можна використати для побудови булевих схем множення двох $n$-бітних цілих чисел з вартістю $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ Проте складність цього методу створює значні накладні витрати, через що він практичний лише для чисел із десятками тисяч бітів.

Ще одна базова задача — ділення, під яким розуміємо обчислення як частки, так і остачі для заданих цілого дільника та діленого.

Ділення цілих чисел

Вхід: цілі числа $N$ і $M\neq0$
Вихід: цілі числа $q$ і $r$, що задовольняють $0\leq r < |M|$ та $N = q M + r$

Вартість цілочисельного ділення схожа на вартість множення: якщо $N$ має $n$ бітів, а $M$ має $m$ бітів, то існують булеві схеми розміром $O(nm)$ для розв'язання цієї задачі. І так само, як для множення, відомі асимптотично кращі методи.

Тепер порівняємо відомі алгоритми обчислення НСД з алгоритмами додавання та множення. Алгоритм Евкліда для обчислення НСД $n$-бітного числа $N$ та $m$-бітного числа $M$ потребує булевих схем розміром $O(nm),$ аналогічно стандартним алгоритмам множення та ділення. Також, як і для множення та ділення, існують асимптотично швидші алгоритми НСД — зокрема такі, що потребують $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ елементарних операцій для обчислення НСД двох $n$-бітних чисел.

Дещо дорожче обчислення, що виникає в теорії чисел, — модульне піднесення до степеня.

Цілочисельне модульне піднесення до степеня

Вхід: цілі числа $N,$ $K,$ та $M$ з $K\geq 0$ та $M\geq 1$
Вихід: $N^K \hspace{1mm} (\text{mod }M)$

Під $N^K\hspace{1mm} (\text{mod }M)$ ми маємо на увазі остачу від ділення $N^K$ на $M,$ тобто єдине ціле число $r$, що задовольняє $0\leq r < M$ та $N^K = q M + r$ для деякого цілого числа $q.$

Якщо $N$ має $n$ бітів, $M$ має $m$ бітів, а $K$ має $k$ бітів, ця задача може бути розв'язана булевими схемами розміром $O(k m^2 + nm).$ Це зовсім не очевидно. Розв'язок полягає не в тому, щоб спочатку обчислити $N^K,$ а потім взяти остачу — це потребувало б експоненціальної кількості бітів тільки для збереження числа $N^K.$ Натомість можна скористатися алгоритмом піднесення до степеня (відомим також як бінарний метод та повторне квадратування), який використовує двійкове представлення $K$ для виконання всього обчислення за модулем $M.$ За умови, що $N,$ $M$ та $K$ — всі $n$-бітні числа, ми отримуємо алгоритм зі складністю $O(n^3)$ — або кубічний алгоритм за часом. І знову, відомі алгоритми, що є складнішими, але асимптотично швидшими.

Вартість цілочисельної факторизації

На відміну від щойно розглянутих алгоритмів, відомі алгоритми цілочисельної факторизації набагато дорожчі — що й слід очікувати з раніше обговореного в уроці.

Один простий підхід до факторизації — пробне ділення, де алгоритм перебирає список $2,\ldots,\sqrt{N}$ у пошуках простого дільника вхідного числа $N.$ У найгіршому випадку, коли $N$ — $n$-бітне число, це потребує $O(2^{n/2})$ ітерацій. Кожна ітерація вимагає пробного ділення, що означає $O(n^2)$ елементарних операцій на ітерацію (за стандартним алгоритмом ділення). У результаті маємо схеми розміром $O(n^2 2^{n/2}),$ що є експоненціальним відносно розміру вхідних даних $n.$

Існують алгоритми цілочисельної факторизації з кращим масштабуванням. Наприклад, решето числового поля, згадане раніше, — алгоритм, що використовує випадковість, — загалом вважається (але не доведено строго) таким, що потребує

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

елементарних операцій для факторизації $n$-бітних цілих чисел з високою ймовірністю. Хоча дуже суттєво, що $n$ зведено до степеня $1/3$ у показнику цього виразу, той факт, що він все одно з'являється в показнику, все ще є проблемою, що призводить до поганого масштабування — і пояснює зокрема, чому RSA1024 залишається поза межами застосовності цього алгоритму.

Поліноміальна та експоненціальна вартість

Класичні алгоритми для додавання, множення, ділення цілих чисел та обчислення найбільшого спільного дільника дозволяють розв'язувати ці задачі миттєво для вхідних даних із тисячами бітів. Додавання має лінійну вартість, тоді як три інші задачі мають квадратичну вартість (або субквадратичну з використанням асимптотично швидких алгоритмів). Модульне піднесення до степеня дорожче, але все ж досить ефективне — з кубічною вартістю (або субкубічною з використанням асимптотично швидких алгоритмів).

Усі це приклади алгоритмів із поліноміальною вартістю, тобто з вартістю $O(n^c)$ для деякої фіксованої константи $c > 0.$ Як груба апроксимація першого порядку, алгоритми з поліноміальною вартістю абстрактно розглядаються як ефективні алгоритми.

Натомість відомі класичні алгоритми для цілочисельної факторизації мають експоненціальну вартість. Іноді вартість решета числового поля описується як субекспоненціальна, бо $n$ зведено до степеня $1/3$ у показнику, але в теорії складності цей термін зазвичай застосовується до алгоритмів, чия вартість є

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

для кожного $\varepsilon > 0.$ Так звані NP-повні задачі — це клас задач, для яких невідомо (і широко вважається, що не існує) алгоритмів з поліноміальною вартістю. Схемне формулювання гіпотези про експоненціальний час постулює щось ще сильніше: жодна NP-повна задача не може мати алгоритм із субекспоненціальною вартістю.

Ототожнення алгоритмів з поліноміальною вартістю з ефективними алгоритмами слід розуміти як вільну абстракцію. Звичайно, якщо вартість алгоритму масштабується як $n^{1000}$ або $n^{1000000}$ для вхідних даних розміру $n,$ то назвати такий алгоритм ефективним — велике перебільшення. Однак навіть алгоритм із вартістю, що масштабується як $n^{1000000},$ має зробити щось розумне, щоб уникнути експоненціальної вартості, якої ми зазвичай очікуємо від алгоритмів, що базуються так чи інакше на «грубій силі» або «повному переборі». Навіть витончені вдосконалення решета числового поля, наприклад, не можуть уникнути цього експоненціального масштабування вартості. Алгоритми з поліноміальною вартістю, з іншого боку, вміють використовувати структуру задачі певним чином, що дозволяє уникнути експоненціального масштабування.

На практиці ідентифікація алгоритму з поліноміальною вартістю для задачі — лише перший крок до реальної ефективності. Завдяки алгоритмічним вдосконаленням алгоритми з поліноміальною вартістю та великими показниками степеня іноді можна суттєво поліпшити, знизивши вартість до більш «розумного» поліноміального масштабування. Іноді речі стають простішими, коли відомо, що вони можливі, — тому ідентифікація алгоритму з поліноміальною вартістю для задачі може також надихнути на нові, ще більш ефективні алгоритми.

Розглядаючи переваги квантових обчислень над класичними, ми насамперед звертаємо погляд на експоненціальні переваги або принаймні суперполіноміальні — ідеально знаходячи квантові алгоритми з поліноміальною вартістю для задач, для яких невідомі класичні алгоритми з поліноміальною вартістю. Теоретичні переваги такого порядку мають найбільше шансів призвести до реальних практичних переваг — але виявити такі переваги надзвичайно складно. Зараз відомо лише кілька прикладів, але пошук продовжується.

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

Прихована вартість схемних обчислень

Є ще одне питання, яке варто згадати, хоча ми не будемо ним займатися далі в цьому курсі. Існує «прихована» обчислювальна вартість при роботі зі схемами, і вона стосується специфікацій самих схем. Зі збільшенням вхідних даних потрібні дедалі більші схеми — але нам потрібно якось отримати описи цих схем, якщо ми збираємося їх реалізовувати.

Для всіх обговорених прикладів — або тих, що будуть розглянуті в наступних уроках, — існує базовий алгоритм, з якого виводяться схеми. Зазвичай схеми в сімействі слідують деякому базовому шаблону, що легко екстраполюється на дедалі більші вхідні дані, наприклад каскадування повних суматорів для побудови булевих схем додавання або виконання шарів вентилів Адамара та інших вентилів за деяким простим шаблоном.

Але що відбувається, якщо з шаблонами в самих схемах пов'язані непосильні обчислювальні витрати? Наприклад, опис кожного елемента $C_n$ сімейства схем може в принципі визначатися деякою надзвичайно складно обчислюваною функцією від $n.$

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