Почему QMA должны решать проблемы, обещающие проблемы?

10

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

Связано ли это с тем фактом, что k-локальная гамильтонова задача является проблемой обетованной?

Кроме того, это приводит меня к связанному вопросу: существуют ли QMA-полные проблемы, которые по своей природе не являются «квантовыми» по природе?

cc.complexity-theory quantum-computing Генри Юн
источник
3
Я думаю, это было бы интересно, потому что QMA определяется как семантический класс, такая полная проблема дала бы синтаксическую характеристику. Проверьте связанные вопросы о синтаксических / семантических классах сложности на cstheory / Mathoverflow.
Каве
3
Более того, это явление не является специфическим для QMA, в частности. Другие семантически определенные классы, такие как MA, являются BPP, также, как известно, не имеют полных языков.
Робин Котари
1
Интересно, каковы на практике необходимые и достаточные условия для того, чтобы проблема была «не квантовой». Я предполагаю, что любая проблема, которая вызывает полностью положительное отображение ( например, является ли данная CP-карта обратимой или далеко не обратимой?) Или структура тензорного произведения ( например, имеет ли положительный полуопределенный оператор, заданный в k-локальном представлении, собственные значения меньше, чем дельта, или все они существенно больше дельты?) были бы примерами подозрительно квантовых проблем, независимо от того, представлены ли они в терминах квантовых каналов / эволюции или пространства состояний совокупной системы ...
Ниль де Бодрап,

Ответы:

6

По второму вопросу: http://arxiv.org/abs/0905.4755v2 дает классическую QMA-полную задачу на собственные значения, связанную цепями Маркова.

Мартин Шварц
источник