QUBO solvers#

Solvers for robot QUBO problems: classical baselines and a thin Qiskit QAOA adapter.

The classical solvers (exhaustive(), simulated_annealing(), greedy_descent()) are the baselines a quantum result must be reported against. qaoa() does not re-implement QAOA: it hands the problem’s Ising Hamiltonian to Qiskit’s own QAOAAnsatz and simulates the circuit exactly, so the algorithm is Qiskit’s and the only thing added here is the connection to the robot problems and the bookkeeping (energy, probability of the optimum, best sampled solution).

Classes

SolverResult

What a solver returns.

Functions

exhaustive

Exact optimum by enumeration (at most 22 variables).

simulated_annealing

Single-bit-flip simulated annealing with a geometric schedule (classical baseline).

greedy_descent

Best-improvement single-bit descent from random starts (the simplest classical baseline).

random_sampling

Best of shots uniformly random bit strings: the null baseline for any sampling-based solver.

qaoa

QAOA through Qiskit's QAOAAnsatz, simulated exactly (at most 16 qubits).
class SolverResult(x, energy, method, info=<factory>)[source]#

Bases: object

What a solver returns.

Variables:

  • x (numpy.ndarray) – Best bit string found.

  • energy (float) – QUBO energy of x.

  • method (str)

  • info (dict) – Method-specific details (for QAOA: expected_energy, p_optimal, depth).

Parameters:
exhaustive(qubo)[source]#

Exact optimum by enumeration (at most 22 variables).

Returns:

SolverResult

simulated_annealing(qubo, sweeps=1000, restarts=10, t_start=None, t_end=None, seed=0)[source]#

Single-bit-flip simulated annealing with a geometric schedule (classical baseline).

Single flips cannot move between two feasible assignments without crossing the penalty barrier of the encoding, so on penalty QUBOs this solver is often weaker than greedy_descent() with many restarts; report both.

Parameters:

  • qubo (Qubo)

  • sweeps (int, optional) – Sweeps over all variables per restart.

  • restarts (int, optional) – Independent restarts; the best result is returned.

  • t_start (float, optional) – Start and end temperature (defaults from the largest energy change of one flip).

  • t_end (float, optional) – Start and end temperature (defaults from the largest energy change of one flip).

  • seed (int, optional)

Returns:

SolverResult

greedy_descent(qubo, restarts=20, seed=0)[source]#

Best-improvement single-bit descent from random starts (the simplest classical baseline).

Returns:

SolverResult

random_sampling(qubo, shots=1000, seed=0)[source]#

Best of shots uniformly random bit strings: the null baseline for any sampling-based solver.

A quantum sampler that returns the best of shots samples must beat this with the same shots, otherwise its success only reflects how many samples it drew from a small search space.

Returns:

SolverResult

qaoa(qubo, depth=2, restarts=3, shots=1000, maxiter=150, seed=0)[source]#

QAOA through Qiskit’s QAOAAnsatz, simulated exactly (at most 16 qubits).

The circuit parameters are optimised classically (COBYLA) to minimise the expected QUBO energy; the returned solution is the lowest-energy bit string among shots samples of the final state, as on hardware.

Parameters:

  • qubo (Qubo)

  • depth (int, optional) – Number of QAOA layers p.

  • restarts (int, optional) – Random starting angles; the best expected energy is kept.

  • shots (int, optional) – Samples drawn from the optimised state.

  • maxiter (int, optional) – COBYLA iterations per restart.

  • seed (int, optional)

Returns:

SolverResult – info holds expected_energy, p_optimal (probability mass on the exact optimum), depth and ratio (expected energy over the optimum, for energies measured from the worst case).

Raises:

  • ImportError – If Qiskit is not installed (pip install "quantum-mind[qiskit]").

  • ValueError – If the problem has more than 16 variables.