用三条本地路线求解同一个 MIS¶
在三节点路径图 a — b — c 上，比较 Digital QAOA、Hybrid QAOA 和 Analog QAA。固定图和解码顺序，每条路线尝试两个参数点，再用穷举答案核对选中的结果。这次练习要学会读比较报告，避免把“偶尔采到一次最优解”当成求解效果很好。
先完成图优化入门、D-A-D 实验和实验设计。使用学习环境，在仓库根目录运行。课堂版共三个节点、六次参数评估，每次采样 128 次。一次 macOS、Python 3.11 开发环境实测约需 1.5 秒，包含报告；更大问题或其他机器可能需要更长时间。
固定问题，说明比较条件¶
图有 (a, b) 和 (b, c) 两条边，位置分别为 (0, 0)、(6, 0)、(12, 0)，单位为微米。唯一最大独立集为 {a, c}，按 [a, b, c] 顺序编码为 101，大小为 2。
Digital 和 Hybrid 使用单层 QAOA，两个参数点为 (gamma_0, beta_0) = (0.16, 0.24) 和 (0.28, −0.18)。Analog 使用 QAA，两个调度为 (anneal_time, omega_max) = (0.4 us, 1 rad/us) 和 (0.7 us, 1.4 rad/us)。这些只是刻意控制规模的候选，没有经过训练，也不代表全局最优调度。参数点数量相同，不代表物理时长、模拟成本或搜索难度相同。
ProblemCompiler 把同一个图映射为三种程序。optimize(parameter_sets=...) 评估给定参数点，选择期望目标值最小的点，并列时按输入顺序选择。这个例子的目标值来自理想概率分布，counts 则是从选中分布得到的有限样本。当前流程在选参后没有额外进行独立确认采样。
运行前想一想：如果三条路线都至少采到过一次最优解，是否足以认为它们效果相同？
运行并比较报告¶
python3 examples/learning/projects/mis_routes.py
打开 artifacts/mis-routes/mis-zh.html。路线报告读取已完成的执行结果，按共用 Problem 目标进行比较。routes.json 保存图、完整执行结果、参数历史和模拟设置，英文报告来自同一批结果。
{
"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
}
| 字段 | 含义 |
|---|---|
problem_hash、logical_order |
检查三条路线是否使用相同数学问题和解码顺序 |
objective_value |
选中参数点的编译目标期望值，本例越小越好 |
best_observed_bitstring |
选中样本里观察到的最佳候选，不保证未来每次都能采到 |
feasible_frequency |
选中样本中不违反图边约束的比例 |
optimal_frequency |
选中样本中等于精确答案 101 的比例 |
history_shots |
两个参数点的采样总和，默认每条路线 256 次 |
selected_result_shots |
选中点的 128 个样本，已包含在历史预算内 |
整个搜索因此采样 768 次，不是 1,152 次：不能把选中点的样本再加一次。保存两种语言的报告也不会把实验运行两遍。
在这个本地理想例子里，Digital 和 Hybrid 实现等价的 QAOA 演化，概率在数值精度范围内一致；使用相同 seed 时，计数也可能相同。Analog 调度的时间演化和目标响应不同，需要结合它自己的设置，以及共同的解码问题来解释。
把状态空间差异写进结论¶
Analog 路线采用模拟目标的自动硬阻塞选择。在当前几何下，允许的基态包含独立集，并排除了相邻原子同时激发。因此，即使很少采到最优解，可行比例也可能为 1。这部分来自所选状态表示，不能据此判断短调度找到了更好的解。
Digital 和 Hybrid QAOA 可以采到无效位串，并由编译后的罚项处理。比较可行比例前先说明这个差异。研究比较还需决定保持哪些条件相同：搜索预算、目标约束、数值精度、物理时长，或其中几项。
阅读实现¶
脚本先穷举八个候选得到参考，再使用公开 Problem 编译和报告接口。可行比例与最优解频率直接从 counts 计算，你可以逐项核对。
"""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()
写一份能复查的比较说明¶
- 从 counts 重新计算三条路线的可行比例和最优解频率。解释为什么仅看最佳位串会隐藏分布差异。
- 使用
--shots 1024 --seed 4703 --output-dir artifacts/mis-more-shots重跑。哪个量是期望代价？哪些量会带有新的采样不确定度？ - 在本地副本中只修改 Analog 参数集，记录所有尝试过的调度和目标值。为什么仅凭两个手选参数点，还不足以比较 QAA 和 QAOA 各自能达到的最佳表现？
- 扩展到已有的 3×3 网格示例。运行前先列出增加后的变量数、基空间大小和数值设置，再决定预算。
核对思路
可行比例累加 000、001、010、100 和 101 的计数；最优解频率只使用 101。很少出现与经常出现的最优解，可能给出相同的最佳位串。这个理想流程的期望代价由概率得到，候选频率随 seed 和 shots 波动；增加采样不会探索新的参数点。3×3 图有九个变量，约化前的完整基空间有 512 个状态。原示例的精度和时间步设置也不同，必须记录，不能默认与这里的三节点实验相同。
研究扩展应预先确定搜索预算，保留全部参数历史，检查数值收敛性，并用独立样本确认选中候选。报告成功频率的不确定度，也要写明经典穷举或其他参考方法的适用规模。这个小型本地比较不能证明量子优势或真机性能。