Моя любимая теорема в теории сложности - это теорема об иерархии времени. Однако это было сделано в 1965 году.
Тогда я хотел узнать, есть ли что-нибудь подобное для квантовых вычислений.
Кроме того, если нет, что люди / группы работают в этом направлении!
Ответы:
Более свежая цитата для теорем иерархии времени - «Общая иерархия времени для семантических моделей с одним небольшим советом» Дитера ван Мелкебека и Константина Первышева, которую вы можете получить на веб-странице Дитера. Методы там дают временную иерархию с 1 небольшим советом для «любой разумной» семантической модели вычислений, включая квантовые алгоритмы.
Кроме того, обычно относительно легко получить иерархию для задач обещания, вычисляемых семантическими моделями. Задача обещания требует только того, чтобы алгоритм «хорошо себя вел» (например, имел ограниченную ошибку) на некоторых входах - тех, которые выбраны, чтобы быть частью проблемы обещания. Для входов, не выбранных в качестве части обещания, алгоритм может вести себя произвольно (например, не иметь ограниченной ошибки). Иерархия проблем обещаний - это фольклорный результат; Дитер ван Мелкебек и Джефф Кинн (я), которые вы можете получить на веб-странице Дитера или на моей веб-странице, подтверждают настройки BPP в разделе «Результаты пространственной иерархии для рандомизированных и других семантических моделей». Это должно относиться и к квантовым алгоритмам.
Таким образом, ответ таков: теоремы приличной иерархии известны для квантовых алгоритмов, которые либо получают 1 совет, либо могут игнорировать проблемные входные данные. Некоторые из методов для этих результатов основаны на свойствах рандомизированных алгоритмов. Было бы интересно попытаться использовать свойства квантовых алгоритмов в области теорем иерархии.
Несколько связанной областью, где есть результаты, специфичные для квантовых алгоритмов, является область нижних границ пространства-времени. Есть опрос Дитера ван Мелкебека: «Обзор нижних границ для удовлетворения и связанных с этим проблем».
источник
Ответ - нет. У нас даже нет теоремы иерархии времени для вероятностного полиномиального времени с ограниченной ошибкой (т. Е. BPTIME). Детерминированные и недетерминированные теоремы иерархии времени имеют аргумент диагонализации, который, похоже, не работает для семантических классов. Вот почему у нас нет строгих теорем иерархии для семантических классов.
Лучший результат, о котором я знаю, - это теорема об иерархии для BPTIME с одним небольшим советом: Fortnow, L .; Santhanam R. (2004). Теоремы об иерархии для вероятностного полиномиального времени .
Я не знаю ни одной группы, работающей над теоремой квантовой иерархии времени. Я предполагаю, что это потому, что кажется, что проблема иерархии BPTIME проще, поэтому исследователи вместо этого решат эту проблему.
(Несколько связанные вопросы: есть ли синтаксическая характеристика для BPP, BQP или QMA в MathOverflow и классах семантической и синтаксической сложности в cstheory.)
источник
Недетерминированные квантовые классы, ограниченные временем и пространством, - это классы, в которых языки представляют собой наборы строк, принимаемых квантовыми машинами Тьюринга, работающими в соответствующих границах с ненулевой вероятностью.
В разделе 8 « Доказательство силы поствыбора » мы показываем, что существуют жесткие иерархии для недетерминированных квантовых классов, ограниченных временем и пространством.
источник