Distance-Based Classifier with Quantum Interference Circuit - Paper Implementation

[Vanshaj0429]

Paper Implementation: Distance-Based Classifier with Quantum Interference Circuit

Paper Information

• Title: Implementing a distance-based classifier with a quantum interference circuit
• Authors: Maria Schuld, Mark Fingerhuth, Francesco Petruccione
• arXiv: 1703.10793
• Year: 2017

Problem Statement

This paper presents a novel approach to quantum machine learning by implementing a distance-based binary classifier using a minimal quantum circuit. Unlike other proposals that adapt classical algorithms to quantum computers, this work takes the opposite approach: starting with the simplest possible quantum circuit and developing a classifier around it. The classifier uses quantum interference to compute distances between data points in parallel.

Significance

1. The paper demonstrates a practical quantum ML algorithm implementable on near-term quantum devices with minimal resources.
2. The classifier was experimentally validated on IBM's 5-qubit quantum computer using the Iris dataset.
3. It shows surprisingly good classification performance on benchmark tasks despite its simplicity.
4. This implementation could serve as a building block for more complex quantum machine learning systems.

Technical Details

The quantum classifier implements the following binary classification formula:

ỹ = sgn(∑ᵐ yᵐ[1 - (1/4M)|x̃ - xᵐ|²])

where:

• x̃ is the new input to classify
• xᵐ are the training inputs
• yᵐ are the corresponding training labels
• M is the number of training examples

The kernel function κ(x,x') = 1 - (1/4M)|x-x'|² measures similarity between data points.

The quantum implementation requires:

• State preparation: Encoding feature vectors into quantum states
• A quantum circuit with only a Hadamard gate and two measurements
• Post-processing of measurement results

Implementation Plan

Phase 1: Classical Pre-processing

1. Implement the standardization and normalization of feature vectors
   • Standardize data to zero mean, unit variance
   • Normalize each vector to unit length
2. Prepare the Iris dataset as used in the paper's experimental demonstration

Phase 2: Core Quantum Circuit Implementation

1. Implement the state preparation routine
   • Create function to encode feature vectors in quantum states
   • Implement the full state preparation as shown in Figure 3 of the paper
2. Build the interference circuit
   • Create the basic 4-qubit circuit (ancilla, index, data, and class qubits)
   • Implement the Hadamard operation and measurement scheme

Phase 3: Classiq-Specific Implementation

1. Leverage Classiq's high-level quantum programming features
   • Implement the circuit using Classiq's functional modeling approach
   • Optimize the circuit for the Classiq platform
2. Create utility functions for:
   • Calculating rotation angles for amplitude encoding
   • Processing measurement results to make classification decisions
   • Evaluating classification performance

Phase 4: Testing and Analysis

1. Reproduce the Iris dataset experiment from the paper
   • Replicate the specific experiment with Iris samples 28, 33, 36, and 85
   • Compare with the original results from IBM's quantum computer
2. Evaluate performance metrics
   • Classification accuracy on the Iris dataset
   • Resource requirements and circuit depth
3. Compare with classical implementation of the same algorithm

Deliverables

1. Complete implementation of the quantum distance-based classifier in Classiq
2. Jupyter notebook with:
   • Step-by-step implementation walkthrough
   • Visualizations of data preprocessing
   • Circuit diagrams and explanations
   • Experimental results from the Iris dataset classification
3. Documentation explaining:
   • The theoretical foundation
   • Implementation details
   • Performance analysis

Expected Challenges

1. Efficient amplitude encoding for the feature vectors
2. Optimizing the circuit for Classiq's architecture
3. Handling the postselection step in the algorithm

Relevance to Classiq

This implementation will showcase Classiq's ability to:

1. Build practical quantum machine learning models
2. Implement circuits with precise amplitude encoding
3. Create reusable quantum modules for machine learning
4. Optimize quantum circuits for classification tasks

The minimal resource requirements make this an ideal candidate for early quantum advantage demonstrations, while the performance on real datasets makes it practically relevant.

Timeline

• Week 1: Classical pre-processing and understanding the algorithm
• Week 2: Core quantum circuit implementation in Classiq
• Week 3: Testing and analysis
• Week 4: Documentation and refinement

Possible Extensions

The paper mentions several promising extensions that could be implemented as future enhancements to this core implementation:

1. Polynomial Feature Map: The authors demonstrate that using two copies of each quantum state allows implementation of a polynomial feature map, which can significantly improve classification performance for non-linearly separable datasets (e.g., improving accuracy from 93% to 100% for Iris classes 2 and 3, and enabling classification of concentric circles).

2. Alternative Kernel Functions: Modifying the circuit to realize different kernel functions that allow for more localized distance measures could increase the power and flexibility of the classifier.

3. Entanglement-Based Enhancements: The paper suggests considering circuits that make more use of quantum resources such as entanglement.

These extensions could be considered after successfully implementing the core algorithm.

References

1. Schuld, M., Fingerhuth, M., & Petruccione, F. (2017). Implementing a distance-based classifier with a quantum interference circuit. arXiv:1703.10793
2. IBM Quantum Experience - Used in the original paper implementation

[TomerGoldfriend]

Thank you @Vanshaj0429 , sounds interesting. From a quick look it seems like this implementation depends on some efficient state preparation of the data. Is it clear how to perform this quantum block? (you have mentioned figure 3 in the paper, but it seems related to the classifier, rather than to the state preparation).

[Vanshaj0429]

Thank you @TomerGoldfriend for your comment! You've identified a critical aspect of the implementation. The state preparation is indeed a significant part of this quantum classification algorithm.

To clarify: Figure 3 in the paper shows the complete circuit including both state preparation (steps A-E) and the classifier operations (step F). The state preparation specifically creates the quantum state described in Equation 2 of the paper.

This preparation involves encoding feature vectors into amplitude distributions using controlled rotation gates. For the 2D Iris dataset example, this is implemented with specific Ry rotations as shown in the detailed circuit.

The state preparation works as follows:

1. Initialize ancilla and index qubits in superposition (step A)
2. Encode the new input vector in amplitudes, entangled with |0⟩ state of ancilla (step B)
3. Encode training vectors in amplitudes, entangled with |1⟩ state of ancilla and respective index states (steps C & D)
4. Encode class labels by conditionally flipping the class qubit (step E)

You're right that state preparation is a challenge in this implementation. The authors mention that for larger datasets, efficient state preparation routines like QRAM would be needed, but the approach would follow the same principle.

[TomerGoldfriend]

OK @Vanshaj0429 I think I get it.
Please note that we accept high-quality implementations to our repository and will be glad to accept a contribution that meets our standards.
Feel free to reach out to the community for any questions!

Good luck!