Quantum-Inspired Query Optimizer Tuning

Quantum-Inspired Optimizer Tuning — 100x Speedup on Big-Join Queries

Crate: heliosdb-research/crates/quantum-optimizer Modules: cost_model, grover, join_optimizer, planner, quantum_annealing, variational Status: “Production-Ready” per crate README — 60+ tests, TPC-H validated, 100% safe Rust (no unsafe)

---

UVP

For a 4-way join, the classical optimizer is fine. For a 10-way join, the search space is 10! = 3.6M orderings, exhaustive search takes 95 seconds, and your dashboard times out. The Full edition’s quantum-inspired optimizer uses simulated quantum annealing, Grover-style search-space reduction, and QAOA-inspired cardinality estimation to land 528x faster on 10-table joins, within 5% of the optimal cost. No quantum hardware. No external services. Pure-Rust simulation that runs on the same CPU as the rest of your query path. Plus a built-in classical fallback — if the quantum run misses its time budget, the planner falls back automatically.

---

Prerequisites

• HeliosDB Full v7.x+ with the heliosdb-research workspace built.
• Workloads with 6+-way joins, or you won’t notice.
• About 20 minutes.

---

1. The Configuration Surface

From planner.rs:

pub struct QuantumPlannerConfig {
    pub enable_join_optimization: bool,        // quantum annealing on
    pub enable_grover_search: bool,            // Grover search-space reduction on
    pub enable_variational_estimation: bool,   // QAOA-style cardinality on
    pub timeout_ms: u64,                       // quantum-run budget
    pub fallback_to_classical: bool,           // safety net
    pub min_tables_for_quantum: usize,         // skip small queries
}

Defaults (from Default::default()):

QuantumPlannerConfig {
    enable_join_optimization: true,
    enable_grover_search: true,
    enable_variational_estimation: true,
    timeout_ms: 5000,
    fallback_to_classical: true,
    min_tables_for_quantum: 4,
}

min_tables_for_quantum: 4 is the sweet spot from the published benchmarks — below that the classical optimizer ties or wins.

---

2. Bring Up the Planner

use heliosdb_quantum_optimizer::prelude::*;

let mut planner = QuantumQueryPlanner::default();

let mut query = Query::new();
query.add_table("orders".to_string(), orders_stats);
query.add_table("lineitem".to_string(), lineitem_stats);

query.joins.push(JoinEdge {
    left_table: "orders".to_string(),
    right_table: "lineitem".to_string(),
    left_column: "orderkey".to_string(),
    right_column: "orderkey".to_string(),
    join_type: JoinType::Inner,
});

let (plan, stats) = planner.plan(&query)?;

println!("Optimized in {:?}", stats.planning_time);
println!("Cost: {}", plan.cost());

stats: OptimizationStats is the audit trail:

pub struct OptimizationStats {
    pub planning_time: Duration,
    pub join_optimization_time: Duration,
    pub space_reduction_ratio: f64,
    pub estimated_cost: f64,
    pub estimated_rows: u64,
    pub num_tables: usize,
    pub num_joins: usize,
    pub used_quantum: bool,             // did we actually run quantum?
    pub algorithms_used: Vec<String>,   // ["annealing", "grover", "qaoa"]
}

used_quantum: false means the planner fell back to classical (timeout or min_tables_for_quantum not met).

---

3. Tune Quantum Annealing

The annealer simulates quantum tunneling to escape local minima in the cost landscape:

use heliosdb_quantum_optimizer::quantum_annealing::AnnealingConfig;

let config = AnnealingConfig {
    num_steps: 2000,         // more steps = better quality, longer runtime
    num_replicas: 16,        // more replicas = more exploration
    tunneling_strength: 0.6, // higher = escape local minima easier
    ..Default::default()
};

let optimizer = QuantumJoinOptimizer::with_config(config);

Defaults inside QuantumQueryPlanner::new (from planner.rs):

• num_steps: 1500
• num_replicas: 12

Tuning advice (from the crate’s docs/TUNING_GUIDE.md):

Knob	Lower →	Higher →
num_steps	Faster, lower quality	Slower, higher quality
num_replicas	Less RAM, less exploration	More RAM, better global optima
tunneling_strength	Greedy, can stick in local minima	Aggressive, may overshoot

---

4. Tune Grover Search

Grover-style amplitude amplification reduces the search space from O(N!) to O(√N!):

use heliosdb_quantum_optimizer::grover::GroverConfig;

let config = GroverConfig {
    iterations: 15,
    sample_size: 80,
    ..Default::default()
};

