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

Classical kernel methods become difficult to estimate as feature spaces grow. This paper experimentally implements quantum variational classification and quantum kernel estimation using quantum feature spaces, achieving classification success rates up to 100% despite noise.

  • Problem

    Large feature spaces can make kernel functions computationally expensive to estimate, motivating feature maps with overlaps that may be classically hard to estimate.

  • Method

    The paper maps classical data into a 4^n-dimensional quantum state space and trains either a variational classifier or a classifier using experimentally estimated quantum kernels.

  • Results

    Classification success reached values close to 100% for circuit depths above 1 and remained high through depth 4 despite decoherence and noise.

  • Takeaways & Limitations

    The experiments demonstrate a noise-tolerant classifier that exploits a quantum feature space and suggest potential applications beyond binary classification.

  • Takeaways & Limitations

    Shot noise and experimental errors can make the estimated kernel matrix non-positive-semidefinite, potentially invalidating the optimization problem's concavity.

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:

The quantum variational classifier maps inputs into quantum states, applies a trainable variational circuit and binary measurement, and optimizes its parameters to classify data. Experimentally, classification success increased with circuit depth and reached rates up to 100% despite noise.

  • Quantum variational classifier: The classifier maps x to a quantum state, applies a trainable circuit W(θ), and assigns binary labels from a measurement of the resulting state.The decision rule uses repeated measurement shots to estimate label probabilities and includes an optimizable bias b.
  • Quantum variational classifier: Training optimizes (θ, b) by minimizing empirical classification error, with Spall’s SPSA performing well in the noisy experimental setting.After convergence, the trained circuit classifies previously unlabeled data according to the measurement-based decision rule.
  • Experimental setup: The experiment implemented five circuit depths, l = 0 through l = 4, using three datasets per depth with 20 training points per label.The binary measurement used the parity function f = Z1Z2, and all experiments applied error mitigation.
  • Relation to SVMs: The variational circuit and binary measurement act as a separating hyperplane in quantum state space, directly relating the method to conventional SVMs.The corresponding feature vectors are quantum-state density operators with kernel inner products K(x,z) = |⟨Φ(x)|Φ(z)⟩|^2.
  • Experimental results: Success rates reached up to 100% despite noise in the experimentally demonstrated quantum-feature-space classifier.The authors identify suitable feature maps with provable quantum advantages and improved real-world performance as future goals.

Supplementary Information is available in the online version of the paper. … Quantum variational classification

The paper formalizes supervised classification and presents quantum variational classification as a quantum analogue of SVM-style hyperplane separation, with training and measurement-based prediction stages. The supplementary material records funding, contributions, and author information.

  • Supplementary Information is available in the online version of the paper.: The supplementary material states that classifier theory was led by V.H. and K.T., while the experiment was designed by A.D.C., J.M.G., and K.T., with all authors contributing.The work acknowledges Sergey Bravyi and support from the MIT-IBM Watson AI Lab, IBM Research Frontiers Institute, and IARPA.
  • Classification problems: Supervised classification provides labeled training data but withholds test labels, requiring an inferred map that predicts each test sample’s class with high probability.Classification success is quantified by agreement between the inferred and unknown labeling maps.
  • Classification problems: The learning problem assumes correlated training and test samples drawn from class-labeled d-dimensional distributions, although the programmer receives only finitely many samples and training labels.The underlying labeling distributions are not directly available to the programmer.
  • Description of the Algorithm: Both proposed schemes map classical data into a 4^n-dimensional n-qubit state space and construct a separating hyperplane there.The mapping begins from |0⟩⟨0|^n and uses a unitary circuit family.
  • Quantum variational classification: Quantum variational classification uses a variational circuit to find an optimal cutting hyperplane in a large quantum Hilbert space, analogously to Support Vector Machines.The method has separate training and classification stages.
  • Quantum variational classification: Training calibrates short-depth hardware circuits, initializes variational parameters, repeatedly measures labeled feature-map states, and optimizes an empirical misclassification cost using a routine such as SPSA.Measurement frequencies estimate class probabilities for each training sample.
  • Quantum variational classification: After optimization, classification applies the fixed discriminator to an unlabeled test state, samples measurement outcomes, and returns the label with the largest empirical probability.The same feature-map and discriminator circuit structure is used with optimal parameters.

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

