Structural risk minimization for quantum linear classifiers

1 Introduction

• The paper identifies observable rank and Frobenius norm as controls on the trade-off between generalization performance and expressivity.The analysis covers quantum models including those introduced by Havlíček et al. [1] and Schuld & Killoran [2].Source: §1 · p. 2
• Limiting the dimension of the sum of observable images controls a VC-dimension bound, with rank limits providing a way to regularize it.The paper also gives analytical VC-dimension bounds in terms of the span of the observables and the dimension of their summed images.Source: §1 · p. 2
• Limiting observable Frobenius norm controls fat-shattering dimension, for which the paper provides explicit analytical bounds.Source: §1 · p. 2
• High-rank observables are strictly more expressive: they can classify every set classifiable with a low-rank observable, and some sets require at least a specified rank.Source: §1 · p. 2
• Larger Frobenius norms can achieve larger margins, and some example sets require at least a specified norm to reach a given margin.Because Frobenius norm controls fat-shattering dimension, this can also positively affect generalization performance.Source: §1 · pp. 2–3
• Observable rank and Frobenius norm also control the model’s ability to capture correlations in training examples.The paper discusses theoretically motivated regularization options that require no extra quantum hardware, including rank-penalizing training that need not produce a kernel method [17].Source: §1 · p. 3

2.1 Quantum linear classifiers

• Quantum linear classifiers embed inputs as density matrices and use observables as separating hyperplanes in a real vector space of n-qubit Hermitian operators.The classifiers are formed from functions of the feature-map states and observables.Source: §2.1 · p. 4
• The explicit approach implements observables with a parameterized circuit, computational-basis measurement, and postprocessing, while the implicit approach uses a kernel expansion over training examples.The implicit approach evaluates feature-state overlaps and obtains its coefficients on a classical computer.Source: §2.1 · pp. 4–6

2.2 Structural risk minimization: generalization bounds and model selection

• The VC dimension measures which labelings a classifier family can realize, while the fat-shattering dimension also accounts for achievable margins.The margin-aware measure can refine the expected-error bound; the two complexity measures need not provide the same guarantees or practical performance.Source: §2.2 · pp. 7–8
• Structural risk minimization selects among classifier families by minimizing an expected-error bound that combines training error with a complexity penalty.Increasing family complexity can lower training error while increasing the complexity term.Source: §2.2 · p. 8, Figure 3 · p. 8

3.1 Complexity of quantum linear classifiers: fat-shattering and VC dimension

• The VC dimension is bounded by the dimension of the observables’ span, itself bounded by the square of the dimension of the space on which they act nontrivially.For explicit classifiers, ansatzes whose relevant columns span a low-dimensional subspace can make the bound tunable through the final measurement rank; limiting that rank alone is not always sufficient.Source: §3.1 · pp. 9–10
• Limiting observable Frobenius norms controls fat-shattering dimension, while good generalization bounds require minimizing the norm without sacrificing training margin.The bounds depend on both Frobenius norm and functional margin, so maximizing geometric margin is one way to retain a large margin while reducing the norm.Source: §3.1 · pp. 10–11

3.2 Expressivity of quantum linear classifiers: model parameters & errors

• Any finite example set classifiable by a rank-k observable is classifiable by some rank-r observable with r > k, but some sets require observables of at least a certain rank.The proof uses a tomography-inspired protocol that tests observable rank using only the classifier’s sign labels.Source: §3.2 · p. 11
• For bounded feature maps, rank-limited classifier families are strictly nested, and normalized classical linear classifiers can be embedded in a rank-at-most-one quantum classifier family.The passage also states that quantum classifiers with a feature map can be represented by classical linear classifiers with a corresponding feature map.Source: §3.2 · p. 12
• Some example sets require an observable with Frobenius norm at least η to achieve margin η/√m, showing that norm controls achievable margins.Increasing the norm can increase margin by scaling an observable, but does not replace increasing rank when rank is needed to classify a set correctly.Source: §3.2 · p. 12

3.3 Structural risk minimization for quantum linear classifiers in practice

• In a controlled-register ansatz, choosing final measurement rank ℓ = m2^t (m < 2^c) bounds VC dimension by ℓ^2 + 1, enabling rank regularization.The section presents regularization as jointly minimizing training error and a complexity penalty, with these approaches described as NISQ-suitable.Source: §3.3 · p. 13
• For Pauli-string ansätze, the VC dimension is at most r^2 + 1 with r = ℓ·2^d, so measurement rank ℓ and circuit depth d can tune the bound.Choosing d appropriately can keep the bound from growing exponentially in the number of qubits n.Source: §3.3 · p. 14
• For permutation-symmetry-preserving ansätze, the span dimension is bounded by r = ℓ·∏_j(m_j + 1), yielding VC dimension at most r^2 + 1 and making ℓ tunable.The product gives the dimension of the space invariant under permutations within each partition.Source: §3.3 · pp. 14–15
• Across these constructions, varying final measurement rank ℓ controls the VC-dimension upper bound, but regularized explicit classifiers need not correspond to kernel methods or outperform implicit ones.The usual relationship between explicit and implicit models [17] does not necessarily hold in these cases.Source: §3.3 · p. 15
• Regularizing observable Frobenius norms controls fat-shattering dimension, but generalization also depends on functional margin, so the norm should be minimized while keeping training margins large.For explicit classifiers the norm can be estimated by sampling computational basis states; for implicit classifiers, regularizing ||α||1 regularizes ||Oα||F, while usual quadratic-program weights already optimally regularize it [17].Source: §3.3 · p. 15
• Circuit-angle, depth, width, gate-count, and noise-based regularization are additional options, but their structural-risk effects or relationships between explicit and implicit classifiers remain unresolved.Theoretical analysis of angle regularization is identified as future work.Source: §3.3 · p. 15

