PaperlayerView exact revision on arXiv

Source-linked AI summary

Covariant quantum kernels for data with group structure

Jennifer R. Glick, Tanvi P. Gujarati, Antonio D. Corcoles, Youngseok Kim, Abhinav Kandala, Jay M. Gambetta, Kristan Temme

arXiv:2105.03406v2quant-ph

TL;DR

Quantum kernels may be hard to evaluate classically, but finding ones that help on group-structured learning tasks remains a challenge. This paper defines covariant kernels from group representations and optimizable fiducial states, then reports 100% test accuracy on a 27-qubit noisy-hardware instance.

  • Problem

    Finding quantum kernels that offer a classification advantage for practically relevant data remains a challenge, including data with group structure.

    Source: §1 · p. 6, Appendix B · p. 6

  • Method

    The paper defines covariant quantum kernels from a group representation and fiducial state, and optimizes the state using kernel alignment for a coset-space learning problem.

    Source: Appendix B · p. 6, Appendix C · p. 9, §1 · p. 10

  • Results

    100% test accuracy was reached on a 27-qubit problem instance on noisy hardware.

    Source: §2 · p. 11

  • Takeaways & Limitations

    The coset-space benchmark is a geometric learning problem in a Euclidean feature space whose mapping is motivated by group structure.

    Source: Appendix C · pp. 9–10

    The authors expect barren plateaus as system size increases if the fiducial state is not chosen carefully.

    Source: §3 · p. 12

Abstract

from arXiv · show

The use of kernel functions is a common technique to extract important features from data sets. A quantum computer can be used to estimate kernel entries as transition amplitudes of unitary circuits. Quantum kernels exist that, subject to computational hardness assumptions, cannot be computed classically. It is an important challenge to find quantum kernels that provide an advantage in the classification of real-world data. We introduce a class of quantum kernels that can be used for data with a group structure. The kernel is defined in terms of a unitary representation of the group and a fiducial state that can be optimized using a technique called kernel alignment. We apply this method to a learning problem on a coset-space that embodies the structure of many essential learning problems on groups. We implement the learning algorithm with $27$ qubits on a superconducting processor.

Appendix A: Support vector machines

Support vector machines classify data by fitting a linear threshold in a feature space, using a kernel to avoid explicit computation in potentially high-dimensional spaces.

Appendix A: Support vector machines

  • SVMs map nonlinearly separable data into a higher-dimensional Euclidean feature space, where a linear threshold separates the classes.The classifier is trained by optimizing a soft-margin bound on generalization error; C controls the cost of nonseparable points.Source: Appendix A · p. 5
  • The kernel is the inner product between mapped data points, enabling the SVM dual to use kernel values rather than explicit feature coordinates.The dual is a quadratic program in one Lagrange multiplier per training constraint.Source: Appendix A · p. 5
  • The kernel method lets SVM training and classification operate in arbitrary or infinite-dimensional feature spaces when kernel values can be evaluated efficiently.The kernel replaces explicit feature vectors with their pairwise inner products in the dual optimization and decision function.Source: Appendix A · pp. 5–6

1. Quantum kernels and quantum feature maps

Quantum kernels encode data in quantum feature states and use their inner products to represent similarity. A quantum computer can estimate these kernel entries through circuit transition probabilities.

1. Quantum kernels and quantum feature maps

  • Quantum kernel methods are motivated by feature maps whose kernel values are classically hard to evaluate but can be approximated on a quantum computer.If the fidelity is classically efficiently estimable, conventional SVM methods can use it without a quantum speedup.Source: §1 · p. 6
  • The quantum feature space treats each mapped datum as a density matrix, and its kernel is the trace inner product between feature states.In a suitable Hermitian-matrix basis, the feature space has dimension 4^n − 1; kernel estimation can use the all-zero outcome after applying U†(x)U(z).Source: §1 · p. 6
  • Using pure-state inner products instead of density-matrix feature states makes the kernel and classifier sensitive to global phase.The density-matrix formulation ensures a Euclidean feature space and determines how the feature space is accessed.Source: §1 · p. 6

Appendix B: Covariant quantum kernels

Covariant quantum kernels combine a group representation with a fiducial state to map group-structured data into quantum feature states. A discrete-logarithm example illustrates a conditional separation between quantum and classical learning.

