Quantum-inspired permanent identities
Quantum-inspired permanent identities
复制标题
DOI：
10.22331/q-2022-12-19-877
复制
发表时间：
2022-07
期刊：
影响因子：
6.4
通讯作者：
Ulysse Chabaud;A. Deshpande;S. Mehraban
中科院分区：
文献类型：
--
作者：
Ulysse Chabaud;A. Deshpande;S. Mehraban
永久式是复杂性理论和组合学的关键。在量子计算中，永久量出现在线性光学计算的输出振幅的表达式中，例如玻色子采样模型。利用这种联系，我们给出了许多现有的以及新的显着的永久身份量子启发的证明。最值得注意的是，我们给出了一个量子启发的麦克马洪主定理的证明，以及证明这个定理的新的推广。这个定理以前的证明使用了完全不同的思想。除了它们的纯粹的组合应用，我们的结果表明，经典的硬度精确和近似采样的线性光量子计算与输入猫状态。
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.