Beyond Classical Limits: A Deep Dive into Quantum Vector Search

9 min readMar 24, 2024

Quantum computing marks a significant shift in computational power, especially evident in search algorithms like Grover’s algorithm. This blog posts dives into implementing quantum vector search, by looking into the encoding process, oracle creation, and the mechanics of Grover’s algorithm within the scope of current quantum technologies and its limitations.

Quantum Computing Fundamentals

Quantum computing uses qubits to perform calculations. Unlike classical bits, qubits can be in multiple states at once (superposition) and be linked (entanglement), providing quantum computers a computational edge.

Grover’s Algorithm: The Quantum Search Revolution

Grover’s algorithm, a cornerstone of quantum computing, offers an efficient way to search through unsorted databases, significantly outpacing traditional algorithms.

Grover’s algorithm optimizes search tasks in unstructured databases by quadratically reducing the number of steps to find a target item, demonstrating quantum computing’s potential to outperform traditional methods.

At its core, Grover’s algorithm leverages the principles of superposition and interference to find a target item within an unstructured database with remarkable efficiency.

How Grover’s Algorithm Works

Grover’s algorithm can be broken down into several key steps:

Initialisation: The algorithm starts by initializing all qubits in a superposition state, equally representing all possible states (or database entries) simultaneously. This setup exploits quantum parallelism, allowing the algorithm to “check” all entries in parallel.
Oracle Application: An oracle, a black-box quantum operation, is applied to the system. The oracle knows which item(s) are the search targets and marks them by inverting their phase. To an observer, nothing appears to change, but quantum mechanically, the target states are now different from the rest.
Amplitude Amplification (Diffusion Operator): After marking the target state(s), Grover’s algorithm employs a diffusion operator that amplifies the probability amplitude of the marked states. This step essentially increases the likelihood that a measurement will collapse the system into one of the target states. The operator works by inverting the amplitudes about their average, which effectively boosts the marked states’ amplitudes while diminishing the others.
Measurement: Finally, measuring the state of the qubits collapses the superposition to one of the basis states. Due to the preceding amplification, the probability is significantly skewed towards the target states, making the algorithm incredibly efficient at finding the desired item.

Just Asking Questions

Can we leverage Grover’s algorithm for Vector Search?

Yes, vector search can be adapted to leverage Grover’s quantum search algorithm under certain conditions.

For vector search, which typically involves finding the closest or most similar vectors to a given query vector in a dataset, there are a few considerations and adaptations needed:

Quantisation of the Search Space: To apply Grover’s algorithm, the search space needs to be quantized, meaning that the vector space is discretized into a finite set of states that can be represented on a quantum computer. This involves encoding the vectors into quantum states.
Defining the Oracle: Grover’s algorithm requires an “oracle” function that can identify the target state(s). For vector search, this oracle function needs to encapsulate the criteria for vector similarity or closeness, such as distance metrics (e.g., Euclidean distance) or similarity metrics (e.g., cosine similarity). The oracle function marks the states (vectors) that are close to the query vector according to the chosen metric.
Post-Processing: After running Grover’s algorithm, the output quantum state(s) corresponding to the vectors closest to the query vector are measured. These measurements then need to be decoded back into classical information to identify the corresponding vectors in the dataset.

Implementing Quantum Vector Search e2e

Encoding Challenge

Quantization involves mapping the classical data vectors into a finite set of quantum states that can be manipulated by a quantum computer. This process is crucial because quantum computers operate on qubits that represent quantum states, not classical data directly.

There are several methods to encode classical data into quantum states. Two common approaches are amplitude encoding and basis encoding.

Amplitude encoding represents data vectors as amplitudes of a quantum state, allowing a compact representation of the data. However, it requires complex quantum operations to prepare the state.

Basis encoding, on the other hand, represents data by mapping it directly onto the basis states of qubits. For example, a classical binary string 1010 would be directly represented by the corresponding quantum state ∣1010⟩. While simpler in terms of preparation, basis encoding requires as many qubits as there are elements in the binary representation, making it less efficient for representing large or high-dimensional data sets compared to amplitude encoding.

Encoding classical vectors into quantum states for processing is our starting point. We will go with amplitude encoding. For a vector v of N dimensions, amplitude encoding can represent v using log2(N) qubits, with each amplitude corresponding to a component of the vector — efficient in terms of qubit usage but requiring complex state preparation circuits.

