ь).
Доведіть, що оператори зі стандартного базису породжують всюди щільне безліч в.
Доведіть, що фазові зрушення можна реалізувати в стандартному базисі, використовуючи напрокат додаткові q-біти.
Доведіть, що заперечення і елемент Дойча, де, - ірраціональне, утворюють повний базис для квантового обчислення.
Доведіть, що будь-який оператор, діючий на одному q-бите, може бути наближено реалізований у розширеному сенсі з точністю схемою розміру в стандартному базисі, і є поліноміальний алгоритм побудови цієї схеми за описом.
Це завдання досить складна, до її вирішення краще приступати після знайомства з розділами 11 і 12 і вирішення завдання 12.3 (квантове перетворення Фур'є). Пропонований шлях вирішення є досить витонченим. У статті [<# "22" src = "doc_zip1537.jpg"/>. br/>
Список літератури
1. Ахо. А., Хопкрофта, Дж., Ульман, Дж Побудова та аналіз обчислювальних алгоритмів М.: Мир, 1979
. Віноградов.І.М Основи теорії чисел Ізд.8-е, испр. М.: Наука, 1972
. Гері.М., Джонсон.Д Обчислювальні машини і труднорешаемие завдання М.: Мир, 1982
. Кітаев.А.Ю. Квантові обчислення: алгоритми і виправлення помилок УМН, номер6, 1997
. Кліні.С. Математична логіка М.: Мир, 1973
. Кліні.С Введення в метаматематику М.: ІЛ, 1957
. Кнут.Д Мистецтво програмування на ЕОМ. У 3т М.: Мир, 1977
. Кострикін А.І., Манін Ю.І Лінійна алгебра і геометрія М.: Наука, 1986
. Мак-Вільямс Ф., Дж., Слоен Н., Дж. А. Теорія кодів, що виправляють помилки М.: Связь, 1979
. Мальцев А. І Алгоритми і рекурсивні функції М.: Наука, 1965
. Пападімітріу Х., Стагліц До Комбінаторна оптимізація. Алгоритми та складність М.: Мир, 1985
. Прасолов В.В Завдання і теореми лінійної алгебри М.: Наука. Фізматліт, 1996
. Роджерс Х Теорія рекурсивних функцій і ефективна вичіслімость М.: Мир, 1972
. Схрейвер А Теорія лінійного і цілочисельного програмування. У 2т М.: Мир, 1991
. Шафаревич І.Р Основні поняття алгебри// Алгебра-1. Підсумки науки і техніки М.: ВІНІТІ, 1986
. Шенфілд Дж.Р Математична логіка М.: Наука, 1975
.
