Towards Perfect Completeness in QMA-猫眼课题宝

DOI：

发表时间：

2012

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

S. Jordan;Hirotada Kobayashi;Daniel Nagaj;H. Nishimura

本演讲提出了两个量子非相对论性的结果，并且可以说是朝着肯定地解决QMA与QMA1问题（即具有完全完备性的片面有界误差的量子梅林-亚瑟证明系统是否具有等同于具有双面有界误差的一般量子梅林-亚瑟证明系统的验证能力的问题）迈出了一步。首先，证明了经典见证量子梅林-亚瑟证明系统可以达到完全完备性。即QCMA = QCMA1。这在任何可以精确实现Hadamard变换和任意经典可逆变换的门集合下都成立，例如{Hadamard， Toffoli, NOT}。该证明使用了一种简单但新颖的量子技术，可以累加地调整成功概率，这可能是独立的兴趣。其次，证明了QMA中的任何问题都存在一个具有恒定可靠误差的完全完备性的双消息量子交互证明系统，其中验证者只需发送恒定数量的EPR对的一半。这特别意味着类QMA必须包含在具有完全完备性的双消息量子交互证明的问题类QIP1(2)中，从而给出了QMA在量子交互证明方面的第一个非平凡上界。本次演讲基于以下两篇论文：•Stephen P. Jordan, Hirotada Kobayashi， Daniel Nagaj和Harumichi Nishimura。在经典见证量子梅林-亚瑟证明系统中实现完全完备性。量子信息与计算，12(5-6):0461-0471,2012。arXiv: 1111.5306 v2 [quant-ph]。•Hirotada Kobayashi， franois Le Gall和Harumichi Nishimura。使量子交互证明完美完成的更强大的方法。第四届理论计算机科学创新会议论文集，2013。出现。arXiv: 1210.1290 (quant-ph)。*部分工作是在SJ在美国加州理工学院量子信息研究所，DN在斯洛伐克布拉迪斯拉发斯洛伐克科学院物理研究所量子信息研究中心，HN在大阪堺市大阪府立大学理科研究生院数学与信息科学系完成的。具有Merlin-Arthur （MA）证明系统的问题的经典复杂性类MA，首先由Babai [Bab85]提出，是类NP的自然概率推广。非正式地，在Merlin-Arthur证明系统中，概率多项式时间验证者Arthur首先从全能但不可信的证明者Merlin那里接收消息（证人），然后以高概率检查Merlin声明的有效性，即公共输入是问题的“是”实例。量子梅林-亚瑟（QMA）证明系统是梅林-亚瑟证明系统在量子环境中的推广，其概念在量子计算研究的早期阶段就已经在Knill [Kni96]的技术报告中进行了讨论。在这个设置中，Arthur现在从Merlin那里收到一个量子见证，并执行多项式时间量子计算，以高概率检查输入是否是一个yes-instance。由此产生的复杂度类被称为QMA [Wat00]（最初被称为BQNP [Kit99， KSV02]），它一直是量子复杂性理论发展的核心，因为它在经典计算中扮演着类似NP的角色。定义MA和QMA的标准方法允许双向有界错误：每个yes-instance可能以小概率错误地拒绝（完整性错误），而每个no-instance也可能以小概率错误地接受（可靠性错误）。如果完备性错误为零，也就是说，yes-instance从来没有被错误地拒绝过，那么对应的系统就被称为完全完备性。完备完备的MA和QMA版本分别用MA1和QMA1表示。经典地，已知任何可能存在双面有界误差的Merlin-Arthur证明系统都可以被修正为另一个具有完全完备的片面有界误差的Merlin-Arthur证明系统，即MA = MA1成立[ZF87， GZ11]。一个自然的问题是，同样的性质是否也适用于量子梅林-亚瑟证明系统，即QMA是否= QMA1。这个问题经过多年的调查仍未得到解决。除了理论利益之外，以肯定的态度回答这个问题还会导致许多后果。特别地，对于QMA1类来说，任何已经完成的计算问题，比如量子可满足性（QSAT） [Bra06]，也会立即成为QMA类的完整问题。此外，几年来，研究人员一直试图证明著名的PCP定理[AS98， ALM+98]的量子模拟[AALV09， AALV11, AE11]。QMA = QMA1的证明可以帮助实现这一目标，因为片面错误验证更容易处理，而且QSAT问题比局部哈密顿问题更直接地类似于SAT问题。因此，我们可以更接近于经典的PCP定理，它可以被看作是证明了3SAT问题的一个特殊情况的np完备性，在这个情况下，对于每一个无实例，最多有一个常数部分的子句同时是可满足的。作为肯定回答QMA与QMA1问题的障碍，Aaronson [Aar09]构造了一个量子神谕，相对于QMA1是QMA的适当子类，这意味着QMA = QMA1的“黑盒”证明不存在。然而，没有已知的经典预言将QMA1与QMA分开，Nagaj， Wocjan和Zhang [NWZ09]向肯定问题的答案迈出了一步，表明对于量子梅林-亚瑟证明系统的特殊情况是可以实现的，其中与给定系统的最大接受概率相关的实数可以用多项式长度的位串精确表示。量子梅林-亚瑟证明系统可以被视为更一般的量子交互式证明系统的特殊情况，其中验证者和证明者可以使用多轮通信交换消息。Kitaev和Watrous [KW00]在他们的开创性论文中表明，在量子交互证明系统中可以实现完全完备性。更准确地说，通过两个额外的消息，任何可能涉及双面有界错误的量子交互证明系统都可以转化为另一个具有完全完备性单边有界错误的量子交互证明系统。特别地，这意味着QMA≥QIP1(3)，其中QIP1(3)为具有完全完备性的三消息量子交互证明系统的一类问题。不幸的是，QIP1(3)已经非常强大，它包含了PSPACE [Wat03]（实际上，QIP1(3) = QIP = PSPACE [KW00, JJUW11]），其中QIP表示具有一般性的问题的类别

