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.

For all group elements, green ones are non-members of the subgroup consisting of the blue elements.

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.