Задачі, які можна реалізувати на квантових обчисленнях

Главная » Каталог статей » Статьи на украинском » Квантовий комп’ютер » Задачі, які можна реалізувати на квантових обчисленнях

1133524115159883_1

Відомо два приклади нетривіальних задач, в яких квантові обчислення (KО) дають радикальний виграш.

Перший з них — задача розкладання цілих чисел на прості множники і, як наслідок, обчислення дискретного логарифма (ДЛ). Далі мова піде саме про ДЛ.

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

Так от, для дискретного логарифма є ефективний квантовий алгоритм. Його придумав Шор в кінці 1994 року. Після його статті і почався вибух публікацій з КО. Незалежно від нього, Олексій Кітаєв побудував квантовий алгоритм для цієї і деяких загальніших задач [8]. Ідеї у них були різні.

Шор використовував приблизно таку ідею, вона істотно квантова: розглянемо базис у фазовому просторі. Він складається з класичних станів. Але в лінійному просторі багато базисів. Ми можемо знайти деякий оператор, який ефективно будує інший базис; ми можемо до нього перейти, зробити там якісь обчислення, повернутися назад і одержати щось абсолютно відмінне від того, що ми мали б в класичному базисі. Одна з можливостей використовувати квантовість полягає у тому, що ми будуємо якийсь дивний базис, в ньому щось робимо, повертаємося назад і інтерпретуємо результат. Шор саме цю ідею і реалізував. Причому перетворення виявилося таке, яке і у фізиці, і в математиці має принципове значення — дискретне перетворення Фур’є.

Його можна уявити у вигляді тензора операторів, які діють на кожний з кубіт такою матрицею:

clip_image002

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

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

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

Друга задача запропонована Гровером (L. Grover) [127]. Розглянемо базу даних, що містить 2N записів. Ми хочемо знайти рівно один запис. Є якась процедура визначення того, потрібний запис ми узяли чи ні. Записи не впорядковані. З якою швидкістю ми можемо вирішити цю задачу на звичному комп’ютері? У гіршому разі нам доведеться перебрати всі 2N записів — це очевидно. Виявляється, що на КК досить числа запитів порядку кореня з числа записів – 2N/2.

Цікава задача — створення оптимальних мікросхем. Нехай є функція, яку потрібно реалізувати мікросхемою, і ця функція задана програмою, яка використовує поліноміально обмежену пам’ять. Побудова потрібної мікросхеми з мінімальним числом функціональних елементів — завдання PSPACE. Тому поява пристроїв, які ефективно вирішують PSPACE-задачі, дозволила б одноманітно проектувати оптимальні за своїми показниками обчислювальні пристрої звичного типу. Крім того, в PSPACE потрапляє більшість задач «штучного інтелекту»: машинне навчання, розпізнавання образів і т.д.

Так от, точно встановлено, що KО знаходяться десь між звичними обчисленнями вірогідності і PSPACE. Якщо все ж таки виявиться, що KО можна ефективно реалізувати на класичних машинах вірогідності, не буде сенсу у фізичній реалізації квантових машин. Якщо ж з’ясується, що за допомогою KО можна ефективно вирішувати ті або інші PSPACE-задачі, то фізична реалізація КК відкриє принципово нові можливості.

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

Давайте подивимося на таке питання: як можна еволюцію квантової системи вивчати на звичному комп’ютері? Це постійно робиться, оскільки це задача важлива для хімії, молекулярної біології, фізики і т.п. Але, за рахунок експоненціального зростання розмірності при тензорному добутку, для моделювання десяти спинів вам потрібно оперувати із 100-мірним простором, сто спинів — це вже кінець. А якщо пригадати, що в молекулі білка десятки тисяч атомів, то… Там, правда, не усюди доцільне саме квантове моделювання, але в цілому ясно, що є дуже серйозні перешкоди для моделювання квантових систем на класичних комп’ютерах. Отже, якщо створити обчислювальний пристрій, який функціонує за квантовим принципом, то принаймні один важливий клас задач на ньому є сенс вирішувати — можна моделювати реальні квантові системи, які виникають у фізиці, хімії, біології [128].

Оставьте комментарий к статье