HARDNESS OF APPROXIMATION FOR QUANTUM PROBLEMS

作     者：Gharibian, Sevag Kempe, Julia 

作者机构：Univ Calif Berkeley Berkeley CA 94720 USA Univ Paris 07 CNRS Lab Informat Algorithm Fondements & Applicat Paris France 

出 版 物：《QUANTUM INFORMATION & COMPUTATION》 (Quantum Inf. Comput.)

年 卷 期：2014年第14卷第5-6期

页      面：517-540页

核心收录：

学科分类：07[理学] 070201[理学-理论物理] 0702[理学-物理学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSERC CGS NSERC CGS-MSFSS EU-Canada David R. Cheriton School of Computer Science at the University of Waterloo Israeli Science Foundation European Research Council (ERC) Wolfson Family Charitable Trust 

主　　题：Hardness of approximation polynomial time hierarchy succinct set cover quantum complexity 

摘      要：The polynomial hierarchy plays a central role in classical complexity theory Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999]. The problems for which we prove hardness of approximation for include, among others, a quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian problem with hybrid classical-quantum ground states.