PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum machine learning for quantum anomaly detection

Nana Liu, Patrick Rebentrost

arXiv:1710.07405v1quant-ph

TL;DR

Detecting outliers in quantum states is a potential need as quantum technologies develop. This paper presents quantum versions of kernel PCA and one-class SVM for anomaly detection, with resource use logarithmic in state dimension and, for pure states, training-set size.

  • Problem

    Anomaly detection identifies outliers when training data describe normal patterns; the paper considers this task for quantum states, including outliers from faulty quantum devices.

    Source: §I · p. 1

  • Method

    The paper presents quantum kernel PCA and one-class SVM algorithms that detect outliers in quantum states supplied as training and test data.

    Source: §I · p. 1

  • Results

    Resources scale logarithmically in both training-state number M and dimension d for pure states, and logarithmically in d for mixed states.

    Source: §I · p. 1, §IV · p. 6, §V · p. 7

  • Takeaways & Limitations

    The algorithms may find applications in identifying novel quantum phenomena and in secure quantum data transfer, computation, and cloud verification.

    Source: §V · p. 7

Abstract

from arXiv · show

Anomaly detection is used for identifying data that deviate from `normal' data patterns. Its usage on classical data finds diverse applications in many important areas like fraud detection, medical diagnoses, data cleaning and surveillance. With the advent of quantum technologies, anomaly detection of quantum data, in the form of quantum states, may become an important component of quantum applications. Machine learning algorithms are playing pivotal roles in anomaly detection using classical data. Two widely-used algorithms are kernel principal component analysis and one-class support vector machine. We find corresponding quantum algorithms to detect anomalies in quantum states. We show that these two quantum algorithms can be performed using resources logarithmic in the dimensionality of quantum states. For pure quantum states, these resources can also be logarithmic in the number of quantum states used for training the machine learning algorithm. This makes these algorithms potentially applicable to big quantum data applications.

I. Introduction

The paper asks whether anomaly detection can operate directly on quantum states without first reconstructing their classical descriptions through costly state tomography. It develops quantum counterparts of kernel PCA and one-class SVM for detecting outliers among quantum states, building on classical methods that learn from normal data.

I. Introduction

  • Quantum anomaly detection targets outliers among quantum states, where classical-description methods require state tomography and many measurements.The paper frames this as relevant to quantum computation, simulation, communication, and potentially cloud or quantum-internet settings.Source: §I · p. 1

II. Anomaly detection in classical machine learning

  • Semi-supervised methods fit settings where normal training examples are available but anomalous examples are too scarce to form a training set.The paper focuses on point anomalies, rather than contextual or collective anomalies, which it leaves for future work.Source: §II · p. 2

A. Kernel PCA

  • Kernel PCA scores a datum by comparing its distance from the training centroid with training-data variance along that direction.A larger proximity measure indicates a more anomalous datum; kernelization also permits nonlinear feature spaces.Source: A. Kernel PCA · p. 2

B. One-class SVM

  • One-class SVM characterizes training data with a hyperplane that maximizes its distance from the feature-space origin while minimizing squared data-to-hyperplane distances.The paper uses the restricted setting r = c = 1, which is stated to preserve the ordering when only relative distances matter.Source: B. One-class SVM · pp. 2–3

III. Pure state anomaly detection

For pure quantum states, the paper adapts kernel PCA to score a test state against normal training states. The protocol estimates the score from state inner products, with the described implementation scaling polynomially in M and log d.

III. Pure state anomaly detection

  • The pure-state setup assumes access to training-state preparation unitaries, a control unitary, and a preparation unitary for the test state.Multiple identical state copies are required, reflecting the no-cloning constraint.Source: §III · p. 3

1. Algorithm using resources logarithmic in d

  • The quantum kernel-PCA proximity measure quantifies how anomalous a test state is relative to the training states and is bounded between 0 and 1.The centered-state normalization has an O(log M) resource method.Source: §1 · pp. 3–4
  • The direct protocol computes the proximity measure using O(poly(M log d)) resources by estimating the required inner products with modified swap tests.The tests estimate real and imaginary components; O(poly(log d)) measurements suffice per test when an error of order O(1/log d) is accepted.Source: §1 · p. 4

2. Algorithm using resources logarithmic in d and M

The paper gives an alternative pure-state kernel-PCA protocol that targets logarithmic dependence on the training-set size by preparing a superposition of centered data. It also sets out quantum one-class SVM methods based on fidelity kernels and matrix inversion.

2. Algorithm using resources logarithmic in d and M

  • Preparing a superposition of centered data yields an alternative kernel-PCA protocol for computing the proximity measure using O(log M) resources.The score is measured with a swap test using copies of the centered test state and the covariance matrix.Source: §2 · p. 4

B. Quantum one-class SVM (pure state)

  • For pure-state one-class SVM, the kernel matrix uses fidelity values |⟨ψi|ψj⟩|^2 and can be normalized as a density matrix.Its positive-semidefinite property follows from representing the kernel as an inner product of a feature map.Source: B. Quantum one-class SVM (pure state) · p. 4
  • The one-class SVM approach first computes its proximity measure with a swap test using resources logarithmic in dimension, then presents a matrix-inversion approach potentially logarithmic in dimension and training-set size.The latter approach relies on a quantum matrix inversion algorithm.Source: B. Quantum one-class SVM (pure state) · p. 4

1. Algorithm using resources logarithmic in d

The paper contrasts a protocol that avoids the controlled training-state unitary but retains polynomial dependence on the training-set size with one that uses that unitary for a logarithmic-size matrix-inversion approach. In the latter, the overlap measurement cost can be logarithmic in M and d when error of order O(1/log(Md)) is accepted.

1. Algorithm using resources logarithmic in d

  • Without access to U_C, pairwise swap tests and classical matrix inversion compute the proximity measure with O(M^2 log d) resources for all pairs and O(M^3) inversion cost.This protocol uses only the state-preparation unitaries {U_i} and U_0, but does not achieve O(log M) resources.Source: §1 · p. 4

2. Algorithm using resources logarithmic in d and M

  • With U_C, HHL can obtain the coefficient state |⃗α⟩ in O(log M) runtime, provided the kernel matrix can be efficiently exponentiated.The stated matrix-inversion conditions include a condition number at most O(log M), requiring 1/P_T ≲ O(log M).Source: §2 · p. 5
  • The kernel-matrix exponential is simulated using copies of a density matrix related to the kernel matrix through a modified quantum PCA method.The construction concatenates steps to approximate exp(−iKt) with error O(t^2/n) using 2n copies of K0.Source: §2 · p. 5
  • N_f ≲ 1/(4ε^2) and is O(log(Md)) when error of order O(1/log(Md)) is accepted.This bounds the measurements needed to estimate the real and imaginary parts of the overlap used in the proximity measure.Source: §2 · p. 6

IV. Mixed state anomaly detection

The paper extends anomaly detection to mixed quantum states, relevant when states contain unknown noise or are designed as mixtures. It proposes mixed-state similarity methods, while noting that scaling with the number of training states has unresolved requirements.

IV. Mixed state anomaly detection

  • Mixed-state anomaly detection addresses settings with unknown noise sources or quantum processes designed to output mixed states, such as NMR.The paper frames this as a generalization of pure-state anomaly detection.Source: §IV · p. 6
  • For mixed-state kernel PCA, the paper proposes an analogous similarity measure and an algorithm requiring O(log d) resources.The paper describes this as a mixed-state extension of the pure-state approach.Source: §IV · p. 6
  • A speedup in the number of mixed training states requires additional capabilities, including efficient preparation of multiple copies of a density matrix proportional to the kernel matrix.The paper says how to generate these copies with minimal assumptions is unclear; a simple experimental procedure for the proximity measure may also be needed.Source: §IV · p. 6

A. Quantum kernel PCA (mixed state)

The mixed-state kernel PCA method defines a similarity measure that recovers the pure-state proximity measure in the pure-state limit. It estimates the measure from mixed-state overlaps, with total resources scaling as O(poly(M log d)).

A. Quantum kernel PCA (mixed state)

  • The mixed-state proximity measure is constructed from analogues of the pure-state inner-product terms and reduces to the pure-state measure in the pure-state limit.The paper distinguishes its mixed-state inner product from tr(ρiρκ), which yields fidelity rather than the pure-state inner product.Source: A. Quantum kernel PCA (mixed state) · p. 7
  • The method estimates mixed-state inner products through quantum operations on an ancilla and the states, then uses an ancilla measurement to estimate the overlap.The probability of measuring the ancilla in |1⟩ after a Hadamard depends on the real part of the overlap.Source: A. Quantum kernel PCA (mixed state) · p. 7
  • O(poly(M log d)) resources suffice to compute the mixed-state proximity measure at error O(1/log d).The estimate uses O(poly(M)) overlap terms, with O(1/ϵ^2) measurements per term for precision ϵ.Source: A. Quantum kernel PCA (mixed state) · p. 7

B. Quantum one-class SVM (mixed state)

For mixed-state one-class SVM, the paper uses superfidelity as a kernel and describes a route to compute the classifier parameters. The discussion presents anomaly detection for pure and mixed states, while identifying other quantum anomaly-detection algorithms as unexplored.

B. Quantum one-class SVM (mixed state)

  • Superfidelity is used as a kernel for mixed-state one-class SVM because it obeys the properties of a kernel matrix and reduces to fidelity for pure states.The paper extends the pure-state proximity measure to mixed states using this kernel.Source: B. Quantum one-class SVM (mixed state) · p. 7
  • With O(poly(M) log d) resources for proximity computation, pairwise mixed-state swap tests cost about O(M^2 log d), and classical matrix inversion costs O(M^3).This approach no longer requires access to UC.Source: B. Quantum one-class SVM (mixed state) · p. 7

V. Discussion

  • The paper reports anomaly-detection algorithms for both pure and mixed states using resources logarithmic in state dimension, with pure-state resources also logarithmic in training-set size.It notes that many other machine-learning anomaly-detection algorithms remain unexplored for quantum data.Source: §V · p. 7

A. Generating centroid quantum state |ψc⟩

The appendix describes preparation of the centroid and centered quantum states used by the algorithms. The centroid procedure uses Hadamard gates and postselection, while centered-state preparation has success probability scaling as O(1) under the stated conditions.

A. Generating centroid quantum state |ψc⟩

  • Hadamard operations followed by projective measurement on the index register recover the centroid state |ψc⟩.The centroid preparation uses O(log M) Hadamard gates, and the procedure also recovers |Nc|^2 using O(log M) resources.Source: A. Generating centroid quantum state… · p. 8
  • When the covariance matrix is low rank and training states have similar, high-fidelity overlaps, the centroid-preparation success probability Pχ is O(1).The paper relates this condition to training samples belonging to a single type.Source: A. Generating centroid quantum state… · p. 8

B. Generating centered quantum states |zi⟩and |z0⟩

  • Preparing the centered states uses O(log M) Hadamard gates and state-preparation operations conditioned on the non-ancilla registers.The appendix describes these operations as part of generating |zi⟩ and |z0⟩.Source: B. Generating centered quantum states… · p. 8
  • The centered-state preparation succeeds with probability scaling as O(1), but |zi⟩ does not exist when all training states are exactly the same.The stated success-probability scaling follows an argument similar to the centroid preparation.Source: B. Generating centered quantum states… · p. 8

C. Generating state |χc⟩for kernel PCA

The preparation uses a superposition of labels with controlled state preparation and Hadamard operations. Measuring the label register in the all-zero state obtains the desired state, with gate resources scaling as O(log M).

C. Generating state |χc⟩for kernel PCA

D. Positive semi-definite kernel matrix K and fidelity measure

The appendix establishes kernel validity using positive-semidefinite criteria and a feature-map representation of the superfidelity. It also describes an efficiently simulatable Hamiltonian for applying a matrix element-wise product.

D. Positive semi-definite kernel matrix K and fidelity measure

  • A kernel is positive semidefinite when its training-set kernel matrix is positive semidefinite, equivalently when it has a feature-map inner-product representation.Source: D. Positive semi-definite kernel… · p. 9
  • The superfidelity is selected as the kernel, and its feature-map representation yields a valid positive kernel matrix.The passage notes that the matrix entries are real.Source: D. Positive semi-definite kernel… · p. 9

E. Hadamard product and transpose

F. Generating states |AR⟩and |AI⟩

The construction generates |AR⟩ using a control-unitary operation and ancilla measurement. An alternate initial state in the same construction generates |AI⟩.

F. Generating states |AR⟩and |AI⟩

Loading 1710.07405v1…