QMA
В теории сложности, QMA — это квантовый аналог NP в классической теории сложности и аналог MA в вероятностной. Он связан с BQP также, как NP связан с P, или MA связан с BPP.
Неформально — это множество языков для принадлежности к которым есть полиномиальное квантовое доказательство принимаемое полиномиальным по времени квантовым алгоритмом с высокой вероятностью.
Содержание
Определение
Язык L принадлежит <math>\mbox{QMA}(c,s)</math> если существует полиномиальный по времени квантовый алгоритм V и многочлен p(x) такой, что:[1][2]
- <math>\forall x \in L</math>, существует квантовое состояние <math>|\psi\rangle</math> такое, что вероятность того, что V примет <math>(|x\rangle, |\psi\rangle)</math> больше чем <math>c</math>.
- <math>\forall x \notin L</math>, для любого квантового состояния <math>|\psi\rangle</math>, вероятность того, что V примет <math>(|x\rangle, |\psi\rangle)</math> меньше чем <math>s</math>.
где <math>|\psi\rangle</math> квантовое состояние с p(x) кубитами.
Класс <math>\mbox{QMA}</math> определим как класс равный <math>\mbox{QMA}({2}/{3},1/3)</math>. На самом деле константы не важны и класс не изменится, если<math>c</math> и <math>s</math> произвольные константы такие, что <math>c</math> больше <math>s</math>. Также для любых многочленов <math>q(n)</math> и <math>r(n)</math>, верно
- <math>\mbox{QMA}\left(\frac{2}{3},\frac{1}{3}\right) =\mbox{QMA}\left(\frac{1}{2}+\frac{1}{q(n)},\frac{1}{2}-\frac{1}{q(n)}\right)=\mbox{QMA}(1-2^{-r(n)},2^{-r(n)})</math>.
Связанные классы
<math>\mbox{QCMA}</math> (или <math>\mbox{MQA}</math> [2]) название читается как квантовый классический Мерлин Артур (или Мерлин Квантовый Артур), является аналогом QMA, но доказательство (присылаемое Мерлином) должно быть обычной строкой. Неизвестно совпадают ли QMA и QCMA.
<math>\mbox{QIP}(k)</math> - это класс языков распознаваемых квантовыми интерактивными протоколами с полиномиальным временем и k раундами, является обобщением QMA в котором разрешается передавать не одно сообщение, а k. Из определения следует, что QMA совпадает с QIP(1). Про QIP(2) известно, что он содержится в PSPACE.[3]
<math>\mbox{QIP}</math> - это класс языков из QIP(k), где k разрешается быть полиномиальным от числа кубит. Известно, что QIP(3) = QIP.[4] Так же известно, что QIP = IP.[5]
<math>\mbox{QMA}_1</math> - это класс языков принимаемых квантовым протоколами Мерлин Артур с идеальной полнотой.
Отношения с другими классами
Про QMA известно, что
- <math>\mbox{P} \subseteq \mbox{NP} \subseteq \mbox{MA} \subseteq \mbox{QCMA} \subseteq \mbox{QMA}\subseteq \mbox{PP} \subseteq \mbox{PSPACE}</math>
Первое вложение следует из определения NP. Следующие два включения верны из-за того, что верифаеры становятся более сильными. Утверждение о том, что QMA содержится в PP был доказан Алексеем Китаевым и Джоном Ватрусом. PP также содержится в PSPACE.
Неизвестно какие из этих включений строгие.
Напишите отзыв о статье "QMA"
Примечания
- ↑ Dorit Aharonov & Tomer Naveh (2002), "Quantum NP - A Survey", arΧiv:[www.arxiv.org/abs/quant-ph/0210077v1 quant-ph/0210077v1] [quant-ph]
- ↑ 1 2 John Watrous (2008), "Quantum Computational Complexity", arΧiv:[www.arxiv.org/abs/0804.3401v1 0804.3401v1] [quant-ph]
- ↑ Two-Message Quantum Interactive Proofs Are in PSPACE // FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science. — IEEE Computer Society, 2009. — P. 534–543. — ISBN 978-0-7695-3850-1.
- ↑ (2003) «PSPACE has constant-round quantum interactive proof systems». Theor. Comput. Sci. (Elsevier Science Publishers Ltd.) 292 (3): 575–588. DOI:10.1016/S0304-3975(01)00375-9. ISSN [worldcat.org/issn/0304-3975 0304-3975].
- ↑ QIP = PSPACE // STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing. — ACM, 2010. — P. 573–582. — ISBN 978-1-4503-0050-6.
Литература
- «Algorithms for quantum computation: discrete logarithms and factoring» P.W. Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700
Ссылки
- А. Х. Шень, М. Н. Вялый, [www.intuit.ru/studies/courses/1057/136/lecture/2006?page=3 Курс лекций «Классические и квантовые вычисления». Лекция 8: Определение квантового вычисления. Примеры] // Интуит.ру, 15.03.2007
| ||||||||||||||||||
Отрывок, характеризующий QMA
– Non, ce n'est rien, je voulais dire seulement… [Нет, ничего, я только хотел сказать…] (Он намерен был повторить шутку, которую он слышал в Вене, и которую он целый вечер собирался поместить.) Je voulais dire seulement, que nous avons tort de faire la guerre рour le roi de Prusse. [Я только хотел сказать, что мы напрасно воюем pour le roi de Prusse . (Непереводимая игра слов, имеющая значение: «по пустякам».)]Борис осторожно улыбнулся так, что его улыбка могла быть отнесена к насмешке или к одобрению шутки, смотря по тому, как она будет принята. Все засмеялись.
– Il est tres mauvais, votre jeu de mot, tres spirituel, mais injuste, – грозя сморщенным пальчиком, сказала Анна Павловна. – Nous ne faisons pas la guerre pour le Roi de Prusse, mais pour les bons principes. Ah, le mechant, ce prince Hippolytel [Ваша игра слов не хороша, очень умна, но несправедлива; мы не воюем pour le roi de Prusse (т. e. по пустякам), а за добрые начала. Ах, какой он злой, этот князь Ипполит!] – сказала она.
Разговор не утихал целый вечер, обращаясь преимущественно около политических новостей. В конце вечера он особенно оживился, когда дело зашло о наградах, пожалованных государем.
– Ведь получил же в прошлом году NN табакерку с портретом, – говорил l'homme a l'esprit profond, [человек глубокого ума,] – почему же SS не может получить той же награды?
– Je vous demande pardon, une tabatiere avec le portrait de l'Empereur est une recompense, mais point une distinction, – сказал дипломат, un cadeau plutot. [Извините, табакерка с портретом Императора есть награда, а не отличие; скорее подарок.]
– Il y eu plutot des antecedents, je vous citerai Schwarzenberg. [Были примеры – Шварценберг.]
– C'est impossible, [Это невозможно,] – возразил другой.
– Пари. Le grand cordon, c'est different… [Лента – это другое дело…]
Когда все поднялись, чтоб уезжать, Элен, очень мало говорившая весь вечер, опять обратилась к Борису с просьбой и ласковым, значительным приказанием, чтобы он был у нее во вторник.
– Мне это очень нужно, – сказала она с улыбкой, оглядываясь на Анну Павловну, и Анна Павловна той грустной улыбкой, которая сопровождала ее слова при речи о своей высокой покровительнице, подтвердила желание Элен. Казалось, что в этот вечер из каких то слов, сказанных Борисом о прусском войске, Элен вдруг открыла необходимость видеть его. Она как будто обещала ему, что, когда он приедет во вторник, она объяснит ему эту необходимость.
Приехав во вторник вечером в великолепный салон Элен, Борис не получил ясного объяснения, для чего было ему необходимо приехать. Были другие гости, графиня мало говорила с ним, и только прощаясь, когда он целовал ее руку, она с странным отсутствием улыбки, неожиданно, шопотом, сказала ему: Venez demain diner… le soir. Il faut que vous veniez… Venez. [Приезжайте завтра обедать… вечером. Надо, чтоб вы приехали… Приезжайте.]
В этот свой приезд в Петербург Борис сделался близким человеком в доме графини Безуховой.
Война разгоралась, и театр ее приближался к русским границам. Всюду слышались проклятия врагу рода человеческого Бонапартию; в деревнях собирались ратники и рекруты, и с театра войны приходили разноречивые известия, как всегда ложные и потому различно перетолковываемые.
Жизнь старого князя Болконского, князя Андрея и княжны Марьи во многом изменилась с 1805 года.
В 1806 году старый князь был определен одним из восьми главнокомандующих по ополчению, назначенных тогда по всей России. Старый князь, несмотря на свою старческую слабость, особенно сделавшуюся заметной в тот период времени, когда он считал своего сына убитым, не счел себя вправе отказаться от должности, в которую был определен самим государем, и эта вновь открывшаяся ему деятельность возбудила и укрепила его. Он постоянно бывал в разъездах по трем вверенным ему губерниям; был до педантизма исполнителен в своих обязанностях, строг до жестокости с своими подчиненными, и сам доходил до малейших подробностей дела. Княжна Марья перестала уже брать у своего отца математические уроки, и только по утрам, сопутствуемая кормилицей, с маленьким князем Николаем (как звал его дед) входила в кабинет отца, когда он был дома. Грудной князь Николай жил с кормилицей и няней Савишной на половине покойной княгини, и княжна Марья большую часть дня проводила в детской, заменяя, как умела, мать маленькому племяннику. M lle Bourienne тоже, как казалось, страстно любила мальчика, и княжна Марья, часто лишая себя, уступала своей подруге наслаждение нянчить маленького ангела (как называла она племянника) и играть с ним.
