1 Introduction↩︎

Combinatorial optimization problems are ubiquitous in physics, logistics, and computational biology [1]–[3]. Max-Cut, where the goal is to partition graph vertices to maximize the weight of crossing edges, is a canonical NP-Hard optimization problem [4]. Classical approaches achieve a \(0.878\) approximation via semidefinite programming [5], but quantum algorithms offer a potential pathway to better solutions on large instances.

The Quantum Approximate Optimization Algorithm (qaoa) [6] is among the most promising variational quantum algorithms for Max-Cut on near-term quantum hardware [7]. The algorithm prepares a parameterized quantum state by alternating cost and mixer unitary operations for \(p\) layers (Fig 1). Increasing depth \(p\) improves solution quality in principle, but requires optimizing \(2p\) classical parameters and causes the energy landscape to become increasingly complex [3], [8]. This creates a practical bottleneck: as \(p\) grows, the number of quantum circuit evaluations needed for reliable optimization grows rapidly.

Recent work has shown that optimal qaoa parameters exhibit concentration— they cluster near instance-independent values across different graph instances of the same type [9]–[12]. This suggests that the set of optimal parameters lies on a low-dimensional manifold in the \(2p\)- dimensional parameter space. [13] exploited this by applying linear Principal Component Analysis (PCA) to project parameters onto their top-2 principal components, achieving near-optimal performance at shallow depths \(p \leq 2\). However, PCA assumes a linear manifold structure, which becomes increasingly violated as depth increases [14], [15].

We propose Kernel PCA (KPCA) with a Radial Basis Function (RBF) kernel as a nonlinear alternative to PCA. Kernel methods implicitly map data into a higher-dimensional feature space where curved manifolds become approximately linear, enabling effective dimensionality reduction even when the underlying structure is nonlinear [16]. Our contributions are:

1. A theoretical explanation for why the qaoa parameter manifold becomes nonlinear with depth, rooted in the Fourier complexity of the energy landscape and the multi-modal nature of deeper circuits.

2. An empirical evaluation of KPCA-based subspace optimization across three graph families (ER, BA, WS) at \(n = 12\) substantially beyond prior work limited to \(n \leq 8\).

3. Demonstration that KPCA achieves approximation ratios above \(0.86\) at \(p = 8\) while PCA degrades to \(0.81\), with both methods reducing quantum evaluations by over \(93\%\).

2 Background↩︎

2.1 QAOA and Parameter Concentration↩︎

For a graph \(G=(V,E)\) with edge weights \(w_{ij}\), the Max-Cut value is \[C(\mathbf{z}) = \sum_{(i,j)\in E} w_{ij}\,\frac{1 - z_i z_j}{2}, \quad z_i \in \{+1,-1\}, \label{eq:maxcut}\tag{1}\] qaoa encodes this as a cost Hamiltonian \(H_C = \sum_{(i,j)\in E} w_{ij}(I - Z_iZ_j)/2\) and prepares the state \[|\psi(\boldsymbol{\gamma},\boldsymbol{\beta})\rangle = \prod_{k=1}^{p} e^{-i\beta_k H_B}\,e^{-i\gamma_k H_C}\,|{+}\rangle^{\otimes n}, \label{eq:qaoa95state}\tag{2}\] where \(H_B = \sum_i X_i\) is the mixer and \(|{+}\rangle^{\otimes n}\) is the uniform superposition. The \(2p\) parameters \((\boldsymbol{\gamma},\boldsymbol{\beta})\in\mathbb{R}^{2p}\) are optimized to minimize \(\langle\psi|H_C|\psi\rangle\). Performance is the approximation ratio \[r = \frac{\langle\psi|H_C|\psi\rangle}{C_{\max}}. \label{eq:approx95ratio}\tag{3}\]

A key observation is that optimal parameters concentrate across graph instances of the same class, clustering on a low-dimensional manifold [9]–[12]. For large, locally tree-like graphs, this occurs because the qaoa cost function at depth \(p\) depends primarily on \(p\)-hop neighborhoods, which have the same distribution across instances [12], [17].

2.2 PCA↩︎