• Embedding the observable span in Hermitian-operator space yields a VC-dimension bound using the linear-classifier dimension ℓ + 1 and the ambient Hermitian-space dimension dim(H)^2.The proof establishes the ambient dimension and identifies the relevant span as a subspace.Source: §A.1 · p. 18
• The proof lower-bounds dim(V) by showing that dim(H) projectors onto selected states in V are linearly independent.It argues by contradiction that a dependence among these projectors would contradict the selected states' properties.Source: §A.1 · p. 18
• For some ansatzes, the dimension inequalities are strict: dim(H) < dim(V) < dim(H)^2.The text points to the first example in Section 3.3.Source: §A.1 · p. 18

• I_i measures how much the image of observable O_i overlaps the sum of the later observable images: it is 0 for full overlap and R for no overlap.The discussion uses observables of fixed rank R.Source: §A.2 · p. 19
• Even for an infinite family of n-qubit observables, finitely many images suffice because they lie in a finite-dimensional space.The passage states that a subset of at most 2^n observables suffices.Source: §A.2 · p. 19
• The lemma relates r, defined in Proposition 3, to observable rank R and the image-overlap quantities I_i.Its proof repeatedly applies the dimension formula for the sum of two subspaces.Source: §A.2 · p. 19

• The proof uses a previously established fat-shattering bound for real-valued linear functions as its classical starting point.The proposition concerns functions on a ball of radius R in R^N.Source: §A.3 · p. 20
• The quantum bound follows by viewing n-qubit density matrices as radius-1 points in Hermitian space and observables as hyperplanes with Frobenius norms at most η.The proof adapts the classical result because the norm restriction applies to the observables defining the hyperplanes.Source: §A.3 · p. 20
• k ≤ min{9η^2/γ^2, N + 1} + 1 bounds the size of a γ-shattered set after scaling unit-radius points by η.Here the proof scales the points to radius η before applying the linear-function bound.Source: §A.3 · p. 20

• The paper derives a PAC sample-complexity corollary by applying established classifier sample-complexity results to its fat-shattering bound.The text describes this corollary as a dual of the result in [36].Source: §A.3.1 · p. 21
• The stated setting draws examples independently from a distribution and selects a function whose sample predictions differ from the target by at most ν, with γε ≥ 7ν.The corollary states a probability guarantee over the distribution, but the supplied passage does not include its bound.Source: §A.3.1 · p. 21

B.1 Proof of Proposition 6

• For every finite example set classified by a quantum linear classifier of rank k, a classifier of rank r>k can also classify it correctly.The proof perturbs the observable while preserving the classifications, yielding an observable of exactly rank r.Source: §B.1 · pp. 21–22
• A finite query protocol distinguishes rank-r target classifiers from classifiers of rank below r: any lower-rank classifier must disagree on at least one queried state.The protocol checks observable entries through classifier labels, then uses Gershgorin discs to establish at least r distinct eigenvalues when all queried labels agree.Source: §B.1 · pp. 21, 25
• Conversely, some finite example set classified by a rank-r classifier cannot be classified correctly by a classifier of rank k<r.If a lower-rank classifier agreed with the rank-r target on the protocol's finite queries, its spectrum would have to include at least r distinct eigenvalues, contradicting its rank.Source: §B.1 · pp. 21, 22, 25

B.2 Proof of Proposition 7

• A bounded classical feature map into R^N can be extended to a unit-norm map into R^(N+1) while preserving its linear classifier family.The proof embeds the bias as an added coordinate and rescales it using the feature-map norm bound.Source: §B.2 · p. 25
• For a unit-norm classical feature map into R^N, a quantum feature map on n=⌈log N+1⌉+1 qubits represents its linear classifiers using rank-one observables.The proof embeds vectors into a larger space and constructs a rank-one observable for the corresponding classifier.Source: §B.2 · pp. 25–26
• There exists a classical feature map Φ′: Rℓ→R4n such that the quantum and classical linear-classifier families are equal: Cqlin(Φ) = Clin(Φ′).Source: §B.2 · p. 25

B.3 Proof of Proposition 8

• A quantum linear classifier with Frobenius norm η′<η can classify all constructed examples with margin at least η/√m.The construction applies for every η>0 and 0<m≤2^n, using m binary-labeled n-qubit pure states.Source: §B.3 · p. 26
• The constructed example set D_m can be classified by an observable with margin η/√m.The proof notes explicitly that the classifier c_O,0 classifies D_r with this margin.Source: §B.3 · p. 26