Appendix B: Covariant quantum kernels

  • The covariant kernel framework targets learning tasks whose data are subsets of a group, using a group representation and a fiducial state as its defining components.The representation circuit must be efficient, and the fiducial state is assumed efficiently preparable.Source: Appendix B · p. 6
  • The fiducial state affects classification quality, and left- and right-invariant feature maps provide two kernel constructions.The corresponding kernels are determined by a single function of z⁻¹x for the right-invariant case or xz⁻¹ for the left-invariant case.Source: Appendix B · p. 7
  • The left-invariant kernel can be represented through non-Abelian Fourier coefficients determined by the fiducial state and group representation.The coefficients arise from rank-one projectors induced by the fiducial state restricted to irreducible-representation subspaces.Source: Appendix B · pp. 7–8

1. Example with formal separation

  • The formal-separation example uses Z*_p under multiplication modulo p, where computing the discrete logarithm is assumed classically super-polynomial in n = ⌈log2(p)⌉.The generator g represents group elements as powers, and the labeling rule assigns labels according to the discrete logarithm.Source: §1 · p. 8
  • Under the discrete-logarithm hardness assumption, no classical classifier predicts the decision rule’s labels with probability greater than 1/2 + poly(n)^−1; the appropriate quantum kernel attains near-perfect accuracy with polynomial effort.Source: §1 · p. 8
  • The prior discrete-logarithm kernel is a covariant-kernel instance using the regular representation and a fiducial state uniform over generator powers.Its feature states are obtained by applying the representation to that fiducial state.Source: §1 · pp. 8–9

a. The importance of the fiducial state choice

The fiducial state can radically change the kernel and its classification behavior. A computational-basis choice produces an identity kernel, while the example motivates choosing the state to suit the learning problem.

a. The importance of the fiducial state choice

  • Choosing |ψ⟩ = |0n⟩ makes the kernel the identity matrix, a trivial kernel associated with a very poor classifier.The representation maps the reference state to |x⟩, so distinct data points have zero kernel similarity.Source: a. The importance of the fiducial… · p. 9
  • The example shows that a useful fiducial state depends on the learning problem and its ground-truth distribution.Different fiducial states can produce substantially different kernels and classification behavior.Source: a. The importance of the fiducial… · p. 9

Appendix C: The learning problem

The section defines a binary classification problem on two cosets, with labeled data perturbed away from their cosets. It frames the perturbed task as geometric learning in quantum feature space.

Appendix C: The learning problem

  • The benchmark is “labeling cosets with error,” a homogeneous-space classification problem chosen so that arbitrarily small classification error is possible.Source: Appendix C · p. 9
  • Two left cosets receive opposite labels, and their data distributions place most of their mass within an ε-window measured by a representation-dependent distance.Source: Appendix C · p. 9
  • Each sample is generated by selecting a label and a coset element uniformly, then applying a random group perturbation within distance ε of the identity.Source: Appendix C · pp. 9–10
  • At ε = 0, classification reduces to coset membership; perturbations move labeled elements outside the cosets and make the task geometric in a Euclidean feature space.Source: Appendix C · p. 10
  • A subgroup-invariant fiducial state gives each coset a unique representing state, so the classifier distinguishes two states whose perturbations are expected to remain classifiable when small.Source: Appendix C · p. 10
  • The experiment uses n-qubit single-qubit rotations, G = SU(2)^⊗n, and the heavy-hex graph-stabilizer subgroup, whose invariant state follows the chip topology.Source: Appendix C · p. 10

Appendix D: Quantum kernel alignment algorithm

The algorithm searches over parameterized fiducial states while optimizing the SVM dual variables. This min-max procedure selects a kernel by minimizing an upper bound on classification error.

Appendix D: Quantum kernel alignment algorithm

  • The kernel family is built from fiducial states |ψλ⟩ = Vλ|0ⁿ⟩, with alignment optimizing circuit parameters λ together with SVM multipliers α.Source: §1 · p. 10
  • The min-max problem selects among available kernels to minimize the SVM bound on classification error.Source: §1 · p. 10
  • The bound is data-dependent and tied to fat-shattering dimension; optimizing the objective searches for a fiducial state yielding the smallest such generalization bound.Source: §1 · p. 11

2. Stochastic algorithm

The stochastic algorithm alternates quantum kernel evaluation with classical optimization of kernel and SVM parameters. On noisy hardware, the reported 27-qubit instance reached 100% test accuracy.

