ність цієї проблеми. Результат Шора був приголомшуючим для більшості вчених і спонукав їх до широкомасштабних досліджень в області квантових обчислень. p> У більшості алгоритмів, включаючи алгоритм Шора, використовується стандартний спосіб зведення задачі розкладання до задачі пошуку періоду функції. Шор використовує квантовий паралелізм для отримання суперпозиції всіх значень функції за один крок. Потім він виробляє квантове перетворення Фур'є, результатом якого, як для класичного перетворенні Фур'є, є функція, аргумент якої кратний величині, зворотній періоду. З високою ймовірністю вимір стану повертає період, який у свою чергу, служить для розкладання цілого числа М.
Все що було сказано вище, розкриває суть квантового алгоритму, але в дуже спрощеному вигляді. Найбільша трудність полягає в тому, що квантове перетворення Фур'є засноване на швидкому перетворенні Фур'є і, таким чином, дає тільки приблизний результат в більшості випадків. br/>
.3.2 Алгоритм Гровера
Великий клас завдань можна визначати як завдання пошуку кшталт В«знайти з безлічі можливих рішень, таке, що твердження - істинноВ». Діапазон подібних завдань широкий: від пошуку інформації в базі даних до зафарбовування графа. Наприклад, завдання зафарбовування графа можна розглядати як пошук такого позначення квітів вершин, що твердження В«всі примикають вершини мають різні кольориВ» є вірним. Аналогічно завдання сортування може бути розглянута, як пошук перестановки, для якої твердження В«перестановка переводить первинний стан сортування в бажанеВ» було б вірним. p> У задачі неупорядкованого пошуку нічого не відомо про структуру простору рішень та про затвердження. Наприклад, визначення не дає ніякої інформації про можливе значенні для. У задачі впорядкованого пошуку можна використовувати інформацію про простір пошуку та про затвердження. p> Наприклад, пошук за алфавітним списком є ​​завданням упорядкованого пошуку, і алфавітний порядок використовується для побудови алгоритму. В інших випадках, скажімо, в задачах, де потрібно знайти хоча б одне рішення, структуру задачі можна використовувати для побудови евристичних алгоритмів, які швидко дають рішення для деяких окремих випадків. Але в загальному випадку, коли ми маємо задачу неупорядкованого пошуку, найкраще, що можна зробити класичним шляхом - це послідовно перевіряти істинність кожного твердження. Для пошукового простору з елементів звичайне завдання неупорядкованого пошуку вимагає перевірок. На квантовому ж комп'ютері, як показав Гровер, завдання неупорядкованого пошуку можна вирішити з великою ймовірністю виробляючи близько перевірок. Таким чином, квантовий алгоритм Гровера є свідомо більш ефективним, ніж будь-який алгоритм для невпорядкованого пошуку, що виконується на класичному комп'ютері. p> Гровер також показав, що деякі пошукові завдання, які на класичних комп'ютерах Випоняемие за можуть бути вирішені за на квантовому комп&#...
