Предположим, что P = NP верно. Будет ли тогда какое-либо практическое применение для построения квантового компьютера, такое как быстрое решение определенных задач, или же любое такое улучшение будет неуместным, основываясь на том факте, что P = NP верно? Как бы вы охарактеризовали повышение эффективности, которое могло бы произойти, если бы квантовый компьютер мог быть построен в мире, где P = NP, в отличие от мира, в котором P! = NP?
Вот вымышленный пример того, что я ищу:
Если P! = NP, мы видим, что класс сложности ABC равен классу квантовой сложности XYZ ... но если P = NP, класс ABC все равно сворачивается в связанный класс UVW.
(Мотивация: мне любопытно, и я относительно новичок в квантовых вычислениях; перенесите этот вопрос, если он недостаточно продвинут.)
Ответы:
Статья Скотта Ааронсона « BQP и полиномиальная иерархия » напрямую отвечает на ваш вопрос. Если P = NP, то PH рухнет. Кроме того, если бы BQP были в PH, то в этом случае квантовое ускорение было бы невозможным. С другой стороны, Ааронсон свидетельствует о проблеме с квантовым ускорением вне PH, таким образом, такое ускорение переживет коллапс PH.
источник
Ответ однозначный да. Квантовые компьютеры определенно все еще будут полезны.
Квантовые компьютеры - это не оракулы для BQP, а устройства, которые обрабатывают квантовые состояния и могут общаться с помощью квантовых состояний. Точно так же, как способность делать недетерминированные запросы принципиально более мощна, чем способность делать чисто детерминированные запросы, независимо от статуса P против NP (и в действительности это корень разделения оракула), способность делать квантовые запросы и общаться с использованием квантовых состояний принципиально более мощным, чем чисто классический аналог.
Это приводит к преимуществам в широком спектре приложений
Помимо аргументов сложности, есть еще одна практическая причина, чтобы хотеть квантовые компьютеры. В наши дни большая часть данных, обрабатываемых на классических компьютерах, получена при зондировании мира природы (например, с помощью ПЗС в цифровой камере). Однако такие измерения обязательно отбрасывают некоторую информацию о системе, чтобы отобразить результат измерения в виде классической битовой цепочки (например, коллапсирующая пространственная суперпозиция фотонов), и не всегда ясно, какая информация позднее будет считаться наиболее важной, когда Первоначально запись данных. Поэтому разумно полагать, что способность сохранять и обрабатывать квантовые состояния напрямую, а не сворачивать их в некоторой основе перед обработкой, будет становиться все более желательной.
источник
Решение практической части.
Насколько я могу судить, достаточно мощный квантовый компьютер будет представлять практический интерес в этом случае.
источник
Есть исследования в отношении между BQP и полиномиальной иерархией PH. Например, существует проблема, относительно которой BQP не содержится в PH ( http://arxiv.org/abs/0910.4698 ), и гипотеза, которая доказывает тот же результат в нерелятивизированном мире ( http://arxiv.org /abs/1007.0305 ). См. Также проблему BosonSampling, которая заключается в выборке из вероятностного исхода фотонов, выходящих из сети светоделителя, считается классически сложной, хотя ее можно реализовать с помощью довольно простых квантовых систем, которые даже не являются универсальным квантовым компьютером (см. для статьи Ааронсон, Архипов - Вычислительная сложность линейной оптики. Это еще один намек на то, что квантовые вычисления сильнее, чем PH: действительно, если классический компьютер может эффективно решить BosonSampling с оракулом для проблемы PH, тоP#P⊆BPPPH , которые подразумевают многочлен иерархия разрушится.
В заключение, мы не знаем, какова точная мощность квантовых компьютеров, но есть результаты, предполагающие, что BQP может быть вне PH.
источник