PaperlayerView exact revision on arXiv

Source-linked AI summary

Supervised learning with quantum enhanced feature spaces

Vojtech Havlicek, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, Jay M. Gambetta

arXiv:1804.11326v2quant-phstat.ML

TL;DR

Because Hilbert-space dimension alone does not establish quantum advantage, this paper investigates quantum feature maps for classification. It experimentally implements variational and kernel-based quantum classifiers on a superconducting processor. The demonstrated classifier achieved success rates up to 100% despite noise.

Abstract

from arXiv · show

Machine learning and quantum computing are two technologies each with the potential for altering how computation is performed to address previously untenable problems. Kernel methods for machine learning are ubiquitous for pattern recognition, with support vector machines (SVMs) being the most well-known method for classification problems. However, there are limitations to the successful solution to such problems when the feature space becomes large, and the kernel functions become computationally expensive to estimate. A core element to computational speed-ups afforded by quantum algorithms is the exploitation of an exponentially large quantum state space through controllable entanglement and interference. Here, we propose and experimentally implement two novel methods on a superconducting processor. Both methods represent the feature space of a classification problem by a quantum state, taking advantage of the large dimensionality of quantum Hilbert space to obtain an enhanced solution. One method, the quantum variational classifier builds on [1,2] and operates through using a variational quantum circuit to classify a training set in direct analogy to conventional SVMs. In the second, a quantum kernel estimator, we estimate the kernel function and optimize the classifier directly. The two methods present a new class of tools for exploring the applications of noisy intermediate scale quantum computers [3] to machine learning.

Quantum variational classification:

This section describes quantum variational and kernel classifiers built around quantum feature states and reports their experimental classification results.

Quantum variational classification

  • The variational classifier maps inputs to feature states, applies trainable W(θ), measures Z-basis outputs through parity f = Z1Z2, and trains θ and bias b using SPSA.After the parameters converge, the trained circuit assigns labels to unlabeled data.Source: Quantum variational classification · p. 3
  • Increasing circuit depth lowered the converged empirical risk but required more optimization steps; error mitigation helped substantially at larger depths, but not at depth 0.The experiment used three data sets per depth, with 20 training points per label, and applied first-order zero-noise extrapolation.Source: Quantum variational classification · p. 3
  • At depths larger than 1, variational classification reached values very close to 100% and remained there through depth 4 despite decoherence associated with 8 CNOTs.The figure shows classification results for 60 classifications per depth, from three trained data sets.Source: Figure 3 · p. 4, Quantum variational classification · p. 4

Quantum kernel estimation

A path to quantum advantage

  • The variational rule is an SVM hyperplane in quantum state space, and quantum advantage requires feature maps with kernels that are hard to estimate classically.The paper describes such kernel hardness as conjectured and identifies feature maps with provable advantage and improvement on real-world data as future needs; the SVM connection also supplies conventional VC-dimension bounds for structural risk minimization.Source: Quantum variational classification · pp. 4–6

Quantum kernel estimation

  • Kernel training estimates feature-state overlaps for all training pairs, then solves a classical SVM; an operator-norm kernel estimate within ε requires O(ε^-2|T|^4) shots.For new data, the quantum computer estimates overlaps with support vectors.Source: Quantum variational classification · p. 5

SUPPLEMENTARY INFORMATION: … Quantum variational classification

The supplementary section defines supervised classification from labeled training data to unlabeled test data, then describes a quantum variational classifier that uses a variational circuit to find a separating hyperplane and classify new inputs.

Classification problems

  • The programmer receives labels only for training samples and uses them to infer labels for test samples, with accuracy measured by classification success.Source: Classification problems · p. 7
  • The learning setup assumes training and test samples come from distributions whose labeling outputs are correlated, while the distributions themselves remain unknown to the programmer.Source: Classification problems · p. 7

Description of the Algorithm

  • Both learning schemes map classical data into an n-qubit state space of dimension 4n using a unitary circuit family, then construct a separating hyperplane there.Source: Description of the Algorithm · p. 8