Defaults inside QuantumQueryPlanner::new:

• iterations: 15
• sample_size: 80

For 10-table joins these defaults cut search time ~30x with <5% quality loss vs. exhaustive.

---

5. Per-Query Override

You don’t have to commit to a single config:

use heliosdb_quantum_optimizer::planner::QuantumPlannerConfig;

let config = QuantumPlannerConfig {
    enable_join_optimization: true,
    enable_grover_search: false,           // skip Grover for this run
    enable_variational_estimation: true,
    timeout_ms: 1000,                      // tighter budget
    fallback_to_classical: true,           // safety net stays on
    min_tables_for_quantum: 6,             // raise the bar
};

let mut planner = QuantumQueryPlanner::new(config);

This is how you’d build a “fast lane” planner for OLTP-shaped queries that occasionally have a 6-way join.

---

6. Verify the Speedup

From the crate README:

Tables	Classical	Quantum	Speedup	Quality
4	12 ms	4 ms	3x	99%
6	180 ms	12 ms	15x	97%
8	4,200 ms	50 ms	84x	95%
10	95,000 ms	180 ms	528x	95%

TPC-H:

• Q3 (3-way join): 2.5x faster, 98% quality
• Q5 (6-way join): 2.7x faster, 96% quality
• Q8 (7-way join): 3.3x faster, 95% quality

Run on your own data:

# In the heliosdb-quantum-optimizer crate
cargo bench --bench quantum_benchmarks
cargo bench --bench tpch_benchmarks
cargo bench -- "Join Size Scaling"

---

7. Monitoring in Production

OptimizationStats is the structured form of “did quantum help today?”:

let (plan, stats) = planner.plan(&query)?;

if stats.used_quantum {
    metrics.quantum_runs.inc();
    metrics.quantum_planning_ms.observe(stats.planning_time.as_millis() as f64);
    metrics.space_reduction.observe(stats.space_reduction_ratio);
    for algo in &stats.algorithms_used {
        metrics.algorithms_used.with_label_values(&[algo]).inc();
    }
} else {
    metrics.classical_runs.inc();
}

Wire these into Prometheus alongside the rest of the observability surface.

---

8. The Built-In Fallback

fallback_to_classical: true (the default) means: if the quantum run hits timeout_ms, the planner returns the best plan it has so far, falling back to classical heuristics. You never lose a query because of the quantum optimizer. Worst case is “quantum tried, didn’t finish, classical took over”. stats.used_quantum will read false for those queries.

Turn it off (fallback_to_classical: false) only in research mode where you want to see the quantum result or nothing.

---

9. Feature Flags

The crate exposes compile-time feature flags in features module:

pub mod features {
    pub const QUANTUM_ANNEALING: bool = true;
    pub const GROVER_SEARCH: bool = true;
    pub const QAOA_OPTIMIZATION: bool = true;
    pub const PARALLEL_TEMPERING: bool = true;
    pub const ALL_QUANTUM: bool = QUANTUM_ANNEALING && GROVER_SEARCH
        && QAOA_OPTIMIZATION && PARALLEL_TEMPERING;
}

These are build-time constants confirming which subsystems were compiled in. The runtime knobs are in QuantumPlannerConfig.

---

10. Algorithm Reference

Algorithm	Module	Job
Quantum Annealing	quantum_annealing	Find optimal join ordering by simulating tunneling
Grover Search	grover	Reduce candidate set from O(N!) to O(√N!)
QAOA	variational	Variational cardinality estimation
Parallel Tempering	quantum_annealing::ParallelTempering	Run multiple replicas at different temperatures
Quantum Cost Model	cost_model	Uncertainty-aware cost estimation

Based on:

• Grover’s Algorithm (Grover, 1996)
• Quantum Annealing (Kadowaki & Nishimori, 1998)
• QAOA (Farhi et al., 2014)

This is, per the crate’s own framing, “the first application to production database query optimization”.

---

11. When NOT to Use It

• Queries with <4 tables — turn it off via min_tables_for_quantum.
• Sub-millisecond OLTP — the planner adds overhead even when it falls back.
• Workloads where the planner already produces optimal plans deterministically (small star schemas with great statistics).

---

Where Next

• docs/QUANTUM_OPTIMIZATION.md — full algorithm chapter.
• docs/TUNING_GUIDE.md — workload-specific tuning.
• pitr-recovery.md and raft-setup.md — make sure the rest of the stack matches the optimizer’s bar.
• Source: heliosdb-research/crates/quantum-optimizer/README.md.