PaperlayerView exact revision on arXiv

Source-linked AI summary

Nearest Centroid Classification on a Trapped Ion Quantum Computer

Sonika Johri, Shantanu Debnath, Avinash Mocherla, Alexandros Singh, Anupam Prakash, Jungsang Kim, Iordanis Kerenidis

arXiv:2012.04145v2quant-ph

TL;DR

Making quantum machine learning practical remains challenging, despite the potential impact of machine learning and provable quantum advantages. This work demonstrates a quantum Nearest Centroid classifier on real hardware, matching classical accuracy on real datasets and reaching 100% on synthetic data.

  • Problem

    Making quantum machine learning practical remains challenging, although machine learning has broad potential impact and quantum computers can offer provable advantages for some applications.

    Source: §I · p. 1

  • Method

    The authors design a quantum Nearest Centroid classifier using procedures to load classical data into quantum states and estimate distances.

    Source: §I · p. 2

  • Results

    The classifier achieved accuracy comparable to classical classifiers on real datasets and 100% accuracy on synthetic data.

    Source: §I · p. 2, §IV · p. 13

  • Takeaways & Limitations

    The authors argue that shallow circuits tolerant to certain noise levels and classification's need only to compare centroid distances support applicability on NISQ machines.

    Source: §IV · p. 13

    The authors do not claim the quantum procedure is faster than the classical one now or in the very near future.

    Source: §2 · p. 8

Abstract

from arXiv · show

Quantum machine learning has seen considerable theoretical and practical developments in recent years and has become a promising area for finding real world applications of quantum computers. In pursuit of this goal, here we combine state-of-the-art algorithms and quantum hardware to provide an experimental demonstration of a quantum machine learning application with provable guarantees for its performance and efficiency. In particular, we design a quantum Nearest Centroid classifier, using techniques for efficiently loading classical data into quantum states and performing distance estimations, and experimentally demonstrate it on a 11-qubit trapped-ion quantum machine, matching the accuracy of classical nearest centroid classifiers for the MNIST handwritten digits dataset and achieving up to 100% accuracy for 8-dimensional synthetic data.

I. INTRODUCTION

The paper presents a quantum Nearest Centroid classifier as a proof-of-concept application combining quantum hardware and algorithms. It reports classical-comparable accuracy on real data and up to 100% accuracy on synthetic data.

I. INTRODUCTION

  • Quantum applications require concurrent hardware and algorithm progress, while hardware advances and algorithmic work targets resource reductions for NISQ devices.The introduction cites trapped-ion and superconducting hardware and examples including amplitude-estimation variants and gate-count reductions.Source: §I · p. 1
  • Quantum machine learning is motivated by classical machine learning's broad applications and by potential quantum advantages, including data loading and distance estimation.The paper also names interpretability, transparency, and energy consumption as performance measures where quantum computing may offer advantages.Source: §I · p. 1
  • Quantum machine-learning speedup proposals face efficient data-loading assumptions, potentially costly state tomography, and instance-specific parameters that complicate runtime claims.The paper describes logarithmic-depth data-loading circuits using as many qubits as data features and cautions that many speedups may be polynomial rather than exponential.Source: §I · pp. 1–2
  • Variational quantum classifiers have limited theoretical and practical evidence, with concerns including trainability, circuit expressivity, and lengthy training.The introduction notes that constant-depth circuits with only consecutive-qubit gates cannot act as fully connected neural networks.Source: §I · p. 2
  • The hardware-software collaboration advances quantum machine-learning implementation, while the authors characterize the implementation's scale as a proof of concept.The paper frames classification as a canonical supervised-learning problem with many applications.Source: §I · p. 2
  • Similarity-based classifiers offer interpretability and performance guarantees, while neural networks can perform better with large datasets; Nearest Centroid assigns each point to its closest class centroid.Nearest Centroid performance can deteriorate when data are far from convex classes with similar variances.Source: §I · p. 2
  • The quantum Nearest Centroid classifier matched classical accuracy on real datasets and achieved up to 100% accuracy on synthetic data; the authors say noise analysis supports performance as problem size scales.The reported implementation used up to 8 qubits; the scaling statement concerns the error-mitigation and noise-model analysis.Source: §I · pp. 2–3
  • Earlier hardware demonstrations of variational classification included small binary-classification experiments on synthetic and IRIS data [27] [29] [30].One cited IRIS experiment used two qubits and reported training for over an hour and three million circuit runs [27].Source: §I · p. 3

II. ALGORITHM AND SOFTWARE

This section describes the algorithm and software tools used to implement quantum classification.

II. ALGORITHM AND SOFTWARE

  • Section II describes the algorithm and software tools used to implement quantum classification.Source: §II · p. 3

A. Data loaders and distance estimation

The section constructs a classical-data loader that prepares amplitude-encoded quantum states and a circuit that estimates distances between data points. It also describes a gate-merging optimization for the distance circuit.

