论文标题
量子乱码
Quantum Garbled Circuits
论文作者
论文摘要
我们提出了一种用于量子电路的垃圾方案，从而实现了用于量子计算的分解随机编码方案。具体而言，我们展示了如何计算给定量子电路和量子输入的编码，从中可以得出计算的输出，而无需其他。在经典环境中，乱码电路（通常是随机编码）是一种多功能加密工具，具有许多应用程序，例如安全的多方计算，授权计算，加密原始词的深度还原，复杂性下降等级等等。但是，在这项工作之前，尚不清楚用于插入通用电路的量子类似物。我们希望我们的量子随机编码方案类似地对于量子计算和加密中的应用也有用。 为了说明量子随机编码的有用性，我们使用它来设计一个概念上的简单零知识（ZK）证明系统，用于复杂性类别$ \ mathbf {qma} $。我们的协议具有带有单位挑战的所谓$σ$格式，并允许输入延迟到最后一轮。 $ \ mathbf {qma} $的唯一以前已知的Zk $σ$ -Sprotocol是由于Broadbent和Grilo（focs 2020）所致，它没有上述属性。
We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else. In the classical setting, garbled circuits (and randomized encodings in general) are a versatile cryptographic tool with many applications such as secure multiparty computation, delegated computation, depth-reduction of cryptographic primitives, complexity lower-bounds, and more. However, a quantum analogue for garbling general circuits was not known prior to this work. We hope that our quantum randomized encoding scheme can similarly be useful for applications in quantum computing and cryptography. To illustrate the usefulness of quantum randomized encoding, we use it to design a conceptually-simple zero-knowledge (ZK) proof system for the complexity class $\mathbf{QMA}$. Our protocol has the so-called $Σ$ format with a single-bit challenge, and allows the inputs to be delayed to the last round. The only previously-known ZK $Σ$-protocol for $\mathbf{QMA}$ is due to Broadbent and Grilo (FOCS 2020), which does not have the aforementioned properties.