At \(p = 1\), the qaoa expectation value \(\langle H_C \rangle(\boldsymbol{\gamma}, \boldsymbol{\beta})\) is a low-frequency trigonometric polynomial, and optimal parameters lie near a smooth, nearly one-dimensional curve in parameter space. Linear PCA effectively captures this structure by projecting onto the dominant linear direction (Fig 2).

As \(p\) increases, the Fourier content of \(\langle H_C \rangle\) grows with depth. At depth \(p\), the energy function contains trigonometric terms up to frequency \(p\) in each parameter direction [8], [15]. Coupling between layer parameters means the number of distinct frequency components grows combinatorially with \(p\), not just linearly. Consequently, the manifold of near-optimal parameters develops increasing curvature in the \(2p\)-dimensional space. This curvature is intrinsic and cannot be removed by reparameterization. As a result, no 2-dimensional linear subspace can adequately approximate the optimal parameter manifold at large \(p\), and PCA incurs systematic error that grows with depth.

Discrete symmetries compound this problem. [14] showed that qaoa solutions exhibit permutation symmetry (swapping layers), reflection symmetry \((\boldsymbol{\gamma}, \boldsymbol{\beta}) \to (-\boldsymbol{\gamma}, -\boldsymbol{\beta})\), and shift symmetries, creating multiple disconnected clusters of optima in parameter space. The union of symmetry-related optima further deforms the manifold away from any linear subspace. Together, the increasing Fourier complexity and discrete symmetry structure mean that PCA’s assumption of a linear manifold becomes increasingly violated with depth, motivating a nonlinear alternative.

Figure 2 shows 2D projections of 200 training optimal parameter vectors under PCA and KPCA at each depth. At \(p = 1\) both representations are similar. At higher depths, the PCA projections become more dispersed, while the KPCA projections retain more organization, consistent with the increasing nonlinearity of the parameter manifold.

2.3 Kernel PCA↩︎

Kernel PCA (KPCA) [16] generalizes standard PCA by performing it in a feature space induced by a kernel function. For a dataset \(\{\boldsymbol{\theta}_i\}\) and a kernel \(k(\boldsymbol{\theta}_i, \boldsymbol{\theta}_j)\), KPCA computes the eigendecomposition of the centred kernel matrix and identifies nonlinear principal components.

The RBF kernel \[k_{\rm RBF}(\boldsymbol{\theta}_i,\boldsymbol{\theta}_j) = \exp\!\left(-\frac{\left\|\boldsymbol{\theta}_i -\boldsymbol{\theta}_j\right\|^2}{2\sigma^2}\right) \label{eq:rbf}\tag{4}\] has several advantages for the qaoa parameter space. First, it is universal, meaning it can approximate any smooth function arbitrarily well [19]. Second, it assigns high similarity to nearby parameters (within a cluster) and low similarity to distant ones (across clusters), naturally encoding the symmetric structure without explicit specification. Third, in the limit of large bandwidth \(\sigma\), it reduces to standard PCA, making it a proper generalization.

The RBF kernel implicitly maps parameters into an infinite-dimensional space via the Mercer expansion [20]. In this high-dimensional feature space, the curved parameter manifold becomes approximately flat, allowing PCA to find the relevant directions. The bandwidth parameter \(\sigma\) controls the scale: we use the median heuristic, \(\sigma = \mathrm{median}_{i \neq j}\left\|\boldsymbol{\theta}_i - \boldsymbol{\theta}_j\right\|\), a standard data-driven approach [21].

