Source-linked AI summary
Implementing a distance-based classifier with a quantum interference circuit
Maria Schuld, Mark Fingerhuth, Francesco Petruccione
TL;DR
Estimating a quantum classifier’s prediction probability requires controlling sampling error, especially across different sample sizes. The paper analyzes confidence-interval estimators for this setting and reports that a refined estimator yields runtime scaling of O(ϵ^-1).
Problem
The paper addresses how to estimate prediction error and confidence intervals for a probabilistic quantum classification result as the sample size changes.
Method
It estimates the class probability by repeated sampling and compares the Wald interval with the more refined Wilson score estimator.
Results
O(ϵ^-1) runtime scaling is predicted when using the refined estimation procedure.
Takeaways & Limitations
The refined confidence-interval estimator provides a lower predicted repetition-growth rate for estimating the classifier’s error.
Abstract
from arXiv · showhide
Lately, much attention has been given to quantum algorithms that solve pattern recognition tasks in machine learning. Many of these quantum machine learning algorithms try to implement classical models on large-scale universal quantum computers that have access to non-trivial subroutines such as Hamiltonian simulation, amplitude amplification and phase estimation. We approach the problem from the opposite direction and analyse a distance-based classifier that is realised by a simple quantum interference circuit. After state preparation, the circuit only consists of a Hadamard gate as well as two single-qubit measurements, and computes the distance between data points in quantum parallel. We demonstrate the proof-of-principle using the IBM Quantum Experience and analyse the performance of the classifier with numerical simulations, showing that it classifies surprisingly well for simple benchmark tasks.
Appendix A: Estimating the prediction error with confidence intervals
The appendix estimates classification prediction error from repeated Bernoulli outcomes and confidence intervals. It contrasts the Wald interval’s O(ϵ^-2) repetition scaling with a Wilson-score estimate that predicts O(ϵ^-1) runtime while addressing failures at small samples or extreme probabilities.
- Estimating prediction error: The classifier estimates p by repeating the algorithm R times and averaging binary class-qubit outcomes.The outcomes are sampled from a Bernoulli random variable Q with expectation E[Q] = p.
- Estimating prediction error: Classification returns 1 when p̂ > 0.5 and −1 when p̂ < 0.5.The appendix seeks to quantify how estimation error ϵ decreases with sample size R at a high confidence level.
- Wald interval: 2.58 corresponds to a 99% confidence level for the confidence intervals around the estimator.The Wald interval is described as suited to large R and p ≈ 0.5, conditions expected for the classifier.
- Wald interval: O(ϵ^-2) is the repetition scaling required by the Wald-based error estimate.This counts repetitions of the classification algorithm, including state preparation.
- Wilson score interval: Small R or p near zero or one can make the Wald estimation fail severely, motivating the Wilson-score alternative.The Wilson score provides a more refined estimator for p in these regimes.
- Wilson score interval: O(ϵ^-1) is the runtime scaling predicted by the more refined Wilson-score estimation.The appendix presents this as an improvement over the less refined estimation.
Appendix B: Details on the experiment with the IBM Quantum Experience
The IBM Quantum Experience implementation is constrained by gate and measurement errors, decoherence, and limited qubit connectivity. The classifier circuit maps its controlled operations onto the processor’s specific five-qubit arrangement.
- Hardware constraints: 83 ns single-qubit gates and maximally 483 ns CNOT gates characterize the IBM processor’s operation times.The processor uses five qubits arranged with cross-resonance interactions.
- Hardware constraints: 3.3 × 10−3 single-qubit error and 6.4 × 10−2 single-qubit measurement error limit the current hardware setup.These values are reported as the maximum errors for single-qubit operations and measurements, respectively.
- Hardware constraints: 80 quantum operations per qubit enable 79 quantum gates and one measurement under the device’s error and decoherence constraints.The operation budget follows from the reported qubit errors and decoherence times.
- Circuit implementation: The classification circuit uses ancilla, index, data, and class qubits, but IBMQЕ’s limited CNOT connectivity requires mapping operations to the processor arrangement.The data qubit |i⟩ is the most frequently used target for controlled operations.