arxiv: 2604.18754 · v1 · submitted 2026-04-20 · 🪐 quant-ph · cs.CC

Recognition: unknown

Quantum embedding of graphs for subgraph counting

Bibhas Adhikari

Authors on Pith no claims yet

Pith reviewed 2026-05-10 04:21 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC

keywords subgraph countingquantum embeddinggraph adjacency statemotif countingquantum logspacetriangle countingclique countingquantum algorithms

0 comments

The pith

A quantum encoding of any graph into a state on O(log N) qubits enables counting its subgraphs through measurements on multiple copies.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to represent a graph with N vertices as a quantum state on roughly 2 log N working qubits plus two ancilla qubits by storing its adjacency list. It then constructs measurement operators that detect the edge patterns of a chosen subgraph when applied to m copies of this state, where m is the number of edges in the subgraph. Repeating the measurements yields an estimate of how many times that subgraph appears. The resulting procedure runs in quantum logarithmic space, providing algorithms for motif counting that have no known classical logspace equivalents. The framework is demonstrated for triangles, cycles, and cliques.

Core claim

We encode a graph on N vertices into a quantum state on 2⌈log₂ N⌉ working qubits and 2 ancilla qubits using its adjacency list, with worst-case gate complexity O(N²), 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. This approach yields quantum logspace algorithms for motif counting, with no known classical counterpart.

What carries the argument

The graph adjacency state, a quantum state on O(log N) qubits that stores a graph's adjacency list, together with measurement operators that probe the edge structure of a target subgraph on m copies of the state.

Load-bearing premise

The measurement operators applied to the m-fold tensor product produce accurate estimates of subgraph counts using only polynomial overhead and without exponential resources or noise that would break the logspace bound.

What would settle it

For a concrete small graph whose exact subgraph counts are known by classical enumeration, run the proposed quantum circuit and check whether the measurement statistics converge to the true counts or instead deviate by more than the claimed polynomial error.

Figures

Figures reproduced from arXiv: 2604.18754 by Bibhas Adhikari.

**Figure 2.** Figure 2: The quantum circuit for preparing |G⟩. Algorithm 1 Preparing the adjacency state |G⟩ Input: |0⟩ ⊗⌈log2 N⌉ for working qubits in register QR1, QR2; |0⟩ for ancillary qubits, the quantum circuits for UD and U (r) for each vertex r (Algorithms 3 and 2). Output: |G⟩ on the working qubits register Implement UD by measuring the ancilla qubit wrt Pauli Z operator in QR1 upon receiving |1⟩ for r = 0, 1, . . . , N … view at source ↗

**Figure 3.** Figure 3: (a) A random graph on 8 vertices. (b) The quantum circuit following Algorithm 2 for U (4) . Note that the quantum circuit representation of U (r) given by Algorithm 2 is expressed as U (r) = Y 0 j=dr−1 U (r,cj ) : |0⟩ |0⟩ ⊗n 7→ d Xr−1 j=0 1 √ dr |1⟩ |cj ⟩, where U (r,cj ) implements the map |0⟩ |0⟩ ⊗n q 7→ dr−j−1 dr−j |0⟩ |0⟩ ⊗n + q 1 dr−j |1⟩ |cj ⟩ for 0 ≤ j ≤ dr −1. For example, consider the randomly gen… view at source ↗