Quantum variational classification

  • The variational classifier uses a large Hilbert space to find an SVM-like separating hyperplane, training on labeled samples and evaluating success on a separate set.Source: Quantum variational classification · p. 8
  • The circuit prepares a feature-map state, applies the variational unitary, and measures in the Z basis; repeated bit-string samples estimate label probabilities for the two-class experiment.Source: Figure S1 · p. 8
  • During training, encoded feature states pass through a variational discriminator and measurements estimate label probabilities that define an empirical error cost for parameter optimization.The procedure uses a finite number of measurement shots and an optimization routine such as SPSA.Source: Quantum variational classification · p. 8
  • For classification, the optimized circuit is run on unlabeled test inputs, and the label with the largest measured empirical probability is returned.Source: Quantum variational classification · p. 9

Quantum kernel estimation · The Relationship of variational quantum classifiers to support vector machines · Support vector machines (SVM):

The sections explain how quantum circuits provide feature maps and kernel estimates for SVM classification, and relate variational quantum classifiers to classical SVMs. They describe the SVM margin and support-vector framework, including how kernels extend classification to nonlinear feature spaces.

Quantum kernel estimation

  • For binary classification, the quantum computer estimates the training kernel matrix from squared state overlaps, then a classical SVM solves the dual optimization problem.Each matrix entry is estimated by sampling the circuit output for R shots and counting 0^n outcomes; nonzero α_i identify the support vectors.Source: Quantum kernel estimation · p. 9
  • To classify a test datum, the quantum computer estimates its kernel with each training support vector, and the classifier uses those values to assign its label.The support vectors are determined during training, so the label can be computed once these test-point kernel values are available.Source: Quantum kernel estimation · p. 9

The Relationship of variational quantum classifiers to support vector machines

  • The paper presents the variational circuit classifier as bearing similarities to a classical nonlinear SVM.The section refers readers to for an introduction to SVM construction for pattern recognition.Source: The Relationship of variational… · p. 9

Support vector machines (SVM):

  • A linear SVM seeks a separating hyperplane with the largest margin, minimizing the norm of its normal vector; training points with tight constraints become support vectors.Only support vectors have nonzero α_i in the dual classifier.Source: Support vector machines (SVM) · pp. 10–11
  • For non-separable data, nonnegative slack variables soften the constraints and add a penalty to the objective; choosing r ≥ 1 keeps the optimization problem convex.For r = 1, the slack variables and their Lagrange multipliers do not appear in the dual Lagrangian.Source: Support vector machines (SVM) · p. 10
  • SVMs can classify nonlinear data by mapping it into a feature space and using inner products as kernels, without explicitly constructing mapped data.The paper uses a tunable quantum circuit family as a classical-to-quantum feature map; quantum states may offer hard-to-estimate overlaps, while Hilbert-space dimension alone does not provide an advantage.Source: Support vector machines (SVM) · p. 11

Variational circuit classifiers:

The variational classifier maps data to quantum states, applies a parameterized circuit, and measures binary labels. Its decision expression matches a conventional SVM after feature mapping, while the relevant separating space is the space of density matrices.

Variational circuit classifiers:

  • The classifier encodes each input as an n-qubit state, applies a parameterized circuit, measures in the Z basis, and assigns the most likely binary label.Source: Variational circuit classifiers · p. 11
  • The decision expression is identical to a conventional SVM after feature mapping, but observable-derived weights are constrained and label probabilities must be estimated.Source: Variational circuit classifiers · p. 12
  • The separating hyperplane belongs in the space of density matrices, not Hilbert space, because global-phase-equivalent states can lie on opposite sides of a plane.Source: Variational circuit classifiers · p. 12

Encoding of the data using a suitable feature map

A feature map injectively encodes classical data as an n-qubit quantum state, with the state designed to depend nonlinearly on the input. Product-state maps use single-qubit rotations, but their kernel computations scale linearly with the number of qubits and offer no expected quantum advantage.

Encoding of the data using a suitable feature map

