Theoretical Research on Quantum Supremacy

本学年我们研究了与量子算法和后量子密码学相关的各种问题。我们研究了分布式量子算法的图着色问题。特别是，对于圆的3-着色问题，在我们的工作之前，量子算法的功率没有已知的非平凡限制。我们设法证明了非相邻顶点的颜色之间存在一定的相关性，这对每个3-着色都成立。在密码学中，随机置换、随机函数以及它们所涉及的各种计算问题都扮演着重要的角色。然而，与随机函数不同的是，对于随机排列，我们目前还不知道很多证明量子硬度结果的技术。我们研究了一个置换的逆问题，并展示了如何使用最近引入的压缩oracle框架来证明该问题的最优查询下界，我们还研究了允许无限控制位数的受控单量子位门的奇偶校验的浅深度量子电路的计算能力。虽然这些无界门可能使模型更加强大，但我们获得的一些初步结果表明情况并非如此。特别是，我们将所有深度2电路的拓扑结构分为几类，对于其中的大多数，我们已经证明它们不能计算超过4个输入位的奇偶校验，这已经可以通过一个和两个量子位门实现。

This academic year we worked on various problems related to quantum algorithms and post-quantum cryptography.We investigated the problem of graph coloring by distributed quantum algorithms. In particular, for the problem of 3-coloring a circle, prior to our work, no nontrivial limitations on the power of quantum algorithms were known. We managed to show that there is a certain correlation among the colors of non-adjacent vertices that holds for every 3-coloring. As a result, we proved that one round of one way quantum communication is not sufficient to solve the problem.In cryptography, random permutations, random functions, and various computational problems on them play important roles. However, unlike for random functions, for random permutations we currently do not know many techniques to prove quantum hardness results. We studied the problem of inverting a permutation, and showed how the recently-introduced compressed oracle framework can be used to prove optimal query lower bounds for the problem.We also studied the computational power of shallow-depth quantum circuits for parity that permit controlled single-qubit gates of unbounded number of control bits. While these unbounded gates might make the model much more powerful, we obtained some preliminary results suggesting that that is not the case. In particular, we classified topologies of all depth-2 circuits in few classes, and for most of them we already showed that they cannot compute the parity of more than 4 input bits, which is already achievable by one and two qubit gates.