PaperActive

Learning structural balance of graphs from quantum spectral features

quality89

Updated 7 h ago · first seen 11 Sept 2026

paper_01M294FRB4NRFJE2DPCA66PS99

Published: 11 Sept 2026; T1 · 7 h ago
arXiv: 2609.11736; T1 · 7 h ago
Category: quant-ph; T1 · 7 h ago

Abstract

We develop a quantum approach to spectral feature extraction from the density of states (DOS) of a problem-dependent Hamiltonian, and apply it to machine learning on signed graphs. We propose to embed a signed graph as an Ising model instance with positive and negative interactions, and use the standardized moments of the Ising DOS as features for learning. We show that these moments count signed closed walks, are switching-invariant, and are size-free by construction. As a benchmark, we target learning the frustration index, an NP-hard measure of structural balance that can be labeled exactly at moderate size. At zero field, the models can be sampled classically, allowing the quantum extraction procedure to be certified against exact ground truth. We propose DOS-QPE, a phase estimation on a purified maximally mixed probe, which samples the spectral density with orders of magnitude fewer shots than Hadamard test-based trace sampling and feeds the resulting features directly into classically trained models. On $1.4\times10^5$ labeled graphs the exact DOS determines the frustration index, and five moments recover it with a mean error of 0.4, well below one sign flip. Beyond zero field, the underlying trace-estimation problem is DQC1-complete, providing access to spectral features for which no efficient classical sampling method is known. Our work opens routes towards quantum applications in social network balance analysis, spin-glass studies, correlation clustering, and protein-interaction networks.

Authors 2

Stefano Scali, Oleksandr Kyriienko

Specification

Official page: arxiv.org/abs/2609.11736
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
Arxiv announce type: cross
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
arXiv id: 2609.11736
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
Categories: quant-ph, cond-mat.dis-nn, cs.LG, cs.SI
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
PDF: arxiv.org/pdf/2609.11736
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
Primary category: quant-ph
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
Published: 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh

Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →

Provenance

Attributed facts

Source tiers

T19

Freshest observation

7 h ago

Conflicts

None

As of

Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.

Claim history

9 claims · 9 properties

Official pageofficial_url1

Claim history for Official page
Value	Valid from → to	Status	Source	Confidence	Extractor
https://arxiv.org/abs/2609.11736	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Abstractabstract1

Claim history for Abstract
Value	Valid from → to	Status	Source	Confidence	Extractor
We develop a quantum approach to spectral feature extraction from the density of states (DOS) of a problem-dependent Hamiltonian, and apply it to machine learning on signed graphs. We propose to embed a signed graph as an Ising model instance with positive and negative interactions, and use the standardized moments of the Ising DOS as features for learning. We show that these moments count signed closed walks, are switching-invariant, and are size-free by construction. As a benchmark, we target learning the frustration index, an NP-hard measure of structural balance that can be labeled exactly at moderate size. At zero field, the models can be sampled classically, allowing the quantum extraction procedure to be certified against exact ground truth. We propose DOS-QPE, a phase estimation on a purified maximally mixed probe, which samples the spectral density with orders of magnitude fewer shots than Hadamard test-based trace sampling and feeds the resulting features directly into classically trained models. On $1.4\times10^5$ labeled graphs the exact DOS determines the frustration index, and five moments recover it with a mean error of 0.4, well below one sign flip. Beyond zero field, the underlying trace-estimation problem is DQC1-complete, providing access to spectral features for which no efficient classical sampling method is known. Our work opens routes towards quantum applications in social network balance analysis, spin-glass studies, correlation clustering, and protein-interaction networks.	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Arxiv announce typearxiv_announce_type1

Claim history for Arxiv announce type
Value	Valid from → to	Status	Source	Confidence	Extractor
cross	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

arXiv idarxiv_id1

Claim history for arXiv id
Value	Valid from → to	Status	Source	Confidence	Extractor
2609.11736	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Authorsauthors1

Claim history for Authors
Value	Valid from → to	Status	Source	Confidence	Extractor
Stefano Scali, Oleksandr Kyriienko	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Categoriescategories1

Claim history for Categories
Value	Valid from → to	Status	Source	Confidence	Extractor
quant-ph, cond-mat.dis-nn, cs.LG, cs.SI	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

PDFpdf_url1

Claim history for PDF
Value	Valid from → to	Status	Source	Confidence	Extractor
https://arxiv.org/pdf/2609.11736	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Primary categoryprimary_category1

Claim history for Primary category
Value	Valid from → to	Status	Source	Confidence	Extractor
quant-ph	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Publishedpublished_at1

Claim history for Published
Value	Valid from → to	Status	Source	Confidence	Extractor
11 Sept 2026	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →

Source documents
Source	Document	Type	Tier	Last observed	Snapshots
arXiv (Atom API + RSS)	rss.arxiv.org/rss/cs.LG	feed	T1· Official	5 h ago	1

Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.