Quantum Kernels for Parity-Structured Classification: A Hybrid Pipeline
For quantum machine learning researchers, this work identifies parity complexity as a concrete axis where quantum kernels provide a genuine advantage over classical methods, though the advantage is limited to high-complexity regimes.
The paper studies quantum kernel advantage for parity (XOR) classification, finding that at high parity complexity (11 features), the quantum ZZ kernel achieves 66.3% accuracy, outperforming classical methods (near-random) and a binary encoding baseline (54.3%) by 12 percentage points, demonstrating genuine quantum advantage not due to encoding alone.
Parity (XOR) classification requires detecting discrete, high-order feature interactions that smooth classical kernels cannot efficiently capture. We study how quantum kernel advantage depends on parity complexity, the number of features entering the XOR rule, and find a clear threshold behavior. We pair a ZZ quantum feature map with binary {0, pi} encoding (features median thresholded before circuit input) to expose parity structure. A binary encoding ablation, RBF SVM trained on the identical {0, pi} features, separates encoding from circuit effects: at low complexity (n = 5 features), binary RBF achieves 83.4% +/- 1.7% and the quantum kernel 81.2% +/- 1.9%, showing encoding drives performance there. At high complexity (n = 11 features, 11 qubits, r = 3 ZZ repetitions), all classical methods collapse to near-random (approx. 50%), binary RBF reaches only 54.3% +/- 1.1%, and the quantum ZZ kernel achieves 66.3% +/- 3.2% (mean +/- std, 10 seeds), a +12.0 percentage-point margin over the binary ablation and approx. 7x higher kernel-target alignment (0.094 +/- 0.020 vs. 0.013 +/- 0.001). These results identify parity complexity as a concrete axis along which genuine quantum kernel advantage, not attributable to encoding alone, emerges.