A. Data loaders and distance estimation

  • The parallel unary loader prepares amplitude-encoded data using d qubits, d−1 parametrized two-qubit gates, and log d depth.Its circuit has a binary-tree architecture.Source: A. Data loaders and distance estimation · pp. 3–4
  • Classical preprocessing computes the gate parameters in eO(d) time and tracks vector norms; a coordinate update changes only O(log d) parameters.The parameters follow a binary-tree organization of the data coordinates.Source: A. Data loaders and distance estimation · p. 4
  • The described distance-estimation variant applies when the data-point inner product is positive; one extra qubit extends it to non-positive inner products.Source: A. Data loaders and distance estimation · p. 6
  • For two vectors, the distance estimator combines a loader and an inverse loader; measuring |1⟩ has probability equal to the squared normalized inner product.The inner product estimate is combined with classically calculated vector norms to obtain Euclidean distance.Source: A. Data loaders and distance estimation · p. 6
  • Merging adjacent middle RBS gates reduces the distance circuit to 3d/2−2 gates and lowers its depth by one.The merged gates act on the same consecutive qubits and use the sum of their angles.Source: A. Data loaders and distance estimation · p. 6

1. Algorithm and software development

The classifier fits class centroids classically, then predicts by estimating distances from each test point to each centroid. Its software implements this workflow alongside a scikit-learn version.

1. Algorithm and software development

  • Model fitting computes each class centroid as the average of its labeled training points, a one-time offline classical cost.Source: §1 · p. 7
  • Prediction estimates each test point’s distance to every centroid and assigns the label of the nearest one using the quantum distance estimator.Source: §1 · p. 7
  • The software provides quantum and scikit-learn Nearest Centroid implementations, with prediction calling distance estimation for each point-centroid pair.The estimated Euclidean distances determine the assigned nearest-centroid label.Source: §1 · p. 7
  • Estimating distances to centroids in superposition is proposed as a faster alternative that would require more qubits.Source: §1 · p. 7

2. Runtime and Scalability

The section analyzes Nearest Centroid runtime in terms of data dimension, dataset size, and distance-estimation accuracy. Its quantum advantage is tied to distance estimation, but the authors do not claim a present or near-term speedup over classical methods.

2. Runtime and Scalability

  • The authors present Nearest Centroid as a benchmark because its quantum behavior and runtime scaling with data dimension and dataset size are understood.They explicitly do not claim the procedure is faster than the classical one now or in the very near future.Source: §2 · pp. 7–8
  • Distance estimation uses a circuit of depth 2 log d and requires Ns = O(1/ϵ^2) repetitions; amplitude estimation could reduce the time to O(log d/ϵ).The authors report that distance accuracy of 0.1 for most points and 0.03 for a few difficult points sufficed, including for 784-dimensional MNIST.Source: §2 · p. 7
  • Distance estimation is the source of the quantum advantage, and its accuracy requirement depends on how separable points are from their centroids.The authors say the required accuracy does not really depend on dataset dimension and expect shot counts not to change significantly as problem sizes scale up.Source: §2 · p. 7
  • The quantum running time is O(kd + nd + kn log(d/ϵ)), versus O(nkd) for the basic classical Nearest Centroid algorithm.The quantum circuits use d qubits; the quantum cost includes one-off centroid and data preprocessing followed by distance estimation and label assignment.Source: §2 · pp. 7–8

A. Trapped ion quantum computer

The experiment uses a commercially available 11-qubit trapped-ion processor. Its ion chain is optically initialized, and the device's gate operations and calibrations are described.

A. Trapped ion quantum computer

1. Implementation of the circuits on the ionQ processor

The circuits are adapted to the IonQ hardware by using a modified RBS gate. This mapping leaves the distance-estimation circuit unchanged and is evaluated in 4- and 8-qubit versions.

1. Implementation of the circuits on the ionQ processor

  • The hardware mapping replaces RBS(θ) with a modified gate, iRBS(θ), while leaving the distance-estimation circuit unchanged.Source: §1 · p. 8
  • The iRBS(θ) gate is implemented with the Fig. 7 circuit, decomposing it into CNOT gates realizable with native Molmer Sorensen gates and single-qubit rotations.Source: §1 · p. 8
  • The 4-qubit circuits use 12 TQG, while the 8-qubit circuits use 30 TQG.Source: §1 · p. 8

B. Experimental Results

Experiments evaluate quantum Nearest Centroid classification on synthetic, Iris, and down-scaled MNIST data against classical labels or accuracy. Results include 100% accuracy on selected synthetic and binary-MNIST tasks, and near-classical accuracy on ten-class MNIST.

Experimental method

  • To estimate the desired output probability on noisy hardware, the unmitigated method measures the first qubit, while mitigation measures all qubits and discards outcomes outside the unary basis.The mitigated estimate divides counts of |10..0⟩ by the retained unary-basis outcomes; the unmitigated estimate divides first-qubit 1 counts by all circuit runs.Source: B. Experimental Results · pp. 8–9