The paper estimates quantum kernels from state overlaps for binary classification, while relating variational quantum classifiers to SVMs and motivating quantum feature spaces through hard-to-estimate overlaps.

  • Quantum kernel estimation: The quantum kernel protocol estimates a |T| × |T| matrix K(x_i,x_j)=|⟨Φ(x_i)|Φ(x_j)⟩|^2 by sampling overlaps for every training-point pair.The quantum computer is used to estimate the kernel matrix for binary labels C={+1,−1}.
  • Quantum kernel estimation: For a test datum s, the classifier estimates K(x_i,s) for support vectors and directly computes its label using the trained SVM coefficients.Only support vectors indexed by N_S are queried during classification.
  • The Relationship of variational quantum classifiers to support vector machines: Variational quantum classifiers are presented as closely analogous to classical nonlinear SVM classifiers for supervised pattern recognition.The cited references provide an introduction to SVM construction for pattern-recognition tasks.
  • Support vector machines (SVM):: A linear SVM seeks a hyperplane separating binary-labeled data with the largest possible margin, with support vectors determining the tight constraints.For linearly separable data, the constraints are y_i(w·x_i+b)≥1.
  • Support vector machines (SVM):: For non-separable data, nonnegative slack variables soften separability constraints and add a penalty term weighted by C to the objective.The resulting optimization remains convex when the slack penalty exponent r≥1.
  • Support vector machines (SVM):: SVMs can replace inner products with kernels after mapping data nonlinearly into a high-dimensional feature space, without explicitly constructing the mapped vectors.Examples include polynomial and Gaussian kernels, and only inner products involving training or test points are required.
  • Support vector machines (SVM):: Quantum Hilbert-space dimension alone does not guarantee an advantage, because classical kernels can access infinite-dimensional spaces; the opportunity instead lies in hard-to-estimate quantum overlaps.The quantum feature-space motivation is therefore constructing states whose overlaps are difficult to estimate classically.

Variational circuit classifiers:

The variational circuit classifier maps data to quantum states, applies a parameterized circuit, and classifies through computational-basis measurement. Its resulting decision function is identical to a conventional SVM after feature mapping, but the separating feature space is the quantum state space of density matrices.

  • Variational circuit classifiers:: The classifier maps x to an n-qubit quantum state, applies W(θ), measures in the Z basis, and assigns each resulting bit string through a Boolean labeling function.The resulting label probabilities determine the classification output.
  • Variational circuit classifiers:: Labels are chosen by comparing their empirical probabilities, equivalently using the sign of the measured expectation value with an optional bias b.The decision rule assigns y over −y when p_y > p_−y − yb.
  • Variational circuit classifiers:: The variational circuit’s decision function is identical to a conventional SVM classifier after feature mapping, while its coefficients are constrained by the rotated measured observable.In experiments, the label probabilities are estimated rather than accessed exactly.
  • Variational circuit classifiers:: The relevant linearly separable feature space is the quantum state space of density matrices rather than Hilbert space, because physical states are equivalent up to global phase.States differing only by a global phase represent the same physical state and cannot consistently occupy opposite sides of a separating hyperplane.

Encoding of the data using a suitable feature map

A quantum feature map injectively encodes classical data into an n-qubit quantum state generated by a data-dependent unitary circuit. Product-state maps can use single-qubit rotations, but their kernels scale linearly with qubit number and offer no expected quantum advantage.

  • Quantum feature maps injectively encode x ∈ R^d as a density matrix |Φ⟩⟨Φ| on an n-qubit register.The density matrices are positive semidefinite and have unit trace.
  • A unitary circuit U_Φ(x) applied to a reference state |0⟩^n produces |Φ(x)⟩, whose dependence on the data should be nonlinear.
  • Product state feature maps: Product-state feature maps apply single-qubit SU(2) rotations with Euler angles chosen as nonlinear functions of x.The full map is assembled from individual-qubit states U(ϕ_i(x))|0⟩.
  • Product state feature maps: The tensor-network feature map of Stoudenmire and Schwab encodes each component x_i in a separate qubit.
  • Product state feature maps: Product-state kernels are evaluated with resources scaling linearly in the number of qubits, so no quantum advantage is expected in this setting.The kernel is replaced by the inner product between the resulting product states.

