В теории сложности, QMA (от ) — это квантовый аналог NP в классической теории сложности и аналог MA в вероятностной. Он связан с BQP также, как NP связан с P, или MA связан с BPP.
Неформально — это множество языков для принадлежности к которым есть полиномиальное квантовое доказательство, принимаемое полиномиальным по времени квантовым алгоритмом с высокой вероятностью.
Определение Язык L принадлежит если существует полиномиальный по времени квантовый алгоритм V и многочлен p(x) такой, что: , существует квантовое состояние такое, что вероятность того, что V примет больше чем . , для любого квантового состояния , вероятность того, что V примет меньше чем . где квантовое состояние с p(x) кубитами.
Класс определим как класс равный . На самом деле константы не важны и класс не изменится, если и произвольные константы такие, что больше . Также для любых многочленов и , верно .
Связанные классы (или ) название читается как квантовый классический Мерлин Артур (или Мерлин Квантовый Артур), является аналогом QMA, но доказательство (присылаемое Мерлином) должно быть обычной строкой. Неизвестно совпадают ли QMA и QCMA.
— это класс языков распознаваемых квантовыми интерактивными протоколами с полиномиальным временем и k раундами, является обобщением QMA в котором разрешается передавать не одно сообщение, а k. Из определения следует, что QMA совпадает с QIP(1). Про QIP(2) известно, что он содержится в PSPACE.
— это класс языков из QIP(k), где k разрешается быть полиномиальным от числа кубит. Известно, что QIP(3) = QIP. Так же известно, что QIP = IP.
— это класс языков принимаемых квантовым протоколами Мерлин Артур с идеальной полнотой.
Отношения с другими классами Про QMA известно, что
Первое вложение следует из определения NP. Следующие два включения верны из-за того, что верифаеры становятся более сильными. Утверждение о том, что QMA содержится в PP был доказан Алексеем Китаевым и Джоном Ватрусом. PP также содержится в PSPACE.
Неизвестно какие из этих включений строгие.
Примечания
Литература «Algorithms for quantum computation: discrete logarithms and factoring» P.W. Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700
Ссылки А. Х. Шень, М. Н. Вялый, Курс лекций «Классические и квантовые вычисления». Лекция 8: Определение квантового вычисления. Примеры // Интуит.ру, 15.03.2007
Категория:Классы сложности