A new design of circuit networks to display quantum two-player games

This study is led by Dr. Xiangdong Zhang (Key Laboratory of Advanced Optoelectronic Quantum Architecture and Measurements of Ministry of Education, Beijing Key Laboratory of Nanophotonics and Ultrafine Optoelectronic Systems and Beijing Institute of Technology). The theoretical scheme and derivation were conducted by Dr. Tian Chen, and the experiments were performed by MSc. Jinliang Zhang. In today’s scenarios, the ability to make decisions quickly often proves to be a decisive factor in achieving success. Research has shown that if two-player games are cast into a decision tree, e.g., AND-OR trees, then the minimax value of the game tree corresponds precisely to the value of the optimal solution in the two-player game. Therefore, the evaluation of game problems hinges on efficiently obtaining the optimal solution to the AND-OR tree problems. Despite the fact that no algorithm has outperformed this classical zero-error algorithm for a long time, it remains quite slow when the inputs increase.

Chen and Zhang, led by the lab director Zhang, sought to look for a new quantum algorithm to solve the two-player game quickly, and a novel scheme to realize a two-player game based on AND-OR tree structures. After the intricate design, they employed a subgame design technique to develop a quantum algorithm for the Hamiltonian AND-OR tree using continuous-time quantum walk. The proposed algorithm not only exhibits quantum speedup, but also has speedup effects even compared to existing quantum algorithms. Moreover, they validated the quantum speedup characteristics of this algorithm within the new design of circuit networks.

The team designed the game tree following this game process. During the game, the first player (Alice) makes the “OR” operation of their child nodes, and the second player (Bob) does the “AND” operation of their child nodes. One round of game contains one “OR” and “AND” operations. In one round, Alice can make a choice at the beginning, and Bob wants to choose the strategy to win, no matter what moves made by Alice before. In this way, a new round of game is run. Alice needs to find a new strategy to win in the new situation, and the “OR” operation is made by Alice again. Therefore, the “OR” and “AND” operations appear alternatively during the game process. Finally, the lowest root node in the tree structure is connected to a runway, which affects the evolution the wave function on the runway. Whether to obstruct or allow the wave packet to pass this lowest root node depends on the computation result of the AND-OR tree. “This design is rather interesting, for the game results can be reflected upon the evolution behaviors of wave function on the runway.” Zhang says.

The researchers also fabricated the circuit networks designed above and experimentally demonstrated the fast processing of different inputs. At first, the two-input quantum OR or AND tree was designed. Based on the evolution results of wave packet on the runway, the game results can be fully determined at the time requested by quantum algorithms, which is shorter than the time required in classical algorithms. Then, the research was extended to three, four and five-input quantum AND-OR game trees. All results demonstrated that the game times satisfy the quantum algorithms, which showcase the quantum speedup of the AND-OR tree in circuit realization.

Zhang said, “These experimental results on the electric circuit illustrate the incredible performance in the two-player games. This new design can be easily extended to chip-implemented circuit sensor. There are three main advantages in the implementation on the chip, the first thing is the easily configurable components in the realization, the second thing is the enormous reduction of the parasitic effect, and the third thing is the increase operating frequency. In this way, considering three main advantages above, he implementation of the game problem on integrated circuits can scale up to larger inputs, while keeping the circuit size within the millimeter range.”

Fast games processing is of fundamental importance and widely used in modern society, such as in chess, economics, cybersecurity, computer science, and finance, among others. The authors in this work designed and fabricated corresponding circuit networks to demonstrate quantum advantage in the two-player games. It provides a new idea for improving computing power in the era of big data and will be widely used in various fields.