Game theory problems are widely applied in many research areas such as computer science and finance, with the key issue being how to quickly make decisions. Here, we present a novel quantum algorithm for game theory problems based on a continuous quantum walk. Our algorithm exhibits quantum advantage compared to classical game algorithms. Furthermore, we exploit the analogy between the wave function of the Schrödinger equation and the voltage in Kirchhoff's law to effectively translate the design of quantum game trees into classical circuit networks. We have theoretically simulated the quantum game trees and experimentally validated the quantum functionality speedup on classical circuit networks. Due to the robust scalability and stability inherent in classical circuit networks, quantum game trees implemented within this framework hold promise for addressing more intricate application scenarios.
Game theory problems are widely applied in many research areas such as computer science and finance, with the key issue being how to quickly make decisions. Here, we present a novel quantum algorithm for game theory problems based on a continuous quantum walk. Our algorithm exhibits quantum advantage compared to classical game algorithms. Furthermore, we exploit the analogy between the wave function of the Schrödinger equation and the voltage in Kirchhoff's law to effectively translate the design of quantum game trees into classical circuit networks. We have theoretically simulated the quantum game trees and experimentally validated the quantum functionality speedup on classical circuit networks. Due to the robust scalability and stability inherent in classical circuit networks, quantum game trees implemented within this framework hold promise for addressing more intricate application scenarios.
Quantum walks on binary trees are used in many quantum algorithms to achieve important speedup over classical algorithms. The formulation of this kind of algorithms as quantum circuit presents the advantage of being easily readable, executable on circuit based quantum computers and simulators and optimal on the usage of resources. We propose a strategy to compose quantum circuit that performs quantum walk on binary trees following universal gate model quantum computation principles. We give a particular attention to NAND formula evaluation algorithm as it could have many applications in game theory and reinforcement learning. We therefore propose an application of this algorithm and show how it can be used to train a quantum reinforcement learning agent in a two player game environment.
Classical game theory is a powerful tool focusing on optimized resource distribution, allocation, and sharing in classical wired and wireless networks. As quantum networks are emerging as a means of providing true connectivity between quantum computers, it is imperative and crucial to exploit game theory for addressing challenges such as entanglement distribution and access, routing, topology extraction, and inference. Quantum networks provide the promising opportunity of employing quantum games owing to their inherent capability of generating and sharing quantum states. In addition, quantum games offer enhanced payoffs and winning probabilities, new strategies, and equilibria, which are unimaginable in classical games. Employing quantum game theory to solve fundamental challenges in quantum networks opens a new fundamental research direction necessitating inter-disciplinary efforts. In this article, we introduce a novel game-the-oretical framework for exploiting quantum strategies to solve – as an archetypal example – one of the key functionalities of a quantum network, namely, entanglement distribution. We compare quantum strategies with classical ones by showing the quantum advantages in terms of link fidelity improvement and latency decrease in communication. In the future, we will generalize our game framework to optimize entanglement distribution and access over any quantum network topology. We will also explore how quantum games can be leveraged to address other challenges like routing, optimization of quantum operations, and topology design.
A quantum algorithm is defined by a sequence of operations that runs on a realistic model of quantum computation. Since the first quantum algorithm proposed by David Deutsch(1985), a large number of impressive quantum algorithms have been developed. Quantum random walks on a graph, which are analogous to classical stochastic walk, form the basis for some of the recent quantum algorithms that promise to significantly outperform existing classical random walk algorithms. Though research has been done on the application of quantum random walk to important computational problems, very little work has been done on its quantum circuit design. There are two types of quantum random walk algorithms: discrete-time and continuous-time. In this paper, we propose quantum circuit designs for both types of random walk algorithms that operate on various graphs. We consider in detail two important problems to which random walk algorithms are applicable: the triangle finding problem and binary welded tree problem. Though there exist a few research works related to quantum circuit design for random walk on graphs, to the best of our knowledge, the circuit designs we present here are first of their kind. We also provide an estimate of the quantum cost of these circuits for several physical machine descriptions (PMDs)of quantum systems, based on the number of quantum operations and execution cycles.
Quantum search algorithm, which can search an unsorted database quadratically faster than any known classical algorithms, has become one of the most impressive showcases of quantum computation. It has been implemented using various quantum schemes. Here, we demonstrate both theoretically and experimentally that such a fast search algorithm can also be realized using classical electric circuits. The classical circuit networks to perform such a fast search have been designed. It has been shown that the evolution of electric signals in the circuit networks is analogies of quantum particles randomly walking on graphs described by quantum theory. The searching efficiencies in our designed classical circuits are the same to the quantum schemes. Because classical circuit networks possess good scalability and stability, the present scheme is expected to avoid some problems faced by the quantum schemes. Thus, our findings are advantageous for information processing in the era of big data.
Abstract The ultimate goal of developing quantum algorithms and constructing quantum computers is to achieve faster information processing than using current classical computers. Quantum walks are powerful kernels in quantum computing protocols and possess strong capabilities in speeding up various simulation and optimization tasks. One striking example is provided by quantum walkers evolving on unbalanced trees, which demonstrate faster hitting performances than classical random walk. However, direct experimental construction of unbalanced trees to prove quantum advantage with exponential speedup remains a great challenge due to the highly complex arrangements of the structure. This study attempts to simulate quantum algorithm by classical circuit. Inspired by the quantum algorithm, the classical circuit networks are designed and fabricated with unbalanced tree structures. It is then demonstrated, both theoretically and experimentally, that the quantum algorithm for the fast hitting problem can be simulated in the structure. It is shown that the hitting efficiency of electric signals in the circuit networks with unbalanced tree structures is exponentially faster than the corresponding cases of classical random walks. Because classical circuit networks possess good scalability and stability, the results open up a scalable new path toward quantum speedup in complex problems.
Game theory is a well established field with applications in many areas including the social sciences, biology, and computer science [6]. Recently, however, researchers in quantum computation have begun to study the implications of games set in the quantum domain (i.e. game theoretical situations where either one or more players have quantum computational power or where the implementation of strategies uses some form of quantum information). Such a setting allows for entanglement and superpositions of strategies and evaluation of payoffs using quantum measurement. This approach to game theory, according to some scholars in the field, could help us understand certain physical systems, improve economic markets, and develop quantum algorithms. I have conducted an investigation into quantum game theory. I have constructed simulation tools using Maple that, along with research into related work, have helped gain some insight into this new field. The important solutions in classical game theory are usually Nash equilibria. What do they look like in the quantum realm? In what