Зачем нужны квантовые компьютеры
Квантовый компьютер (кк) — устройство, использующее квантовые эффекты для решения вычислительных задач. Используя свойства суперпозиции состояний и «запутанности», кк в теории могут решать некоторый класс задач, имеющий практическое значение (NP-полные задачи), намного быстрее, чем любые классические компьютеры.
Квантовая система — физическая система, обладающая квантовыми свойствами, и могущая пребывать в 1 из 2х состояний (самая простая - электрон со спином вверх и вниз). Отличительная особенность: к. система может пребывать в состоянии 0, 1, и суперпозиции этих двух состояний — т. е. в обоих одновременно, до измерения. Благодаря этому и достигается ускорение — вычисление идёт одновременно по всем возможным путям.
Теория вычислений
Классический детерминистический компьютер (Turing 1936; McCullogh and Pitts 1943):
Данные представлены битами (0,1).
Машина Тьюринга: лента с записанными символами, и вдоль неё ездит по определённым правилам считывающе\записывающая головка. Главные операции - линейная последовательность, ветвление, условный переход вперёд-назад (покрывает ветвление, и цикл, и рекурсию).
Например, для 2-битного регистра, состояние компьютера в любой момент времени будет одной из 22=4 2-битных строк: 00, 01, 10, 11.
Квантовый компьютер (David Deutsch 1985):
Может находиться в один момент времени во всех состояниях, и каждое получится при измерении с некоторой вероятностью. Состояние описывается 4-мерным вектором (a, b, c, d) – кетом: a |00> + b |01> + c |10> + d |11>. Коэффициенты — комплексные числа, и сумма квадратов их величин должна быть равна 1: |a2|+|b2|+|c2|+|d2|=1.
Бра-кет: Запись <y1,...ym| - это бра; |x1,..., xn> - это кет; <y1,...ym|x1,..., xn> — это бра-кет - обобщение произведения векторов в комплексном векторном пространстве, или Гильбертовом пространстве.
Применение, требования, проблемы
Применение:
Взлом криптографии.
Алгоритмы шифрования RSA, и на эллиптических кривых - основаны на задаче разложить большое число на простые множители. Классические алгоритмы делают это за время O((1+ε) n). Квантовый алгоритм Шора — за O((log N)2(log log N)(log log log N)).
Но есть и криптосистемы, основанные на других сложных задачах, для которых не известно ни классического ни квантового эффективного алгоритма (например, McEliece cryptosystem, Lattice-based cryptosystems).
Моделирование квантовых физических и химических процессов
Вычислительная сложность задачи моделирования системы из нескольких микрочастиц растёт экспоненциально с увеличением числа частиц. Современные классические алгоритмы становятся малопригодны уже для системы из 10 частиц.
Не доказано строго математически, что достаточно быстрый классический алгоритм для этой задачи невозможен — но это маловероятно.
Алгоритм Залки—Визнера моделирует поведение системы n квантовых частиц за почти линейное время: применяя оператор гамильтониана (суммы кинетической и потенциальной энергии системы) к уравнению Шрёдингера, мы получаем результирующее состояние системы.
Квантовый поиск по базе данных.
Алгоритм Гровера даёт квадратичное ускорение по сравнению с любым классическим алгоритмом: O(N 1/2) против O(N) для классического алгоритма — и быстрее доказанно невозможно.
Также алгоритм Гровера даёт квадратичное ускорение для решения прямым перебором любой NP-полной задачи (Nondeterministic Polynomial – задачи, решение которых проверяемо за полиномиальное время. Например, задача коммивояжёра).
4) Квантовое сверхплотное кодирование — метод, позволяющий передать два бита классической информации с помощью лишь одного кубита, используя явление квантовой сцепленности.
Пусть Алиса хочет отправить классическую информацию Бобу, используя кубиты вместо битов. Алиса кодирует классическую информацию состоянием кубита, и отправляет Бобу. Боб извлекает информацию, производя измерение состояния кубита. Какой объем классической информации можно передать, используя один кубит? Согласно теореме Холево, неортогональные состояния невозможно различить с достоверностью, так что Алиса сможет передать 1 бит. Т.е. тут кубиты не дают выигрыша. Но если Алиса и Боб имеют в своем распоряжении запутанное состояние пары кубитов (один у Алисы, другой у Боба), то можно передать не 1, а 2 бита классической информации, используя 1 кубит (через одно из преобразований в состояние Белла). Подобное удвоение «эффективности» передачи информации и носит название квантового сверхплотного кодирования.
5) Квантовая криптография (Беннет и Брассар, 1989) — использует факт, что измерение квантового состояния меняет его. Таким образом, если Ева перехватила и прослушала (измерила) сообщение от Алисы к Бобу — то когда Алиса и Боб сравнят свои результаты, то по уровню их различия смогут определить, с какой вероятностью было промежуточное измерение.
Таким образом, с вероятностью 1 — 2-k (где k — число сравненных битов) канал не прослушивался.
Проблема та же — декогеренция. Что ограничивает расстояние передачи. Рекорд расстояния - 87 км, со скоростью 1б/с и уровнем ошибок 1,4 %. В другом опыте, с регулярной автоматической подстройкой — добились уровня ошибки 0,5 % при скорости 5 кбит/с для 1км-канала.
Есть уже схемы как Еве обмануть детекторы Боба. Но есть и контрмеры к этим схемам.
Требования к практически применимому кк:
· физически расширяемый, чтобы увеличивать число кубитов
· инициализировать кубиты на произвольные значения
· вентили, работающие быстрее времени декогеренции
· универсальный набор вентилей
· кубиты, с которых легко считать информацию
Проблемы:
1) Любой квантовый компьютер можно смоделировать на классическом компьютере, при достаточном времени и ресурсах (т. е. кк не нарушают Тезис Чёрча-Тьюринга). Чтобы описать состояние n кубитов, на классическом компьютере понадобится 2 n комплексных чисел.
2) Пока ещё на практике не сделали кк, который бы решил задачу быстрее, чем классический компьютер. И возможность получения квантового ускорения для произвольного классического алгоритма является большой редкостью. Более того, пока даже нет кк, который вообще решал бы сколь-нибудь значимую практически задачу. Те что есть — невероятно дороги, сложны в использовании, хрупки, и делаются вручную каждый раз, под конкретную задачу (по сути, годятся только для демонстрации принципиальной возможности квантовых вычислений).
(Замечание: в 2011 году появился D-Wave One — первый коммерческий кк. Он основан на адиабатическом кк. Но до сих пор ведутся споры, является ли он действительно квантовым, и даёт ли он ускорение, по сравнению с классическим)
3) Квантовая декогеренция: работа квантового компьютера целиком опирается на его пребывание в запутанном состоянии кубитов. Проблема же — запутанность очень быстро декогерирует (исчезает) при взаимодействиях с внешней средой. Изоляция кк от всех внешних воздействий (механических, тепла, света) — сложнейшая инженерная задача. Пока что, в существующих системах время декогеренции составляет от наносекунд до секунд при сверхнизких температурах (вплоть до 20 mK).
Если величина ошибок достаточно мала, предлагается использовать к. коррекцию ошибок, вносящую поправки на декогеренцию — это позволит время вычисления больше, чем время декогеренции. На данный момент, величина ошибки для каждого вентиля принимается 10−4 (вентиль должен выполнить работу за 1/10000 времени декогеренции системы).
Однако, механизм коррекции ошибок требует значительного увеличения количества кубитов. Например, для алгоритма Шора увеличение не слишком большое (N2 возрастает до N3). Так, для 1000-битного числа потребуется 104кубитов без коррекции ошибок, и 107с нею (время работы также составит 107 шагов).
Принципиально иной подход к проблеме стабильности-декогеренции предлагает топологический кк.
История развития:
1981 — Ричард Фейнман предложил первую идею КК. Томмасо Тоффоли предложил универсальный вентиль Тоффоли.
1984 — Чарльз Беннетт и Жиль Брассар предложили модель квантовой криптографии на открытых ключах.
1985 — Девид Дойч описал универсальный КК, и к. машину Тьюринга.
1994 — Питер Шор описал алгоритм Шора разложения больших чисел на множители.
1996 — Лов Гровер описал к. алгоритм поиска по базе данных.
1997 — Алексей Китаев описал принципы топологического КК, чтобы решить проблемы декогеренции.
1998 — первая экспериментальная демонстрация к. алгоритма: 2-кубитный КК решает задачу Дойча.
2001 — продемонстрировали работу алгоритма Шора, чтобы разложить 15=3x5. Эммануэль Книлл описал принципы оптического КК на линейных элементах.
2006 — в университете Арканзаса создали первый КК на к. точках.
2009 — создали первую ионную ловушку на полупроводнике.