A subtlety arises because KPCA finds coordinates in the feature space, but qaoa requires concrete parameters in the original \(2p\)-dimensional space. We use the approximate pre-image procedure of [22]: given a 2D feature coordinate, find the original-space parameter that best approximates it via gradient descent. This is solved as an unconstrained optimization in \(\mathbb{R}^{2p}\). Concretely, given a target feature-space point \(\boldsymbol{\phi}^*\), we minimize the squared distance in feature space \[\hat{\boldsymbol{\theta}} = \mathop{\mathrm{arg\,min}}_{\boldsymbol{\theta} \in \mathbb{R}^{2p}} \left\| \boldsymbol{\phi}(\boldsymbol{\theta}) - \boldsymbol{\phi}^* \right\|^2, \label{eq:preimage}\tag{5}\] where \(\boldsymbol{\phi}(\boldsymbol{\theta})\) denotes the implicit feature-space embedding induced by the RBF kernel. Since \(\boldsymbol{\phi}(\boldsymbol{\theta})\) is never computed explicitly, the objective is expressed in terms of kernel evaluations via \[\left\| \boldsymbol{\phi}(\boldsymbol{\theta}) - \boldsymbol{\phi}^* \right\|^2 = k(\boldsymbol{\theta}, \boldsymbol{\theta}) - 2\sum_{i} \alpha_i\, k(\boldsymbol{\theta}, \boldsymbol{\theta}_i) + \text{const}, \label{eq:preimage95kernel}\tag{6}\] where \(\{\alpha_i\}\) are the KPCA expansion coefficients and \(\{\boldsymbol{\theta}_i\}\) are the training parameters. The gradient of this objective with respect to \(\boldsymbol{\theta}\) is available in closed form through the RBF kernel’s differentiability, making gradient descent efficient. We initialize from the training parameter closest to the current 2D coordinate and run until convergence, which typically requires fewer than 50 gradient steps in practice.

3 Methods↩︎

3.1 Experimental Setup↩︎

We used three graph families to test whether results generalize:

• Erdős-Rényi (ER) [23]: \(G(n, 0.5)\) with uniform random edges.

• Barabási-Albert (BA) [24]: Preferential attachment with \(m=2\), producing power-law degree distributions.

• Watts-Strogatz (WS) [25]: Small-world networks with clustering and short path lengths.

Training graphs: 200 per family, \(n \in \{7, 8, 9, 10\}\) nodes.
Test graphs: 30 per family, \(n = 12\) nodes, reserved exclusively for evaluation. Exact Max-Cut values were computed by brute-force enumeration. Test graphs at 12 nodes provide a substantially harder optimization landscape (\(2^{11} = 2048\) possible cuts vs.\(2^7 = 128\) for 8-node graphs).

3.2 QAOA Training↩︎

For each training graph at depths \(p \in \{1, 2, 4, 8\}\), we built the qaoa circuit in Qiskit [26], executed on the Qiskit Aer simulator with up to 2048 shots, and optimized using cobyla with a 1000 evaluation cap. We ran five random initializations from the uniform distribution \([0,\pi]^{2p}\) and retained the best. The optimal parameters \(\boldsymbol{\theta}^*\) were stored for each instance.

3.3 Dimensionality Reduction Models↩︎

For each graph family and depth, we aggregated 200 optimal parameter vectors and mean-centred them. We then fitted two models:

PCA. Standard PCA, retaining the top-2 principal components.

KPCA. Kernel PCA with RBF kernel, retaining the top-2 components. We centred the kernel matrix, computed its eigendecomposition, and extracted the top 2 eigenvectors. The bandwidth was set via the median heuristic.

3.4 Test Evaluation↩︎

For each test graph, we optimized using cobyla (1000 evaluation cap) under three conditions:

1. Full qaoa: Optimize all \(2p\) parameters.

2. PCA-subspace: Optimize a 2D coordinate with parameters recovered by linear projection onto the top-2 PCA components.

3. KPCA-subspace: Optimize a 2D coordinate with parameters recovered via the KPCA pre-image.

We recorded the approximation ratio and number of quantum estimator calls. Statistical significance was assessed with paired \(t\)-tests.

4 Results↩︎

3.5pt

At \(p \leq 2\) all three methods perform similarly. PCA and KPCA show no significant difference (\(p > 0.05\)), consistent with an approximately linear structure at shallow circuits.

4.0.0.1 Approximation Ratio.

At \(p \geq 4\) divergence emerges. At \(p=4\), KPCA achieves \(r = 0.903\) (ER), \(0.886\) (BA), and \(0.878\) (WS), while PCA degrades to \(0.861\) (ER), \(0.831\) (BA), and \(0.819\) (WS). The BA degradation is most severe, reflecting the power-law degree distribution’s effect on manifold curvature. At p=8, PCA declines to r = 0.831 (ER), 0.814 (BA), and 0.807 (WS), while KPCA maintains \(r > 0.86\) across all families. All differences at \(p \geq 4\) are significant (\(p < 0.001\)).

