Experimental verification of group non-membership in optical circuits
For all group elements, green ones are non-members of the subgroup consisting of the blue elements.
Quantum effect can be exploited to enhance information processing in many ways. Besides speeding up solving certain problems, quantum computers can also be used to construct novel interactive proof systems (IPS). An IPS usually involves a verifier who wants to solve certain problems and a prover who has infinite computational power and can exchange messages with the verifier.
Different setup of IPS can give the verifier different computational ability. Especially, it is believed that the verifier can efficiently solve more problems with the help of quantum information processing.
The group non-membership (GNM) problem, which is important as it is related to many problems in the group theory, is expected to be solved more efficiently in the framework of quantum IPS. By allowing the verifier to receive and process a quantum state from the prover, the GNM problem is proved to be solvable in polynomial time under reasonable assumptions, whereas no classical protocol so far has reached this efficiency. It is conjectured that similar quantum speedup can be presented in many other problems with finite groups, such as the problems of deciding proper subgroups and simple groups.
The research group led by Prof. Chuan-Feng Li and Jin-Shi Xu from University of Science and Technology of China collaborating with the group of Man-Hong Yung from Southern University of Science and Technology researched an experimental verification of group non-membership in optical circuits. The research results are published in Photonics Research, Volume 9, No. 9, 2021 (Kai Sun, Zi-Jian Zhang, Fei Meng, Bin Cheng, Zhu Cao, Jin-Shi Xu, Man-Hong Yung, Chuan-Feng Li, Guang-Can Guo. Experimental verification of group non-membership in optical circuits[J]. Photonics Research, 2021, 9(9): 09001745).
In this work, a new protocol is proposed, which greatly improves the previous protocol by making it much friendlier to near-term quantum processors. For the groups with at most elements, each quantum circuit in the new protocol only requires O(1) group oracle calls, whereas the previous protocol requires O() oracle calls in one circuit. The number of qubits needed is also half-reduced.
The new protocol is designed based on the idea of "sampling inspection". In the previous protocol, the verifier needs to reversibly inspect the quantum state provided by the prover and check its validity before the next process. The requirement of reversibility makes the quantum circuit very deep.
In the new protocol, it requires the prover to send many copies of the quantum state as a big proof. The verifier just needs to destructively check many copies of the quantum states and randomly select one as checked to carry out the following process. The researchers also designed a map from general quantum circuit to optical circuit for using the optical components more efficiently. And this experimental implementation of the verification process for GNM broadens the pathway to investigate the quantum protocols in IPS with the near-term quantum devices.
The researchers believe that, with the growing power of quantum internet infrastructures and quantum computation, it has become a meaningful question how to implement the potential applications of quantum IPS under the current available quantum devices and quantum technologies.
It is expected that the protocol proposed in this work is very likely to be used to construct more similar quantum protocols which could be practical in near term. For the next step, as it is very likely that similar verification process of GNM can be used in other problems of finite groups, it will be interesting if this validity was formally proven and experimentally demonstrated.
新量子协议：高效验证群非成员问题
群元素中，绿柱是子群（蓝柱组成）的非成员
量子计算机除了能够加速解决某些计算问题，还可以用来构建新颖的交互式证明系统（interactive proof system，IPS）。理想的IPS通常包括要解决问题的验证者和拥有无限计算能力并能与验证者交换信息的证明者。
不同的IPS可以赋予验证者不同的计算能力。研究人员相信，当验证者可以利用量子信息进行处理时，量子IPS可以有效地解决更多问题。
群非成员（group non-membership，GNM）问题与群论中的许多问题有关。研究者认为，GNM问题可以在量子IPS的框架内得到更有效的解决。前期研究表明，如果验证者能够接收并处理来自证明者的量子态信息，在合理假设下，GNM问题可以在多项式时间内解决，而这是目前任何经典协议都无法实现的。
研究人员还预测，类似的量子加速可以出现在许多其他的有限群问题中，例如真子群和单群的判定问题。虽然展现出了潜在的量子加速能力，已有的验证GNM的量子协议需要很深的量子线路，这使得它难以在近期可实现的量子设备上运行。
因此，如何简化之前的协议，并在目前可用的设备上实验实现是当前亟需解决的问题。
中国科学技术大学李传锋、许金时教授课题组和南方科技大学翁文康教授课题组合作在Photonics Research 2021年第9期上发表的文章中(Kai Sun, Zi-Jian Zhang, Fei Meng, Bin Cheng, Zhu Cao, Jin-Shi Xu, Man-Hong Yung, Chuan-Feng Li, Guang-Can Guo. Experimental verification of group non-membership in optical circuits[J]. Photonics Research, 2021, 9(9): 09001745）介绍了利用量子光学线路实验验证群非成员问题的工作。
该项工作中，研究团队在极大地改进以前协议的基础上提出了一个新的协议，新协议对近期已实现的量子设备更加友好。对于最多只有个元素的群，新协议中的每个量子线路只需要O(1)个预言调用，而以前的协议则需要O()个。同时，在新协议中，所需的量子比特的数量也减少了一半。
新协议是基于“抽样检查”的思想而设计。在旧协议中，验证者需要可逆地检查由证明者提供的量子态，并在下一个步骤前检查其有效性，此可逆性要求更深的量子路线。而在新协议中，要求证明者发送多份量子态的拷贝作为一个大证明，验证者只需要破坏性地检查多个拷贝，并随机地保留一个拷贝进行接下来的验证步骤。
在实验上，该研究团队设计了从量子线路到量子光路的映射，能更有效地使用光学元件来实现相应的线路。他们认为，这个更为有效地验证GNM的实验实现，拓宽了利用近期可实现的量子设备研究量子IPS的思路。
随着量子互联网基础设施和量子计算能力不断增强，如何在现有的量子设备和量子技术下实现量子交互式证明系统及其各种潜在应用已成为一个值得探究的问题。该团队认为，此工作中提出的新协议很有可能被用来构建更多类似的、适用于近期量子设备的量子协议。
对于未来工作，由于验证GNM的技术很可能被应用于其他类似的关于有限群的问题，该研究团队会致力于将该技术应用在其他有限群问题上的理论与实验工作中。