This talk presents two results, both of which are quantumly nonrelativizing, and arguably step towards affirmatively settling the QMA versus QMA1 problem (i.e., the problem of whether quantum Merlin-Arthur proof systems with one-sided bounded error of perfect completeness have verification power equivalent to general quantum Merlin-Arthur proof systems with two-sided bounded error). First, it is proved that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, QCMA = QCMA1. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, e.g., {Hadamard, Toffoli, NOT}. The proof uses a simple but novel quantum technique that additively adjusts the success probability, which may be of independent interest. Second, it is proved that any problem in QMA has a two-message quantum interactive proof system of perfect completeness with constant soundness error, where the verifier has only to send a constant number of halves of EPR pairs. This in particular implies that the class QMA is necessarily included by the class QIP1(2) of problems having two-message quantum interactive proofs of perfect completeness, which gives the first nontrivial upper bound for QMA in terms of quantum interactive proofs. This talk is based on the following two papers: • Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information and Computation, 12(5–6):0461–0471, 2012. arXiv:1111.5306v2 [quant-ph]. • Hirotada Kobayashi, François Le Gall, and Harumichi Nishimura. Stronger methods of making quantum interactive proofs perfectly complete. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference, 2013. To appear. arXiv:1210.1290 [quant-ph]. ∗Part of this work was done while SJ was at the Institute for Quantum Information, California Institute of Technology, Pasadena, CA, USA, DN was at the Research Center for Quantum Information, Institute of Physics, Slovak Academy of Sciences, Bratislava, Slovakia, and HN was at the Department of Mathematics and Information Sciences, Graduate School of Science, Osaka Prefecture University, Sakai, Osaka, Japan. 1 Background and Motivation The classical complexity class MA of problems having Merlin-Arthur (MA) proof systems, first introduced by Babai [Bab85], is a natural probabilistic generalization of the class NP. Informally, in a Merlin-Arthur proof system, Arthur, a probabilistic polynomial-time verifier, first receives a message (a witness) from Merlin, an allpowerful but untrustworthy prover, and then checks with high probability the validity of Merlin’s claim that the common input is a yes-instance of the problem. Quantum Merlin-Arthur (QMA) proof systems are a generalization of the Merlin-Arthur proof systems to the quantum setting, whose notion was already discussed at an early stage of quantum computing research in a technical report by Knill [Kni96]. In this setting, Arthur now receives a quantum witness from Merlin and performs polynomial-time quantum computation to check with high probability whether the input is a yes-instance or not. The resulting complexity class is called QMA [Wat00] (originally called BQNP [Kit99, KSV02]), and has been central to the development of quantum complexity theory in that it plays a role similar to that NP plays in classical computation. The standard way of defining MA and QMA allows two-sided bounded error: each yes-instance may be wrongly rejected with small probability (completeness error), while each no-instance may also be wrongly accepted with small probability (soundness error). If completeness error is zero, that is, yes-instances are never wrongly rejected, the corresponding system is said to have perfect completeness. The versions of MA and QMA with perfect completeness are denoted by MA1 and QMA1, respectively. Classically, it is known that any Merlin-Arthur proof system that may have two-sided bounded error can always be modified into another Merlin-Arthur proof system with one-sided bounded error of perfect completeness, i.e., MA = MA1 holds [ZF87, GZ11]. A natural question to ask is whether the same property holds for quantum Merlin-Arthur proof systems as well, i.e., whether QMA = QMA1. This question still remains unsolved after many years of investigation. Besides its theoretical interest, answering this question by the affirmative would lead to many consequences. In particular, any computational problem complete for the class QMA1, such as QUANTUM SATISFIABILITY (QSAT) [Bra06], would immediately become complete for the class QMA as well. Furthermore, for several years, researchers have been trying to prove a quantum analogue [AALV09, AALV11, AE11] of the celebrated PCP theorem [AS98, ALM+98]. A proof that QMA = QMA1 could aid in this goal, because onesided error verifications are much easier to treat, and also because the QSAT problems are more direct quantum analogues of the SAT problems than the LOCAL HAMILTONIAN problems. Thus, one could draw a closer parallel to the classical PCP theorem, which can be viewed as proving the NP-completeness of a special case of the 3SAT problem in which, for every no-instance, at most a constant fraction of clauses are simultaneously satisfiable. As a barrier to affirmatively answering the QMA versus QMA1 question, Aaronson [Aar09] constructed a quantum oracle relative to which QMA1 is a proper subclass of QMA, which means that a “black-box” proof of QMA = QMA1 cannot exist. Nevertheless, no classical oracle is known that separates QMA1 from QMA, and Nagaj, Wocjan, and Zhang [NWZ09] made a step towards an affirmative answer to the question by showing that perfect completeness is achievable for a special case of quantum Merlin-Arthur proof systems in which some real number related to the maximum acceptance probability of a given system can be exactly expressed with a bit string of polynomial length. Quantum Merlin-Arthur proof systems may be viewed as a special case of more general quantum interactive proof systems, where the verifier and the prover may exchange messages using many rounds of communications. In their seminal paper, Kitaev and Watrous [KW00] showed that perfect completeness is achievable in quantum interactive proof systems. More precisely, with two additional messages, any quantum interactive proof system that may involve two-sided bounded error can be transformed into another quantum interactive proof system that has one-sided bounded error of perfect completeness. This in particular implies that QMA ⊆ QIP1(3), where QIP1(3) is the class of problems having three-message quantum interactive proof systems of perfect completeness. Unfortunately, QIP1(3) is already so powerful that it includes PSPACE [Wat03] (actually, QIP1(3) = QIP = PSPACE [KW00, JJUW11], where QIP denotes the class of problems having general

Towards Perfect Completeness in QMA

文献摘要

相似文献