Non-trivial feature map with entanglement

The feature-map family uses entangling, low-degree phase interactions to encode nonlinear data and its Fourier-Walsh transform, with the kernel conjectured to be classically hard to estimate. This hardness is not guaranteed by a single Hadamard–diagonal layer, whose kernel remains classically estimable.

  • Feature-map motivation: The proposed feature maps are designed so that K(x,y) = |⟨Φ(x)|Φ(y)⟩|^2 is computationally hard to estimate classically up to polynomially small additive error, preserving potential quantum advantage.The hardness is stated as a conjecture for the considered family.
  • Feature-map construction: The experimentally used maps restrict the phase expansion to degree d = 2, implementing Ising-type interactions on the superconducting chip’s connectivity graph.Low-degree maps can be implemented efficiently, and the chip graph determines which interactions are available.
  • Feature-map construction: The circuit applies Hadamard and diagonal phase layers twice, encoding both the phase function Φ_x(z) and its Fourier-Walsh transform for every computational-basis element.The resulting construction encodes the function and transform across the feature space.
  • Hardness rationale: The hardness conjecture is motivated by a connection to hidden-shift circuits for Boolean functions, including bent-function constructions possible on bipartite interaction graphs.For d = 2, Maiorana-McFarland bent functions can be encoded by choosing selected phase coefficients as π or 0.
  • Limitation: A single Hadamard–diagonal layer does not provide an advantage: its kernel can be estimated classically by sampling, with error scaling O(ϵ).The sampling estimate uses R = ϵ^-2 samples, and the variance is bounded because |Φ_x(z)|^2 = 1.

Quantum variational classification

The quantum variational classifier appends parametrized single-qubit rotations and entangling layers to the feature-map circuit, forming a short-depth circuit W(⃗θ). Its entanglers use CZ gates along the feature-map interaction graph, and sufficient depth makes the gate set universal.

  • Quantum variational classification: The classifier appends layers of single-qubit unitaries and entangling gates to the feature-map circuit, with each additional depth adding entanglers across the algorithm’s qubits.The resulting short-depth circuit W(⃗θ) is implemented on a coherently controllable superconducting system with n transmon qubits.
  • Quantum variational classification: The variational circuit interleaves l repeated entanglers with layers of local single-qubit rotations parametrized by θt ∈ R2n and θi,t ∈ R2.The circuit’s single-qubit rotations are U(θi,t) ∈ SU(2), while the entangling operation follows the superconducting chip’s interaction graph.
  • Quantum variational classification: The entangling unitary is chosen as products of controlled-phase gates CZ(i, j) between qubits connected by the feature-map interaction graph G = (E, V) [16] [17].For the illustrated five-qubit circle, the entangler is a product of CZi,i+1 gates following G = C5.
  • Quantum variational classification: With sufficiently many layers d, the short-depth circuit can generate any unitary; its entangling evolution and arbitrary single-qubit control pulses therefore form a universal gate set [35].The entangling evolution can be understood as bang-bang control of an Ising-model Hamiltonian, interspersed with SU(2) single-qubit pulses.

Choosing the cost-function for the circuit optimization

The circuit is optimized by minimizing the probability of assigning an incorrect label after estimating outcome probabilities from repeated measurements. Multi-label classification is handled by modifying the final measurement and using the resulting empirical misclassification rate as the risk.

  • Cost-function objective: The cost function minimizes the probability of assigning the wrong label after R repeated shots, using a winner-takes-all rule based on the largest outcome probability.The optimized classifying circuit W(θ) aims to separate differently labeled datasets.
  • Multi-label measurement: Multi-label classification requires modifying only the final measurement M, for example by measuring in the computational basis and mapping bit-string outcomes to class labels.The mapping assigns each outcome z ∈ {0, 1}^n to one of c labels through a function f.
  • Empirical risk: The empirical risk R_emp(θ) is defined as the individual datum’s misclassification probability, derived from the overall expected misclassification rate across measurement outcomes.R shots estimate the largest outcome probability for each class measurement M_y.

