Вопрос по поводу квантовых алгоритмов.

[swarog46]

Добрый вечер,
В универе читают курс по квантовой криптографии и так вскользь упомянули что некоторые квантовые алгоритмы работают существенно быстрее чем такие же классические(Дейкстра, Гровер).
При этом в доказательствах вычислительной сложности используется та же $O$ и $\Theta$ символика что и для доказательства вычислительной сложности классических алгоритмов.
Вопрос в том, что действительно ли корректно использовать для квантовых алгоритмов О-символику?
И соответственно является ли квантовый компьютер Машиной тьюринга?

[Xaositect]

swarog46 в сообщении #785816 писал(а):

Вопрос в том, что действительно ли корректно использовать для квантовых алгоритмов О-символику?

O-символику можно использовать для чего угодно. Главное, понимать, что именно считается (может считаться количество кубитов, может - количество гейтов)

swarog46 в сообщении #785816 писал(а):

И соответственно является ли квантовый компьютер Машиной тьюринга?

Нет. Квантовые модели вычислений обычно рассматривают неуниформные. Хотя какие-то квантовые аналоги машины Тьюринга тоже есть.

[Neos]

Считается, что квантовый компьютер может решить задачу даже тогда, когда нет эффективного алгоритма. К примеру, проверка числа на "простоту" производится с помощью "решета Эратосфена", который не относится к эффективным алгоритмам. Но можно использовать вероятностные методы многократно, и они должны почти точно ответить, является ли число простым или нет. Это одно из объяснений эффективности квантовых вычислений. Поскольку квантовый компьютер - это в некотором роде вероятностная машина. Хотя машину Тьюринга никто не отменял.

[swarog46]

Xaositect
В случае алгоритма Гровера говорят что он работает быстрее чем любой другой поиск на множестве в $\sqrt{N}$ раз. То есть сравнивается с обычным алгоритмом поиска, работающим за $O(N)$. Корректно ли такое сравнение?

[swarog46]

Xaositect
Что вы имеете в виду под неуниформными?

[Xaositect]

swarog46 в сообщении #785858 писал(а):

В случае алгоритма Гровера говорят что он работает быстрее чем любой другой поиск на множестве в $\sqrt{N}$ раз. То есть сравнивается с обычным алгоритмом поиска, работающим за $O(N)$. Корректно ли такое сравнение?

Да, если четко понимать предположения. Во-первых, функция проверки ("база данных") нам дается в виде блока, который мы можем использовать. Соответственно, нельзя просто взять классическую базу данных и подключить ее к квантовому компьютеру. Во-вторых, алгоритмы рассматриваются последовательные, то есть в классическом случае не разрешается взять и параллельно перебрать по $\sqrt{N}$ вариантов на $\sqrt{N}$ параллельных блоках.

swarog46 в сообщении #785874 писал(а):

Что вы имеете в виду под неуниформными?

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