Solve the same MIS through three local routes¶
Compare Digital QAOA, Hybrid QAOA and Analog QAA on the three-node path a — b — c. Keep the graph and decoding order fixed, try two parameter points per route, and compare the selected results against exhaustive enumeration. The exercise teaches how to read a comparison without mistaking one successful sample for a good solver.
Complete graph problems, the D-A-D experiment and experimental design. Use the installed learning environment and run from the repository root. The classroom version uses three nodes and six parameter evaluations, with 128 shots per evaluation. A macOS/Python 3.11 development run took about 1.5 seconds including reports; larger problems or other machines may take longer.
Fix the problem and define the comparison¶
The graph has edges (a, b) and (b, c) and positions (0, 0), (6, 0), (12, 0) in micrometres. Its unique maximum independent set is {a, c}, encoded as 101 in order [a, b, c], with size two.
Digital and Hybrid use one-layer QAOA. Their two parameter sets are (gamma_0, beta_0) = (0.16, 0.24) and (0.28, −0.18). Analog uses QAA schedules with (anneal_time, omega_max) = (0.4 us, 1 rad/us) and (0.7 us, 1.4 rad/us). These are deliberately small candidate sets, not trained or globally optimized schedules. Equal numbers of parameter points do not make physical duration, simulation effort or search difficulty equal.
ProblemCompiler maps the same graph to the three programs. optimize(parameter_sets=...) evaluates the supplied points and selects the minimum expected objective, breaking ties by input order. This example uses the ideal distribution for that objective; the counts are finite samples from the selected distribution. There is no extra independent confirmation run after selection in this workflow.
Before running, predict whether “all three routes sampled the optimum at least once” is enough to conclude that they are equally effective.
Run and compare the reports¶
python3 examples/learning/projects/mis_routes.py
Open artifacts/mis-routes/mis-en.html. The route comparison uses the completed executions and their shared Problem objective. routes.json retains the graph, full executions, parameter histories and simulation settings. The Chinese report uses the same results.
{
"artifacts": {
"data": "artifacts/mis-routes/routes.json",
"report_en": "artifacts/mis-routes/mis-en.html",
"report_zh": "artifacts/mis-routes/mis-zh.html"
},
"classical_maximum_size": 2,
"classical_optimal_bitstrings": [
"101"
],
"modes": {
"analog": {
"algorithm": "qaa",
"best_observed_bitstring": "101",
"best_observed_feasible": true,
"counts": {
"000": 92,
"001": 9,
"010": 12,
"100": 13,
"101": 2
},
"evaluation_count": 2,
"feasible_frequency": 1.0,
"history_shots": 256,
"logical_order": [
"a",
"b",
"c"
],
"objective_value": -0.32725200794438375,
"optimal_frequency": 0.015625,
"parameter_sets": [
{
"anneal_time": 0.4,
"omega_max": 1.0
},
{
"anneal_time": 0.7,
"omega_max": 1.4
}
],
"problem_hash": "826a555614f6b069611aa1a14214968356def14aba43be0b3f3a45c5c6ae1c5b",
"selected_evaluation_index": 1,
"selected_result_shots": 128
},
"digital": {
"algorithm": "qaoa",
"best_observed_bitstring": "101",
"best_observed_feasible": true,
"counts": {
"000": 13,
"001": 13,
"010": 20,
"011": 19,
"100": 19,
"101": 21,
"110": 12,
"111": 11
},
"evaluation_count": 2,
"feasible_frequency": 0.671875,
"history_shots": 256,
"logical_order": [
"a",
"b",
"c"
],
"objective_value": -0.7202251513922284,
"optimal_frequency": 0.1640625,
"parameter_sets": [
{
"beta_0": 0.24,
"gamma_0": 0.16
},
{
"beta_0": -0.18,
"gamma_0": 0.28
}
],
"problem_hash": "826a555614f6b069611aa1a14214968356def14aba43be0b3f3a45c5c6ae1c5b",
"selected_evaluation_index": 1,
"selected_result_shots": 128
},
"hybrid": {
"algorithm": "qaoa",
"best_observed_bitstring": "101",
"best_observed_feasible": true,
"counts": {
"000": 13,
"001": 13,
"010": 20,
"011": 19,
"100": 19,
"101": 21,
"110": 12,
"111": 11
},
"evaluation_count": 2,
"feasible_frequency": 0.671875,
"history_shots": 256,
"logical_order": [
"a",
"b",
"c"
],
"objective_value": -0.7202251513922278,
"optimal_frequency": 0.1640625,
"parameter_sets": [
{
"beta_0": 0.24,
"gamma_0": 0.16
},
{
"beta_0": -0.18,
"gamma_0": 0.28
}
],
"problem_hash": "826a555614f6b069611aa1a14214968356def14aba43be0b3f3a45c5c6ae1c5b",
"selected_evaluation_index": 1,
"selected_result_shots": 128
}
},
"sdk_version": "1.0.8a",
"seed": 4702,
"shots_per_evaluation": 128
}
| Quantity | Meaning |
|---|---|
problem_hash, logical_order |
Check that the mathematical problem and decoding order agree across routes |
objective_value |
Expected compiled cost at the selected parameter point; smaller is preferred here |
best_observed_bitstring |
Best candidate seen in the selected samples, not a guarantee about every future sample |
feasible_frequency |
Fraction of selected samples that violate no graph edge |
optimal_frequency |
Fraction equal to the exact reference solution 101 |
history_shots |
Sum of shots over both evaluated points, 256 per route by default |
selected_result_shots |
The selected point's 128 samples, already included in the history budget |
The whole search therefore uses 768 shots, not 1,152: do not add selected samples to the history a second time. Saving two reports also does not run two experiments.
In this local ideal example, Digital and Hybrid implement equivalent QAOA dynamics and their probabilities agree to numerical precision. Their sampled counts can also agree under the same seed. The Analog schedule has a different time evolution and objective response; compare it using its own settings and the common decoded problem.
Account for the state space¶
The Analog route uses the mock target's automatic hard-blockade choice. With this geometry, its allowed basis includes the independent sets and excludes adjacent double excitations. Consequently its feasible fraction can be one even when the optimum is rarely sampled. This is partly a property of the selected representation, not evidence that the short schedule found a better solution.
Digital and Hybrid QAOA can sample infeasible bitstrings and handle them through the compiled penalty objective. Document this difference before comparing feasible fractions. A fairer research study must specify what is held equal: search budget, target constraints, simulation precision, physical time or some combination.
Read the implementation¶
The script exhausts eight candidates to establish the reference, then uses the public Problem compiler and report interface. The example derives feasibility and optimum frequencies directly from counts, so you can independently check every displayed fraction.
"""Compare three local compilation routes for the same three-node MIS problem."""
from __future__ import annotations
import argparse
import json
from pathlib import Path
from typing import Any
import cascaqit
from cascaqit import LocalBackend, MockNeutralAtomTarget, SimulationOptions, visualize
from cascaqit.problems import GraphProblemIR, ProblemCompiler, decode_graph_bitstring
def experiment(
output_dir: Path, *, shots: int = 128, seed: int = 4702
) -> dict[str, Any]:
"""Keep problem, candidates, parameter budgets and report inputs together."""
if shots < 1:
raise ValueError("shots must be positive.")
output_dir.mkdir(parents=True, exist_ok=True)
graph = GraphProblemIR.from_edges(
problem_id="lesson.project.mis-routes",
positions={"a": (0.0, 0.0), "b": (6.0, 0.0), "c": (12.0, 0.0)},
edges=(("a", "b"), ("b", "c")),
)
candidates = [decode_graph_bitstring(graph, f"{i:03b}") for i in range(8)]
feasible = [c for c in candidates if c["is_independent"]]
optimum = max(c["selection_size"] for c in feasible)
target = MockNeutralAtomTarget.local_ahs_v0_1()
backend = LocalBackend(target=target, analog_time_steps=32)
options = SimulationOptions(
dtype="complex128", integrator="fixed_step_krylov", max_steps=32
)
parameter_sets = {
"digital": (
{"gamma_0": 0.16, "beta_0": 0.24},
{"gamma_0": 0.28, "beta_0": -0.18},
),
"hybrid": (
{"gamma_0": 0.16, "beta_0": 0.24},
{"gamma_0": 0.28, "beta_0": -0.18},
),
"analog": (
{"anneal_time": 0.4, "omega_max": 1.0},
{"anneal_time": 0.7, "omega_max": 1.4},
),
}
executions = {}
modes = {}
for mode, parameters in parameter_sets.items():
algorithm = "qaa" if mode == "analog" else "qaoa"
compiled = ProblemCompiler().compile(
graph, mode=mode, algorithm=algorithm, target=target
)
execution = compiled.optimize(
parameter_sets=parameters,
shots=shots,
seed=seed,
backend=backend,
options=None if mode == "digital" else options,
)
counts = execution.result.counts
decoded = [
(decode_graph_bitstring(graph, bits), count)
for bits, count in counts.items()
]
feasible_shots = sum(count for item, count in decoded if item["is_independent"])
optimal_shots = sum(
count
for item, count in decoded
if item["is_independent"] and item["selection_size"] == optimum
)
history_shots = sum(item.shots for item in execution.parameter_history)
modes[mode] = {
"algorithm": algorithm,
"problem_hash": execution.problem_hash,
"logical_order": list(execution.logical_order),
"parameter_sets": parameters,
"evaluation_count": len(execution.parameter_history),
"history_shots": history_shots,
"selected_result_shots": sum(counts.values()),
"selected_evaluation_index": execution.selected_evaluation_index,
"objective_value": execution.objective_value,
"best_observed_bitstring": execution.best_observed_candidate.bitstring,
"best_observed_feasible": execution.best_observed_candidate.feasible,
"counts": counts,
"feasible_frequency": feasible_shots / shots,
"optimal_frequency": optimal_shots / shots,
}
executions[mode] = execution
artifacts = {"data": str(output_dir / "routes.json")}
for language in ("en", "zh"):
path = output_dir / f"mis-{language}.html"
visualize(
executions,
output=path,
language=language,
title="MIS: Digital / Hybrid / Analog",
)
artifacts[f"report_{language}"] = str(path)
summary = {
"sdk_version": cascaqit.__version__,
"seed": seed,
"shots_per_evaluation": shots,
"classical_maximum_size": optimum,
"classical_optimal_bitstrings": [
c["bitstring"] for c in feasible if c["selection_size"] == optimum
],
"modes": modes,
"artifacts": artifacts,
}
raw = {
**summary,
"graph": graph.to_dict(),
"simulation_options": options.to_dict(),
"executions": {mode: run.to_dict() for mode, run in executions.items()},
}
Path(artifacts["data"]).write_text(
json.dumps(raw, indent=2) + "\n", encoding="utf-8"
)
return summary
def main() -> None:
parser = argparse.ArgumentParser(description=__doc__)
parser.add_argument("--output-dir", type=Path, default=Path("artifacts/mis-routes"))
parser.add_argument("--shots", type=int, default=128)
parser.add_argument("--seed", type=int, default=4702)
args = parser.parse_args()
print(
json.dumps(
experiment(args.output_dir, shots=args.shots, seed=args.seed),
sort_keys=True,
)
)
if __name__ == "__main__":
main()
Write a comparison that another student can check¶
- Recalculate each route's feasible fraction and optimum frequency from its counts. Explain why the best observed bitstring alone hides differences between distributions.
- Run with
--shots 1024 --seed 4703 --output-dir artifacts/mis-more-shots. Which quantity is the expected cost, and which quantities carry new sampling uncertainty? - Change only the Analog parameter set in a local copy. Record every tried schedule and its objective. Explain why two manually chosen points are insufficient to compare the best possible performance of QAA and QAOA.
- Expand to the existing 3×3 grid example. First list the increased number of variables, basis size and numerical settings; choose a budget before running.
Check your reasoning
The feasible fraction sums counts for 000, 001, 010, 100 and 101; the optimum frequency uses only 101. A rare optimum and a frequent optimum can have the same best observed bitstring. The expected cost in this ideal workflow comes from probabilities, while observed candidate frequencies fluctuate with seed and shots. Increasing sample count does not explore new parameter points. The 3×3 graph has nine variables and a full basis of 512 states before any reduction; its original example uses different precision and step settings, which must be recorded rather than silently equated to this three-node experiment.
For research, repeat a predeclared search budget, preserve all parameter histories, test numerical convergence and use independent samples to confirm selected candidates. Report uncertainty in success frequencies, as well as classical enumeration or another explicitly bounded reference. This small local comparison cannot establish quantum advantage or hardware performance.