Product state feature maps

  • In a product-state map, each qubit undergoes a single-qubit rotation whose Euler angles are chosen as nonlinear functions of the input.The angle map takes x into (0, 2π]^2 × [0, π].Source: Encoding of the data using a suitable… · p. 13
  • Stoudenmire and Schwab’s feature map assigns one component x_i ∈ [0, 1] to each of n qubits and uses local Pauli expectation values in the decision function.Its kernel is the product of the individual qubit-state overlaps; these evaluations scale linearly in qubit number, so no quantum advantage is expected.Source: Encoding of the data using a suitable… · p. 13

Non-trivial feature map with entanglement

The section defines an entangling quantum feature-map family intended to make its kernel computationally hard to estimate classically, while distinguishing it from a superficially hard circuit whose kernel remains classically estimable.

Non-trivial feature map with entanglement

  • The authors conjecture that estimating the proposed feature map’s kernel to additive polynomially small error is classically hard.Their intuition connects the circuit to hidden-shift algorithms for Boolean bent functions; the implemented overlap-estimation circuit is larger than the related circuit, and proving the conjecture would be a step toward establishing quantum advantage on near-term devices.Source: Non-trivial feature map with… · pp. 13–14
  • Experiments restrict the phase expansion to degree d = 2, using Ising interactions on the superconducting chip’s connectivity graph to enable short-depth circuits.The construction provides |V| + |E| real parameters: at least |V| = n for data values and up to |E| ≤ n(n−1)/2 additional interaction parameters.Source: Non-trivial feature map with… · p. 13
  • The feature map applies Hadamard gates around two diagonal-phase layers, encoding both phase-function values and their Fourier-Walsh transform.The circuit representation shows the sequence of Hadamard and diagonal-phase operations; the map encodes the function and its transform for each basis element.Source: Figure S2 · p. 14, Non-trivial feature map with… · p. 14
  • A single-Hadamard-layer IQP feature map does not imply a classically hard kernel: it can be estimated to additive error ϵ using R = ϵ^-2 uniform random bit strings.Although related IQP output probabilities have hardness results under multiplicative-error or sampling conditions [34], the kernel’s additive-error estimate is classically accessible by averaging samples.Source: Non-trivial feature map with… · pp. 14–15

Quantum variational classification

The variational classifier uses a parameterized short-depth circuit of local rotations and entanglers, with the entangling pattern following the feature map’s interaction graph. Its controlled-phase gates support compilation across device topologies.

Quantum variational classification

  • The classifier interleaves local rotations with repeated entanglers; controlled-phase gates follow the feature map’s interaction graph and can be translated by the compiler for the target system.The circuit schematic shows the short-depth classifier and an example entangling pattern on a circular graph.Source: Quantum variational classification · p. 15, Figure S3 · p. 15
  • For the two-qubit experiment, each depth adds one controlled-phase gate, and the classifier uses only Y and Z rotations to reduce the optimizer’s parameter count.The rotations are parameterized by θt ∈ R2n and θi,t ∈ R2.Source: Quantum variational classification · p. 15

Choosing the cost-function for the circuit optimization

The section defines circuit optimization around minimizing misclassification after R measurement shots and describes measurement choices for multi-label classification.

Choosing the cost-function for the circuit optimization

  • The cost function minimizes the probability of assigning the wrong label after R shots under a winner-takes-all rule that selects the most probable outcome.The goal is to find a classifying circuit W(⃗θ) that separates data with different labels.Source: Choosing the cost-function for the… · p. 16
  • For multi-label classification, the final measurement can use computational-basis outcomes mapped to labels or commuting Pauli measurements akin to quantum-stabilizer syndrome checks.The computational-basis strategy assigns each measured bit string a label through a function mapping outcomes to classes.Source: Choosing the cost-function for the… · p. 16
  • The empirical risk Remp(⃗θ) is defined as the error probability Perr for misclassifying an individual datum.The section describes estimating outcome probabilities from R shots and using the resulting error probability in the cost function.Source: Choosing the cost-function for the… · p. 16

Binary label classification

