Квантовый поиск по базе данных

Зачем нужны квантовые компьютеры

Квантовый компьютер (кк) — устройство, использующее квантовые эффекты для решения вычислительных задач. Используя свойства суперпозиции состояний и «запутанности», кк в теории могут решать некоторый класс задач, имеющий практическое значение (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(N1/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 кубитов, на классическом компьютере понадобится 2nкомплексных чисел.

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 — создали первую ионную ловушку на полупроводнике.

Поиск по сайту: