Проблемы без известного квантового преимущества

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

Прежде всего, я думаю, что вычисление расстояния редактирования - это то, для которого самый быстрый из известных квантовых алгоритмов кажется самым быстрым из известных классических. Более условно, я бы также предложил сортировку как еще одну проблему, для которой нет известного квантового ускорения (по сравнению с самым быстрым известным алгоритмом RAM слова с единичной стоимостью).

Хотя я не хочу устанавливать жесткие ограничения, меня особенно интересуют проблемы с NP и / или проблемы, у которых нет известного эффективного классического решения.

Следуя предложению Хуана Бермехо Веги, вот некоторые дополнительные пояснения. Меня интересуют проблемы в NP, для которых в настоящее время вообще нет известного большого преимущества в сложности если вы используете квантовый компьютер. $O$

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

ds.algorithms quantum-computing big-list Lembik
источник

Сложность в том, что нет ускорения в общем времени выполнения или что языковой класс закрыт под операцией?

Райан

@ Райан Я не имел в виду ускорение в общем времени бега. Спасибо за вопрос.

Лембик

Что-нибудь уже полиномиальное время. :-)

кастерма

@kasterma Я не думаю, что это правильно. Существует множество временных проблем, для которых в настоящее время наблюдается квантовое ускорение.

Лембик

Я бы предложил уточнить этот вопрос, указав, что (а) речь идет о «нет доказуемого квантового преимущества» по сравнению с «нет известного квантового преимущества»; (б) речь идет об экспоненциальном или полиномиальном ускорении (в отношении проблем, не связанных с P или BPP); и (c) разрешены ли другие типы ускорений (например, логарифмические ускорения по сравнению с проблемами в пределах P или BPP).

Хуан Бермехо Вега

Ответы:

Это не в NP, а сортировка на основе сравнения. нижняя граница информация Теоретико. $\Omega(n \log n)$

Тайсон Уильямс
источник

Оценка, являющаяся теорией информации, не показывает, что квантовые алгоритмы не могут ее преодолеть. (Рассмотрим алгоритм Гровера .)

$\:$

$\;\;\;\;$

@RickyDemer Я не уверен, что вы думаете. Информационно-теоретические аргументы остаются вне зависимости от модели вычисления. Для неструктурированного поиска вход представляет собой массив из элементов и целевого элемента , а вывод представляет собой индекс такой, что (который, я полагаю, существует для простоты). Поскольку каждый бит изучается по одному биту, теория информации говорит, что любой алгоритм должен делать запросов. Алгоритм Гровера при запросах далеко не привязан к этой границе, пусть и меньше ее.

A

$A$

n

$n$

x

$x$

i

$i$

A [i] = x

$A[i] = x$

\log n

$\log n$

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

Тайсон Уильямс

Насколько я понимаю, аргументы, основанные на энтропии / подсчете, не всегда справедливы для квантовых алгоритмов, поскольку они касаются вероятностных распределений, а не суперпозиций квантовых состояний. упорядоченный поиск нижней границы, например , была FOCS статьи Ambainis и сортировка нижней границы также , кажется, требуют некоторой работы arxiv.org/abs/quant-ph/0102078 . Таким образом, кажется, что ваше заявление верно, но не так быстро, как вы предлагаете.

Ω (\log n)

$\Omega(\log n)$

Сашо Николов

@SashoNikolov Проблема неструктурированного поиска, как я ее определил для Рики, не давала возможность потерпеть неудачу. Аргумент, который я привел для этой проблемы. Нижняя граница, данная Амбайнисом в FOCS (которую я не смог найти), вероятно, относится к более общей проблеме, которая требует успеха только с небольшой вероятностью. То же самое касается проблемы сортировки и бумаги arXiv, на которую вы ссылаетесь.

Тайсон Уильямс

@SashoNikolov: Я согласен с тем, что вы написали. Информационно-теоретические границы вида, описанного Тайсоном, где «один бит выучен одним запросом» не всегда верны для кванта. Рассмотрим проблему Бернштейна-Вазирани, где выход задачи равен битам, и, таким образом, классическая машина должна сделать запросов по теоретико-информационным причинам, но квантовый компьютер может сделать это с 1 запросом.

n

$n$

n

$n$

Робин Котари

Недавно эта статья в SODA 2018 демонстрирует алгоритм аппроксимации с постоянным коэффициентом для редактирования расстояния в квантовых компьютерах с субквадратичным временем. Обратите внимание, что пока еще не известен алгоритм аппроксимации с постоянным множителем для редактирования расстояния в классических компьютерах с субквадратичным временем. Более того, считается, что в классических компьютерах такого алгоритма не существует.

Mohemnist
источник

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

Лембик

@Lembik Вы были правы. Бумага как - то де-quantumized предыдущего документа и нашла алгоритм аппроксимации коэффициента постоянная для редактирования расстояния в subquadratic сложности времени. Смотрите этот пост в блоге для получения дополнительной информации.

Могемнист