Binary label classification

Binary classification estimates label probabilities from repeated shots for labels y ∈ {−1, 1}, then approximates the resulting misclassification cost with a smooth sigmoid-based rule.

  • Binary classification uses R shots to estimate the probability that a datapoint receives each label y ∈ {−1, 1}.
  • The argmax decision rule determines misclassification probabilities after accounting for the shot counts and prior bias b.
  • For large R, the binomial CDF underlying the misclassification probability is approximated by an error function and then a sigmoid.
  • The experiment sampled with R = O(10^3) shots but evaluated the cost with R̃ = O(10^2) to provide a smoother optimization function.The smoothed estimate is used as the misclassification cost in the optimization objective.

Multi label classification

For multi-label classification, the method analyzes argmax misclassification using sampled output frequencies, first for three labels and then for the general k-label case. Because the resulting probability depends on competing class counts and lacks a simple general analytic solution, γ is estimated using a maximum-class approximation.

  • Multi label classification: For three labels, the argmax misclassification probability for a sample s ∈ T0 is analyzed from R independently drawn samples with output frequencies {n0, n1, n2}.The analysis considers samples drawn independently from the output probability distribution.
  • Multi label classification: The comparison underlying misclassification is expressed through the condition 2n0 < 2 max(n1, n2) = |n1 − n2| + n1 + n2 = |n1 − n2| + N − n0.This inequality reformulates the competing-label count in terms of the absolute difference between n1 and n2 and the total count N.
  • Multi label classification: The three-label expression still depends on n1 and n2, which cannot be simply eliminated.This dependence prevents a straightforward closed-form simplification of the probability.
  • Multi label classification: For a general k-label case, there is no simple analytic solution for γ, so the probability is estimated by taking γ = maxc′.The supplied passage gives the maximum-class approximation only in truncated form.

Quantum kernel estimation

The quantum kernel estimator uses the quantum computer to estimate feature-state overlaps, then solves the classical SVM optimization to construct the classifier. Overlap estimation has sampling cost that scales as O(ϵ^-2|T|^4), and experimental noise can make the estimated kernel non-positive-semidefinite.

  • Quantum kernel estimation: The quantum computer estimates K(x_i,x_j)=|⟨Φ(x_i)|Φ(x_j)⟩|^2 for labeled training data, after which classical optimization yields Lagrange multipliers, support vectors, and the classifier.For a new datum, the classifier evaluates kernels between that datum and the support vectors.
  • Kernel estimation circuit: The kernel can be estimated by applying U_Φ(y) followed by U†_Φ(x) to |0^n⟩ and recording the all-zero frequency, with sampling error O(R^-1/2).Alternatively, the SWAP expectation-value circuit estimates the same state overlap; the optimized protocol in [27] avoids the conventional swap test’s long controlled-SWAP sequence.
  • Sampling complexity: Ensuring maximum kernel-matrix deviation ϵ with high probability requires O(ϵ^-2|T|^2) shots per entry and expected total sampling complexity O(ϵ^-2|T|^4).Symmetry and trivial diagonals reduce the number of estimated training-set entries to |T|(|T|−1)/2.
  • Noise and correction: Shot noise and other experimental errors can make the estimated kernel K̂ non-positive-semidefinite, breaking the concavity condition of the optimization problem; provides a correction approach.That approach finds the closest positive-semidefinite K-matrix in trace norm to K̂, subject to the stated consistency condition.

Device parameters · Gate characterization · Readout correction