For binary labels y ∈ {−1, 1}, the classifier uses repeated shots to estimate label probabilities and determine misclassification under an argmax rule. For large shot counts, the binomial CDF is approximated by an error function and then a sigmoid to provide a cost function for optimization.

Binary label classification

  • With R shots for a datapoint, the classifier estimates the probability of assigning each binary label y ∈ {−1, 1}.The resulting empirical probability estimate is for the datum being labeled y.Source: Binary label classification · p. 16
  • After R = r_y + r_−y shots and a prior bias b, the method estimates the probability that the argmax rule misclassifies a sample of label y.This estimated misclassification probability is used in the cost-function construction.Source: Binary label classification · p. 16
  • For large R, the binomial CDF is approximated by an error function and then a sigmoid, which is used to estimate sample misclassification in the optimization cost.In the experiment, data were sampled with R = O(10^3) shots, while the cost function was evaluated with ˜R = O(10^2) for a smoother optimization function.Source: Binary label classification · p. 17, Figure S4 · p. 17

Multi label classification · Quantum kernel estimation

The section describes sampled-count argmax classification for multiple labels and a quantum-kernel workflow that uses quantum estimates with classical classifier optimization. It presents two overlap-estimation circuits and discusses sampling complexity and errors that can make the estimated kernel non-positive-semidefinite.

Multi label classification

  • For three labels, misclassification by argmax is considered using sampled output counts; the analysis retains dependence on n1 and n2, and general k-label classification lacks a simple analytic solution for γ.The text therefore estimates the probability using an approximate choice of γ.Source: Multi label classification · p. 18

Quantum kernel estimation

  • The quantum computer estimates training-set kernels, while classical optimization finds Lagrange multipliers and support vectors; classifying new data requires kernels between it and those support vectors.The kernel is K(x_i, x_j) = |⟨Φ(x_i)|Φ(x_j)⟩|^2.Source: Quantum kernel estimation · p. 18
  • The SWAP-based estimator obtains the state fidelity from sampled eigenvalues, and its circuit can be constant depth when pairs of CNOT gates run in parallel, following [27].The figure also presents a direct feature-state fidelity circuit that records the all-zero outcome.Source: Figure S5 · p. 18, Quantum kernel estimation · p. 18
  • For structured feature states, applying U†Φ(y)UΦ(x) and measuring in the Z basis estimates the kernel from the all-zero frequency, with sampling error O(R^-1/2).The circuit and zero-outcome interpretation are shown in Fig. S5.b.Source: Quantum kernel estimation · pp. 18–19
  • O(ϵ^-2|T|^4) total shots are expected to estimate the symmetric training kernel matrix within maximum deviation ϵ with high probability.The stated bound uses O(ϵ^-2|T|^2) shots per matrix entry and estimates |T|(|T|−1)/2 entries.Source: Quantum kernel estimation · p. 19
  • Shot noise and other experimental errors can make the estimated kernel non-positive-semidefinite, but the experiments found performance almost optimal without projecting it to a nearby positive-semidefinite matrix.The suggested correction solves an optimization problem for the closest positive-semidefinite matrix in trace norm.Source: Quantum kernel estimation · p. 19

Device parameters · Gate characterization

The device section reports processor parameters and control-pulse implementation, while gate characterization uses randomized benchmarking to assess single- and two-qubit operations. The reported CNOT errors differ for the two cross-resonance pulse durations.

Device parameters

  • The processor is fabricated on a 720-µm-thick Si substrate, with Nb CPW structures and qubit capacitors and electron-beam-patterned, double-angle-deposited Al Josephson junctions.Source: Device parameters · p. 19
  • Dispersive readout signals are amplified by Josephson Parametric Converters, and the processor and amplifiers are thermally anchored to the dilution refrigerator’s mixing chamber plate.Source: Device parameters · p. 19
  • The qubit frequencies are 5.2760(4) and 5.2122(3) GHz, with anharmonicities −330.3 and −331.9 MHz; the readout resonators are at 6.530553 and 6.481651 GHz.The connecting CPW bus resonator was unmeasured and designed to be 7.0 GHz; readout dispersive shifts are −1.06 and −1.02 MHz, and linewidths are 661 and 681 kHz.Source: Device parameters · p. 19
  • Mean qubit lifetimes were T1(i) = {55, 38} µs, with T ∗ 2(i) = {16, 17} µs and T echo 2(i) = {43, 46} µs for i ∈{0, 1}.Measurements were taken intermittently throughout the experiments.Source: Device parameters · p. 19

