论文标题
量子启发的永久身份
Quantum-inspired permanent identities
论文作者
论文摘要
永久性是复杂性理论和组合学的关键。在量子计算中，永久性出现在线性光学计算的输出幅度的表达中，例如在玻色子采样模型中。利用这一联系，我们为许多现有和新的永久身份提供了量子启发的证据。最值得注意的是，我们给出了Macmahon Master定理的量子启发的证明，以及该定理的新概括的证明。该定理的先前证明使用了完全不同的想法。除了纯粹的组合应用外，我们的结果还证明了使用输入CAT状态进行线性光学量子计算的精确和近似采样的经典硬度。
The permanent is pivotal to both complexity theory and combinatorics. In quantum computing, the permanent appears in the expression of output amplitudes of linear optical computations, such as in the Boson Sampling model. Taking advantage of this connection, we give quantum-inspired proofs of many existing as well as new remarkable permanent identities. Most notably, we give a quantum-inspired proof of the MacMahon master theorem as well as proofs for new generalizations of this theorem. Previous proofs of this theorem used completely different ideas. Beyond their purely combinatorial applications, our results demonstrate the classical hardness of exact and approximate sampling of linear optical quantum computations with input cat states.