**Figure 4.** Figure 4: The quantum circuit following Algorithm 3 for [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

**Figure 6.** Figure 6: Normalized RMSE for estimating 4-cycle counts in ER graphs on N vertices [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗

**Figure 7.** Figure 7: Normalized RMSE for estimating 4-clique counts in ER graphs on N vertices the adjacency relations of a graph as a normalized vectorization of its adjacency matrix. The construction applies to both directed and undirected graphs through appropriate normalization, providing a unified framework for quantum graph embedding. We leverage this state to estimate subgraph frequencies, including cliques and cycles, … view at source ↗

**Figure 5.** Figure 5: Normalized RMSE for estimating triangle counts [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper sketches a logspace quantum encoding of graphs into O(log N) qubits plus measurements on tensor products to count fixed motifs, with the construction checking out at the resource level but thin on derivations.

read the letter

The main point is a quantum construction that loads a graph's adjacency list into a state on roughly 2 log N qubits and two ancillas, then estimates subgraph counts by designing measurement operators on the m-fold tensor product of that state, where m is the number of edges in the motif. It works through examples for triangles, cycles, and cliques and claims the whole procedure stays in quantum logspace with no known classical match at that space bound. The preparation circuit is O(N^2) gates, which is standard for adjacency data. The stress-test note is right that the qubit count and circuit size remain polynomial and logarithmic with no hidden exponential blowup for constant m. That part of the resource accounting holds up cleanly. What the paper does well is keep the same state preparation across motifs and only swap the measurement operators, which gives a unified framework without re-encoding the graph each time. The illustrations show how the edge structure gets captured directly in the operators. The soft spots are the missing pieces that would let a reader verify the central claims. The abstract describes the measurements as capturing edge structure and enabling estimation, but there are no explicit operator definitions, no derivation showing the expectation value equals the count without bias or scaling factors, and no shot-count or error analysis. Those details matter for confirming the polynomial overhead and the logspace bound in practice. The statement that there is no known classical counterpart also needs a direct comparison to classical space-bounded algorithms for fixed-motif counting; without it the novelty claim is hard to weigh. This is for people working on quantum algorithms for graphs or network analysis who want to think about space-efficient methods. A reader focused on quantum complexity or motif applications in biology or social networks could pull useful ideas even if they adapt the construction. I would send it to peer review. The basic model is consistent and the resource story is coherent, so referees can check the proofs, fill in the operator math, and test the classical comparison.

Referee Report

1 major / 2 minor

Summary. The manuscript develops a unified quantum framework for subgraph (motif) counting. Graphs on N vertices are encoded into a 'graph adjacency state' on 2⌈log₂ N⌉ working qubits plus 2 ancilla qubits via the adjacency list, prepared with O(N²) gates. Measurement operators are designed to capture the edge structure of a target m-edge subgraph; the subgraph count is estimated from expectation values on the m-fold tensor product of the adjacency state. The construction is illustrated for triangles, cycles, and cliques and is asserted to yield quantum logspace algorithms for fixed-motif counting with no known classical counterpart.

Significance. If the central construction is correct, the result would be significant: it supplies a direct quantum-logspace procedure for a family of graph problems whose classical logspace status is open, using only standard quantum operations, O(log N) qubits, and polynomially many measurements. The explicit qubit count, gate complexity, and tensor-product measurement design constitute concrete, falsifiable contributions to quantum complexity.

major comments (1)

[Measurement design] The central claim that expectation values of the designed operators on the m-fold tensor product yield unbiased estimates of the subgraph count (with only polynomial overhead) is load-bearing for the quantum-logspace assertion. The manuscript should supply the explicit operator definition and the short derivation showing that the expectation equals the desired count (including normalization).

minor comments (2)

[Abstract] The abstract states 'worst-case gate complexity O(N²)' for state preparation; it would be useful to state whether this bound is tight for sparse graphs and whether measurement circuits add further gates.
[Illustrations] For the triangle, cycle, and clique examples, a small-N numerical check (e.g., N=4 or 5) confirming that the measured expectation reproduces the known count would strengthen the presentation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

Thank you for the thorough review and the recommendation for minor revision. We appreciate the recognition of the potential significance of our quantum framework for subgraph counting. We address the major comment as follows.

read point-by-point responses

Referee: [Measurement design] The central claim that expectation values of the designed operators on the m-fold tensor product yield unbiased estimates of the subgraph count (with only polynomial overhead) is load-bearing for the quantum-logspace assertion. The manuscript should supply the explicit operator definition and the short derivation showing that the expectation equals the desired count (including normalization).

Authors: We agree that an explicit general definition of the measurement operators and the corresponding derivation will strengthen the presentation and make the unbiased estimation property easier to verify. In the revised manuscript we will add a dedicated subsection that defines the Hermitian measurement operator for an arbitrary m-edge motif as a sum, over all vertex tuples, of projectors onto the specific edge pattern of the motif tensored with the identity on the remaining qubits. We will include a short derivation showing that the expectation value of this operator on the m-fold tensor product of the graph adjacency state equals the subgraph count multiplied by a known normalization factor of order 1/N^{O(1)}, thereby confirming that the count can be recovered from polynomially many measurements. This addition directly supports the quantum-logspace claim. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents a direct quantum construction: the graph adjacency state is explicitly built from the adjacency list on O(log N) qubits with O(N^2) gates, and measurement operators are defined on the m-fold tensor product to extract subgraph counts via expectation values. No parameters are fitted, no self-citations justify core steps, and the logspace claim follows immediately from the stated qubit count and polynomial circuit size without reduction to prior results or definitions. The derivation chain is self-contained as a standard quantum algorithmic encoding.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available, so the ledger lists the minimal assumptions required to interpret the stated claims. No free parameters or invented entities are mentioned. The framework rests on standard quantum circuit assumptions and the premise that adjacency-list information can be faithfully embedded into the described qubit state.

axioms (2)

standard math Standard quantum circuit model with unitary gates and projective measurements
The encoding, state preparation, and measurement operators presuppose the usual quantum computing formalism.
domain assumption Graph adjacency information can be encoded into a quantum state on 2 log N + 2 qubits
The central construction begins with this embedding step.

pith-pipeline@v0.9.0 · 5413 in / 1372 out tokens · 64972 ms · 2026-05-10T04:21:51.014832+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

47 extracted references · 7 canonical work pages · 1 internal anchor

[1]

Laplacian matrices of weighted digraphs represented as quantum states.Quantum information processing, 16:1–22, 2017

Bibhas Adhikari, Subhashish Banerjee, Satyabrata Adhikari, and Atul Kumar. Laplacian matrices of weighted digraphs represented as quantum states.Quantum information processing, 16:1–22, 2017

2017
[2]

Discrete-time quantum walks: A quantum advantage for graph representation.arXiv preprint arXiv:2407.11630, 2024

Boxuan Ai. Discrete-time quantum walks: A quantum advantage for graph representation.arXiv preprint arXiv:2407.11630, 2024

work page arXiv 2024
[3]

Chapman and Hall/CRC, 2007

Uri Alon.An Introduction to Systems Biology: Design Principles of Biological Circuits. Chapman and Hall/CRC, 2007

2007
[4]

Complex networks: structure and dynamics.Physics Reports, 874:1–92, 2020

Stefano Battiston, Giulia Cencetti, Iacopo Iacopini, et al. Complex networks: structure and dynamics.Physics Reports, 874:1–92, 2020

2020
[5]

Training deep quantum neural networks.Nature communications, 11(1):808, 2020

Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias J Os- borne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf. Training deep quantum neural networks.Nature communications, 11(1):808, 2020

2020
[6]

Quantum machine learning of graph-structured data

Kerstin Beer, Megha Khosla, Julius K ¨ohler, Tobias J Osborne, and Tianqi Zhao. Quantum machine learning of graph-structured data. Physical Review A, 108(1):012410, 2023

2023
[7]

Quantum Amplitude Amplification and Estimation

Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation.arXiv preprint quant-ph/0005055, 2000

work page internal anchor Pith review arXiv 2000
[8]

The laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states.Annals of Combinatorics, 10:291–317, 2006

Samuel L Braunstein, Sibasish Ghosh, and Simone Severini. The laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states.Annals of Combinatorics, 10:291–317, 2006

2006
[9]

Motif counting beyond five nodes.ACM Transactions on Knowledge Discovery from Data, 13(2):1–25, 2019

Marco Bressan, Stefano Leucci, and Alessandro Panconesi. Motif counting beyond five nodes.ACM Transactions on Knowledge Discovery from Data, 13(2):1–25, 2019

2019
[10]

Persistent entanglement in arrays of interacting particles.Physical Review Letters, 86(5):910, 2001

Hans J Briegel and Robert Raussendorf. Persistent entanglement in arrays of interacting particles.Physical Review Letters, 86(5):910, 2001

2001
[11]

The complexity of theorem-proving procedures

Stephen A Cook. The complexity of theorem-proving procedures. InLogic, automata, and computational complexity: The works of Stephen A. Cook, pages 143–152. 2023

2023
[12]

Spectral entropies as information-theoretic tools for complex network comparison

Manlio De Domenico and Jacob Biamonte. Spectral entropies as information-theoretic tools for complex network comparison. Physical Review X, 6(4):041062, 2016

2016
[13]

Double sparse quantum state preparation.Quantum Information Processing, 21(6):204, 2022

Tiago ML de Veras, Leon D da Silva, and Adenilton J da Silva. Double sparse quantum state preparation.Quantum Information Processing, 21(6):204, 2022

2022
[14]

Quantum encoding of dynamic directed graphs.Journal of Logical and Algebraic Methods in Program- ming, 136:100925, 2024

Davide Della Giustina, C Londero, Carla Piazza, Brian Riccardi, and Riccardo Romanello. Quantum encoding of dynamic directed graphs.Journal of Logical and Algebraic Methods in Program- ming, 136:100925, 2024

2024
[15]

Con- dition for zero and nonzero discord in graph laplacian quan- tum states.International Journal of Quantum Information, 17(02):1950018, 2019

Supriyo Dutta, Bibhas Adhikari, and Subhashish Banerjee. Con- dition for zero and nonzero discord in graph laplacian quan- tum states.International Journal of Quantum Information, 17(02):1950018, 2019

2019
[16]

A complete characteriza- tion of unitary quantum space.arXiv preprint arXiv:1604.01384, 2016

Bill Fefferman and Cedric Yen-Yu Lin. A complete characteriza- tion of unitary quantum space.arXiv preprint arXiv:1604.01384, 2016

work page arXiv 2016
[17]

Quantum logspace com- putations are verifiable

Uma Girish, Ran Raz, and Wei Zhan. Quantum logspace com- putations are verifiable. In2024 Symposium on Simplicity in Algorithms (SOSA), pages 144–150. SIAM, 2024

2024
[18]

An efficient algorithm for sparse quantum state preparation

Niels Gleinig and Torsten Hoefler. An efficient algorithm for sparse quantum state preparation. In2021 58th ACM/IEEE Design Automation Conference (DAC), pages 433–438. IEEE, 2021

2021
[19]

Quantum experiments and graphs ii: Quantum interference, com- putation, and state generation.Proceedings of the National Academy of Sciences, 116(10):4147–4155, 2019

Xuemei Gu, Manuel Erhard, Anton Zeilinger, and Mario Krenn. Quantum experiments and graphs ii: Quantum interference, com- putation, and state generation.Proceedings of the National Academy of Sciences, 116(10):4147–4155, 2019

2019
[20]

Implementation of grover’s algorithm to solve the maximum clique problem

Andrew Haverly and Sonia L ´opez. Implementation of grover’s algorithm to solve the maximum clique problem. In2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 441–446. IEEE, 2021

2021
[21]

Probability inequalities for sums of bounded random variables.Journal of the American statistical association, 58(301):13–30, 1963

Wassily Hoeffding. Probability inequalities for sums of bounded random variables.Journal of the American statistical association, 58(301):13–30, 1963

1963
[22]

Encoding graphs into quantum states: an axiomatic approach.Physical Review A—Atomic, Molecular, and Optical Physics, 85(6):062313, 2012

Radu Ionicioiu and Tim P Spiller. Encoding graphs into quantum states: an axiomatic approach.Physical Review A—Atomic, Molecular, and Optical Physics, 85(6):062313, 2012

2012
[23]

Basic notions for the analysis of large two-mode networks.Social Networks, 30(1):31–48, 2008

Matthieu Latapy, Cl ´emence Magnien, and Nathalie Del Vecchio. Basic notions for the analysis of large two-mode networks.Social Networks, 30(1):31–48, 2008

2008
[24]

Improved quantum algorithm for triangle finding via combinatorial arguments

Franc ¸ois Le Gall. Improved quantum algorithm for triangle finding via combinatorial arguments. In2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 216–225. IEEE, 2014

2014
[25]

Nearly optimal circuit size for sparse quantum state preparation.arXiv preprint arXiv:2406.16142, 2024

Jingquan Luo and Lvzhou Li. Circuit complexity of sparse quantum state preparation.arXiv preprint arXiv:2406.16142, 2024

work page arXiv 2024
[26]

Quantum circuits for sparse isometries.Quantum, 5:412, 2021

Emanuel Malvetti, Raban Iten, and Roger Colbeck. Quantum circuits for sparse isometries.Quantum, 5:412, 2021

2021
[27]

Towards optimal circuit size for quantum sparse state preparation.arXiv preprint arXiv:2404.05147, 2024

Rui Mao, Guojing Tian, and Xiaoming Sun. Towards optimal circuit size for quantum sparse state preparation.arXiv preprint arXiv:2404.05147, 2024

work page arXiv 2024
[28]

Equivariant quantum graph circuits

P ´eter Mernyei, Konstantinos Meichanetzidis, and Ismail Ilkan Ceylan. Equivariant quantum graph circuits. InInternational conference on machine learning, pages 15401–15420. PMLR, 2022

2022
[29]

Finding small and largek-clique instances on a quantum computer

Sara Ayman Metwalli, Franc ¸ois Le Gall, and Rodney Van Meter. Finding small and largek-clique instances on a quantum computer. IEEE Transactions on Quantum Engineering, 1:1–11, 2020

2020
[30]

Network motifs: Simple building blocks of complex networks.Science, 298(5594):824–827, 2002

Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: Simple building blocks of complex networks.Science, 298(5594):824–827, 2002

2002
[31]

Ef- ficient deterministic preparation of quantum states using decision diagrams.Physical Review A, 106(2):022617, 2022

Fereshte Mozafari, Giovanni De Micheli, and Yuxiang Yang. Ef- ficient deterministic preparation of quantum states using decision diagrams.Physical Review A, 106(2):022617, 2022

2022
[32]

Mark E. J. Newman.Networks: An Introduction. Oxford University Press, 2010

2010
[33]

Cambridge university press Cambridge, 2001

Michael A Nielsen and Isaac L Chuang.Quantum computation and quantum information, volume 2. Cambridge university press Cambridge, 2001

2001
[34]

Circuit-based quantum random access memory for classical data

Daniel K Park, Francesco Petruccione, and June-Koo Kevin Rhee. Circuit-based quantum random access memory for classical data. Scientific reports, 9(1):3949, 2019

2019
[35]

Quantum circuit design for finding k-cliques via quantum amplitude amplification strategies

Simone Perriello. Quantum circuit design for finding k-cliques via quantum amplitude amplification strategies. InProceedings of the 22nd ACM International Conference on Computing Frontiers, pages 55–63, 2025

2025
[36]

Simple quantum algorithm to efficiently prepare sparse states.Physical Review A, 110(3):032609, 2024

Debora Ramacciotti, Andreea I Lefterovici, and Antonio F Ro- tundo. Simple quantum algorithm to efficiently prepare sparse states.Physical Review A, 110(3):032609, 2024

2024
[37]

A one-way quantum computer.Physical review letters, 86(22):5188, 2001

Robert Raussendorf and Hans J Briegel. A one-way quantum computer.Physical review letters, 86(22):5188, 2001

2001
[38]

A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets.ACM computing surveys (csur), 54(2):1–36, 2021

Pedro Ribeiro, Pedro Paredes, Miguel EP Silva, David Aparicio, and Fernando Silva. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets.ACM computing surveys (csur), 54(2):1–36, 2021

2021
[39]

On the role of graphs in quantum computing

Riccardo Romanello et al. On the role of graphs in quantum computing. 2025

2025
[40]

Quantum graph learning and algorithms applied in quantum computer sciences and image classification.Applied Physics Reviews, 12(2), 2025

Farzaneh Shayeganfar, Ali Ramazani, Veera Sundararaghavan, and Yuhua Duan. Quantum graph learning and algorithms applied in quantum computer sciences and image classification.Applied Physics Reviews, 12(2), 2025

2025
[41]

Chialvo, Marcus Kaiser, and Claus C

Olaf Sporns, Dante R. Chialvo, Marcus Kaiser, and Claus C. Hilgetag. Organization, development and function of complex brain networks.Trends in Cognitive Sciences, 8(9):418–425, 2004

2004
[42]

Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(10):3301–3314, 2023

2023
[43]

Efficient algorithms for clique problems

Virginia Vassilevska. Efficient algorithms for clique problems. Information Processing Letters, 109(4):254–257, 2009

2009
[44]

Space-bounded quantum complexity.Journal of Computer and System Sciences, 59(2):281–326, 1999

John Watrous. Space-bounded quantum complexity.Journal of Computer and System Sciences, 59(2):281–326, 1999

1999
[45]

Motif counting in complex networks: A comprehensive survey.arXiv preprint arXiv:2503.19573, 2025

Haozhe Yin, Kai Wang, Wenjie Zhang, Yizhang He, Ying Zhang, and Xuemin Lin. Motif counting in complex networks: A comprehensive survey.arXiv preprint arXiv:2503.19573, 2025

work page arXiv 2025
[46]

On encoding matrices using quantum circuits.arXiv preprint arXiv:2510.20030, 2025

Liron Mor Yosef and Haim Avron. On encoding matrices using quantum circuits.arXiv preprint arXiv:2510.20030, 2025

work page arXiv 2025
[47]

Quantum state preparation with optimal circuit depth: Implementations and applications.Physical Review Letters, 129(23):230504, 2022

Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. Quantum state preparation with optimal circuit depth: Implementations and applications.Physical Review Letters, 129(23):230504, 2022

2022