изити ймовірність помилки до як завгодно малої величини. p> Ми тільки що сформулювали (опускаючи деякі подробиці) математичну модель квантового обчислення. Тепер природно задати два питання. p> Для яких завдань квантове обчислення дає виграш в порівнянні з класичним?
Яку систему можна використовувати для фізичної реалізації квантового комп'ютера? (Це не обов'язково має бути система спінів.) p> З приводу першого питання зараз відомо наступне. По-перше, на квантовому комп'ютері можна моделювати будь-яку квантову систему за поліноміальний число кроків. Це дозволить (за наявності квантового комп'ютера) передбачати властивості молекул і кристалів, проектувати мікроскопічні електронні пристрої розміром у кілька десятків ангстрем. (Зараз такі пристрої знаходяться на межі технологічних можливостей, але в майбутньому вони, ймовірно, будуть застосовуватися у звичайних комп'ютерах.) Другий приклад - розкладання на множники та аналогічні теоретико-числові завдання, пов'язані з Абелеві групами. У 1994 році П. Шор (P. Shor) придумав квантовий алгорітм4) <# "11" src = "doc_zip161.jpg"/> знаків за кроків (). Цей красивий результат може мати скоріше шкідливе, ніж корисне застосування: розкладаючи числа на множники, можна підбирати ключі до шифрів, підробляти електронні підписи і т.д. (Втім, труднощі на шляху створення квантового комп'ютера такі великі, що протягом найближчих 10 років користувачі шифрів можуть спати спокійно.) Третій приклад - це пошук потрібного запису в невпорядкованою базі даних. Тут виграш не настільки значний: для знаходження одного запису з потрібно близько операцій на квантовому комп'ютері замість операцій на класичному. На цьому список відомих прикладів закінчується - не тому що квантові комп'ютери марні для інших завдань, а тому що теорія квантових обчислень поки не розроблена. Будемо сподіватися, що скоро з'являться нові математичні ідеї, які дозволять придумати нові приклади. p> Фізична реалізація квантового комп'ютера - надзвичайно цікава, але складне завдання. Ще кілька років тому висловлювалися сумніви в її принципової можливості розв'язання. Справа в тому, що будь-яке унітарне перетворення можна реалізувати лише з деякою точністю. Крім того, систему спінів або аналогічну квантову систему не можна повністю захистити від збурень з боку навколишнього середовища. Все це повинно приводити до погрішностей, які будуть накопичуватися в процесі обчислення. Через кроків (де - точність кожного унітарного перетворення) ймовірність помилки стане порядку одиниці. На щастя, ці труднощі можна подолати, використовуючи квантові коди, що виправляють помилки. У 1996 році П. Шор запропонував схему корекції помилок в процесі квантового обчислення (fault-tolerant quantum computation), яка була незабаром вдосконалена. Остаточний результат полягає в наступному. Існує деяке порогове значення точності, таке що при можливо як завгодно довге квантове обчислення. Однак при помилки нако...
