Theoretical Research on Quantum Supremacy

量子霸权理论研究

• 批准号: 19F19079
• 负责人: ルガル フランソワ
• 金额: $ 0.96万
• 依托单位: Nagoya University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-07-24 至 2021-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19F19079/
• 关键词: Quantum computing; Complexity theory; Algorithms

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.

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

项目成果

A Tight Lower Bound For Non-Coherent Index Erasure

非相干索引擦除的严格下界

• 发表时间: 2020
• 期刊: Leibniz International Proceedings in Informatics (ITCS 2020)
• 作者: Srinivasan Arunachalam;Aleksandrs Belovs;Andrew M. Childs;Robin Kothari;Ansis Rosmanis and Ronald de Wolf;Nathan Lindzey and Ansis Rosmanis
• 通讯作者: Nathan Lindzey and Ansis Rosmanis

Quantum and Classical Algorithms for Approximate Submodular Function Minimization

近似子模函数最小化的量子和经典算法

• 发表时间: 2019
• 期刊: Quantum Information & Computation
• 影响因子: 1
• 作者: Yassine Hamoudi;Patrick Rebentrost;Ansis Rosmanis and Miklos Santha
• 通讯作者: Ansis Rosmanis and Miklos Santha

University of Latvia(ラトビア)

拉脱维亚大学（拉脱维亚）

Quantum Coupon Collector

量子优惠券收集器

• 发表时间: 2020
• 期刊: Leibniz International Proceedings in Informatics (Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography)
• 作者: Srinivasan Arunachalam;Aleksandrs Belovs;Andrew M. Childs;Robin Kothari;Ansis Rosmanis and Ronald de Wolf
• 通讯作者: Ansis Rosmanis and Ronald de Wolf