Quantum embedding of graphs for subgraph counting

• URL: http://arxiv.org/abs/2604.18754v1
• Date: Mon, 20 Apr 2026 18:58:35 GMT
• Title: Quantum embedding of graphs for subgraph counting
• Abstract summary: We develop a unified quantum framework for subgraph counting in graphs.<n>We encode a graph on $N$ vertices into a quantum state on $2lceil log N rceil$ working qubits and $2$ ancilla qubits using its adjacency list.<n>This approach yields quantum logspace algorithms for motif counting, with no known classical counterpart.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Extending the Bloch sphere model to an N-qubit system [63.01002236320087]
  We propose a novel geometric model extending the Bloch sphere representation to arbitrary $N$-qubit systems.<n>We demonstrate that any pure 2-qubit state is uniquely described by three spheres: two for individual qubits and a third encapsulating bipartite entanglement.
  arXiv  Detail & Related papers  (2026-07-06T12:14:04Z)
• Quantum Algorithms for Approximate Graph Isomorphism Testing [0.0]
  We study the quantum query complexity of approximate graph isomorphism testing.<n>We present a quantum algorithm based on MNRS quantum walk search over the product graph $(G,H)$ of the two input graphs.
  arXiv  Detail & Related papers  (2026-03-03T06:43:41Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs.<n>We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.
  arXiv  Detail & Related papers  (2026-02-13T08:12:38Z)
• Combinatorial structures in quantum correlation: A new perspective [1.2078273498134855]
  We introduce a new class of quantum states, called $A_$-graph states.<n>The constructed states are different from the standard graph states arising from stabiliser formalism.<n>We develop a graph-theoretic formulation of a moments-based entanglement detection criterion.
  arXiv  Detail & Related papers  (2025-12-17T18:44:07Z)
• Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits [20.069035622098905]
  We focus on the Hamming-Weight-preserving states, defined as $psi_textHr = sum_textHW(x)=k alpha_x |xrangle$, which have leveraged their strength in quantum machine learning.<n>We propose an algorithm to build the preparation circuit of $O(log n)$-depth with $O(m)$ ancillary qubits.<n>Specifically for the $n$-qubit tree-structured and grid-structured states, the number of ancillary qubits in the corresponding preparation circuits
  arXiv  Detail & Related papers  (2025-08-20T06:50:13Z)
• Studies of properties of bipartite graphs with quantum programming [0.0]
  Multi-qubit quantum states corresponding to bipartite graphs $G(U,V,E)$ are examined.<n>The entanglement distance of the resulting states is derived analytically for an arbitrary bipartite graph structure.
  arXiv  Detail & Related papers  (2025-07-22T14:49:57Z)
• Graph state extraction from two-dimensional cluster states [37.19059223604783]
  We introduce graph state manipulation tools that allow one to increase the local degree and to merge subgraphs.<n>We show how to minimize overheads by avoiding multiple edges, and compare with a local manipulation strategy based on measurement-based quantum computation together with transport.<n>These schemes have direct applications in entanglement-based quantum networks, sensor networks, and distributed quantum computing in general.
  arXiv  Detail & Related papers  (2025-05-13T09:49:54Z)
• Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
  Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing. How to efficiently implement CTQWs is a challenging issue. In this paper, we study implementation of CTQWs on sparse graphs.
  arXiv  Detail & Related papers  (2024-08-20T05:20:55Z)
• Graph Neural Thompson Sampling [18.83205413952483]
  We consider an online decision-making problem with a reward function defined over graph-structured data. We then propose textttGNN-TS, a Graph Neural Network powered Thompson Sampling (TS) algorithm which employs a GNN approximator for estimating the mean reward function.
  arXiv  Detail & Related papers  (2024-06-15T16:45:27Z)
• Learning quantum graph states with product measurements [22.463154358632472]
  We consider the problem of learning $N$ identical copies of an unknown $n$-qubit quantum graph state with product measurements. We detail an explicit algorithm that uses product measurements on multiple identical copies of such graph states to learn them.
  arXiv  Detail & Related papers  (2022-05-13T02:55:21Z)
• Quantum Approximate Counting for Markov Chains and Application to Collision Counting [0.0]
  We show how to generalize the quantum approximate counting technique developed by Brassard, Hoyer and Tapp [ICALP 1998] to estimating the number of marked states of a Markov chain. This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful "quantum walk based search" framework established by Magniez, Nayak, Roland and Santha.
  arXiv  Detail & Related papers  (2022-04-06T03:04:42Z)
• On quantum tomography on locally compact groups [0.0]
  We introduce quantum tomography on locally compact Abelian groups $G$. We provide three examples in which $G=mathbb R$ (the optical tomography), $G=mathbb Z_n$ (corresponding to measurements in mutually unbiased bases) and $G=mathbb T$ (the tomography of the phase) As an application we have calculated the quantum tomogram for the output states of quantum Weyl channels.
  arXiv  Detail & Related papers  (2022-01-16T13:48:22Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.