КВАНТОВЫЙ КОМПЬЮТЕР КВАНТОВЫЕ ВЫЧИСЛЕНИЯ (В.А.Садовничий)

  

УДКК 530.15
Библиотека «Квантовый компьютер и квантовые вычисления», том II

Главный редактор В.А.Садовничий
Редколлегия:
В. В. Белокуров
А. П. Бельтюков
А. В. Борисов
И. С. Мамаев
О. А. Хрусталев

Издание осуществлено при финансовой поддержке Физикотехнологического института «ФТИАН» и Московского государственного университета им. М. В. Ломоносова

Квантовый компьютер и квантовые вычисления. Ижевск: Ижевская республиканская типография, 1999. 288 стр.

Второй выпуск библиотеки «Квантовый компьютер и квантовые вычисления» представляет собой сборник классических работ (Фейнман, Шор и др.) и новый обзор Ю. И. Манина.

Для широкого круга читателей – физиков, математиков, инженеров, интересующихся возможностями создания квантового компьютера и связанными с ним областями науки и техники.
(C) Редакция журнала «Регулярная и хаотическая динамика», 1999


Оглавление

ФИЗИКИ УЧАТ КОМПЬЮТЕР СЧИТАТЬ ПО-НОВОМУ
НЕОБРАТИМОСТЬ И ВЫДЕЛЕНИЕ ТЕПЛА В ПРОЦЕССЕ ВЫЧИСЛЕНИЙ
Введение
Классификация
Логическая необратимость
Логическая необратимость и возникновение энтропии
Подробный анализ бистабильной ямы
Три источника ошибок
Заключение
ЛОГИЧЕСКАЯ ОБРАТИМОСТЬ ВЫЧИСЛЕНИЙ
Введение
Логически обратимые машины Тьюринга
Обсуждение
Физическая обратимость
КВАНТОВОМЕХАНИЧЕСКИЕ ГАМИЛЬТОНОВЫ МОДЕЛИ МАШИН ТЬЮРИНГА
Введение
Машины Тьюринга
Предварительные сведения
Модель спинов на решетке
Состояния и операторы модели
Состояния модели
Проекционные операторы модели
Операторы изменения конфигураций модели
Зависящие от времени гамильтоновы модели
Запись, вычисление и сдвиги
Зависящие от времени гамильтонианы
Гамильтонианы, не зависящие от времени
Характеристики моделей
Представление вычислений
Локальность во времени
Сложность гамильтонианов
Диссипация энергии
Измерения
Не зависящие от времени модели
Модели с гамильтонианами, зависящими от времени
Обсуждение
Р. Фейнман МОДЕЛИРОВАНИЕ ФИЗИКИ НА КОМПЬЮТЕРАХ
Введение
Моделирование времени
Моделирование вероятности
Квантовые компьютеры – универсальные квантовые моделирующие устройства
Можно ли моделировать квантовые системы вероятностным образом на классическом компьютере?
Отрицательная вероятность
Поляризация фотонов – системы двух состояний
Эксперимент по двухфотонной корреляции
Обсуждение
КВАНТОВОМЕХАНИЧЕСКИЕ КОМПЬЮТЕРЫ
Введение
Вычисление на обратимой машине
Квантовомеханический компьютер
Недостатки и необратимые потери свободной энергии
Простейшая реализация
Заключение
КВАНТОВАЯ ТЕОРИЯ, ПРИНЦИП ЧЁРЧА-ТЬЮРИНГА И УНИВЕРСАЛЬНЫЙ КВАНТОВЫЙ КОМПЬЮТЕР
Вычислительные машины и принцип ЧёрчаТьюринга
Квантовые компьютеры
Свойства универсального квантового компьютера
Случайные числа и дискретные стохастические системы
Квантовые корреляции
Полное моделирование произвольных конечных физических систем
Параллельное вычисление на последовательном компьютере
Более быстрые компьютеры
Следствия для интерпретации квантовой теории
Дальнейшие связи между физикой и компьютерной наукой
Квантовая теория сложности
Связи между принципом Чёрча-Тьюринга с другими частями физики
Программирование физики
БЫСТРОЕ РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ КВАНТОВЫХ ВЫЧИСЛЕНИЙ
ПОЛИНОМИАЛЬНЫЕ ПО ВРЕМЕНИ АЛГОРИТМЫ РАЗЛОЖЕНИЯ ЧИСЛА НА ПРОСТЫЕ МНОЖИТЕЛИ И НАХОЖДЕНИЯ ДИСКРЕТНОГО ЛОГАРИФМА ДЛЯ КВАНТОВОГО КОМПЬЮТЕРА
Введение
Квантовые вычисления
Обратимая логика и возведение в степень по модулю
Квантовое преобразование Фурье
Разложение числа на простые множители
Нахождение дискретных логарифмов
Комментарии и открытые проблемы
КЛАССИЧЕСКОЕ ВЫЧИСЛЕНИЕ, КВАНТОВОЕ ВЫЧИСЛЕНИЕ И АЛГОРИТМ ФАКТОРИЗАЦИИ ШОРА
Почему нужно квантовое вычисление?
Классическая теория вычислений
Конструктивная вселенная
Определение.
Модели вычислений I: нормальные модели.
Предложение.
Модели вычислений II: булевские схемы (схемы из логических элементов).
Предложение.
Соответствие между машинами Тьюринга и булевскими схемами.
Размер, сложность и вычислимость за полиномиальное время.
Проблема P/NP
Предложение. $E \in \mathrm{NP}$.
Предложение. $E$ – NP-полно.
Замечание.
Квантовый параллелизм
Описание проблемы.
Квантовые параллельные вычисления: версия I.
Квантовые параллельные вычисления: версия II.
Избранные квантовые подграммы
Избранные квантовые подпрограммы
Инициализация.
Квантовое вычисление классических функций.
Предложение.
Быстрое преобразование Фурье.
Лемма.
Квантовый поиск.
Предложение.
Алгоритм факторизации Шора
Обозначения.
Классический алгоритм.
Предложение
Квантовый алгоритм, вычисляющий r.
Обоснование.
Колмогоровская сложность и рост рекурсивных функций
Предложение
Приложение
email@scask.ru