We develop a unified quantum framework for subgraph counting in graphs. We encode a graph on $N$ vertices into a quantum state on $2\lceil \log_2 N \rceil$ working qubits and $2$ ancilla qubits using its adjacency list, with worst-case gate complexity $O(N^2)$, which we refer to as the graph adjacency state. We design quantum measurement operators that capture the edge structure of a target subgraph, enabling estimation of its count via measurements on the $m$-fold tensor product of the adjacency state, where $m$ is the number of edges in the subgraph. We illustrate the framework for triangles, cycles, and cliques. This approach yields quantum logspace algorithms for motif counting, with no known classical counterpart.
We develop a unified quantum framework for subgraph counting in graphs. We encode a graph on N vertices into a quantum state on 2⌈log2N⌉ working qubits and 2 ancilla qubits using its adjacency list, with worst-case gate complexity O(N2), which we refer to as the graph adjacency state. We design quantum measurement operators that capture the edge structure of a target subgraph, enabling estimation of its count via measurements on the m-fold tensor product of the adjacency state, where m is the number of edges in the subgraph. We illustrate the framework for triangles, cycles, and cliques. This approach yields quantum logspace algorithms for motif counting, with no known classical counterpart.
Abstract The identification of RNA motifs plays a crucial role in understanding biological functions, predicting RNA 3D structures, and designing RNA-based therapeutics. One of the efficient strategies approaches this task by analyzing secondary structure graphs annotated with non-canonical base interactions, effectively reframing the problem as a two-dimensional graph-theoretic challenge. However, both the graph isomorphism problem and the maximum common subgraph problem in this domain are classified as NP-complete. Classical computing architectures struggle to address these problems efficiently due to their substantial computational resource demands. In this work, we propose a quantum algorithm specifically designed for processing RNA secondary structure graphs. By encoding the adjacency matrix into a quantum circuit and incorporating base interaction families as edge weights, our approach achieves a resource efficiency of 𝒪 (log 2 N ) in terms of qubits. Numerical simulations demonstrate the algorithm’s capability to identify 15 distinct motifs across three structural categories: hairpin loops, internal loops, and three-way junction loops. Furthermore, the method successfully detects the common motif between two complete RNA chains. Finally, 29 high conserved RNA motifs were identified in four cell lines of a key lung cancer biomarker gene (MIF), and their potential roles as drug targets were explored. This work presents a highly promising quantum computing framework for addressing the RNA motif identification problem.
We introduce a new notion of distance between two graph states ∣G⟩ and ∣G′⟩ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state ∣G⟩ from which both ∣G⟩ and ∣G′⟩ can be ``easily prepared''. (When preparing graph states, we are only allowed to use one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication.) We give a graphical description of this distance through the lens of vertex-minors. We then show how this distance yields quantum network analogs of many graph edit-distance problems.
Using this framework, we develop classical algorithms for identifying the ``highly entangled clusters'' of a graph state ∣G⟩. The ancilla integrity problem asks, given a graph G and integer k, for the minimum -- over all graph states ∣G′⟩ with distance at most k from ∣G⟩ -- of the maximum component size of G′. Up to a factor of 2 in the number of ancilla qubits, this problem is equivalent to rank integrity, where the distance between G and G′ is instead the minimum rank of the sum of their adjacency matrices over GF(2). We prove that rank integrity is XP parameterized by k. We also prove the complementary hardness result that rank integrity is W[1]-hard in k. Finally, we give an explicit O(n6)-time algorithm for ancilla integrity when G has n vertices and k=1.
Many combinatorial optimization problems are NP-hard, giving significant value to the discovery of efficient quantum solvers. In the context of quantum annealing, problems are expressed in the Ising model, and can be viewed as graphs. Thus an understanding of how such graphs can be embedded in an array of qubits, and how many qubits will be needed, are interesting questions. We review the currently known embedding algorithms, and apply them in a controlled fashion to graphs with a variety of sizes and characteristics, comparing the quality of embeddings and execution time. Multiple topologies for qubit couplings are considered, as well as the effect of defects. We develop analytic models and compare to the experimental results. Our lower bound shows that the qubit count scales linearly with the edge count, and gives a good estimate of the actual qubit requirements for dense graphs, without assuming any particular topology.
Subgraph detection asks whether an n-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph H. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of H is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds.
For every fixed r≥4, detecting the clique Kr requires nλr−o(1) queries, where λ4=19/18, the exponents λr increase strictly with r, and λr≥2−42/r+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph H with chromatic number c≥4. These bounds approach quadratic as c grows: for sufficiently large c, detection requires n2−O(loglogc/c)−o(1) queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph Kr,r requires nβr−o(1) queries, where β10=181/180 and βr≥2−O(1/r).
Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.
Quantum networks are important for quantum communication, enabling tasks such as quantum teleportation, quantum key distribution, quantum sensing, and quantum error correction, often utilizing graph states, a specific class of multipartite entangled states that can be represented by graphs. We propose a novel approach for distributing graph states across a quantum network. We show that the distribution of graph states can be characterized by a system of subgraph complementations, which we also relate to the minimum rank of the underlying graph and the degree of entanglement quantified by the Schmidt-rank of the quantum state. We analyze resource usage for our algorithm and show that it improves on the number of qubits, bits for classical communication, and EPR pairs utilized, as compared to prior work. In fact, the number of local operations and resource consumption for our approach scales linearly in the number of vertices. This produces a quadratic improvement in completion time for several classes of graph states represented by dense graphs, which translates into an exponential improvement by allowing parallelization of gate operations. This leads to improved fidelities in the presence of noisy operations, as we show through simulation in the presence of noisy operations. We classify common classes of graph states, along with their optimal distribution time using subgraph complementations. We find a sequence of subgraph complementation operations to distribute an arbitrary graph state which we conjecture is close to the optimal sequence, and establish upper bounds on distribution time along with providing approximate greedy algorithms.
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph H is present in an input graph G, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length k. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly k, or at most k. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes.
When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O(n3/2−αk), where αk∈Θ(c−k) and c=3+17/2≈1.33, beating the previous best upper bound O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n) query algorithm.