Synthetic data

  • Synthetic data reached 100% accuracy for two classes at 4D/100 shots without mitigation and 8D/1,000 shots with mitigation; four-class accuracies were 97.5% (4D) and 90% (8D).The generated clusters could overlap, and the benchmark was agreement with classical labels; operation noise can shift assignments through distance-estimation error.Source: B. Experimental Results · pp. 9–10, Figure 8 · p. 9

Distance estimation

  • Experimental distance estimates could differ significantly from simulated distances, but small error bars on their ratio supported high classification accuracy because the distance ratios matter.The authors note that estimating meaningful classification-accuracy error bars would require an impractical number of experiments.Source: B. Experimental Results · p. 10

Iris dataset

  • On 150 four-dimensional Iris points, classical accuracy was around 92.7%, versus 84% quantum accuracy with mitigation at 500 shots; beyond 500 shots, systematic calibration noise dominated.Figure 10 compares classifications before and after mitigation; the prose reports that mitigation moves some points near the midpoint between centroids to the right class.Source: Figure 9 · p. 10, Figure 10 · p. 10, B. Experimental Results · p. 11

Datasets

  • MNIST images were projected from 784 to 8 dimensions with PCA, reducing both algorithms’ accuracy; Iris has three classes and four features, making it a nontrivial Nearest Centroid benchmark.The Iris data comprise 150 flower samples, with 50 samples in each class; the dataset is not easily classified into all three classes by Nearest Centroid without preprocessing.Source: B. Experimental Results · pp. 10–11

C. Noise model and Scaling of Error Mitigation

The noise model predicts that shallow, logarithmic-depth circuits limit encoding-subspace error, while post-selection can mitigate depolarizing error above a gate-fidelity threshold. Experiments support the model, but sample costs and statistical uncertainty constrain distance estimates, especially for nearly equidistant points.

Noise scaling

  • Per-layer error is bounded by 2Γ, so logarithmic circuit depth yields overall accuracy (1 − Γ)^O(log(n)).For 1024-dimensional data, the authors estimate that distance error 10^-2 requires XX-gate fidelity of order 10^-3, rather than 10^-5 if error grew with gate count.Source: C. Noise model and Scaling of Error… · p. 12

Error mitigation

  • Post-selection becomes more effective against depolarizing error as n increases when two-qubit gate fidelity exceeds 85.8%.The authors derive the condition 2f^4.5 ≫ 1 and state that the post-selected overlap c approaches |a1Γ|² as n increases.Source: C. Noise model and Scaling of Error… · p. 12

Experimental check

Distance estimation

  • Correcting all centroid distances in the same way preserves the classification label, although applications such as matrix-vector multiplication may require accurate distances.The reported focus is classification accuracy, which is robust to errors shared across distances to all centroids.Source: C. Noise model and Scaling of Error… · pp. 12–13

Sampling costs

  • After post-selection, sufficient ideal-density-matrix samples increase exponentially with qubit count, though the authors expect a very small coefficient with lower depolarizing error.They identify encoding-subspace error as the main remaining source, growing only logarithmically with n.Source: C. Noise model and Scaling of Error… · p. 13

Statistical error

  • Statistical distance error scales as 1/√NS, making extra measurements most useful for points nearly equidistant from multiple clusters.The authors propose adaptive runs and amplitude estimation as possible ways to reduce sample needs, but did not perform such optimizations because their run count remained small.Source: C. Noise model and Scaling of Error… · p. 13

IV. DISCUSSION

The paper reports quantum nearest-centroid classification on IonQ’s 11-qubit hardware, matching classical accuracy on down-scaled MNIST and reaching 100% in many synthetic cases. It argues that shallow circuits, noise tolerance, and classification’s limited-precision needs make the approach applicable to NISQ machines.

IV. DISCUSSION

  • MNIST classification across all 10 digits at 8 dimensions matched classical nearest-centroid accuracy, while many synthetic cases reached 100%.The authors state that, to their knowledge, these results had not previously been achieved on quantum hardware with a quantum classification algorithm.Source: §IV · p. 13
  • The authors argue that shallow circuits tolerant to certain noise levels support scalability and applicability to NISQ machines.Classification requires comparing centroid distances, not measuring every distance to high accuracy.Source: §IV · p. 13
  • Unary encoding uses one qubit per feature, but its error grows with logarithmic circuit depth rather than qubit or gate count.The authors say this motivates optimism for the next generation of higher-qubit-count computers; matching classical accuracy on higher-dimensional data is a projection, not an experimental result here.Source: §IV · p. 13
  • The work develops a model of how experimental error affects algorithmic accuracy and calls for further research on real-hardware algorithm performance and benchmarks.Source: §IV · p. 13
  • The authors frame the result as evidence that joint algorithm and hardware development can advance quantum-computer capabilities, while real-world quantum machine-learning applications remain an open question.Source: §IV · p. 13
Loading 2012.04145v2…