Given that this step is complicated by the need to scale quantum resources with vector dimensionality and the constraints of current quantum simulation capabilities, we’ll work with a simplified, conceptual example. We’ll represent our “vectors” as quantum states in a 2-qubit system, which naturally limits us to a search space of 4 states (|00⟩, |01⟩, |10⟩, and |11⟩).

In a real-world application, encoding and preparation techniques would need to address dimensionality and normalization constraints.

from qiskit import QuantumCircuit

def encode_search_space(circuit, qubits):
    """
    Prepares an equal superposition of all states to represent the search space.
    This encoding assumes a uniform distribution over the search space.
    """
    circuit.h(qubits)

Oracle Function

In quantum computing, the design of the oracle function is crucial for implementing Grover’s Algorithm effectively. The oracle’s role is to mark the states that satisfy a particular condition, which, in the context of vector search, often relates to identifying vectors close to a target vector based on a certain metric or similarity measure. The complexity and practicality of the oracle depend heavily on the problem at hand and the chosen metric for “closeness” or similarity.

Distance Metrics: The oracle function needs to implement a criterion for “closeness” based on distance or similarity metrics. For instance, it might compute the Euclidean distance or cosine similarity between the encoded quantum state of the database vectors and the query vector. This involves quantum circuits that can calculate these metrics within the quantum framework.
Implementation: Building an oracle that computes distances or similarities in a quantum circuit requires innovative quantum algorithms to approximate classical computations. For example, the “Swap Test” is a quantum procedure that estimates the overlap between two quantum states. The oracle can use a series of swap tests and ancillary qubits to compute an approximation of the cosine similarity and mark states accordingly.

Conceptual Overview:

Prepare Quantum States: Encode the two vectors a⃗ and b⃗ into quantum states ∣a⟩ and ∣b⟩ using amplitude encoding.
Swap Test: Apply the Swap Test to the prepared states to estimate their overlap. The Swap Test involves an ancilla qubit and controlled-swap (Fredkin) operations between the states ∣a⟩ and ∣b⟩.
Measure Ancilla Qubit: The probability of measuring the ancilla qubit in the state ∣0⟩∣0⟩ gives an estimate of the overlap, from which the cosine similarity can be inferred.

These pseudocode example provides a foundation of conceptual implementation of an effective oracle which differentiate between target and non-target vectors.

def oracle(circuit, control_qubits):
    """
    Oracle that marks the target state by applying a phase flip.
    Example: Marks the |11> state as the target.
    """
    circuit.cz(control_qubits[0], control_qubits[1])  # This example marks |11>

Grover’s Diffusion Operator

The diffusion operator is a crucial component of Grover’s algorithm, serving as the engine for amplitude amplification, which is the process that increases the probability of finding the target vector.

Functionality: After the oracle marks the target vector by inverting its phase, the diffusion operator works to amplify this difference. It does so by first applying a Hadamard transform to all qubits, inverting the amplitudes about their average, and then applying another Hadamard transform. The effect is to increase the amplitude of the target state(s) while decreasing the amplitude of all other states.
Impact on Vector Search: In vector search, where each quantum state can represent a high-dimensional vector, the diffusion operator ensures that even subtle distinctions marked by the oracle are amplified. This amplification is crucial for effectively searching through a dataset where the target vector might only slightly differ from non-target vectors.

def diffusion_operator(circuit, qubits):
    """
    Implements Grover's diffusion operator for amplifying the probability amplitude of the marked state.
    """
    circuit.h(qubits)
    circuit.z(qubits)
    circuit.cz(qubits[0], qubits[1])  # Adds a phase flip if both qubits are 1
    circuit.h(qubits)

Optimal Iteration Calculation

Determining the right number of Grover’s algorithm iterations is essential for maximizing search efficiency, balancing the amplification process to avoid under or over-execution.

The optimal number of iterations depends on the size of the dataset and the number of target vectors. Generally, it’s approximately square root of N, where N is the total number of vectors. For a single target vector, this optimal point ensures the probability of measuring the target state is maximized.

Striking the right number of iterations is crucial.

Too Few Iterations: The algorithm might not amplify the target vector’s amplitude sufficiently, making it hard to distinguish from non-target vectors.
Too Many Iterations: Exceeding the optimal iteration count can lead to amplitude overshooting. The search efficiency diminishes as the amplitudes begin to oscillate, possibly making non-target vectors more probable upon measurement than the target vector.

