Квантовые vs Вероятностные алгоритмы

[jozef]

Скажите пожалуйста, в чём принципиальная особенность квантовых вычислений, что дают операции (действия унитарных операторов) на кубитах? Существует ведь в математике класс задач, которые решаются вероятностными методами. Разве это не одно и тоже? Или я чего-то не понимаю? Не мог нигде найти чёткого описания отличий. Спасибо.

[Ilia_]

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

[jozef]

Вот что есть такое кубит? Если верить wikipedia, то кубит есть простая квантовая система состояние которой описывается в вычислительном базисе и в общем случае представляет собой такой вид:

$| \psi \rangle = \alpha |0 \rangle + \beta |1 \rangle$

Здесь достаточно хорошо видно, что при ненулевых $\alpha$ и $\beta$ мы имеем ту самую суперпозицию о которой Вы говорите. С этим всё понятно. На эти коэффициенты накладывается условие нормировки:

$| \alpha |^2 + | \beta |^2 = 1$

При этом эти квадраты интерпретируются как вероятности нахождения системы (по результату редукции состояния кубита) в $ |0 \rangle$ или $ |1 \rangle$. Получается ведь, что если не обращать внимание на фазу $\alpha$ и $\beta$ (они комплексные), то из условия нормировки из одной вероятности однозначно можно определить другую. Тогда кубит характеризуются лишь одной вероятностью. Что эквивалентно к примеру вероятностной логике. Правда не уверен, что мы вправе не учитывать фазу. Но на что она влияет, если мы производим операции на отдельном кубите и в конце при измерении результата фаза не учитывается?

[fizeg]

jozef
Я думаю вы прочувствуете всю разницу, если почитаете например про алгоритм Дойча-Джоза дающий детерминированный ответ.

[jozef]

fizeg в сообщении #652658 писал(а):

jozef
Я думаю вы прочувствуете всю разницу, если почитаете например про алгоритм Дойча-Джоза дающий детерминированный ответ.

Я правильно понимаю, что Вы хотите сказать, что вся особенность квантовых вычислений заключается только лишь в возможности существования перепутанных состояний (наличию корреляций между состояниями подсистем) квантовых систем? Значит ли это, что с одиночными квантовыми системами, например такими как кубит, можно вполне ограничиться вероятностной логикой?

[fizeg]

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

Уже то, что на входе кубит совсем не эквивалентно тому, что на входе с какой-то вероятностью 0, а с какой 1.

Вот смотрите, есть допустим функция
$F(|0\rangle)=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle),F(|1\rangle)=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$
Для изолированного кубита (т.е. он ни с чем не спутывается, не измеряется) она должна быть унитарной и линейной. Тогда
$F\Bigl(\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\Bigr)=|0\rangle,F\Bigl(\frac{1}{\sqrt{2}}(|1\rangle-|0\rangle)\Bigr)=|1\rangle$

Подавая 0, вы получаете 50% времени 0 и 50% времени 1. Тоже самое если подаете 1. Но как вы подадите на вход $|0\rangle+|1\rangle$? Подавая 50% времени 0 и 50% времени 1 вы не будете всегда получать 0

[jozef]

fizeg спасибо за пример. Довольно наглядно.

Таким образом можно резюмировать особенности:

• Возможность существования суперпозиции чистых квантовых состояний
• Возможность существования перепутанных состояний подсистем некоторой сложной квантовой системы (пример: несколько кубит)

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

[SergeyGubanov]

jozef в сообщении #652426 писал(а):

Разве это не одно и тоже?

Разница во времени затрачиваемом на компьютерное вычисление.

Как бы, есть надежда, что на квантовом компьютере, если он будет создан, можно будет быстро вычислять некоторые задачи, которые на обычном компьютере имеют сложность $O(2^N)$ операций, то есть на практике при большом $N$ за разумное время невыполнимы.

[jozef]

SergeyGubanov в сообщении #652740 писал(а):

jozef в сообщении #652426 писал(а):

Разве это не одно и тоже?

Разница во времени затрачиваемом на компьютерное вычисление.

Как бы, есть надежда, что на квантовом компьютере, если он будет создан, можно будет быстро вычислять некоторые задачи, которые на обычном компьютере имеют сложность $O(2^N)$ операций, то есть на практике при большом $N$ за разумное время невыполнимы.

То что квантовые вычисления на некоторых задачах дают полиномиальный прирост в производительности (в смысле снижают требовательность к ресурсу, например к времени) я в курсе. Мне не были понятны некоторые сравнительные точки теории квантовых вычислений и вероятностной логики. Но вопрос уже снят. Хотя есть ещё интересные для меня пункты, которые можно обсудить: природа редукции состояния кубита (причина вероятностей, каким образом происходит выбор, причина случайности) или каким образом можно снизить влияние декогеренции в сложных квантовых системах...

[fizeg]

jozef
Вы упомянули декогеренцию, но собственно с современным представлением о декогеренции знакомы? Я имею в виду то что называют envieronmental decoherence или часто просто quantum decoherence. Квантовый объект спутывается со средой, в результате чего его матрица плотности теряет недиагональные элементы (т.е. от чистого квантового состояния переходит к смешанному - разные чистые состояния с некоторой вероятностью в классическом смысле) Ее удалось продемонстрировать (что впервые сделал один нобелей по физике этого года), в то время как, насколько я знаю, нет на настоящий момент никаких оснований считать, что есть еще какие-то причины (а они однозначно потребовали бы модификации квантовой теории)

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

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

[jozef]

fizeg в сообщении #652754 писал(а):

jozef
Вы упомянули декогеренцию, но собственно с современным представлением о декогеренции знакомы? Я имею в виду то что называют envieronmental decoherence или часто просто quantum decoherence. Квантовый объект спутывается со средой, в результате чего его матрица плотности теряет недиагональные элементы (т.е. от чистого квантового состояния переходит к смешанному - разные чистые состояния с некоторой вероятностью в классическом смысле) Ее удалось продемонстрировать (что впервые сделал один нобелей по физике этого года), в то время как, насколько я знаю, нет на настоящий момент никаких оснований считать, что есть еще какие-то причины (а они однозначно потребовали бы модификации квантовой теории)

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

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

Я слышал о квантовой декогеренции, как о процессе перепутывания квантовой системы с окружением (сказать о том, что я знаком с этой теорией - слишком громко, поскольку только начал работать в этом направлении). Честно говоря, я только об этой модели и слышал. Знакомиться мне с данным явлением помогает вот эта книга. Когда я упомянул о снижение влияния декогеренции в системах, я в первую очередь думал о том, что возможно существуют какие-нибудь развитые методы изоляции системы, либо какие-нибудь хитрости не позволяющие системе потерять "информацию" о корреляциях (например внесение некоторой избыточности) или какие-нибудь принципиально особенные системы, как например энионы (квантовый эффект Холла). А что Вы тут понимаете под шумами? Ещё я никогда не слышал о системах, которые с ростом температуры не ускоряют декогеренцию (если Вы не имеете в виду что-то вроде энионов). А чтобы не говорить о чуши вероятно лучше больше считать, а не говорить