4.0.0.2 Efficiency.

Both methods dramatically reduce quantum evaluations. At \(p=4\), KPCA and PCA use approximately 76 and 48 calls versus 734 for Full qaoa (a \(89.6\%\) and \(93.5\%\) reduction). At \(p=8\), Full qaoa hits the 1000-evaluation limit while both reduced methods converge in \(\approx 55\)–\(65\) calls (\(> 93\%\) reduction). PCA achieves comparable evaluation counts to KPCA but with worse accuracy at depth.

5 Discussion↩︎

5.1 KPCA at Depth↩︎

At \(p \leq 2\), the optimal parameter manifold is approximately flat, so PCA and KPCA perform similarly. At \(p \geq 4\), the growing Fourier complexity of the energy landscape is the primary source of manifold curvature. As noted in Section 2.2, the number of distinct frequency components grows combinatorially with \(p\) due to coupling between layer parameters, producing a manifold that no 2-dimensional linear subspace can adequately represent. Discrete symmetries are an additional contributing factor: the permutation, reflection, and shift symmetries identified by [14] create multiple disconnected clusters of optima, which further deform the manifold away from any linear subspace. Linear PCA must project onto a 2D subspace that passes through the centroid of these clusters but aligns with none of them, resulting in systematic error at depth.

The RBF kernel assigns high similarity within clusters and lower similarity across clusters. In the implicit feature space, the top-2 KPCA components can align more closely with the local structure of the manifold than a global linear projection can. We do not claim that 2D KPCA fully captures the parameter manifold; rather, at fixed reduced dimension of 2, KPCA captures more of the manifold structure than 2D PCA. The pre-image procedure then maps 2D feature coordinates back to original-space parameters near the appropriate cluster.

The performance gap is most pronounced on BA graphs, where the power-law degree distribution creates larger eigenvalue variance in the cost Hamiltonian, which is associated with greater manifold curvature relative to ER or WS graphs.

At \(p=8\), PCA degrades to \(r = 0.831\) (ER), \(0.814\) (BA), and \(0.807\) (WS), while KPCA maintains \(r > 0.86\) across all families. This pattern is consistent with the increasing nonlinearity of the parameter manifold at greater depth.

5.2 Practical Implications↩︎

The \(93\%\)–\(95\%\) reduction in quantum evaluations is practically significant. On near-term quantum hardware, circuit evaluations contribute to cost due to decoherence, gate errors, and queue latency. Both PCA and KPCA achieve comparable evaluation savings, but only KPCA maintains high approximation ratios at depth.

Our experiments train on 8-node graphs and test on 12-node graphs, demonstrating that learned dimensionality reduction transfers across system sizes. This is consistent with theory predicting size-independent limiting parameters for locally tree-like graphs [12], [17]. Successful cross-size transfer enables using classically-simulable small graphs to guide optimization on larger instances.

Limitations include: (i) noiseless simulation (hardware noise will alter the effective landscape); (ii) fixed 2D reduction (larger \(k\) would reduce gap with Full qaoa); (iii) modest graph sizes (\(n = 12\) test graphs). Future directions include larger graphs via tensor network simulation, adaptive bandwidth selection, hardware experiments, and hybrid approaches combining KPCA with warm-starting techniques [3].

6 Conclusion↩︎

We proposed Kernel PCA with RBF kernels for nonlinear dimensionality reduction in the qaoa parameter space. The approach is motivated by the observation that the Fourier complexity of the energy landscape grows combinatorially with depth, causing the optimal parameter manifold to develop curvature that a linear subspace cannot adequately represent. Discrete symmetries further deform the manifold by creating multiple disconnected clusters of optima. Evaluated across ER, BA, and WS graph families at depths \(p \in \{1, 2, 4, 8\}\), KPCA significantly outperforms PCA at \(p \geq 4\) (all \(p < 0.001\)) while achieving comparable performance at shallow depths. Both methods reduce quantum evaluations by over \(93\%\), but KPCA performs significantly better at depth. These results indicate that kernel methods are a practical approach for scaling qaoa to deeper circuits on near-term quantum hardware.

References↩︎