quantum/README.md

Quantum Navigation Core

The quantum package is the heart of the Quantum Navigation project. It implements a hybrid quantum-classical approach to multi-robot path planning, utilizing QUBO (Quadratic Unconstrained Binary Optimization) formulations to solve complex navigation tasks.

For theoretical background and formulation details, please refer to our paper: Scalable Multi-Robot Path Planning via Quadratic Unconstrained Binary Optimization.

Package Structure

• builder/: Constructs the mathematical models (QUBOs) from problem definitions. Contains logic for grid and graph-based environments.
• solvers/: Interfaces for various quantum and classical solvers (DWave, PennyLane, Simulated Annealing).
• config/: Configuration management, file parsing (YAML, HDF5), and ROS integration tools.
• utils/: Shared utility functions for path handling and data manipulation.
• benchmark/: Tools for benchmarking solver performance and accuracy.

Core Modules

Problem Formulation

• pathFormulation.py: Defines the mathematical formulation of the pathfinding problem. It translates high-level constraints (start, goal, obstacles) into the logic needed by the builders.
• map.py: Handles the internal representation of the environment, including grid data, obstacles, terrain costs, and graph topology.
• robotConfiguration.py: Manages the state and parameters of individual robots within the swarm.

Visualization

• visualizer.py: Tools for visualizing the navigation process, including:
  • 2D grid maps with paths.
  • Energy landscapes of the quantum solution.
  • Real-time solving progress.

Getting Started

To run a navigation task or benchmark, you can use the command-line interface qubo_cli.py for flexibility, or the qubo.py script for hands-on code modification.

Using the CLI (qubo_cli.py)

The CLI allows you to specify maps, problems, solvers, and run benchmarks directly from the terminal:

# DWave example
python qubo_cli.py --map maps/synthetic/10x10/obs10x10_hard --problem four_robots

# Pennylane example
python qubo_cli.py --map maps/synthetic/10x10/no_obs10x10 --problem two_robots --var-limit 605 --solver pennylane --benchmark --num-runs 1

Run python qubo_cli.py --help to see all available options.

Using the Script (qubo.py)

1. Configure: Edit config/config.yaml to set your map and solver preferences.
2. Run: Execute the main script.

python qubo.py

Tip: Control console output verbosity by setting verbose.level in config/config.yaml (or via --verbose in the CLI):

• 0 = Silent (errors only)
• 1 = Minimal (essential info)
• 2 = Standard (default)
• 3 = Debug (all details)

Inside qubo.py, you can switch between different problem configurations (e.g., grid vs. graph) and solvers by uncommenting the relevant lines.

Solving Pipeline

General (top): the map enters a Build Phase — get_logical_variables() (BFS reachability), builder.build() (constraints over active cells), reduce_diag_fixed_vars_iterative() (diagonal-dominant elimination) — then solve_qubo() and _handle_iteration_result().
Iterative (bottom): solve_qubo_smart() checks after each window whether the last timestep or goal is reached. If yes, post-processing runs. If no, current_T advances, _prepare_window() runs the Build Phase again, and the result feeds back into the next iteration.

Stage details

Stage	Key function	Description
Logical Reduction	get_logical_variables()	BFS forward from each robot's current position. Variables at unreachable (robot, t, position) triplets are never added to the QUBO. Start/goal variables are pinned to 1 in fixed_ones.
Build QUBO	builder.build()	All constraint methods query _cells() / _nodes() which return only the active sparse set, so the resulting Q matrix is minimal by construction.
Numerical Reduction	reduce_diag_fixed_vars_iterative()	Variables whose diagonal coefficient dominates the sum of all off-diagonal magnitudes are fixed to 0 and removed. The process repeats until no further reductions are possible.
Solve	solve_qubo()	The reduced QUBO (typically 50–80 % smaller than the naive formulation) is optionally normalized and submitted to the backend.
Post-process	_handle_iteration_result()	The raw binary sample is merged with fixed_vars, decoded to (row, col, t) coordinates, validated for adjacency and collision, and corrected where possible via BFS repair.

Key Concepts

• Windowing: To overcome the qubit limitations of current quantum hardware, paths are solved in "sliding windows" (e.g., 5 steps at a time) rather than all at once.
• Hybrid Solving: The system can dynamically switch between quantum annealers (DWave), gate-based QAOA (PennyLane), and classical heuristics depending on problem complexity and resource availability.
• Coordinate conventions: The core always works in matrix (row, col) — that never changes. Callers can opt into cartesian/robotics (x, y) per-robot at request time (RobotConfig.coordinate_format, qubo_cli.py --coordinate-format) without touching the solver internals; see utils/README.md for the mechanism and maps/README.md for why maps themselves don't have this same runtime choice.