论文标题
量子空间，地面空间遍历以及如何将多杆交互式证明嵌入未输入
Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
论文作者
论文摘要
Savitch的定理指出，可以在Pspace中模拟NPSPACE计算。我们启动了NPSPACE的量子类似物，表示流QCMASPACE（SQCMASPACE），其中将指数的经典证明流到了多空间量子验证器中。除了两个主要结果外，我们还表明，Sqcmaspace = nexp，Savitch定理的量子类似物不太可能存在。为了完整性，我们引入了带有指数式流量子证明的流QMASPACE（SQMASPACE），并显示sqmaspace = qma_exp（nexp的量子类似物）。我们的第一个主要结果表明，与经典设置相反，当允许长时间的证明时，量子约束满意度问题的解决方案空间始终连接。为此，我们展示了如何通过一系列局部统一大门模拟单位过球上的任何Lipschitz连续路径，但以炸毁电路尺寸为代价。这表明，如果量子误差校正的代码无法检测到一个代码，如果进化的发生得足够缓慢，则错误地演变为另一个代码，并回答了关于基态连接性问题的[Gharibian，Sikora，iCalp 2015]的开放问题。我们的第二个主要结果是，任何SQCMASPACE计算都可以嵌入“未输入”中，即与未进入的掠夺者的量子约束满意度问题。正式地，我们展示了如何将SQCMaspace嵌入[Chailloux，Sattath，CCC 2012]的稀疏可分离性哈密顿问题中（QMA（2） - 以1/Poly Promise Gap的速度），以牺牲以流向证明大小为准的承诺差距。作为推论，我们获得了第一个系统的系统构建，用于在任意多杆交互式证明系统上获得QMA（2）型上限，其中QMA（2）在交互式证明中，QMA（2）承诺与差距呈指数缩放。
Savitch's theorem states that NPSPACE computations can be simulated in PSPACE. We initiate the study of a quantum analogue of NPSPACE, denoted Streaming-QCMASPACE (SQCMASPACE), where an exponentially long classical proof is streamed to a poly-space quantum verifier. Besides two main results, we also show that a quantum analogue of Savitch's theorem is unlikely to hold, as SQCMASPACE=NEXP. For completeness, we introduce Streaming-QMASPACE (SQMASPACE) with an exponentially long streamed quantum proof, and show SQMASPACE=QMA_EXP (quantum analogue of NEXP). Our first main result shows, in contrast to the classical setting, the solution space of a quantum constraint satisfaction problem (i.e. a local Hamiltonian) is always connected when exponentially long proofs are permitted. For this, we show how to simulate any Lipschitz continuous path on the unit hypersphere via a sequence of local unitary gates, at the expense of blowing up the circuit size. This shows quantum error-correcting codes can be unable to detect one codeword erroneously evolving to another if the evolution happens sufficiently slowly, and answers an open question of [Gharibian, Sikora, ICALP 2015] regarding the Ground State Connectivity problem. Our second main result is that any SQCMASPACE computation can be embedded into "unentanglement", i.e. into a quantum constraint satisfaction problem with unentangled provers. Formally, we show how to embed SQCMASPACE into the Sparse Separable Hamiltonian problem of [Chailloux, Sattath, CCC 2012] (QMA(2)-complete for 1/poly promise gap), at the expense of scaling the promise gap with the streamed proof size. As a corollary, we obtain the first systematic construction for obtaining QMA(2)-type upper bounds on arbitrary multi-prover interactive proof systems, where the QMA(2) promise gap scales exponentially with the number of bits of communication in the interactive proof.
