Quantum computing for robot algorithms#

Robot problems as binary optimisation, the classical baselines a quantum result must be reported against, and a thin adapter to Qiskit’s QAOA. The equations are on the mathematics page.

Legend: blue inputs, violet internal steps, green outputs, coral people, dashed grey classical baselines. Each entry is labelled by origin: Unique to Quantum Mind designed in this library; it builds on the methods cited with it, Published model, extended implements the cited model as published; Quantum Mind adds the capabilities listed, Published method implements the cited method as published, Software tool infrastructure rather than a model; and by category: Quantum-like quantum probability used to model people; runs on an ordinary computer, Quantum computing quantum circuits; run on the simulator or sent to quantum hardware, Classical classical statistics, decision theory or baselines, Mixed combines parts from more than one of these categories.

Robot problems as QUBOs#

Published model, extended Mixed

Multi-robot allocation, grasp selection and slot scheduling with their QUBO encodings, true objectives, feasibility checks and decoders.

        flowchart LR
    accTitle: Block diagram of Robot problems as QUBOs
    accDescr: Multi-robot allocation, grasp selection and slot scheduling with their QUBO encodings, true objectives, feasibility checks and decoders.
    pr["robot problem<br/>costs · grasps · conflicts"]:::in --> q["QUBO encoding<br/>penalty terms"]:::op
    pr --> obj["true objective<br/>feasibility · decode"]:::out
    q --> sol["any solver"]:::op --> x["bit string"]:::out --> obj
    classDef in fill:#0b2a4a,stroke:#79c0ff,color:#e6edf3
    classDef op fill:#2a1b3d,stroke:#d2a8ff,color:#e6edf3
    classDef out fill:#0f2e1a,stroke:#7ee787,color:#e6edf3
    classDef hum fill:#3d1414,stroke:#ff7b72,color:#e6edf3
    classDef base fill:#262626,stroke:#8b949e,color:#e6edf3,stroke-dasharray:4 3

  • API: multi_robot_allocation(), grasp_selection(), slot_scheduling(), RobotProblem

  • Tutorial: Quantum computing for robot algorithms

  • Origin: Published model, extended: implements the cited model as published; Quantum Mind adds the capabilities listed.

  • Category: Mixed: combines parts from more than one of these categories.

  • Quantum Mind adds: robot objectives, feasibility checks and decoders on top of the published penalty encodings.

  • Reference: Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, 2, 5.

Classical baselines for QUBOs#

Published method Classical

Exhaustive search, greedy descent with restarts, simulated annealing and random sampling with the same number of shots: what a quantum result has to beat.

        flowchart LR
    accTitle: Block diagram of Classical baselines for QUBOs
    accDescr: Exhaustive search, greedy descent with restarts, simulated annealing and random sampling with the same number of shots: what a quantum result has to beat.
    q["QUBO"]:::in --> ex["exhaustive<br/>(optimum)"]:::base & gd["greedy descent"]:::base & sa["simulated annealing"]:::base & rs["random sampling<br/>(null baseline)"]:::base
    classDef in fill:#0b2a4a,stroke:#79c0ff,color:#e6edf3
    classDef op fill:#2a1b3d,stroke:#d2a8ff,color:#e6edf3
    classDef out fill:#0f2e1a,stroke:#7ee787,color:#e6edf3
    classDef hum fill:#3d1414,stroke:#ff7b72,color:#e6edf3
    classDef base fill:#262626,stroke:#8b949e,color:#e6edf3,stroke-dasharray:4 3

  • API: exhaustive(), greedy_descent(), simulated_annealing(), random_sampling()

  • Tutorial: Quantum computing for robot algorithms

  • Origin: Published method: implements the cited method as published.

  • Category: Classical: classical statistics, decision theory or baselines.

  • Reference: Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671-680.

QAOA adapter (Qiskit)#

Software tool Quantum computing

QAOA through Qiskit’s QAOAAnsatz on an exact simulator: the problem’s Ising Hamiltonian goes in, the best sampled solution, the expected energy and the probability of the optimum come out.

        flowchart LR
    accTitle: Block diagram of QAOA adapter (Qiskit)
    accDescr: QAOA through Qiskit's QAOAAnsatz on an exact simulator: the problem's Ising Hamiltonian goes in, the best sampled solution, the expected energy and the probability of the optimum come out.
    q["QUBO"]:::in --> ising["Ising Hamiltonian"]:::op --> an["Qiskit QAOAAnsatz<br/>depth p"]:::op --> opt["classical optimiser<br/>COBYLA, restarts"]:::op
    opt --> sv["exact statevector"]:::op --> out["best sample · P(optimal) · ratio"]:::out
    out -.-> rs["random sampling, same shots"]:::base
    classDef in fill:#0b2a4a,stroke:#79c0ff,color:#e6edf3
    classDef op fill:#2a1b3d,stroke:#d2a8ff,color:#e6edf3
    classDef out fill:#0f2e1a,stroke:#7ee787,color:#e6edf3
    classDef hum fill:#3d1414,stroke:#ff7b72,color:#e6edf3
    classDef base fill:#262626,stroke:#8b949e,color:#e6edf3,stroke-dasharray:4 3

  • API: qaoa()

  • Compared with: random sampling with the same shots; greedy descent; simulated annealing

  • Tutorial: Quantum computing for robot algorithms

  • Origin: Software tool: infrastructure rather than a model.

  • Category: Quantum computing: quantum circuits; run on the simulator or sent to quantum hardware.

  • Reference: Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv:1411.4028.

Solver comparison#

Software tool Mixed

Run several solvers on one robot problem and report them in the robot’s terms: feasibility, true objective and gap to the exact optimum.

        flowchart LR
    accTitle: Block diagram of Solver comparison
    accDescr: Run several solvers on one robot problem and report them in the robot's terms: feasibility, true objective and gap to the exact optimum.
    p["robot problem"]:::in --> s["solvers"]:::op --> r["feasible? · objective · gap"]:::out
    classDef in fill:#0b2a4a,stroke:#79c0ff,color:#e6edf3
    classDef op fill:#2a1b3d,stroke:#d2a8ff,color:#e6edf3
    classDef out fill:#0f2e1a,stroke:#7ee787,color:#e6edf3
    classDef hum fill:#3d1414,stroke:#ff7b72,color:#e6edf3
    classDef base fill:#262626,stroke:#8b949e,color:#e6edf3,stroke-dasharray:4 3

  • API: compare_solvers()

  • Tutorial: Quantum computing for robot algorithms

  • Origin: Software tool: infrastructure rather than a model.

  • Category: Mixed: combines parts from more than one of these categories.