2. Stochastic algorithm

  • Each iteration evaluates kernel matrices on a quantum processor and updates kernel parameters and SVM multipliers with a classical optimizer; the resulting kernel is used in a standard SVM for test predictions.Source: §2 · p. 11
  • SPSA estimates the kernel-parameter gradient using two objective evaluations independent of parameter dimension, while CVXOPT solves the concave multiplier optimization.Source: §2 · p. 11
  • The algorithm calibrates hardware, evaluates perturbed kernel matrices with R shots, updates λ by SPSA, and returns the final aligned kernel parameters.Source: §2 · p. 11
  • 100% test accuracy was reached on a 27-qubit problem instance on noisy hardware as the parameter converged toward its expected value.Source: §2 · p. 11
  • The authors use SPSA as a demonstration, noting that structural insight can guide fiducial-state choices and that other optimizers could be used.Source: §2 · p. 11

3. Additional considerations

The appendix contrasts weighted and unweighted alignment and notes that centering changes alignment values. It identifies open comparisons and a possible scaling concern for variational optimization.

3. Additional considerations

  • Unweighted alignment maximizes within-class kernel overlap and minimizes between-class overlap, whereas weighted alignment targets the SVM gap margin using support vectors.Source: §3 · p. 12
  • Prior studies suggest normalized, centered kernels provide a more useful metric than uncentered alignment, and centered alignment can yield different values.Source: §3 · p. 12
  • Further study is needed to compare weighted and unweighted alignment with and without centered kernels.Source: §3 · p. 12
  • As system size increases, barren plateaus may arise if the fiducial state is not chosen carefully; structurally motivated states and initial parameters may potentially help prevent them.Source: §3 · p. 12

1. Device characterization

The experiment used a 27-qubit superconducting processor, with gate and readout errors characterized across a consistent calibration. The coset-labeling circuits were implemented at two gate-stretch settings.

1. Device characterization

  • The processor used 27 fixed-frequency transmons, with median readout error 9.6e-3 and median CNOT error 7.33e-3 at stretch c = 1.The experiments spanned four consecutive days using one calibration for all gates and readouts.Source: §1 · pp. 12–13
  • The physical circuit represents the coset-labeling family for parameters λ, θ, and ˜θ, with data supplied through U3 and U2 rotations.Circuit duration was 4.6615 µs at c = 1 and 5.9580 µs at c = 1.3; the measurement pulse was not stretched.Source: Figure 4 · p. 13, §1 · p. 13
  • Single-qubit gate error was 2.97e-4, while median CNOT error increased from 7.33e-3 at c = 1 to 9.27e-3 at c = 1.3.The median CNOT durations were 476.4 ns and 618.6 ns, respectively.Source: §1 · p. 13

2. Training data

The training-set kernel alignment process was tracked through output distributions and feature-space geometry. As optimization progressed, label centers separated and within-label variance fell, with error mitigation showing an advantage on both metrics.

2. Training data

  • The training kernels capture pairwise data-point overlaps, and their experimental matrices were examined at odd SPSA steps from 1 through 15.The alignment process used the training dataset to update the kernel parameter λ.Source: §2 · pp. 13–14
  • For training pair, the probability of zero Hamming weight grew during optimization and peaked at step 11; pair [0, 14] moved closer to its noiseless distribution at later steps.The distributions compare experimental output, two gate stretches, zero-noise extrapolation, and noiseless simulation.Source: §2 · p. 14, Figure 5 · p. 14
  • The feature-space metrics track both separation between label centers and the spread of each label’s data points as λ is optimized.The center-of-mass distance and within-label variance provide complementary geometric views of the mapped training set.Source: §2 · p. 14
  • As SPSA progressed, the Hilbert–Schmidt distance between label centers increased while within-label variance decreased; mitigation showed an advantage on both metrics.The ideal metric values were limited by the dataset noise level, ϵ = 0.01.Source: §2 · p. 14, Figure 6 · p. 15

3. Testing data

Test-set kernel matrices showed clearer label contrast with error mitigation, and mitigated runs developed larger decision values during optimization. The individual test-point examples also show that some classifications remain difficult even without experimental noise.

3. Testing data

  • Mitigated test-set Gram matrices show clearer contrast between labels than unmitigated matrices across the displayed SPSA steps.Training points form the columns and test points form the rows.Source: §3 · p. 15, Figure 7 · p. 16
  • Mitigated test data show consistently larger decision values at later SPSA steps, although some points remain close to the decision boundary.Test point 42 stays close to the boundary; its overlap with opposite-label support vectors makes it challenging even in noiseless simulation.Source: §3 · p. 15, Figure 8 · p. 16
  • At SPSA step 11, test point 42 overlaps fairly uniformly with training points, while point 5 overlaps more with negative-label training points and is easier to classify.The noiseless ideal-λ simulation likewise identifies point 42 as challenging and point 5 as easier.Source: §3 · p. 15

Related papers

Loading 2105.03406v2…