Quantum-Assisted Graph Domination Games

C Weeks, P Strange, P Drmota, J Quintanilla · 2025

Read Quantum-Assisted Graph Domination Games by C Weeks, P Strange, P Drmota, J Quintanilla (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-15802.txt.

Introduction

C. Weeks, P. Strange, P. Drmota, and J. Quintanilla study quantum advantage in a one-step graph domination game played on cycle graphs. In a domination game, players place pieces so every vertex is covered by a chosen vertex or its neighbor, and quantum strategies can use superposition to coordinate choices. Prior work found upper bounds for small graphs, leaving open how far the advantage extends.

The authors give explicit strategies that reach those bounds for small cycles and generalize them to larger cycles. They test the ideas three ways: numerically, analytically, and on noisy intermediate-scale quantum processors available today. The hardware runs realized the predicted quantum advantages with high accuracy, confirming the theory in practice.

Catalog record

CREATORC Weeks, P Strange, P Drmota, J Quintanilla
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE8 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-15802

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum-Assisted Graph Domination Games C Weeks, P Strange, P Drmota, J Quintanilla Abstract We study quantum advantage in the 1-step graph domination game on cycle graphs numerically, analytically and through the use of Noisy intermediate scale quantum (NISQ) processors. We find explicit strategies that realise the recently found [ PiotrBasePaper ] upper bounds for small graphs and generalise them to larger cycles. We demonstrate that NISQ computers realise the predicted quantum advantages with high accuracy. 1 Introduction Quantum computing is an important change in the way we approach computation. A quantum processing unit uses quantum bits, or qubits, enabling them to exploit superposition, interference, and entanglement to solve problems that are impractical for classical computers due to excessive computation times [ QCIntro ] . While the term “quantum advantage” usually refers to the time complexity of a problem (as in the algorithms due to Shor [ ShorAlgorithm ] for factorisation and Grover [ GroverAlgoritm ] for searching unstructured databases), qubits can also offer other types of advantage. For instance, quantum entanglement (namely, the ability of qubits to become linked in ways that create complex relationships between their states, even when they are far apart [ vedral2006introduction ] ) can be used to transmit a message with a guarantee that it has not been detected (quantum cryptography [ Pirandola2020Dec ] ) - a feat that is simply not possible using classical means. We could call such advantages “quantum operational advantages” to distinguish them for those of the purely computational kind. The present paper is concerned with a form of operational advantage, namely the use of entanglement to improve the probability of success of coordinated moves by distant parties without exchange of signals [ brukner2006entanglement , RendezvousBase , tucker_quantum-assisted_2024 , PiotrBasePaper ] . In particular, we study recently introduced [ PiotrBasePaper ] quantum-assisted, two-player graph domination games, both theoretically and through simulation using classical as well as quantum processors. In graph theory, the domination problem is a purely combinatorial and static problem [ HaynesHHS1998 ] . A dominating set in a graph is a set of vertices such that every vertex in the graph is either in the set or adjacent to a vertex in the set. The classical graph domination problem asks for the smallest such set, or more generally, for structural and complexity properties of dominating sets. Graph domination has many applications, for instance to facility location and coverage problems [ FacilityLocation , Haynes2023-it ] . Since the early 2000s, however, there has also been interest in dynamic variants of graph domination involving mobile agents constrained to move along the edges of the graph [ Klostermeyer2020Oct ] . For example, the eternal domination problem, introduced in 2005 [ GoddardHedetniemi2005 ] , models guards that must continually relocate in response to attacks while ensuring that the occupied vertices remain a dominating set. More recently, in distributed computing and mobile robotics, researchers have considered algorithms in which robots collectively move so as to form a dominating set, often under additional algorithmic or memory constraints [ chand2023run ] . Unlike classical domination problems [ HaynesHHS1998 ] , the challenge in these agent-based domination problems is not only combinatorial (whether a dominating set exists) but also algorithmic and probabilistic (whether a team of moving agents can find one efficiently). A recent development is the introduction by Viola and Mironowicz of a graph-domination game where players have access to entangled quantum resources [ PiotrBasePaper ] . In the game they considered, two players are placed randomly on the nodes of a graph. They are tasked with coordinating their movements in order to dominate as much of the graph as possible. A node is dominated when there is a player on that node or on a node connected to it by an edge. The degree of success of a given strategy is the number of dominated nodes after the players have moved. Strategies can be characterised by their “domination number”: the average number of dominated nodes after many runs of the game. It was shown that this increases when quantum resources are available. Importantly, the qubits can be entangled before the players learn which vertices have been assigned to them. Afterwards, no further interaction or communication is required. The obtained quantum advantage is therefore not purely formal: it represents a real advantage that could be gained in real-life situations where such games need to be played, without the need to change the nature of the game - only the resources available to each player locally need to be modified. In Ref. [ PiotrBasePaper ] bounds on the degree of domination for 2-player games were obtained through semi-definite programming. Graphs with up to 13 vertices were considered. In the case of the pentagon (graph C_{5} ) the probabilities of all possible moves were reported. Here we build on that work by deducing explicit protocols that realise those probabilities and, for larger graphs, the predicted bounds. We generalise our strategies to cycle graphs of arbitrary size and simulate the games on NISQ hardware, finding that the qubits in present-day quantum processors are of sufficient quality to realise most of the predicted quantum advantage. 2 Theory We start by defining the rules of the game. The graphs the players will move on are unweighted and undirected. Each player will be allowed one move from their random starting positions. These initial positions are taken from a uniform probability distribution (in particular, it is possible that the players start on the same location, though even then they do not know the location of the other player). Waiting is not an allowable action. After all players have moved, their collective domination of the graph is checked. The nodes of the graph are labelled. The players have access to the label of the site they are on and can use that label to determine their actions. In other words, the players have a shared ’map’ of the graph. Finally, the players do not have to follow the same rules when making their decisions (player-asymmetric game). 1 1 1 This implies no loss of generality as player-symmetric strategies are a subset of player-asymmetric ones. Quantum advantage emerges when the players share parts of an entangled quantum system [ PiotrBasePaper ] . Specifically, each player has a member of a pair of entangled, n -state qudits, where n is the number of edges for each node of the graph. After a player measures their qudit they use the result to decide which of the n edges to travel along. Before measurement, each player is allowed to perform an arbitrary rotation on their qudit which may depend on their identity and the site they are on. If the two qudits are entangled, this crucial step allows players to encode information about their location in the shared quantum state - the essential source of the quantum advantage. In this paper, we will consider cycle graphs only, so the players will share a pair of qubits ( n=2 ). The players always start by placing their qubits in the joint Bell state |\psi\rangle=\frac{1}{\sqrt{2}}\left(|00\rangle+|11\rangle\right) (1) They then get separated and each player carries out a local unitary operation on their individual qubit that depends only on the site that

Read the complete text