Как квантовые вычисления изменят программирование? [закрыто]

Чем отличается программирование квантового алгоритма? Как бы выглядел язык, подобный Си, если бы он был разработан для кубитов? Изменятся ли типы?

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

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

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

Проверьте алгоритм поиска Гровера .

ВСТАВЛЕНО, чтобы показать основную работу алгоритма Гровера. Предположим, есть проблема с поиском. Возможные ответы - 0, 1, 2 и 3, но правильный ответ - 2. Таким образом, квантовый компьютер помещается в суперпозицию всех четырех состояний, и он проходит через последовательность шагов, чтобы увидеть, какое из них является правильным, и инвертирует его амплитуду, как черные точки и стрелки ниже:

Вы можете видеть, что стрелка 2 была инвертирована внутри машины, но нет никакого способа сказать это снаружи, потому что снаружи видны только вероятности, которые являются квадратами амплитуд , а в квадрате все они равны.

Однако амплитуды имеют среднее значение, обозначенное красной линией, и компьютер может выполнить последовательность шагов, которая инвертирует каждую амплитуду относительно среднего значения . Когда это будет сделано, амплитуды и вероятности перейдут в состояние 2, правильный ответ ! Итак, если машина наблюдается, состояние 2 светит вперед.

Это не совсем так просто. Как правило, требуется несколько циклов машины, вперед и назад, инвертируя в конце каждого цикла, чтобы максимизировать вероятность правильного ответа. Кроме того, нужно позаботиться о том, чтобы не делать это больше, чем это количество раз, потому что оно может так же легко повернуть себя вспять.

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

Разве это не весело?

Меня лично интересовало, как это можно применить для проверки правильности программного обеспечения. Теперь мы тестируем программное обеспечение, бросая на него кучу тестовых входных данных и (чтобы быть слишком простым), проверяя, попадает ли оно в Assert. В квантовом компьютере может быть возможно запустить его параллельно с более плотным набором входов и посмотреть, не попал ли какой-либо из этих случаев в Assert.

Например, если входные данные для алгоритма были 128 байтов или 1024 бит, есть 2 ^ 1024 или 10 ^ 308 возможных различных входов. Невозможно проверить такое количество входов на обычном компьютере, но квантовый компьютер может попробовать их все параллельно.

Как бы выглядел язык, подобный Си, если бы он был разработан для кубитов? Изменятся ли типы?

Это было бы так радикально отличаться, чтобы быть непостижимым, как C.

Основная проблема (насколько я понимаю) состоит в том, что квантовые вычисления не работают в должной форме: «сделай то, потом то, потом это другое». Попытка заставить C сделать это в «процессоре» квантового компьютера будет, если не невозможно, дико неэффективна.

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

Обратите внимание, что существуют некоторые алгоритмы для квантовых компьютеров, хотя устройства для их запуска не существуют. Алгоритм Саймона, например.

Чтобы максимально эффективно использовать квантовый компьютер, нужно уметь работать со входами и выходами, которые являются состояниями квантового регистра, для которого действительно нет классического аналога. Говоря о своем многолетнем опыте в области квантовой информации, я должен предупредить вас, что ни у кого на самом деле нет хорошей интуиции для этого, кроме абстрактной математики алгебр C *, и мне говорят, что даже эта интуиция оказывается неадекватной если вы начнете интересоваться теорией относительности.

Класс задач, которые эффективно разрешимы на квантовом компьютере, известен как BQP для ограниченного квантового полинома. Это квантовая версия BPP, и вы можете найти больше информации в этом документе: http://www.scottaaronson.com/papers/bqpph.pdf

Как раз вчера вечером исследователь квантовых алгоритмов сказал мне, что есть очень важная проблема, которая является BQP-полной: решение линейной системы из N уравнений. Классически это разрешимо за O (N) шагов с гауссовым исключением. Алгоритм Harrow-Hassidim-Lloyd ( http://arxiv.org/abs/0811.3171 ) решает его в полилоге (N), если вы готовы принять ответ, решение которого закодировано как квантовое состояние. Если вы хотите в полной мере использовать квантовый компьютер, вам, следовательно, необходимо иметь тип, соответствующий состоянию квантового регистра.

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

Имейте в виду, что мы очень долго не владели языком квантового программирования, потому что мы находимся на очень примитивной стадии исследования квантовых вычислений. Запрашивать квантовый C прямо сейчас - все равно что идти к Алану Тьюрингу и просить его спроектировать Python. У нас даже нет квантовой версии вакуумной трубки!