Theoretical Research on Quantum Supremacy

本学年，我们研究了与量子算法和后量子密码学相关的各种问题。利用分布式量子算法研究了图的着色问题。特别是，对于圆的三色问题，在我们的工作之前，量子算法的能力没有已知的非平凡限制。我们设法表明，非相邻顶点的颜色之间存在一定的相关性，这种相关性适用于每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.