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

33

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

MaiaVictor
источник
Примечание: я не уверен, если это правильный вопрос. Извините, если это не так.
MaiaVictor
4
Я думаю, что это. Опять же, я не очень хорошо знаю правила этого сайта. И у меня не очень хороший ответ на этот вопрос, но я знаю об этом алгоритме, который можно было бы использовать для более эффективного разложения
Джон Дэвис,
3
Я думаю, что хотя эта тема все еще находится в научном исследовании, основы гипотетического квантового компьютера хорошо известны AFAIK, поэтому этот вопрос должен отвечать специалист по предметной области (а я - нет). Поэтому я голосую, чтобы не закрывать его.
Док Браун

Ответы:

17

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

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

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

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


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

введите описание изображения здесь

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

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

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

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

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


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

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

Майк Данлавей
источник
2
Проверка алгоритма поиска Гровера ... О Боже! Я не был готов к этому!
Филипп
1
@Philip: я знаю, что математика довольно утомительна, но ключевая идея - это вращение вокруг среднего, которое приводит к переводу вероятности в состояние ответа. Затем вы бежите назад к началу, бежите вперед и делаете это снова, определенное количество раз. Затем, если вы сделаете наблюдение, вы максимизируете вероятность увидеть состояние ответа.
Майк Данлавей
Видишь ли, это действительно не так плохо, когда ты так говоришь. Думаю, я не знаком с обозначениями, которые они используют, или с квантовыми цепями. Страница квантовых алгоритмов также пугающая. Я считаю, что Qubit - это то, с чего нужно начать. (У простой википедии есть страница о компьютерах Quantum , но она может использовать некоторые работы)
Филипп
@Philip: Предположим, у вас есть таблица с 1024 записями, поэтому для ее индексации требуется 10 бит. У вас есть 10-битный регистр, и он имеет 1024 возможных состояния. Итак, вы создаете юниверс, в котором регистр равен 0, другой, в котором он равен 1, до 1024 параллельных юниверсов. Тогда квантовые «инструкции» действуют на все это параллельно. У каждой вселенной есть «вектор амплитуды», величина которого является ее вероятностью, но у нее также есть направление, и этим манипулируют. Поскольку коллекция из 1024 векторов имеет ненулевой средний вектор, вращение делает один больше, остальные меньше.
Майк Данлавей
Я физик-реформатор, и я отклонил этот ответ, потому что он вводит в заблуждение. 1) квантовые алгоритмы часто бывают особенно (асимптотически) быстрыми - алгоритм поиска Гровера работает в O (sqrt (n)), тогда как лучшее, что может сделать классический компьютер, - это O (n). Если бы квантовые компьютеры не были асимптотически быстрее, они были бы не очень интересны. Аппаратное обеспечение может быть медленным, но это не вина алгоритмов!
Бенджамин Ходжсон
7

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

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

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

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

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

Telastyn
источник
ELI5 для квантового алгоритма было бы здорово.
MaiaVictor
3

Чтобы максимально эффективно использовать квантовый компьютер, нужно уметь работать со входами и выходами, которые являются состояниями квантового регистра, для которого действительно нет классического аналога. Говоря о своем многолетнем опыте в области квантовой информации, я должен предупредить вас, что ни у кого на самом деле нет хорошей интуиции для этого, кроме абстрактной математики алгебр 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. У нас даже нет квантовой версии вакуумной трубки!

ядро
источник