Квантовий алгоритм

Квантовий алгоритм - це алгоритм, призначений для виконання на квантовому комп'ютері.

Квантовий алгоритм являє собою класичний алгоритм, який задає послідовність унітарних операцій (гейтов, або вентилів) із зазначенням, над якими саме кубітами їх треба здійснювати. Квантовий алгоритм задається або у вигляді словесного опису таких команд, або за допомогою їх графічного запису у вигляді системи вентилів (quantum gate array).

Результат роботи квантового алгоритму носить імовірнісний характер [1]. За рахунок невеликого збільшення кількості операцій в алгоритмі можна як завгодно наблизити ймовірність отримання правильного результату до одиниці.

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

Будь-яка задача, розв'язувана квантовим алгоритмом, може бути вирішена і класичним комп'ютером шляхом прямого обчислення унітарних матриць експоненційної розмірності, отримання явного виду квантових станів. Зокрема, проблеми, нерозв'язні на класичних комп'ютерах (наприклад, проблема зупинки), залишаються нерозв'язними і на квантових. Але таке пряме моделювання вимагає експонентного часу, і тому виникає можливість, використовуючи квантовий паралелізм, прискорювати на квантовому комп'ютері деякі класичні алгоритми [2].

Прискорення на квантовому комп'ютері не пов'язане з тактовою частотою процесора. Воно засноване на квантовому паралелізмі. Один крок квантового обчислення здійснює набагато більшу роботу, ніж один крок класичного. Однак було б помилкою прирівнювати квантове обчислення до распараллеленному класичному. Наприклад, квантовий комп'ютер не може вирішити завдання перебору швидше, ніж за \ Sqrt {T_ {class}} де T_ {class} - Час роботи детермінованого класичного алгоритму перебору (див. [3]), в той час як недетермінірованний класичний алгоритм вирішує її за час log (T_ {class}) . Але недетермінірованний класичний алгоритм вимагає експонентного ресурсу пам'яті, тобто не є фізично здійсненним, тоді як квантовий алгоритм не суперечить відомим законам природи.

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

Випадки квантового прискорення, на тлі загальної маси класичних алгоритмів, дуже рідкісні (див. [4]). Однак, це не применшує принципового значення квантових обчислень, тому що вони здатні принципово прискорити виконання завдань переборного типу.


1. Основні схеми квантового прискорення

Головний тип завдань, які прискорюються квантовими алгоритмами, є завдання типу перебору. Їх можна розділити на 2 основні групи:

  1. Завдання моделювання динаміки складних систем (початкова ідея Фейнмана) і
  2. Математичні задачі, що зводяться до перебору варіантів:
    1. Загальний випадок перебору: схема Гровера і її варіанти, а також
    2. Завдання пошуку прихованих періодів: схема Шора використання швидкого квантового перетворення Фур'є, і її аналоги.

Тип 1) представлений алгоритмом Залки-Візнера моделювання унітарної динаміки квантових систем n частинок за майже реальний час і з лінійною від n пам'яттю. Цей алгоритм використовує схему Шора квантового перетворення Фур'є.

Тип 2) представлений:

  • алгоритмом Гровера загальної задачі перебору і його безперервним і адіабатичним варіантами, а також алгоритмами, що використовують схему Гровера: структурного пошуку (Фарі, Гутман), алгоритмом пошуку екстремуму (Хойер та ін) і пошуку співпадаючих рядків в базі даних (Амбайніс),
  • алгоритмом Шора факторизації цілих чисел, алгоритмом Абрамса-Ллойда виявлення періоду, алгоритмом Китаєва визначення прихованих підгруп та ін

Тип 1) представляє найбільший інтерес з точки зору подальших застосувань квантового комп'ютера.


2. Класифікація

Класифікація квантових алгоритмів може проводиться за типом квантових перетворень, використовуваних алгоритмом. Серед часто використовуваних перетворень можна відзначити: en: phase kick-back, phase estimation, en: quantum Fourier transform, en: quantum walk, en: amplitude amplification, en: topological quantum field theory. Також можливе групування квантових алгоритмів за типом проблем, розв'язуваних ними. [5]


3. Широко відомі алгоритми

Примітки

  1. "Випадковість як обчислювальний ресурс" - offline.computerra.ru/2002/435/16745 / "Компьютерра" № 10 від 18 березня 2002 року "Квантові алгоритми нагадують імовірнісні. Перш за все, невизначеністю результату."
  2. "Квантові комп'ютери", кфмн Л. Федічкін, ФТІ РАН. Ниж, 2001 № 01 "Впровадження квантових комп'ютерів не приведе до вирішення алгоритмічно не вирішуваних класичних завдань, а лише прискорить деякі обчислення"
  3. Yuri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc.Roy.Soc.Lond. A455 (1999) 2165-2172 [1] - xxx.lanl.gov/abs/quant-ph/9806001
  4. Yuri Ozhigov, Quantum Computers Speed ​​Up Classical with Probability Zero, Chaos Solitons Fractals 10 (1999) 1707-1714 [2] - xxx.lanl.gov/abs/quant-ph/9803064
  5. Childs, Andrew M; Wim van Dam (2008-12-02). " Quantum algorithms for algebraic problems - arxiv.org/abs/0812.0380 ". 0812.0380. Перевірено 2009-08-05.