Status: Proposed Date: 2026-02-06 Authors: ruv.io, RuVector Team Deciders: Architecture Review Board
| Version | Date | Author | Changes |
|---|---|---|---|
| 0.1 | 2026-02-06 | ruv.io | Initial Grover's search architecture proposal |
Grover's algorithm is one of the foundational quantum algorithms, providing a provable quadratic speedup for unstructured search. Given a search space of N = 2^n items and an oracle that marks one or more target items, Grover's algorithm finds a target in O(sqrt(N)) oracle queries, compared to the classical O(N) lower bound.
The algorithm consists of two principal components applied repeatedly:
-
Oracle (O): Flips the phase of marked (target) states
- On hardware: requires multi-controlled-Z decomposition into elementary gates
- In simulation: can be a single O(1) amplitude flip (key insight)
-
Diffuser (D): Inversion about the mean amplitude (also called the Grover diffusion operator)
- D = 2|s><s| - I, where |s> is the uniform superposition
- Implemented as: H^{otimes n} * (2|0><0| - I) * H^{otimes n}
On real quantum hardware, the oracle must be decomposed into a circuit of elementary gates. For a single marked state in n qubits, the oracle requires O(n) multi-controlled gates, each of which may need further decomposition. The full gate count is O(n^2) or worse depending on connectivity.
In a state vector simulator, we have direct access to the amplitude array. The oracle for a known marked state at index t is simply:
amplitudes[t] *= -1
This is an O(1) operation, regardless of qubit count. This fundamentally changes the performance profile of Grover simulation.
| Application | Description |
|---|---|
| Vector DB search | Encode HNSW candidate filtering as a Grover oracle |
| SAT solving | Map boolean satisfiability to oracle function |
| Cryptographic analysis | Brute-force key search with quadratic speedup |
| Database queries | Unstructured search over ruVector memory entries |
| Algorithm benchmarking | Reference implementation for quantum advantage studies |
We provide two oracle modes: optimized index-based for known targets, and general unitary oracle for black-box functions.
When the target index is known (or the oracle can be expressed as a predicate on basis state indices), we bypass gate decomposition entirely:
impl QuantumState {
/// Apply Grover oracle by direct amplitude negation.
///
/// Flips the sign of amplitude at the given index.
/// This is an O(1) operation -- the key simulation advantage.
///
/// On hardware, this would require O(n) multi-controlled gates
/// decomposed into O(n^2) elementary gates.
#[inline]
pub fn oracle_flip(&mut self, target_index: usize) {
debug_assert!(target_index < self.amplitudes.len());
self.amplitudes[target_index] = -self.amplitudes[target_index];
}
/// Apply Grover oracle for multiple marked states.
///
/// Complexity: O(k) where k = number of marked states.
/// Hardware equivalent: O(k * n^2) gates.
pub fn oracle_flip_multi(&mut self, target_indices: &[usize]) {
for &idx in target_indices {
debug_assert!(idx < self.amplitudes.len());
self.amplitudes[idx] = -self.amplitudes[idx];
}
}
}Why this is valid: The oracle operator O is defined as the diagonal unitary
O = I - 2|t><t|, which maps |t> to -|t> and leaves all other basis states unchanged.
In the amplitude array, this is exactly amplitudes[t] *= -1. No physical gate
decomposition is needed because we are simulating the mathematical operator directly.
For black-box oracle functions where the marked states are not known in advance:
/// A general oracle as a unitary operation on the state vector.
///
/// The oracle function receives a basis state index and returns
/// true if it should be marked (phase-flipped).
pub trait GroverOracle: Send {
/// Evaluate whether basis state |index> is a target.
fn is_marked(&self, index: usize, n_qubits: usize) -> bool;
}
impl QuantumState {
/// Apply a general Grover oracle.
///
/// Iterates over all 2^n amplitudes, evaluating the oracle predicate.
/// Complexity: O(2^n) per application (equivalent to hardware cost).
pub fn oracle_apply(&mut self, oracle: &dyn GroverOracle) {
let n_qubits = self.n_qubits;
for i in 0..self.amplitudes.len() {
if oracle.is_marked(i, n_qubits) {
self.amplitudes[i] = -self.amplitudes[i];
}
}
}
}The Grover diffuser (inversion about the mean) is decomposed as:
D = H^{otimes n} * phase_flip(|0>) * H^{otimes n}
where phase_flip(|0>) flips the sign of the all-zeros state: (2|0><0| - I).
Diffuser Circuit Decomposition:
|psi> ──[H]──[phase_flip(0)]──[H]──
Expanded:
┌───┐ ┌──────────────┐ ┌───┐
q[0] ──┤ H ├───┤ ├───┤ H ├──
└───┘ │ │ └───┘
┌───┐ │ 2|0><0| - I │ ┌───┐
q[1] ──┤ H ├───┤ ├───┤ H ├──
└───┘ │ │ └───┘
┌───┐ │ │ ┌───┐
q[2] ──┤ H ├───┤ ├───┤ H ├──
└───┘ └──────────────┘ └───┘
Both the H^{otimes n} layers and the phase_flip(0) benefit from simulation optimizations:
impl QuantumState {
/// Apply Hadamard to all qubits.
///
/// Optimized implementation using butterfly structure.
/// Complexity: O(n * 2^n)
pub fn hadamard_all(&mut self) {
for qubit in 0..self.n_qubits {
self.apply_hadamard(qubit);
}
}
/// Flip the phase of the |0...0> state.
///
/// O(1) operation via direct indexing -- another simulation advantage.
/// On hardware, this requires an n-controlled-Z gate.
#[inline]
pub fn phase_flip_zero(&mut self) {
// |0...0> is at index 0
self.amplitudes[0] = -self.amplitudes[0];
}
/// Apply the full Grover diffuser.
///
/// D = H^n * (2|0><0| - I) * H^n
///
/// Implementation note: (2|0><0| - I) negates all states except |0>,
/// which is equivalent to a global phase of -1 followed by
/// flipping amplitude[0]. We use the phase_flip_zero + global negate
/// approach for efficiency.
pub fn grover_diffuser(&mut self) {
self.hadamard_all();
// Apply 2|0><0| - I:
// Negate all amplitudes, then flip sign of |0> again
// This gives: amp[0] -> amp[0], amp[k] -> -amp[k] for k != 0
for amp in self.amplitudes.iter_mut() {
*amp = -*amp;
}
self.amplitudes[0] = -self.amplitudes[0];
self.hadamard_all();
}
}The optimal number of Grover iterations for k marked states out of N = 2^n total:
iterations = floor(pi/4 * sqrt(N/k))
For a single marked state (k=1):
| Qubits (n) | N = 2^n | Optimal Iterations | Classical Steps |
|---|---|---|---|
| 4 | 16 | 3 | 16 |
| 8 | 256 | 12 | 256 |
| 12 | 4,096 | 50 | 4,096 |
| 16 | 65,536 | 201 | 65,536 |
| 20 | 1,048,576 | 804 | 1,048,576 |
/// Compute the optimal number of Grover iterations.
///
/// For k marked states in a search space of 2^n:
/// iterations = floor(pi/4 * sqrt(2^n / k))
pub fn optimal_iterations(n_qubits: usize, n_marked: usize) -> usize {
let n = (1_usize << n_qubits) as f64;
let k = n_marked as f64;
(std::f64::consts::FRAC_PI_4 * (n / k).sqrt()).floor() as usize
}/// Configuration for Grover's search.
pub struct GroverConfig {
/// Number of qubits
pub n_qubits: usize,
/// Target indices (for index-based oracle)
pub targets: Vec<usize>,
/// Custom oracle (overrides targets if set)
pub oracle: Option<Box<dyn GroverOracle>>,
/// Override iteration count (auto-computed if None)
pub iterations: Option<usize>,
/// Number of measurement shots (for probabilistic result)
pub shots: usize,
}
/// Result of Grover's search.
pub struct GroverResult {
/// Most likely measurement outcome (basis state index)
pub found_index: usize,
/// Probability of measuring the found state
pub success_probability: f64,
/// Number of Grover iterations performed
pub iterations: usize,
/// Total wall-clock time
pub elapsed: Duration,
/// Full probability distribution (optional, for analysis)
pub probabilities: Option<Vec<f64>>,
}Pseudocode for the complete algorithm:
pub fn grover_search(config: &GroverConfig) -> GroverResult {
let n = config.n_qubits;
let num_states = 1 << n;
// Step 1: Initialize uniform superposition
// |s> = H^n |0...0> = (1/sqrt(N)) * sum_k |k>
let mut state = QuantumState::new(n);
state.hadamard_all(); // O(n * 2^n)
// Step 2: Determine iteration count
let k = config.targets.len();
let iterations = config.iterations
.unwrap_or_else(|| optimal_iterations(n, k));
// Step 3: Apply Grover iterations
for _iter in 0..iterations {
// Oracle: flip phase of marked states
match &config.oracle {
Some(oracle) => state.oracle_apply(oracle.as_ref()),
None => state.oracle_flip_multi(&config.targets),
}
// Diffuser: inversion about the mean
state.grover_diffuser();
}
// Step 4: Measure (find highest-probability state)
let probabilities: Vec<f64> = state.amplitudes.iter()
.map(|a| a.norm_sqr())
.collect();
let found_index = probabilities.iter()
.enumerate()
.max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap())
.map(|(i, _)| i)
.unwrap();
GroverResult {
found_index,
success_probability: probabilities[found_index],
iterations,
elapsed: start.elapsed(),
probabilities: Some(probabilities),
}
}This section formalizes the performance advantage unique to state vector simulation.
Hardware cost model (per Grover iteration):
Oracle (hardware):
- Multi-controlled-Z gate: O(n) Toffoli gates
- Each Toffoli: ~6 CNOT + single-qubit gates
- Total: O(n) gates, each touching O(2^n) amplitudes in simulation
- Simulation cost: O(n * 2^n) per oracle application
Diffuser (hardware):
- H^n: n Hadamard gates = O(n * 2^n) simulation ops
- Multi-controlled-Z: same as oracle = O(n * 2^n) simulation ops
- H^n: O(n * 2^n) again
- Total: O(n * 2^n) per diffuser
Per iteration (hardware path): O(n * 2^n)
Total (hardware path): O(n * 2^n * sqrt(2^n)) = O(n * 2^(3n/2))
Simulation cost model (with O(1) oracle optimization):
Oracle (optimized):
- Direct amplitude flip: O(1) for single target, O(k) for k targets
- Simulation cost: O(k)
Diffuser (optimized):
- H^n: O(n * 2^n) -- unavoidable
- phase_flip(0): O(1) via direct index
- H^n: O(n * 2^n)
- Total: O(n * 2^n) per diffuser
Per iteration (optimized): O(n * 2^n) [dominated by diffuser]
Total (optimized): O(n * 2^n * sqrt(2^n)) = O(n * 2^(3n/2))
The asymptotic complexity is the same (diffuser dominates), but the constant factor improvement is significant: the oracle step drops from O(n * 2^n) to O(k), saving roughly 50% of per-iteration time for single-target search.
When multiple states are marked (k > 1), the algorithm converges faster:
iterations(k) = floor(pi/4 * sqrt(N/k))
The success probability oscillates sinusoidally. For k targets:
P(success after t iterations) = sin^2((2t+1) * arcsin(sqrt(k/N)))
/// Compute success probability after t Grover iterations.
pub fn success_probability(n_qubits: usize, n_marked: usize, iterations: usize) -> f64 {
let n = (1_usize << n_qubits) as f64;
let k = n_marked as f64;
let theta = (k / n).sqrt().asin();
let angle = (2.0 * iterations as f64 + 1.0) * theta;
angle.sin().powi(2)
}Over-iteration risk: If too many iterations are applied, the algorithm starts "uncomputing" the answer. The success probability oscillates with period ~pi * sqrt(N/k) / 2. Our implementation auto-computes the optimal count and warns if the user-specified count deviates significantly.
| Qubits | States | Iterations | Oracle Cost | Diffuser Cost | Total |
|---|---|---|---|---|---|
| 4 | 16 | 3 | 3 * O(1) | 3 * O(64) | <0.01ms |
| 8 | 256 | 12 | 12 * O(1) | 12 * O(2048) | <0.1ms |
| 12 | 4,096 | 50 | 50 * O(1) | 50 * O(49K) | ~1ms |
| 16 | 65,536 | 201 | 201 * O(1) | 201 * O(1M) | ~10ms |
| 20 | 1,048,576 | 804 | 804 * O(1) | 804 * O(20M) | ~500ms |
| 24 | 16,777,216 | 3,217 | 3217 * O(1) | 3217 * O(402M) | ~60s |
Gate-count equivalent (for comparison with hardware gate-based simulation):
| Qubits | Grover Iterations | Equivalent Gate Count | Index-Optimized Ops |
|---|---|---|---|
| 8 | 12 | ~200 gates | ~25K ops |
| 12 | 50 | ~1,500 gates | ~2.5M ops |
| 16 | 201 | ~10,000 gates | ~200M ops |
| 20 | 804 | ~60,000 gates | ~16B ops |
The "gates" column counts oracle gates (decomposed) + diffuser gates. The "ops" column counts actual floating-point operations in the optimized simulation path. The ratio confirms that the O(1) oracle trick yields a roughly 2x constant-factor improvement for the overall search.
A speculative but architecturally sound integration path connects Grover's search with ruVector's HNSW (Hierarchical Navigable Small World) index:
Hybrid Quantum-Classical Nearest-Neighbor Search
=================================================
Phase 1: Classical HNSW (coarse filtering)
- Navigate the HNSW graph to find candidate neighborhood
- Reduce search space from N to ~sqrt(N) candidates
- Time: O(log N)
Phase 2: Grover's Search (fine filtering)
- Encode candidate set as Grover oracle
- Search for exact nearest neighbor among candidates
- Quadratic speedup over brute-force comparison
- Time: O(N^{1/4}) for sqrt(N) candidates
Combined: O(log N + N^{1/4}) vs classical O(log N + sqrt(N))
┌──────────────────────────────────────────────┐
│ HNSW Layer Navigation │
│ │
│ Layer 3: o ─────────── o ────── o │
│ │ │ │
│ Layer 2: o ── o ────── o ── o ──o │
│ │ │ │ │ │ │
│ Layer 1: o─o──o──o──o──o─o──o──o─o │
│ │ │ │ │ │ │ │ │ │ │ │
│ Layer 0: o-o-oo-oo-oo-oo-o-oo-oo-o │
│ │ │
│ ┌───────▼────────┐ │
│ │ Candidate Pool │ │
│ │ ~sqrt(N) items│ │
│ └───────┬────────┘ │
│ │ │
└────────────────────┼───────────────────────────┘
│
┌──────────▼───────────┐
│ Grover's Search │
│ │
│ Oracle: distance │
│ threshold on │
│ candidate indices │
│ │
│ O(N^{1/4}) queries │
└──────────────────────┘
This integration is facilitated by ruVector's existing HNSW implementation (150x-12,500x faster than baseline, per ruVector performance targets). The Grover oracle would encode a distance-threshold predicate: "is vector[i] within distance d of the query vector?"
/// Oracle that marks basis states corresponding to vectors
/// within distance threshold of a query.
pub struct HnswGroverOracle {
/// Candidate indices from HNSW coarse search
pub candidates: Vec<usize>,
/// Query vector
pub query: Vec<f32>,
/// Distance threshold
pub threshold: f32,
/// Pre-computed distances (for O(1) oracle evaluation)
pub distances: Vec<f32>,
}
impl GroverOracle for HnswGroverOracle {
fn is_marked(&self, index: usize, _n_qubits: usize) -> bool {
if index < self.distances.len() {
self.distances[index] <= self.threshold
} else {
false
}
}
}Note: This hybrid approach is currently theoretical for classical simulation. Its value lies in (a) algorithm prototyping for future quantum hardware, and (b) demonstrating integration patterns between quantum algorithms and classical data structures.
- O(1) oracle optimization provides a 2x constant-factor speedup unique to state vector simulation, making Grover's algorithm practical for up to 20+ qubits
- Dual oracle modes support both fast known-target search (index-based) and general black-box function search (predicate-based)
- Auto-computed iteration count prevents over-iteration and ensures near-optimal success probability
- Multi-target support handles the general case of k marked states with appropriate iteration adjustment
- HNSW integration path provides a concrete vision for hybrid quantum-classical search that leverages ruVector's existing vector database infrastructure
| Risk | Probability | Impact | Mitigation |
|---|---|---|---|
| Diffuser dominates runtime, limiting oracle optimization benefit | High | Low | Accept 2x improvement; focus on SIMD-optimized Hadamard |
| Multi-target count unknown in practice | Medium | Medium | Quantum counting subroutine (future work) |
| HNSW integration adds complexity with unclear practical advantage | Low | Low | Keep as optional module, prototype-only initially |
| Over-iteration produces incorrect results | Low | High | Auto-compute + warning system + probability tracking |
| Decision | Advantage | Disadvantage |
|---|---|---|
| O(1) index oracle | Massive speedup for known targets | Not applicable to true black-box search |
| Auto iteration count | Prevents user error | Less flexible for advanced use cases |
| General oracle trait | Supports arbitrary predicates | O(2^n) per application (no speedup over gates) |
| Eager probability tracking | Enables convergence monitoring | Memory overhead for probability vector |
- Grover, L.K. "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212-219 (1996)
- Boyer, M., Brassard, G., Hoyer, P., Tapp, A. "Tight bounds on quantum searching." Fortschritte der Physik 46, 493-505 (1998)
- Malviya, Y.K., Zapatero, R.A. "Quantum search algorithms for database search: A comprehensive review." arXiv:2311.01265 (2023)
- ADR-001: ruQu Architecture - Classical Nervous System for Quantum Machines
- ADR-QE-005: VQE Algorithm Support (parameterized circuits, expectation values)
- ruVector HNSW implementation: 150x-12,500x faster pattern search (CLAUDE.md performance targets)
- ruQu crate:
crates/ruQu/src/- syndrome processing and state vector infrastructure