Theoretical Research on Quantum Supremacy

本学年，我们研究了与量子算法和后量子密码学相关的各种问题。我们研究了分布式量子算法的图着色问题。特别是，对于圆的三色问题，在我们的工作之前，量子算法的能力没有任何微不足道的限制。我们成功地证明了不相邻顶点的颜色之间存在一定的相关性，这种相关性对于每三种颜色都成立。在密码学中，随机排列、随机函数以及与之相关的各种计算问题起着重要的作用。然而，与随机函数不同，对于随机排列，我们目前还不知道许多技术来证明量子硬度结果。我们研究了置换的倒置问题，并证明了最近引入的压缩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.