Adjusting the number of iterations allows the algorithm to maintain its robustness and effectiveness.

import numpy as np

def optimal_iterations(num_items):
    """
    Estimates the optimal number of Grover iterations based on the total number of items in the search space.
    """
    return int(np.round(np.pi / 4 * np.sqrt(num_items)))

Now, let’s create a simple test scenario where we have a small search space, making it feasible to run a full quantum simulation using Qiskit. We’ll simulate searching for a specific state in a 4-state system (2 qubits).

As we combine all the components above, our simulation involves encoding vectors into a quantum circuit, integrating a conceptually implemented oracle to mark the target vector, applying the diffusion operator, and executing the algorithm within the simulated environment.

from qiskit import Aer, execute, QuantumRegister, ClassicalRegister
from qiskit.visualization import plot_histogram

# Creating a quantum circuit with 2 qubits for the search space and 2 classical bits for measurement
qr = QuantumRegister(2)
cr = ClassicalRegister(2)
circuit = QuantumCircuit(qr, cr)

# Encoding the search space
encode_search_space(circuit, qr)

# Applying the oracle
oracle(circuit, qr)

# Applying Grover's diffusion operator the optimal number of times
num_items = 4  # With 2 qubits, our search space has 4 states
for _ in range(optimal_iterations(num_items)):
    diffusion_operator(circuit, qr)

# Measurement
circuit.measure(qr, cr)

# Execute the search
backend = Aer.get_backend('qasm_simulator')
result = execute(circuit, backend, shots=1024).result()
counts = result.get_counts(circuit)

# Visualize the results
plot_histogram(counts)

Expected Results and Analysis

The simulation should show the target vector’s state as significantly more probable, confirming Grover’s algorithm’s effectiveness in quantum search scenarios.

Yet, as we look further, it’s crucial to address the practical limitations, assumptions made, and scalability challenges present in applying quantum vector search to real-world problems.

Practical Limitations and Assumptions

High-Dimensional Data Encoding: The efficient encoding of high-dimensional vectors, for example 384 dimensional word embeddings into quantum states is a fundamental challenge. While amplitude encoding offers a compact representation, the complexity of preparing such states and the requirement for quantum resources scale logarithmically with the dimensionality of the vectors is practically challenging with current quantum technologies.
Oracle Design: The assumption that a perfect oracle exists to mark the target vector without error oversimplifies the challenges in real-world applications. Designing an oracle that can accurately identify complex patterns or similarities within vectors requires sophisticated quantum logic, potentially increasing the computational overhead and impacting the algorithm’s overall efficiency.
Noise and Error Rates: Current Noisy Intermediate-Scale Quantum (NISQ) devices are susceptible to errors and noise, which can significantly affect the algorithm’s performance.

The assumptions of ideal conditions in our exploration do not fully account for these practical limitations, which can diminish the probability amplification process and, consequently, the search success rate.

More Scalability Considerations

Quantum Hardware Evolution: The scalability of quantum vector search is closely tied to advancements in quantum hardware. As quantum processors become more capable, with increased qubit counts, longer coherence times, and reduced error rates, the practical application scope of quantum vector search will expand.
Algorithmic Optimizations: Further research into algorithmic optimizations and hybrid quantum-classical approaches may offer solutions to the current scalability and efficiency challenges. For instance, adapting the algorithm to work efficiently with partial or approximate solutions or exploring more efficient data encoding schemes can significantly impact the practicality of quantum vector search.

As we look into the possibilities offered by quantum computing for vector search and beyond, it’s clear that both challenges and opportunities are present. By acknowledging the practical limitations and scalability challenges, we ground our exploration to the scope of current research and quantum computing capabilities while looking forward to the breakthroughs ahead.

Must-Reads for Quantum Enthusiasts

Nielsen, M.A., & Chuang, I.L. (2010). Quantum Computation and Quantum Information.
Grover, L.K. (1997). Quantum Mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79(2), 325.
Schuld, M., Sinayskiy, I., & Petruccione, F. (2015). An introduction to quantum machine learning. Contemporary Physics, 56(2), 172–185.
Farhi, E., & Gutmann, S. (1998). Analog analogue of a digital quantum computation. Physical Review A, 57(4), 2403–2406.
Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. Quantum, 2, 79.