Gate characterization

  • Calibrated Xπ and Xπ/2 rotations serve as single-qubit primitives; Y rotations use pulse-phase adjustments and Z rotations use software frame changes [38].A buffer follows each physical pulse to mitigate reflections and evanescent waves in cryogenic control lines and components.Source: Gate characterization · p. 20
  • The two gate-time sets support Richardson noise extrapolation [10]: the first uses 83 ns single-qubit and 333 ns cross-resonance pulses, while the second stretches times and buffers by 1.5.The resulting CNOT durations are 858 ns and 1.287 µs, and the stretched single-qubit gates last approximately 125 ns.Source: Gate characterization · p. 20
  • Randomized benchmarking [39] was used to verify single- and two-qubit unitaries, with the single-qubit gate results covering individual and simultaneous benchmarking.Table S1 presents the single-qubit randomized benchmarking results; its supplied caption does not provide the numerical values.Source: Gate characterization · p. 20, Table S1 · p. 20
  • 0.0373 ± .0015 and 0.0636 ± .0021 are the CNOT errors for 333 ns and 500 ns cross-resonance pulses, respectively.The CNOTs are constructed from echo cross-resonance sequences.Source: Gate characterization · p. 20

Readout correction · Support vectors · Error mitigation for kernel estimation

The section describes readout correction and support-vector identification, then evaluates zero-noise error mitigation for kernel estimation. Mitigation improves agreement with ideal hyperplanes for Sets I and II but worsens it for Set III.

Readout correction

  • Readout correction used calibration statistics to form and invert a two-qubit measurement matrix, then applied its inverse to observed outcome distributions.Assigned readout fidelity was approximately 95% for both qubits.Source: Readout correction · p. 20

Support vectors

  • The support vectors and αi were calculated from the kernel matrices for all three datasets; Table S2 lists them and Fig. S6 marks those for Sets I and II.The figure distinguishes support vectors as green circles among the training data points.Source: Support vectors · p. 20, Table S2 · p. 21, Figure S6 · p. 21

Error mitigation for kernel estimation

  • Kernel estimation used gate-length variation and extrapolation to zero noise, a technique sensitive to sampling noise and often bounded in precision by readout assignment fidelity.The method is especially powerful when noise is invariant under time rescaling.Source: Error mitigation for kernel estimation · p. 20
  • The study quantified hyperplane agreement with the ideal using inner products across training sets and gate-time stretches c1 and c1.5, including error-mitigated hyperplanes.The stretches correspond to faster and slower gates, respectively.Source: Error mitigation for kernel estimation · pp. 21–22, Figure S8 · p. 22
  • For Sets I and II, which each achieved 100% classification, error mitigation significantly improved hyperplane agreement with the ideal; for Set III (94.75%), it worsened agreement.The 100% success rates were attained over 10 randomly drawn test sets for each of Sets I and II.Source: Error mitigation for kernel estimation · pp. 21–22, Figure S8 · p. 22
  • Set III had lower readout assignment fidelities—93.99% for Q0 and 95.47% for Q1—than Sets I and II, which could partly explain its poorer classification.The passage also notes that other protocol factors, including gates operating in a somewhat non-linear regime after calibration, may contribute.Source: Error mitigation for kernel estimation · p. 22
  • The combined absolute weight of negative kernel eigenvalues was 1.40 for Set I, 1.27 for Set II, and 2.41 for Set III.The paper presents this quantity as another symptom of classification success in a given set.Source: Error mitigation for kernel estimation · p. 22

Related papers

Loading 1804.11326v2…