The experiments use a superconducting two-qubit processor with characterized device parameters, calibrated single- and two-qubit gates, and approximately 95% readout fidelity corrected through measurement-matrix inversion.

  • Device parameters: The device is fabricated on a 720-µm-thick Si substrate using Nb-defined CPW structures and qubit capacitors, with Al Josephson junctions patterned by electron-beam lithography and double-angle deposition.The quantum processor and Josephson Parametric Converter readout amplifiers are thermally anchored to the dilution refrigerator’s mixing-chamber plate.
  • Device parameters: The qubits have fundamental transition frequencies of 5.2760(4) and 5.2122(3) GHz, with anharmonicities of −330.3 and −331.9 MHz.Readout resonators operate at 6.530553 and 6.481651 GHz; their dispersive shifts are −1.06 and −1.02 MHz, and linewidths are 661 and 681 kHz.
  • Device parameters: Measured mean qubit coherence values were T1(i) = {55, 38}, T2*(i) = {16, 17}, and T2echo(i) = {43, 46} µs for i ∈ {0, 1}.
  • Gate characterization: The processor uses calibrated Xπ and Xπ/2 pulses, phase-adjusted Y rotations, software-frame Z rotations, and pulse-end buffers to mitigate control-line effects.Single-qubit pulses are Gaussian with σ = 20.75 ns, while cross-resonance pulses use Gaussian turn-on and turn-off shapes with σ = 10 ns.
  • Gate characterization: Single- and two-qubit unitaries were experimentally verified using randomized benchmarking, including individual and simultaneous single-qubit benchmarking.The reported single-qubit benchmarking results are provided in Table S1.
  • Gate characterization: CNOT errors were 0.0373 ± .0015 and 0.0636 ± .0021 for 333 ns and 500 ns cross-resonance pulses, respectively.The CNOTs use echo cross-resonance sequences with two cross-resonance pulses.
  • Readout correction: Readout assignment fidelity was approximately 95% for both qubits, with outcome probabilities corrected by inverting a calibration-derived measurement matrix.Four calibration sequences were used for one-qubit states and 22 for the joint computational states.

Support vectors · Error mitigation for kernel estimation

The study identifies support vectors and α_i for three datasets, then evaluates error mitigation for experimentally estimated kernel matrices. Error mitigation substantially improves hyperplane agreement for Sets I and II but worsens it for Set III, despite 100% versus 94.75% classification success.

  • Support vectors: Support vectors and α_i are calculated from the K matrices for each of the three studied datasets.The support vectors for all three datasets are shown as green circles in the corresponding figures and table.
  • Error mitigation for kernel estimation: The kernel matrices are estimated at different gate lengths, then expectation values are extrapolated to their zero-noise values.This approach can be powerful when noise is invariant under time rescaling but is particularly sensitive to measurement sampling noise.
  • Error mitigation for kernel estimation: Sets I and II attain 100% classification success across 10 randomly drawn test sets each, while the experimentally determined hyperplane is compared quantitatively with the ideal.The comparison uses inner products between experimentally obtained and ideal hyperplanes.
  • Error mitigation for kernel estimation: The experimentally obtained hyperplane is represented through support vectors as w = Σ α_i y_i x_i, enabling inner-product comparison with the ideal hyperplane.The ideal and experimental support-vector sets determine the hyperplanes being compared.
  • Error mitigation for kernel estimation: Hyperplane comparisons include faster c1 gates, slower c1.5 gates, and error-mitigated results for each training set.Figure S8 reports inner products between experimentally obtained hyperplanes and the ideal.
  • Error mitigation for kernel estimation: Error mitigation significantly improves agreement with the ideal hyperplane for Sets I and II, but worsens it for Set III.Sets I and II classify at 100% success, whereas Set III classifies at 94.75%; for Set III, unmitigated results are closer to ideal than either mitigated result.
  • Error mitigation for kernel estimation: Readout assignment fidelities are lower for Set III than for Sets I and II, potentially contributing to its poorer classification results.The reported Q0(Q1) fidelities are 96.56% (96.31%) for Set I, 95.90% (96.36%) for Set II, and 93.99% (95.47%) for Set III.
  • Error mitigation for kernel estimation: The combined absolute weight of negative kernel eigenvalues is 1.40 for Set I, 1.27 for Set II, and 2.41 for Set III.This quantity is presented as another symptom associated with classification success.
Loading 1804.11326v2…