Quantum Search on Bipartite Multigraphs

2025

Read Quantum Search on Bipartite Multigraphs (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-2504-12586.txt.

Introduction

Gustavo Alves Bezerra, Andris Ambainis, and Renato Portugal speed up search on special graphs in a paper from two thousand twenty-five. Quantum walks can find marked items faster than classical random walks. The team targets two-tessellable graphs, a wider family than ordinary bipartite graphs.

They adapt two quantum walk styles to these graphs and plug in a known fast algorithm for balanced bipartite search. The result finds a marked vertex with a quadratic speedup in oracle queries over classical chain-based search. Generalizing the walk models widens where quantum search helps. The authors present the speedup as a step in mapping which graph shapes suit quantum methods. Classical search pays a square penalty by comparison.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-12586

Browse the full library · About the Tower of Babel

Full text

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

Quantum Search on Bipartite Multigraphs Abstract Quantum walks provide a powerful framework for achieving algorithmic speedup in quantum computing. This paper presents a quantum search algorithm for 2-tessellable graphs, a generalization of bipartite graphs, achieving a quadratic speedup over classical Markov chain-based search methods. Our approach employs an adapted version of the Szegedy quantum walk model (adapted SzQW), which takes place on bipartite graphs, and an adapted version of Staggered Quantum Walks (Adapted StQW), which takes place on 2-tessellable graphs, with the goal of efficiently finding a marked vertex by querying an oracle. The Ambainis, Gilyén, Jeffery, and Kokainis’ algorithm (AGJK), which provides a quadratic speedup on balanced bipartite graphs, is used as a subroutine in our algorithm. Our approach generalizes existing quantum walk techniques and offers a quadratic speedup in the number of queries needed, demonstrating the utility of our adapted quantum walk models in a broader class of graphs. 1 Introduction Quantum walks are the quantum counterparts of classical random walks [ 4 ] and constitute a universal model of computation [ 16 , 23 ] . They have been applied to problems such as element distinctness [ 5 ] and spatial search [ 11 , 33 ] . In the spatial search problem on a graph with N vertices, an oracle marks the desired vertex or vertices, and the goal is to locate one of the marked vertices with the fewest possible queries to the oracle. Spatial search has been studied using various quantum walk models, including coined [ 3 ] , Szegedy’s [ 34 ] , continuous-time [ 19 ] , and staggered [ 31 ] . In the coined model, if we consider that the walker is located at a vertex, the coin determines the distribution of amplitudes to neighboring vertices using the graph structure [ 3 ] . Coined quantum walks were initially applied to spatial search, achieving a query complexity of O(\sqrt{N}) for the hypercube [ 33 ] and \tilde{O}(\sqrt{N}) for the two-dimensional grid [ 8 ] . 1 1 1 \tilde{O}(\cdot) notation hides polylogarithmic factors. Some polylogarithmic factors were eliminated by adding ancillas [ 35 ] , using classical post-processing [ 6 ] , and increasing laziness [ 37 ] . The problem of quantum search with multiple marked vertices has also been investigated [ 9 , 1 , 13 ] . However, in the coined model, certain cases involving multiple marked vertices result in search failure [ 9 , 32 ] . Szegedy [ 34 ] introduced a quantum walk model based on Markov chains. In this model, the Markov chain is transformed into a balanced bipartite graph (parts of equal size), and the quantum walk takes place in the Hilbert space spanned by the edges of this bipartite graph. Szegedy applied this framework to the detection problem. Krovi et al. [ 22 ] proposed a quantum algorithm based on interpolated quantum walks to locate marked vertices on a Markov chain, achieving a query complexity of O(\sqrt{HT^{+}}) 2 2 2 HT^{+} denotes the extended hitting time. . Ambainis et al. [ 7 ] later demonstrated that HT^{+} can be significantly larger than the hitting time HT when multiple marked vertices are present. In the same work, they proposed a quantum algorithm (AGJK’s algorithm) for searching a marked vertex on a Markov chain with a query complexity of \tilde{O}(\sqrt{HT}) even for multiple marked vertices. Our goal in this paper is to extend AGJK’s algorithm to a larger class of graphs. In the continuous-time quantum walk model, the evolution operator is derived from the adjacency or Laplacian matrix of the graph, which is implemented as a Hamiltonian [ 20 , 17 ] . For spatial search, Farhi and Gutmann [ 19 ] achieved a query complexity of O(\sqrt{N}) on the complete graph, while Childs and Goldstone [ 17 ] demonstrated a query complexity of \tilde{O}(\sqrt{N}) for the d -dimensional grid with d\geq 4 . Apers et al. [ 10 ] applied a technique similar to that in [ 7 ] to solve quantum search with \tilde{O}(\sqrt{HT}) queries for graphs corresponding to reversible Markov chains. Using an asymptotic approach, Lugão et al. [ 25 ] achieved a query complexity of O(\sqrt{N}) for Johnson graphs, while Lugão and Portugal [ 24 ] demonstrated the same complexity for certain t -designs. The staggered quantum walk model, introduced by Portugal et al. [ 31 , 28 ] , is based on graph tessellations and extends Szegedy’s quantum walks [ 27 ] . Portugal et al. [ 30 ] later generalized the evolution operator of staggered quantum walks by incorporating Hamiltonians. Initially, when staggered quantum walks without Hamiltonians were applied to the search problem on the two-dimensional grid, the results were no better than those of classical algorithms. However, by incorporating Hamiltonians into the evolution operator, Portugal and Fernandes [ 30 ] successfully performed quantum search on a grid and other general structures. More recently, Higuchi et al. [ 21 ] derived the eigenbasis of the evolution operator for staggered quantum walks with Hamiltonians on 2-tessellable graphs, interpreting the evolution operator as a quantum Markov chain. The set of 2-tessellable graphs corresponds to the line graph of the set \mathcal{S} of bipartite multigraphs, meaning that the set of 2-tessellable graphs is given by L(\mathcal{S}) , where L is the line-graph operator [ 2 ] . Given a graph G , its line graph L(G) is defined such that each vertex of L(G) corresponds to an edge of G , and two vertices in L(G) are adjacent if and only if their corresponding edges in G share a common endpoint. Conversely, if \mathcal{S}^{\prime} represents the set of 2-tessellable graphs, then the set K(\mathcal{S}^{\prime}) corresponds to the set of bipartite multigraphs, where K is the clique-graph operator. For any graph G^{\prime} , its clique graph K(G^{\prime}) is defined as the graph whose vertices correspond to the maximal cliques of G^{\prime} , with two vertices adjacent if their corresponding cliques share at least one vertex. Moreover, if the cliques share more than one vertex, then K(G^{\prime}) contains multiedges. A key limitation of AGJK’s algorithm is that it requires a balanced bipartite graph. Our goal is to extend quantum search to a broader class of graphs: bipartite multigraphs. To achieve this, we first generalize Szegedy’s quantum walk model to arbitrary bipartite graphs (balanced or unbalanced). We then adapt this model to perform quantum search, allowing for arbitrary sets of marked vertices. Lastly, we adapt the staggered quantum walk model to perform quantum search on 2-tessellable graphs allowing for arbitrary sets of marked cliques. By formulating the search in terms of the clique graph of 2-tessellable graphs, our approach effectively performs quantum search on bipartite multigraphs, allowing for arbitrary sets of marked vertices. In the standard Szegedy’s model, a Markov chain is first defined on a simple graph, from which a balanced bipartite graph is derived. In contrast, our approach starts with a quantum walk on an arbitrary bipartite multigraph with marked vertices, from which an underlying reversible Markov chain is obtained. This enables us to apply the AGJK’s algorithm [ 7 ] as a subroutine. However, since the underlying Markov chain does not contain sufficient information to uniquely reconstruct the original bipartite

Read the complete text