Что может квантовый компьютер?

Что такое квантовый компьютер?

Компьютер – машина, умеющая работать с памятью и данными: обрабатывать, изменять, удалять, добавлять.

Основные принципы:

Но традиционный компьютер не вводит понятия неопределенности. Нет возможности написать программу, которая будет неоднозначна.

Что такое квантовая механика?

обычная механика: вероятность = маскировка нашего незнания
квантовая механика: принцип суперпозиции, вероятность отражает физическую реальность
Обычный бит памяти: 0 или 1
Квантовый бит (кубит): вероятность 0 и вероятность 1: кубит = 1 число

Какова вероятность 0 или 1 в кубите?

"Память" квантового компьютера

регистры памяти обычного компьютера: строки из 0 и 1
"память" квантового компьютера - состояние системы кубит, то есть вероятность каждого из возможных комбинаций: p(00000001),p(00000010),...

Например, 1 кубит = 2 числа, 8 кубит = 2^8 = 256 чисел и разных вероятностей для всех этих чисел.

Система n кубит кодирует 2^n чисел

на лаптопе можно эмулировать работу 15 кубит
на суперкомпьютерах - 40 кубит
система из 50 кубит не может быть эмулирована классически (квантовое превосходство)

Квантовая память растет как геометрическая прогрессия.

Почему возможны квантовые вычисления?

квантовые механика имеет вероятностную природу, а нужен точный ответ:

есть важный класс задач (NP), решить которые сложно, но проверить правильность решения легко
квантовый компьютер может угадывать правильный ответ
"квантовый параллелизм"

Благодаря тому, что кубит находится в суперпозиции, система сама ищет лучший вариант с лучшей вероятностью.

Что может квантовый компьютер?

Алгоритм Шора, разложение числа на множетели (экспоненциальное ускорение) - такой компьютер может угадывать простые множители сложных чисел.
Алгоритм Гровера, поиск по базе данных (полиномиальное ускорение) -
широкий ряд оптимизационных задач (поиск положения равновесия/покоя)

Возможные области применения

Основные параметры качества

Основные типы существующих прототипов