Learning structural balance of graphs from quantum spectral features Stefano Scali1, ∗ and Oleksandr Kyriienko2
arXiv:2609.11736v1 [quant-ph] 10 Sep 2026
2
1 Department of Physics and Astronomy, University of Exeter, Exeter EX4 4QL, UK School of Mathematical and Physical Sciences, University of Sheffield, Sheffield S10 2TN, UK
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 × 105 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.
I.
INTRODUCTION
Machine learning models for graphs rely on informative features, and spectral features are among the most effective. The spectra of adjacency and Laplacian operators summarize connectivity in a permutation-invariant way and underpin graph kernels and spectral embeddings [1]. Spectral convolutions built on the graph Laplacian power graph neural networks [2, 3], leading modularity eigenvectors enable community detection [4, 5], and combinatorial Laplacian spectra encode Betti numbers in topological data analysis [6–8]. A recurring object is the density of states (DOS), a global, basis-invariant spectral summary that quantum protocols can estimate directly without diagonalization [7, 9]. One direction that has received much less attention is that of signed graphs. Here every edge carries a positive or negative label, describing systems built on antagonistic pairwise relations: alliances and rivalries in social networks [10–12], correlation structures of financial assets [13], and quenched couplings of spin glasses [14–16]. A signed graph G is balanced when every cycle contains an even number of negative edges, and the frustration index L(G) measures the distance from balance: the minimum number of edge signs one has to flip to reach it. Computing L is NP-hard [15, 17], since it generalizes MAXCUT, which one recovers when all edges are negative. Integer programming solves moderate instances exactly [18], and signed-graph problems have recently drawn attention from the quantum side [19–22]. However, spectral feature sets designed for signed graphs remain scarce [23], even though the sign structure is precisely where quantities like structural balance reside.
Here, we develop a DOS-based quantum feature extraction and learning approach for signed graphs [Fig. 1]. The signed graph is embedded as an Ising Hamiltonian, closely related to Hamiltonian-based encodings for other graph problems [24, 25]. The relevant features are represented by the standardized moments of the Hamiltonian DOS. This construction matches the symmetry of the problem. The moments count signed closed walks through an exact combinatorial identity and are invariant under switching, the gauge transformation that preserves the frustration index. We benchmark the developed approach on the frustration index itself. Although NP-hard in the worst case, it can be labeled exactly at moderate sizes, allowing every prediction to be scored against ground truth. Across a dataset of 1.4 × 105 exactly labeled graphs, the exact DOS determines L, with no two graphs sharing a density of states while differing in frustration index. A regressor using five moments recovers L with a mean absolute error below 0.4 sign flips at n = 12 vertices across seventeen classes, while edge and triangle counting incurs twice the error on the same splits. The standardized moments are size-free, allowing the model to transfer across graph sizes and from synthetic ensembles to real-world signed networks. We highlight that the required features can be extracted natively on quantum hardware, providing access to the DOS without diagonalization. To this end, we simulate two quantum feature extraction routes. The first is a near-term approach that samples the trace of time evolution through Hadamard tests [7]. The second, introduced here as DOS-QPE, targets early fault-tolerant devices and applies quantum phase estimation (QPE) to a purified maximally mixed probe, so that each shot samples directly from the spectral density. Ref. [9] formalizes the corresponding estimation theory and extends the probe beyond maximal mixing. We show that DOS-QPE
2 quantum P
trace sampling · DOS-QPE
DOS p(E) √ ϕ(G) = µ2 , γ3 , . . . , γ6 five moments
H = − e σe Zu Zv Ising encoding classical signed graph G
linear model L̂(G)
switching-invariant · size-free
enumeration · Monte Carlo
Figure 1. The DOS feature pipeline for signed graphs. A signed graph G (positive edges solid, negative edges dashed) is encoded in its native Ising Hamiltonian, Eq. (6). The density of states of H is sampled by either arm of the pipeline: classically, by exact enumeration or Monte Carlo over uniform vertex 2-colorings (Proposition 1), or on quantum hardware, by trace sampling or by the DOS-QPE circuit of Fig. 5. Five spectral moments of the sampled density form the feature vector ϕ(G) of Eq. (3), which is switching-invariant and size-free by construction and feeds a classically trained model; we benchmark on the frustration index L(G), for which exact labels are available.
reaches the noiseless-feature ceiling with orders of magnitude fewer shots than trace sampling and allows its output to be used directly by classically trained models without retraining. At zero field, the pipeline can also be simulated classically. We prove that the DOS is samplable with one edge-list pass per draw (Proposition 1), allowing feature generation at arbitrary graph size while certifying the quantum routes against exact ground truth. For general dynamics, estimation of the normalized trace of the evolution is complete for the one-clean-qubit class (DQC1) [26, 27] and is therefore believed to be classically intractable, while the same feature extraction remains available on quantum hardware. We also show that the choice of encoding is essential: the line-graph (spin-ice) alternative is switching-blind, with a spectrum that carries no sign information (Appendix A). II.
SPECTRAL FEATURES FROM THE DENSITY OF STATES
The density of states (DOS) of a Hamiltonian H acting on a Hilbert space of dimension D, with spectral decomPD PD position H = i=1 ωi |i⟩⟨i|, is S(ω) = D−1 i=1 δ(ω − ωi ), normalized here to represent a probability density. Its Fourier transform is the normalized trace of the time evolution, Z 1 s(t) = tr U (t) = dω S(ω) e−iωt , U (t) = e−iHt , D (1) so estimating s(t) over time and inverting the transform recovers S(ω). This forms the basis of the near-term pipeline described in Sec. VII. We summarize the DOS through its moments, distinguishing two families. The energy moments are the raw spectral averages (2) Mk = tr H k /D, which carry the combinatorial content. For a Hamiltonian supported on a graph, they expand into counts of closed walks (Sec. V A). For learning features, we instead map the spectrum onto the unit interval by an
affine P rescaling ω 7→ x and use the central moments k µk = i pi (xi − x̄) of the resulting discrete distribution {(x P i , pi )}, where pi is the DOS weight of level i and x̄ = i pi xi . We define the standardized moments as k/2 γk = µk /µ2 , of which γ3 and γ4 are the skewness and kurtosis. Given a graph G and its Hamiltonian encoding, our feature vector is √ ϕ(G) = ( µ2 , γ3 , γ4 , γ5 , γ6 ) ,
(3)
providing five numbers per graph that capture the width of the rescaled spectrum and its four leading shape parameters. The standardized moments are dimensionless, while rescaling the spectral support makes the full feature set size-free by construction and comparable across graphs of different sizes. The pipeline, summarized in Fig. 1, has four stages: (i) encode the graph in a Hamiltonian whose spectrum carries the structure of interest; (ii) estimate the DOS, classically, by enumeration or, when the encoding permits it, by Monte Carlo (Sec. V B), or on quantum hardware, by trace sampling or direct spectral sampling; (iii) compress the density into the five moments of Eq. (3); (iv) feed them to a standard, classically trained model. Every stage is problem-agnostic except the first: the encoding decides which invariances the features inherit and which structure they can see. The remainder of the paper instantiates this pipeline for signed graphs, using an Ising Hamiltonian whose spectral features inherit the invariance required by the quantities of interest.
III.
FRUSTRATION INDEX
Next, we recall some core concepts from the theory of signed networks. The frustration index, also known as the line index of balance, is a fundamental measure of structural balance in signed graphs [10]. A signed graph is a graph G = (V, E, σ) with n = |V| vertices, where σ : E → {+1, −1} assigns a sign σe to each edge e, indicating a positive (friendly) or negative (hostile) relationship. For an edge e = {u, v}, we also write σuv . The frustration index measures the “distance” of a graph from
3 balance, i.e., from the condition that every cycle contains an even number of negative edges. Formally, the frustration index L(G) of the signed graph G is defined as the minimum number of edges whose sign reversal results in a balanced graph, ∗ L(G) = min (|X| : G ∗ = (V, E, σX ) is balanced) , X⊆E
(4)
∗ where σX agrees with σ on E \ X and flips the sign of every edge in X. Deleting the edges of X instead of flipping them yields the same minimum [17], so L(G) equally counts the fewest edge deletions that restore balance. Equivalently, the frustration index can be formulated in terms of vertex 2-colorings as o n {u, v} ∈ E : σuv ̸= (−1)f (u)⊕f (v) , L(G) = min f :V→{0,1}
(5) where we call an edge frustrated by the coloring f when it violates the condition σuv = (−1)f (u)⊕f (v) , and satisfied otherwise. This formulation highlights the connection to cut problems: for an all-negative signed graph, Eq. (5) reduces to MAXCUT, and the decision version of the problem is NP-complete [15, 17]. By contrast, deciding balance itself (L = 0) is solvable in linear time, illustrating the sharp difference between detecting perfect balance and determining the degree of frustration. Equation (5) is also the formulation we use to label our datasets exactly via a standard integer linear program (Appendix B) [18, 28, 29]. IV.
ISING GRAPH EMBEDDING
We map the frustration index problem onto a spinglass Ising Hamiltonian with quenched ±1 couplings supported on the edges of G [14, 16], X H= Jij Zi Zj , (6) {i,j}∈E
where Jij = −σij and Zi are Pauli-Z operators. Thus, a positive (friendly) edge gives a ferromagnetic coupling Jij = −1, while a negative (hostile) edge gives an antiferromagnetic coupling Jij = +1. By construction, Jij = 0 for non-neighboring vertices. The frustration index is exactly encoded in the groundstate energy of this Hamiltonian. For a computationalbasis state |s⟩, with s ∈ {±1}|V| denoting the corresponding Z eigenvalues and interpreted as a vertex 2-coloring, each satisfied edge contributes −1 and each frustrated edge +1. Hence, E(s) = 2fG (s) − |E|,
E0 = 2L(G) − |E|,
(7)
where fG (s) counts the edges frustrated by the coloring s. Estimating L(G) is therefore equivalent to determining the ground-state energy, motivating us to bypass optimization and instead extract information from spectral statistics.
Switching invariance. A switching transformation flips the signs of all edges across a cut (S, V \ S). It preserves the frustration index and partitions signed graphs into switching-equivalence classes, with G balanced iff it is switching-equivalent to the all-positive graph [30]. On the Hamiltonian side, switching by Q S is implemented by conjugation with the unitary US = i∈S Xi , with Xi the Pauli-X operator on vertex i: since Xi Zi Xi = −Zi , the conjugation flips exactly the couplings with one endpoint in S, Hσ′ = US Hσ US† ,
(8)
where Hσ denotes the Hamiltonian of Eq. (6) built on the sign function σ, and σ ′ is the switched assignment. The spectrum of H, and hence the DOS and all of its moments, is therefore a switching-class invariant, matching the invariance of L(G). The DOS features thus discard the gauge redundancy associated with the choice of representative within a switching class, while retaining sign information that is absent from the unsigned graph spectrum. In particular, a balanced graph has the same DOS as its unsigned counterpart. We stress that not every graph embedding preserves the relevant sign structure. A natural alternative encodes the signed graph in its line graph, with edges as sites and sign products on adjacent pairs, in the spirit of spinice constructions. We prove in Appendix A that this route is spectrally sign-blind: the signed line graph is switching-equivalent to the line graph of the underlying unsigned graph, so its spectrum carries no information about frustration. By contrast, the direct encoding of Eq. (6) retains the switching-class information on which balance quantities depend, and is therefore the encoding we adopt.
V.
MOMENTS OF THE ISING DENSITY OF STATES
We first consider the Hamiltonian of Eq. (6) without external fields, referring to this case as zero field. Its spectrum is supported on integers E ∈ {−|E|, . . . , |E|} of fixed parity; a transverse field is introduced later in Sec. V B. The affine rescaling of Sec. II then becomes x = (E + |E|)/(2|E|). Since tr H = 0, the rescaled spectrum has mean x̄ = 1/2 and carries no graph-dependent information, and the two moment families are related by µk = Mk /(2|E|)k for k ≥ 2. The first feature contains only the edge-count infor√ mation. As shown below, M2 = |E|, and hence µ2 = p 1/(2 |E|) exactly. We retain this feature because the classifier requires the edge count, while noting that the moment feature set therefore already contains |E|, which is relevant to the feature-set comparisons below. The remaining four standardized moments γ3 , . . . , γ6 capture the shape of the DOS and form the size-free part of the representation.
4
The energy moments of the DOS admit an exact combinatorial expansion in terms of the sign structure of the graph. Expanding the k-th Ppower of Eq. (6) in Eq. (2), with D = 2|V| and H = − {i,j}∈E σij Zi Zj , the uniform average over computational basis states annihilates every term in which any vertex appears an odd number of times. The surviving terms are ordered k-tuples of edges whose multiset has even degree at every vertex and can therefore be decomposed into closed circuits, k
Mk = (−1)
k Y
X k
(e1 ,...,ek ) ∈ E even vertex degrees
σ ea .
(9)
a=1
Q The sign product a σea of any closed circuit is switching-invariant, consistent with the spectral invariance derived above. The lowest moments are M1 = 0, M2 = |E|, M3 = −6 (t+ − t− ) = 12 t− − 6 t,
(10) (11)
where t± is the number of balanced/unbalanced triangles and t = t+ + t− . The third moment, equivalently the skewness of the DOS, counts triangle imbalance directly: unbalanced triangles shift the DOS towards positive skew [Fig. 2], connecting our lowest odd feature to triangle-based balance measures [22]. Even moments are dominated by sign-independent pairings of edges, such as the O(|E|2 ) contribution to M4 , with sign-sensitive corrections entering through short signed circuits (squares in M4 , pentagons in M5 , and so on). Odd moments, by contrast, are purely sign-sensitive. This explains the empirical feature hierarchy observed below: standardized odd moments (skewness, fifth moment) carry the frustration signal, while even moments encode the cycle structure against which it must be normalized. Higher moments probe progressively longer signed circuits, so that the collection {Mk } interpolates between local triangle counts and the global cycle-space information that ultimately determines L(G) through Eq. (7). B.
Classical samplability at zero field
For fixed k, Eq. (9) can be evaluated classically in time polynomial in |E|, so the low-order moments used by our classifier are themselves efficiently computable. At zero field, however, a stronger result holds: the full DOS can be sampled directly. Proposition 1 (Monte-Carlo samplability). Let G be a signed graph with m = |E| edges and let p(E) be the normalized DOS of the Hamiltonian in Eq. (6). Then p(E) P is the distribution of the random variable E(s) = − {u,v}∈E σuv su sv under s drawn uniformly from {±1}|V| . Hence, independent samples from the DOS
0.20 0.15
(b)
L=0 L=5 L = 10
0.5
skewness 3
(a)
Why moments encode frustration
p(E)
A.
0.10 0.05 0.00
0.0 0.5 1.0 1.5
25
0
E
25
2.0
0 2 4 6 8 10 12 14
L
Figure 2. (a) Exact DOS of three signed graphs with n = 10 vertices and |E| = 39 edges, with frustration index L = 0, 5, 10. Frustration drives the spectrum toward symmetry: the skewness rises from γ3 = −1.90 to −0.64 to −0.15 and the kurtosis falls from γ4 = 8.42 to 4.16 to 2.74, moving towards the Gaussian value of 3. The lower edge sits at E0 = −39, −29, −19, which is 2L − |E| in each case, as Eq. (7) requires. (b) DOS skewness γ3 against the frustration index across the n = 10 ensemble (2 × 104 graphs; gray: individual graphs, markers: median and interquartile range). The trend reflects Eq. (11), while the spread shows why a single moment is insufficient, motivating the combined features of Eq. (3).
can be generated classically at O(m) cost per draw, for any graph size.
Proof. The Hamiltonian H is diagonal in the computational basis with diagonal entries E(s), and the DOS assigns every basis state the same weight 2−|V| , which is the uniform distribution over colorings.
Proposition 1 enables a quantum-inspired version of the zero-field pipeline. It scales feature generation to arbitrary graph size, since classical Monte Carlo reproduces the entire zero-field spectral density, rather than only its low moments, at a measured cost near 1 ns per edge per draw. It also gives the quantum pipelines of Sec. VII an exactly certifiable target, a possibility rarely available on classically hard problems. A similar expansion shows where classical computability ends. A transverse field, P H(hx ) = H + hx i∈V Xi , keeps every fixed-order moment a closed-form polynomial in hx , since expanding tr H(hx )k in Pauli words annihilates every word carrying an odd number of X factors on any site, with M3 in particular exactly independent of hx . However, the field breaks the diagonal structure on which Proposition 1 rests, so that no classical sampler is known for the density itself or for spectral functionals beyond fixed-order moments, while the hardware routes of Sec. VII remain available.
5
Datasets. For each n = 6, . . . , 12, we generate a pool of 2 × 104 signed graphs from a density-swept Erdős– Rényi G(n, p) ensemble with p ∈ [0.25, 0.75]. We use two sign generators: independent random signs, and a near-balanced generator, constructed by randomly flipping signs in a balanced graph followed by a random switching, to populate the otherwise rare low- and highL classes. An integer linear program labels every graph exactly [Eq. (5)], in milliseconds at n = 12. The binding constraint on size is therefore not the labeling but the 2|V| enumeration behind the exact DOS, which is the constraint that Proposition 1 removes. Deduplication. Graphs sharing the exact energy histogram are indistinguishable to any method based on the DOS. These include isomorphic and switching-equivalent graphs, the latter produced deliberately by our nearbalanced generator, as well as accidental cospectral pairs. Splitting such graphs across training and test sets would introduce leakage, so we group the pool by exact histogram and retain one representative per group. The reduction is substantial at small sizes but negligible at large ones: the 2 × 104 graphs reduce to 654 distinct spectra at n = 6, 11 402 at n = 8, and 19 862 at n = 12. All numbers below are computed on the deduplicated sets, as mean and standard deviation over five stratified 70/30 splits. We cap each class at 1500 representatives and drop classes with fewer than 50, leaving 4 classes at n = 6 and 17 classes (L = 0, . . . , 16) at n = 12. Further details are given in Appendix B. An empirical ceiling. Grouping by exact histogram also measures how much the representation can possibly deliver. Across all 1.4 × 105 labeled graphs, every group of graphs sharing a DOS also shares a single value of L: no counterexample occurs at any size. On this corpus the exact density of states therefore determines the frustration index, and a Bayes-optimal predictor given the exact DOS would recover L without error. The errors reported below therefore arise from compressing the density into five features and from the learner, rather than from the full DOS representation. Models and baselines. Using the features of Eq. (3), we train a multinomial logistic regression that treats the frustration index as a class, together with linear and random-forest regressors that treat it as an ordinal quantity [31]. Regression performance is measured by the mean absolute error (MAE) of the rounded prediction. We compare against two groups of baselines. The first consists of counting features available directly from the edge list: edge count, negative-edge count, triangle count, and signed-triangle sum, which underlie degreeand triangle-based balance indices. The second consists of spectral balance measures from the signed-graph literaP ture: βA = i (λi (Σ)−λi (G))2 , γA = λ1 (G)−λ1 (Σ), and the smallest signed-Laplacian eigenvalue [23]. Here, Σ and G are the adjacency matrices of the signed graph and its underlying unsigned graph, respectively, with eigen-
(a)
1.0 exact-DOS ceiling
0.8 0.6
0.8 0.6 0.4
(b)
MAE
LEARNING THE FRUSTRATION INDEX
accuracy
VI.
0.4
moments trivial spectral moments+trivial all
0.2 6 7 8 9 10 11 12
n
0.0
6 7 8 9 10 11 12
n
Figure 3. Estimation quality against graph size for the feature sets of Sec. VI, on the deduplicated evaluation sets. Markers and error bars are the mean and standard deviation over five stratified 70/30 splits. (a) Multiclass accuracy of the multinomial logistic regression; the number of classes grows from 4 at n = 6 to 17 at n = 12. The dotted line is the exact-DOS ceiling: every group of graphs sharing a density of states also shares a single L, so a predictor with access to the full density would be exactly right, and the gap below it is the cost of compressing that density into five numbers. (b) Mean absolute error (MAE) of the rounded random-forest regression. Exactclass accuracy necessarily degrades as the label range grows, while the ordinal error stays below 0.4 sign flips throughout.
values ordered as λ1 ≥ · · · ≥ λn . Results. Estimation quality against graph size is shown in Fig. 3. At n = 6, the five DOS moments alone drive a linear classifier to 0.908 ± 0.011 accuracy, while adding the counting features reaches 0.973 ± 0.012. As n grows, the number of classes more than quadruples, and the moments-only accuracy falls to 0.550 ± 0.006 at n = 12, compared with 0.433 ± 0.008 for the counting features on the same splits. The ordinal view remains sharper: the rounded regression MAE is 0.388 ± 0.007 sign flips at n = 12 with moments alone and 0.340 ± 0.003 with all features, while the counting features give 0.759 ± 0.010. The DOS moments outperform the counting features at every size, by roughly 0.12 in accuracy and a factor of two in MAE at n = 12, showing that the DOS captures signed circuits missed by edge and triangle counts. Classical spectral balance summaries [23] outperform the DOS moments at most sizes (0.613±0.003 vs 0.581±0.006 for the random forest at n = 12), showing that frustration leaves a signature in the signed spectrum under different spectral summaries, without privileging our particular choice. The two feature families are complementary, and their union (“all”) gives the best performance throughout, reaching 0.688 ± 0.007 accuracy at n = 12. This remains below the exact-DOS ceiling of unit accuracy, indicating that a more informative summary of the same density is possible. Scope: estimation, not optimization. At the sizes studied here, exact answers are cheap. Twenty restarts of a textbook greedy 1-flip descent over vertex 2-colorings re-
6 cover the exact frustration index on at least 99.8% of the graphs and always provide a certified upper bound. The search cost is comparable to the 2|V| enumeration required for our features at n = 6 and more than an order of magnitude lower at n = 12 (Table I). The purpose of the spectral representation is therefore not to compete with direct optimization at small sizes. Its value lies in providing five switching-invariant, size-free features that any learning model can consume and that can be extracted on quantum hardware. The empirical ceiling stated above makes this precise. The exact density of states determines L on every one of the 1.4 × 105 labeled graphs, and five moments of that density recover it far above the reach of edge and triangle counting. That is a statement about what the spectrum of Eq. (6) encodes, rather than how efficiently it can be computed. A quantity defined through an optimization over 2|V| colorings leaves a strong signature in a handful of low-order spectral statistics, just as the third moment directly counts signed triangles. This makes the frustration index amenable to estimation from a measured density of states, with the quantum device performing Hamiltonian simulation rather than combinatorial optimization. Size transfer. The standardized moments of Eq. (3) are size-free (Sec. II), allowing models trained at small n to be applied directly at larger sizes. Training on n ≤ 11 and testing on n = 12, the moments-plus-counts model retains 0.566 ± 0.007 accuracy and the full feature set 0.621 ± 0.005, whereas the spectral-balance summaries, which are not size-normalized, fall to 0.215 ± 0.001. Within this range, the combined feature sets transfer best. Moments alone are less accurate than the counting features (0.350 ± 0.001 vs 0.410 ± 0.006), while still outperforming them in ordinal error (0.588 ± 0.001 vs 0.773 ± 0.002 MAE). The behavior changes sharply when the test graphs lie entirely outside the training-size range. Real networks. As an out-of-distribution test we apply models trained only on the deduplicated synthetic pools (n ≤ 12) to two classic signed social networks [32].
n 6 8 10 12
mean |Lh − L| 0.000 0.002 0.000 0.002
exact 100.0% 99.8% 100.0% 99.8%
t(features) 4 µs 27 µs 55 µs 371 µs
t(search) 6 µs 11 µs 10 µs 18 µs
MAE 0.123 0.147 0.260 0.388
Table I. Multi-restart local search against the learned estimator, on the deduplicated evaluation sets (500 graphs per size, median times, single thread). Lh is the frustration index returned by the search; t(features) is the exact-DOS enumeration the estimator requires; t(search) is the entire heuristic. The last column repeats the estimator’s momentsonly rounded-regression mean absolute error (MAE) from Fig. 3(b).
Gahuku-Gama alliance network
Figure 4. The Gahuku-Gama alliance network [11] visualized as a signed graph of n = 16 tribes with 29 positive (rova, solid) and 29 negative (hina, dashed) edges corresponding to alliances and antagonistic relations, respectively. Node color marks the two alliance blocs, and the frustration index is L(G) = 7.
The first one is the Gahuku-Gama alliance network of the New Guinea highlands (n = 16, |E| = 58, 29 negative) [11], shown in Fig. 4. The second one is the Sampson monastery network (n = 18) [12], which we discuss below. For Gahuku-Gama the exact frustration index, recomputed with our ILP, is L = 7, in agreement with Ref. [17]. Reading only the five moments, and trained on graphs four vertices smaller, the multinomial logistic regression puts 0.574±0.016 of its probability on the true L = 7, and the linear ordinal regressor predicts 7.09. The feature families behave differently under this extrapolation. Adding the raw counting features, despite improving estimation throughout the training-size range, causes the same classifier to assign 0.978 probability to L = 9 and essentially none to the correct class. Edge, negative-edge, and triangle counts grow directly with graph size, so a model relying on them encounters feature values outside its training range and becomes confidently incorrect. By contrast, the normalized DOS features retain their interpretation across graph sizes and transfer successfully even though they are not the most accurate representation in distribution. The Sampson network [12] probes the opposite boundary and delimits the training envelope. Symmetrized by the sign of the net pair rating it has |E| = 110 and L = 29, far outside the training label range L ≤ 16, forcing the estimator to extrapolate. The classifier saturates at its highest available class, while the random-forest regressor returns a frustration density L/|E| of 0.119 against the true 0.264, with no indication that the input lies outside the training distribution. The practical lesson concerns training pool design: the synthetic ensemble must cover the density and frustration regime of the target graphs. The size-normalized features make this easier to achieve across different graph sizes, since appropriate training data can be generated at any convenient n. Sampson’s ratings are directed, so the frustration index itself depends on how the directed ratings are converted into a signed undirected graph. We therefore examine
7 several conventions rather than assigning a unique value. Symmetrizing by the sign of the net pair rating gives L = 29 over 110 edges; keeping zero-net pairs as positive gives L = 36 over 126 edges; calling an edge negative whenever either direction is negative gives L = 35; and restricting to the 48 reciprocated pairs gives L = 8. The corresponding frustration densities are 0.264, 0.286, 0.278, and 0.167. The normalized quantity is therefore more comparable across conventions than L itself, motivating frustration density as a natural target for realworld networks.
VII.
QUANTUM PIPELINES
The pipeline of Sec. VI used exact spectra. Proposition 1 guarantees that at zero field these spectra are also cheap classically. This makes the frustration index a rare benchmark for quantum protocols: the hardware pipeline can be certified end to end against exact ground truth. Here we perform that certification and ask which quantum route returns the DOS most cheaply, and how much sampling it takes before a downstream classifier stops noticing the difference. We simulate both routes end to end and sample from the exact outcome statistics of each protocol, so that shot noise, the dominant error source, enters exactly. NISQ route: trace sampling. On noisy intermediatescale quantum (NISQ) hardware, the normalized trace s(t) = tr U (t)/2|V| is estimated by Hadamard tests on a maximally mixed input, with Re s and Im s each obtained from a finite number of binary shots [7]. Because the zero-field spectrum is integer, sampling on the uniform time grid tk = 2πk/K with K = 2|E| + 2 points suffices for the inverse discrete Fourier transform to recover the DOS exactly in the infinite-shot limit; at finite shots the reconstructed DOS is clipped at zero and renormalized before computing Eq. (3). Early fault-tolerant route: DOS-QPE. We introduce a circuit that samples the DOS directly, which we name DOS-QPE and draw in Fig. 5: textbook quantum phase estimation run not on an eigenstate but on the maximally mixed state ρ = 1/2|V| , prepared unitarily as half of a maximally entangled state (one Bell pair per system qubit, the purifying register left idle). An M -qubit phase register applies the controlled powk ers U 2 of U = e−iHτ , with τ = 2π/(2|E| + 2), and is read out after an inverse quantum Fourier transform. This τ maps the integer spectrum onto the distinct eigenphases φj = (Ej + |E| + 1)/(2|E| + 2), after the trivial relabeling of register outcomes that absorbs the sign and offset of the raw phase −Ej τ /(2π) mod 1. The choice essentially maximizes τ without aliasing: the spectrum spans 2|E| + 1 integer values, so any period of 2|E| or less would wrap the band edges onto each other; a period of 2|E| + 2, matching the time grid of the trace route, leaves every eigenvalue with its own phase and one empty slot, and any finer τ would waste register
H |0⟩⊗M
H
QFT†
.. .
.. .
y
H |0⟩⊗|V|
H ⊗|V|
U2
0
U2
1
···
U2
M −1
|0⟩⊗|V|
Figure 5. The DOS-QPE circuit. The lower two registers hold |V| qubits each. A layer of Hadamards followed by a transversal cnot prepares one Bell pair per system qubit, so that discarding the purifying register, which takes no further gates and is never measured, leaves the system in ρ = 1/2|V| . Phase estimation then proceeds as usual: the M -qubit register k controls the powers U 2 of U = e−iHτ with τ = 2π/(2|E| + 2), and an inverse quantum Fourier transform is followed by measurement. Because the probe weighs every eigenstate equally, each outcome y is one flat-weight draw from the spectral density, and the empirical moments of the sampled phases are the features of Eq. (3). The register size M sets the resolution of the sampled density and, through Table II, the highest moment order that survives the kernel.
resolution on phases the spectrum never visits. Because the probe weighs all eigenstates equally, the register outcomes y ∈ {0, . . . , 2M − 1} are distributed according to the spectrum P −|V|convolved with the M -bit QPE kernel, P (y) = FM (y; φj ), with FM (y; φ) = j2 |sin π2M ∆ /(2M sin π∆)|2 and ∆ = φ − y/2M . Each shot is one flat-weight draw from the DOS, and the features of Eq. (3) are the empirical moments of the sampled phases. Ref. [9] develops the extension beyond maximally mixed probes, where arbitrary purification unitaries select general spectral weights, together with a formalized post-processing and estimation pipeline. Results. Both routes are run on the same deduplicated graphs the classical estimator was evaluated on, over a full grid of shot budgets and register sizes, with five stratified splits per configuration. Figure 6(b) shows the n = 8 comparison. The two parameters play distinct roles: the shot budget governs how quickly each curve rises by controlling the sampling variance, while the register size determines where it saturates by fixing the kernel bias that cannot be removed by increasing the number of shots. (i) Shot efficiency. DOS-QPE with an M = 10 register reaches 0.764 ± 0.016 at 104 shots. NISQ trace sampling remains at 0.612 ± 0.008 at the same budget, reaches only 0.745 ± 0.019 at 106 shots, and does not attain the QPE performance within the range studied. Matching the DOS-QPE result therefore requires more than two orders of magnitude more measurements for the nearterm route. (ii) The register sets the plateau. At n = 8, the exactmoment ceiling is 0.786 ± 0.012, obtained by feeding the same classifier noiseless moments. This is the best performance attainable by any sampler of Eq. (3) and is distinct from the exact-DOS ceiling of Sec. VI, which no five-
8
(a)
0.8
0.15 0.10 0.05 0.00
exact-moment ceiling
0.7
accuracy
p(E)
0.20
(b)
NISQ DOS-QPE exact
0.6 0.5
NISQ QPE M = 6 QPE M = 8 QPE M = 10 QPE M = 12
0.4 0.3
10
0
E
10
0.2
103
shots
105
Figure 6. (a) DOS reconstruction for an n = 8, |E| = 14, L = 4 graph at 103 shots, aggregated on the physical energy grid: exact spectrum (gray), NISQ trace sampling (orange), DOS-QPE with M = 8 register bits (blue). The NISQ reconstruction develops spurious tail weight, from clipping the noisy inverse Fourier transform, which biases the highorder moments we use as features. (b) Classifier accuracy at n = 8 against shot budget, for models trained and tested on quantum-sampled features. Markers and error bars are the mean and standard deviation over five stratified splits of the deduplicated set; the band is the exact-moment ceiling with its own spread. Two controls act independently: the shot budget sets how fast each curve rises, while the register size M sets the plateau it rises to. A 6-bit register saturates at 0.727 ± 0.012, short of the 0.786 ± 0.012 ceiling, whereas M ≥ 10 reaches the ceiling and stays there. NISQ trace sampling has not caught up even at 106 shots.
number compression reaches. A 6-bit register saturates at 0.727 ± 0.012 and stops improving beyond 105 shots, leaving an irreducible deficit of about 0.06. Increasing the register to M = 8 raises the plateau to 0.777 ± 0.011, while M = 10 and M = 12 reach 0.782 ± 0.011 and 0.785 ± 0.012, respectively, indistinguishable from the ceiling. The same pattern holds at n = 12, where M = 10 and M = 12 both converge to 0.559, against a ceiling of 0.559 ± 0.008. This mirrors Table II: the plateau deficit is set by the moment bias imposed by the kernel, so improving beyond it requires more register qubits rather than more shots. (iii) Train classically, deploy quantumly. Training on exact moments and testing on quantum-sampled features represents the realistic deployment mode, since training data come from classical simulation. This transfer succeeds only when the kernel bias is small enough that the classical and quantum feature distributions remain sufficiently aligned. At n = 8 transfer accuracy tracks the self-trained value almost exactly for M = 12 (0.789 ± 0.014 against 0.784 ± 0.016) and for M = 10 (0.768 ± 0.015 against 0.781 ± 0.012), but falls away at M = 8 (0.597±0.012 against 0.774±0.009) and collapses at M = 6 (0.422±0.016 against 0.725±0.011). The NISQ route reaches 0.638 ± 0.014 only at 106 shots, because clipping the noisy inverse transform distorts the feature
distribution rather than merely broadening it. A classically trained model can therefore be deployed on quantum hardware using sampled features, but only above a register threshold, which for the five-moment feature set is M ≳ 10. Register resolution sets the usable moment order. The register outcomes follow the DOS convolved with the QPE kernel. As this kernel has 1/∆2 tails, it places weight far from each eigenvalue. High-order standardized moments are particularly sensitive to this leakage because they increasingly weight the tails. The resulting error is a bias rather than a variance: it does not vanish with more shots, but only with increasing register size. Table II compares both samplers against the exact moments on 300 graphs at n = 10, each using 105 shots. Classical Monte Carlo, which draws from the true density, maintains small relative errors across all moment orders, with the remaining error due entirely to sampling variance. DOS-QPE matches this accuracy through the fourth moment at M = 10 and through the sixth at M = 12, but then degrades rapidly with moment order. By order 20, the estimate is no longer useful for any register considered here. Each additional pair of register qubits reduces the sixth-moment bias by a factor of three to six, while increasing the number of controlled evolutions by a factor of four. The pipeline of Eq. (3) therefore requires M ≳ 10, set by the highest retained moment rather than by any need to resolve individual spectral levels. This requirement remains mild because the feature set is low-order. Retaining higher moments would require progressively larger registers, which we do not pursue here. At the sizes studied, the additional accuracy from such moments is driven by the lower spectral edge, whose relative weight decreases exponentially with graph size, making this advantage increasingly difficult for any sampling-based approach to retain. Since cumulants add under convolution and the QPE kernel is known in closed form, its contribution could in principle be subtracted rather than resolved, further relaxing the register requirement. We leave this possibility to future work.
moment order 3 4 6 12 20
classical MC 0.033 0.003 0.007 0.022 0.034
M =8 0.059 0.066 0.310 7.3 231
M = 10 0.034 0.011 0.052 1.2 39.8
M = 12 0.032 0.005 0.017 0.24 5.1
Table II. Median relative error |γ̂k − γk |/|γk | of standardized moments estimated from 105 draws, against the exact values, for 300 graphs at n = 10. Classical Monte Carlo draws from the true density and its error is pure variance. DOS-QPE draws from the kernel-convolved density, so its error contains a bias that no shot budget removes.
9 VIII.
DISCUSSION
Our results are average-case statements about estimation over natural ensembles and two real networks, complementary to the worst-case intractability of exact computation. Typical signed graphs carry substantial spectral information about their frustration index, and the exact DOS determines it across our entire dataset. The five-moment representation remains below this ceiling, while the complementary performance of the spectralbalance summaries of Ref. [23] suggests that the same density admits more informative compressions. These could include spectral functionals beyond moments, such as tail quantiles or low-lying gaps, which DOS-QPE can access with the same underlying circuit. On the learning side, the real-network tests also establish a requirement on training-pool design: the ensemble must cover the density and frustration regime of the target graphs. The size-normalized features make this easier to satisfy because training can be performed at a convenient graph size. Interestingly, related approaches to physics-native feature extraction have recently proved useful in other learning settings. Directly measured optical spectra can serve as learning features, with the emission spectrum of a single nonlinear mode enabling classical recognition of squeezed quantum states [33], while quantum Fourier features extracted from quantum-encoded flow fields enable the detection of vortical structures [34]. For graph learning, photonic positional embeddings generated by light propagation on synthetic frequency lattices can augment graph neural networks [35], while lattices of polariton condensates can physically encode relational and topological information for subsequent classical learning [36]. Together with the present results, these examples point to a broader role for physics-native and spectral features as representations that can enhance machine learning. On the hardware side, the register requirement M ≳ 10 is set by kernel bias in the higher-order moments and could be relaxed by the kernel-subtraction postprocessing outlined in Sec. VII. The zero-field benchmark is classically samplable (Proposition 1), which enables exact certification of the quantum extraction routes and provides a controlled boundary between classically accessible and more general dynamics. Beyond zero field, normalized-trace estimation for general dynamics is DQC1-complete [26, 27]. Fixed-order moments remain classically computable even under a transverse field, but spectral functionals beyond them, beginning with the sampled density itself, have no known efficient classical sampler; DOS-QPE provides access to these while retaining the sample-complexity guarantees of Ref. [9]. Another motivation is the native realization of Ising models in neutral atom arrays with Rydberg-mediated interactions. These systems provide a promising hardware route for implementing the Ising dynamics required by both pipelines, with programmable Ising-type Hamiltonians available through analog evolution and gate-
based control [37, 38]. On the application side, the same framework extends naturally beyond balance analysis and social networks. Signed interactions arise in spin glasses [39], regulatory networks [40], and protein-interaction networks [41], and related signed-graph problems include correlation clustering [42]. Across these settings, DOS-based features can provide a compact, switching-invariant summary of global structure that can be extracted on quantum hardware through Hamiltonian simulation. Finally, the lemma in Appendix A adds a broader design principle: spectral methods for signed structures are not encoding-agnostic. The line-graph route, natural from a spin ice perspective, provably discards all sign information, whereas the direct encoding of Eq. (6) preserves the switching-class information on which balance quantities depend. The effectiveness of the resulting representation therefore comes from matching the Hamiltonian symmetry to the invariances of the learning problem. DOS-based spectral features, already useful for topology and community structure [5, 7, 8], extend naturally to signed graphs and provide a route from quantum spectral estimation to classical learning without requiring the quantum device itself to solve the underlying combinatorial optimization problem.
IX.
CONCLUSIONS
We developed a quantum approach to spectral feature extraction from the density of states of a problemdependent Hamiltonian and applied it to signed-graph learning. Signed graphs are embedded as Ising Hamiltonians whose energy moments count signed closed walks and yield switching-invariant spectral features. Using the frustration index as a benchmark, we showed that the exact DOS determines the target across 1.4 × 105 labeled graphs, while five moments recover it with a mean error of 0.4 sign flips. We introduced DOS-QPE, which samples the spectral density with orders of magnitude fewer shots than Hadamard-test trace sampling and supports direct use of classically trained models. At zero field, classical DOS sampling enables exact certification. Beyond zero field, the underlying trace-estimation problem is DQC1-complete, providing access to spectral features for which no efficient classical sampler is known.
ACKNOWLEDGMENTS
The authors would like to thank Shaheen Acheche and Louis-Paul Henry from Pasqal for useful discussions. O. K. acknowledges the support from UK EPSRC award under the Agreement No. EP/Z53318X/1 (QCi3 Hub).
10 Appendix A: Line graphs cannot hear frustration
Given a signed graph G = (V, E, σ) with underlying unsigned graph G, define its signed line graph Λ(G) as the graph whose vertices are the edges E, with e ∼ f whenever e and f share an endpoint, and with edge signs given by the product σef = σe σf . This is the natural “spinice” encoding in which frustrated plaquettes of G would be represented by interactions among edge variables. Lemma 1. Λ(G) is switching-equivalent to Λ(G), the allpositive line graph of the underlying graph: with W = diag (σe )e∈E , AΛ(G) = W AΛ(G) W.
(A1)
Consequently, the adjacency and signed-Laplacian spectra of Λ(G), and the spectrum of any Ising Hamiltonian of the form of Eq. (6) built on Λ(G), are independent of the sign function σ. No spectral functional of Λ(G) can determine L(G). Proof. Entrywise, [AΛ(G) ]ef = σe σf [AΛ(G) ]ef by the definition of the sign product, which is Eq. (A1). Since W is diagonal with entries ±1, it is orthogonal, so the adjacency spectra coincide. The signed Laplacian (the degree matrix minus the adjacency) conjugates the same way because the degree matrix is diagonal. For the Ising HamilQ tonian, conjugation by U = e: σe =−1 Xe maps HΛ(G) to HΛ(G) , cf. the switching argument of the main text. Finally, the frustration index is not constant on sign configurations of a fixed underlying graph (the all-positive and all-negative triangles have L = 0 and L = 1 but identical Λ spectra), so no function of the Λ(G) spectrum can compute it. The lemma explains a dead end that, to our knowledge, has not been recorded: any pipeline that extracts spectral statistics (moments, DOS, gaps, spectral measures of balance) from this line-graph encoding returns exactly the same answer for every signing of a given graph, and cannot even separate balance from maximal frustration. The information loss occurs at the embedding stage, before any classification method is applied. The statement concerns the product-sign line graph defined above; sign conventions based on bidirected incidences [30] define different objects and are not covered by (nor needed for) our argument. We verified Eq. (A1) as an exact integer identity, along with the coincidence of adjacency and Ising spectra and the variation of L across signings, on 320 random signed graphs with n = 5–7 (code accompanies the paper).
[1] Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5:6, 2020. doi:10.1007/s41109-019-0195-3. [2] Michaël Defferrard, Xavier Bresson, and Pierre Van-
Appendix B: Datasets, labeling, and models
Exact labeling. We label every graph by the standard ILP formulation of Eq. (5) [18]: binary color variables xv , frustration indicators ye , constraints ye ≥ ±(xu − xv ) for positive edges and ye ≥ xu + xv P − 1, ye ≥ 1 − xu − xv for negative edges, objective min e ye , with x1 = 0 breaking the global flip symmetry; solved with HiGHS via JuMP [28, 29]. Against brute-force enumeration on 80 graphs (n = 4 to 7) the ILP agrees exactly and runs about 360 times faster already at n = 7. We checked every returned flip set by applying it and confirming the resulting graph has no unbalanced cycle, and every instance in the corpus closed to proven optimality, so no label in this paper rests on a truncated search. Pools. Per size n ∈ {6, . . . , 12}: 2 × 104 graphs made unique at generation time by hashing the edge list and sign vector, generators as in Sec. VI, seeds and generator parameters stored with the data. That hash removes literal repeats only; the far stronger deduplication by exact energy histogram described in Sec. VI, which is what the evaluation uses, is applied afterwards and reduces these pools to between 654 and 19 862 distinct spectra. The zero-field spectrum is computed directly as the 2n coloring energies of Eq. (7), without constructing any operator. Models. Multinomial logistic regression (no regularization, standardized inputs), random-forest classifier and regressor (300 trees), and linear regression [31]. Every reported number is the mean and standard deviation over five stratified 70/30 splits of the deduplicated set, with a per-class cap of 1500 and a minimum class size of 50 applied after deduplication. Reported MAEs score rounded regression outputs against the integer label. Quantum simulations. Both pipelines are sampled from exact outcome statistics: binomial shot noise on Re s(tk ), Im s(tk ) for the NISQ route, and multinomial sampling of the kernel-convolved register distribution for DOS-QPE. Graphs are the deduplicated representatives of Sec. VI, stratified by L with a cap of 400 per class, giving 622, 2883 and 6283 graphs at n = 6, 8 and 12. The grid is rectangular: every shot budget in {102 , . . . , 106 } for NISQ, and every pair of M ∈ {6, 8, 10, 12} with the same budgets for DOS-QPE. The kernel-convolved distribution is built once per graph and register size, then sampled at each budget. Simulator moments converge to the exact features in the large-shot limit (deviations ∼3 × 10−2 in γ6 at 107 shots).
dergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, volume 29, pages 3844–3852, 2016.
11 [3] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. [4] M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577–8582, 2006. doi:10.1073/pnas.0601602103. [5] Chukwudubem Umeano, Stefano Scali, and Oleksandr Kyriienko. Quantum community detection via deterministic elimination. Physical Review A, 112(5):052422, 2025. doi:10.1103/s7cm-c9qy. [6] Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2):255–308, 2009. doi:10.1090/S0273-0979-09-01249-X. [7] Stefano Scali, Chukwudubem Umeano, and Oleksandr Kyriienko. Quantum topological data analysis via the estimation of the density of states. Physical Review A, 110(4):042616, October 2024. ISSN 2469-9934. doi:10.1103/physreva.110.042616. URL http://dx. doi.org/10.1103/PhysRevA.110.042616. [8] Stefano Scali, Chukwudubem Umeano, and Oleksandr Kyriienko. The topology of data hides in quantum thermal states. APL Quantum, 1(3):036106, 2024. doi:10.1063/5.0209201. [9] Stefano Scali, Josh Kirsopp, Antonio Márquez Romero, and Michal Krompiec. Purified phase estimation samples spectra efficiently, 2025. URL https://arxiv.org/abs/ 2510.14744. [10] Frank Harary. On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(2):143–146, 1953. doi:10.1307/mmj/1028989917. [11] Kenneth E. Read. Cultures of the Central Highlands, New Guinea. Southwestern Journal of Anthropology, 10 (1):1–43, 1954. doi:10.1086/soutjanth.10.1.3629074. [12] Samuel F. Sampson. A novitiate in a period of change: An experimental and case study of social relationships. PhD thesis, Cornell University, 1968. [13] Shivam Sharma, Supreeth Mysore Venkatesh, and Pushkin Kachroo. Toward quantum utility in finance: A robust data-driven algorithm for asset clustering. In Frédéric Barbaresco and François Gerin, editors, Quantum Engineering Sciences and Technologies for Industry and Services, pages 14–22, Cham, 2026. Springer Nature Switzerland. ISBN 978-3-032-13855-2. [14] P.W. Anderson. Localisation theory and the Cu– Mn problem: Spin glasses. Materials Research Bulletin, 5(8):549–554, August 1970. ISSN 0025-5408. doi:10.1016/0025-5408(70)90096-6. URL http://dx. doi.org/10.1016/0025-5408(70)90096-6. [15] Francisco Barahona. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15(10):3241–3253, 1982. doi:10.1088/0305-4470/15/10/028. [16] Ada Altieri and Marco Baity-Jesi. An introduction to the theory of spin glasses. In Tapash Chakraborty, editor, Encyclopedia of Condensed Matter Physics, pages 361–370. Elsevier, 2 edition, 2024. ISBN 9780323914086. doi:10.1016/B978-0-323-90800-9.00249-3. [17] Samin Aref and Mark C Wilson. Balance and frustration in signed networks. Journal of Complex Networks, 7(2): 163–189, 2019. doi:10.1093/comnet/cny015. [18] Samin Aref, Andrew J. Mason, and Mark C. Wilson. A modeling and computational study of the frustration index in signed networks. Networks, 75(1):95–110, 2020.
doi:10.1002/net.21907. [19] Etsuo Segawa and Yusuke Yoshie. Quantum search of matching on signed graphs. Quantum Information Processing, 20(5):182, 2021. doi:10.1007/s11128-021-03089-x. [20] Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh. (quantum) complexity of testing signed graph clusterability. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024), volume 310 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.TQC.2024.8. [21] Massimiliano Incudini, Casper Gyurik, Riccardo Molteni, and Vedran Dunjko. Testing the presence of balanced and bipartite components in a sparse graph is QMA1 -hard, 2024. URL https://arxiv.org/abs/2412.14932. [22] Steven Kordonowy, Bibhas Adhikari, and Hannes Leipold. A perfectly distributable quantum-classical algorithm for estimating triangular balance in a signed edge stream, 2026. URL https://arxiv.org/abs/2603. 16029. [23] K. Shahul Hameed, K. Biju, and Zoran Stanić. Spectral measures of balance for signed graphs. Australasian Journal of Combinatorics, 93(1):198–210, 2025. URL https://ajc.maths.uq.edu.au/v93.p198. [24] Itay Hen and A. P. Young. Solving the graphisomorphism problem with a quantum annealer. Physical Review A, 86:042310, 2012. doi:10.1103/PhysRevA.86.042310. [25] Frank Gaitan and Lane Clark. Graph isomorphism and adiabatic quantum computing. Physical Review A, 89: 022342, 2014. doi:10.1103/PhysRevA.89.022342. [26] E. Knill and R. Laflamme. Power of one bit of quantum information. Physical Review Letters, 81(25):5672–5675, 1998. doi:10.1103/PhysRevLett.81.5672. [27] Peter W. Shor and Stephen P. Jordan. Estimating Jones polynomials is a complete problem for one clean qubit. Quantum Information and Computation, 8(8–9): 681–714, 2008. doi:10.26421/QIC8.8-9-1. [28] Miles Lubin, Oscar Dowson, Joaquim Dias Garcia, Joey Huchette, Benoı̂t Legat, and Juan Pablo Vielma. JuMP 1.0: recent improvements to a modeling language for mathematical optimization. Mathematical Programming Computation, 15:581–589, 2023. doi:10.1007/s12532-023-00239-3. [29] Qi Huangfu and J. A. J. Hall. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):119–142, 2018. doi:10.1007/s12532-017-0130-5. [30] Thomas Zaslavsky. Signed graphs. Discrete Applied Mathematics, 4(1):47–74, 1982. doi:10.1016/0166-218X(82)90033-6. [31] Fabian Pedregosa et al. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12: 2825–2830, 2011. [32] Jérôme Kunegis. KONECT: the Koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web (Companion), pages 1343– 1350, 2013. doi:10.1145/2487788.2488173. [33] Wouter Verstraelen, Stanislaw Świerczewski, Andrzej Opala, Andrew Haky, Matteo Gadani, Huawen Xu, Oleksandr Kyriienko, Michal Matuszewski, Alberto Bramati, and Timothy C. H. Liew. Spec-
12 troscopy on a single nonlinear mode recognizes quantum states. ACS Photonics, 13(9):2397–2407, 2026. doi:10.1021/acsphotonics.5c02750. [34] Chelsea A. Williams, Annie E. Paine, Antonio A. Gentile, Daniel Berger, and Oleksandr Kyriienko. Vortex detection from quantum data. Physical Review A, 112 (6):062409, 2025. doi:10.1103/mn3x-8ygh. [35] Yuan Wang and Oleksandr Kyriienko. Photonicsenhanced graph convolutional networks, 2025. URL https://arxiv.org/abs/2512.15549. [36] Yuan Wang, Stefano Scali, and Oleksandr Kyriienko. Polaritonic machine learning for graph-based data analysis. Physical Review E, 114(2):025305, 2026. doi:10.1103/fgy1-n4vp. [37] Loı̈c Henriet, Lucas Beguin, Adrien Signoles, Thierry Lahaye, Antoine Browaeys, Georges-Olivier Reymond, and Christophe Jurczak. Quantum computing with neutral atoms. Quantum, 4:327, 2020. doi:10.22331/q-2020-09-21-327. [38] A. Andrea Gentile, Shaheen Acheche, Atiyo Ghosh, Oleksandr Kyriienko, and Louis-Paul Henry. Hardwareinformed applications, application-informed hardware. IEEE Nanotechnology Magazine, 19(5):33–43, 2025.
doi:10.1109/MNANO.2025.3585999. [39] S. F. Edwards and P. W. Anderson. Theory of spin glasses. Journal of Physics F: Metal Physics, 5(5):965– 974, 1975. doi:10.1088/0305-4608/5/5/017. [40] Elisabeth Remy and Paul Ruet. From minimal signed circuits to the dynamics of Boolean regulatory networks. Bioinformatics, 24(16):i220–i226, 2008. doi:10.1093/bioinformatics/btn287. [41] Livia Perfetto, Leonardo Briganti, Alberto Calderone, Andrea Cerquone Perpetuini, Marta Iannuccelli, Francesca Langone, Luana Licata, Milica Marinkovic, Anna Mattioni, Theodora Pavlidou, Daniele Peluso, Lucia Lisa Petrilli, Stefano Pirrò, Daniela Posca, Elena Santonico, Alessandra Silvestri, Filomena Spada, Luisa Castagnoli, and Gianni Cesareni. SIGNOR: a database of causal relationships between biological entities. Nucleic Acids Research, 44(D1):D548–D554, 01 2016. ISSN 0305-1048. doi:10.1093/nar/gkv1048. [42] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56(1–3):89–113, 2004. doi:10.1023/B:MACH.0000033116.57574.95.