CARVE-Q：量子提议、经典认证的交互式驾驶修复

# CARVE-Q：量子提议、经典验证的交互式驾驶修复  
来源：https://arxiv.org/html/2606.06531  

###### 摘要  
在正确的驾驶否决之后，关键问题不仅在于一个操作是否不安全，还在于被阻止的交互是否允许一种合法、可审计且责任有界的修复。预测和博弈论规划器可以提出合理的合作，但它们不会返回一个证明——即该修复是否尊重硬规则、路权、成本分配以及自车后备方案。我们引入 **CARVE**（通过包络对否决操作进行认证的廉价修复），这是一种无预测的交互式修复证书架构。给定一个被否决的操作，CARVE 构建一个有限修复格，并发出一个结构化证书，记录约束规则、选定的联合修复、按路权缩放的合作包络、按责任加权后的成本分配，以及仅自车可执行的后备方案。这个证书视图揭示了算法的瓶颈：多所有者修复会导出一个乘积格 \(M = \prod_j |\mathcal{A}_j|\)。因此，我们引入 **CARVE-Q**，一种由验证器屏蔽的量子-人工智能搜索层，它仅将量子最小值搜索应用于这个黑盒格，而所有安全权威仍由经典系统保留。在保守的验证器-预言机模型中，精确的经典最小值搜索在最坏情况下需要 \(\Theta(M)\) 次查询，而 Dürr–Hoyer/Grover 最小值搜索以高概率使用 \(O(\sqrt{M})\) 次预言机查询。我们证明了验证器屏蔽的证书可靠性、优先级非诱导性、黑盒查询分离性以及有限精度可逆预言机构造性。随后，我们在 CARVE 修复预言机上演示了多达 65,536 个赋值的状态向量最小值搜索，并在基于 Lanelet2 的 INTERACTION 复现中验证了证书的保留性，实现了 100% 尊重路权、100% 责任一致性，以及零优先级误报。结果形成了一个信任有界的量子-人工智能模式，用于认证的自主系统：量子提议，CARVE 认证。  

## 1. 引言  
交互式驾驶中最重要的决策可能始于正确的否决之后。设想一辆自车进入一个密集的城市合流区域。一个硬规则门控拒绝了该操作，因为另一辆车刚好在所需的间隙内。这个拒绝是安全的，但它并没有解释接下来应该发生什么。预测器可能猜测其他司机会减速；博弈论规划器可能搜索一个兼容的响应。但这两者都不是安全关键系统所需的证明：一个证书，说明操作为何被否决、允许何种有界修复、谁被要求适应、成本如何分配，以及如果合作未到来，自车还能安全做什么。  

这个例子暴露了一个脱节。硬规则否决对于不可恢复的危险是必要的，但当冲突可以通过一个小的、有界的适应（如等待、让行或减速）来解决时，它们在行为上就过于僵硬。预测和社会驾驶模型估计可能的交互（Sadigh 等，2016；Schwarting 等，2019；Alahi 等，2016；Deo 和 Trivedi，2018；Salzmann 等，2020），而规则手册、RSS、屏蔽和形式化安全方法则指定约束（Shalev-Shwartz 等，2017；Censi 等，2019；Alshiekh 等，2018；Garcia 和 Fernandez，2015）。缺失的对象既不是另一个轨迹预测器，也不是另一个否决规则，而是一个携带证书的交互式修复。  

我们引入 **CARVE**，即通过包络对否决操作进行认证的廉价修复。CARVE 将拒绝的操作从终端失败提升为一个有限修复问题，其输出是一个可审计的责任记录。证书命名了约束性硬规则，选择一个有界的联合修复，检查按路权缩放的合作包络，记录按责任加权的成本分配，并保留一个仅自车可执行的后备方案。因此，一个可修复的交互必须同时回答三个问题：修复是否使所有声明的硬规则边界非负？每个请求的适应是否保持在规范允许的包络内？自车是否仍能在不假设其他驾驶员服从的情况下恢复？  

CARVE 也暴露了一个搜索瓶颈。如果 \(n\) 个修复所有者各有一个有限动作集 \(\mathcal{A}_j\)，那么精确的联合修复会搜索一个大小为 \(M = \prod_j |\mathcal{A}_j|\) 的乘积格。密集的无保护转弯、狭窄的施工区域协商以及多智能体合流冲突可能需要若干车辆在等待、减速、让行或无操作编辑中进行选择。量子部分并不是强加于问题的，而是在 CARVE 将交互式修复转化为这个有限证书格之后才出现的。黑盒验证器模型是使量子层有意义的安全假设。如果验证器暴露了稳定的凸性、可分离性或低树宽结构，那么白盒经典求解器应该利用它。然而，在安全关键集成中，规则手册可能变化，谓词可能非凸或具有对抗性耦合，未来的屏蔽可能包含专有的感知模块。因此，信任有界的设计假设没有可利用的结构，并将验证器视为一个不透明的成本预言机。在这个模型下，精确的经典最小值搜索在最坏情况下需要 \(\Theta(M)\) 次查询，而 Grover/Dürr–Hoyer 最小值搜索以高概率使用 \(O(\sqrt{M})\) 次预言机查询（Grover, 1996；Dürr 和 Hoyer, 1996；Bennett 等, 1997；Boyer 等, 1998；Brassard 等, 2002）。这正是 CARVE-Q 中量子搜索必要性的确切含义。  

CARVE-Q 遵循一个信任边界：量子提议，CARVE 认证。量子模块搜索一个低成本联合修复，但在任何证书发出之前，确定的 CARVE 验证器会重新计算每一个谓词。我们不声称新的量子搜索算法、现有硬件加速、在白盒求解器上的普遍优越性，或量子认证的安全性。这些主张是架构性的和预言机理论性的：CARVE 定义了认证的修复对象，CARVE-Q 针对其黑盒联合格瓶颈，而 CARVE 仍然是最终的证书权威。  

我们的贡献是：  
- **认证的交互式修复**。我们将硬规则否决的驾驶交互定义为一个有限修复证书问题，而不是一个预测、游戏响应或仅自车重新规划问题。  
- **CARVE 证书语义**。我们定义了按路权缩放的合作包络 \(B_j(s) = \beta(\pi_j) \alpha_j^{\max}(s)\)、按责任加权的成本、可负担性谓词以及后备有效性。  
- **验证器屏蔽的量子-人工智能搜索**。我们展示了多所有者修复导出一个乘积格 \(M = \prod_j |\mathcal{A}_j|\)，并引入 CARVE-Q，它将量子最小值搜索应用于黑盒验证器-成本预言机，同时保留经典的证书权威。  
- **保证与证据**。我们证明了验证器屏蔽的可靠性、优先级非诱导性、黑盒查询分离性以及可逆预言机构造性；我们通过状态向量最小值搜索、黑盒压力测试、资源核算、复现诊断以及 QAOA/局部搜索审计来验证它们。  

![图 1: CARVE-Q 架构。CARVE 是认证修复架构：它将硬规则否决提升为一个可审计的证书，暴露一个有限的多所有者修复格，并让量子最小值搜索仅搜索那个黑盒瓶颈。量子模块只是一个提议层；最终证书由经典的 CARVE 验证器发出。](fig1)  

## 2. 从否决操作到 CARVE 证书  
CARVE 从一个与基于预测的交互式规划不同的对象开始：一个修复证书。输入是一个场景 \(s\)，一个候选操作 \(m\)，以及一个硬规则集合 \(\mathcal{H}\)。如果所有边界都是非负的，CARVE 返回一个空的满足证书。如果某个约束规则 \(h^\star\) 具有负边界，CARVE 构建一个有限修复格，包含自车拥有的编辑和有限的其他智能体拥有的适应请求。  

**定义 1（CARVE 证书）**：给定一个场景 \(s\)，一个被否决的操作 \(m\)，以及一个约束性硬规则 \(h^\star\)，一个 CARVE 证书是  
\[
\mathcal{C} = (\kappa, h^\star, x^\star, \rho_{\mathrm{ego}}, \{\rho_j\}_{j=1}^n, \mathcal{A}_{\mathrm{fb}}),
\]  
其中 \(\kappa\) 是证书类别，\(x^\star\) 是选定的联合修复赋值，\(\rho_{\mathrm{ego}}\) 和 \(\rho_j\) 是按责任加权的成本分配，\(\mathcal{A}_{\mathrm{fb}}\) 是一个仅自车可执行的后备动作集，无需外部合作即可执行。  

![图 2: 修复证书结构。CARVE 返回一个结构化的证明对象，而不仅仅是一个否决标签或预测轨迹。一个提议可能来自量子搜索、经典搜索或其他启发式方法；接受与否仅取决于经典验证器重新计算 \(H, B, F\) 和 \(\Phi\)。](fig2)  

该设计分离了三个常常被混淆的问题。第一，硬规则可行性询问应用一个修复是否使所有声明的安全边界非负。第二，可负担性询问自车努力和每个请求的智能体适应是否保持在声明的预算内。第三，后备询问自车是否保留一个可执行的应急方案（如果请求的合作未被观察到）。只有当这些谓词通过时，证书才被接受。这个区分正是使 CARVE-Q 成为一个 AI 架构而不仅仅是量子算法的原因。量子子程序是有用的，因为 CARVE 定义了一个有限但指数增长的决策对象。验证器屏蔽是有用的，因为安全关键的语义仍然可解释且可在经典层面审计。  

## 3. 认证的交互式修复语义  
### 规则与所有者。  
设场景 \(s\) 包含自车状态、其他智能体状态、语义地图上下文以及优先级角色 \(\pi_j\)。一个硬规则 \(h_\ell \in \mathcal{H}\) 返回边界 \(g_\ell(m, s)\)。一个修复所有者可以是自车或一个交互智能体。所有者 \(j\) 有一个有限集合 \(\mathcal{A}_j\)，包含无操作和战术性编辑，如等待、减速、让行或微调。一个联合修复赋值是 \(x = (a_1, \dots, a_n) \in \mathcal{A}_1 \times \dots \times \mathcal{A}_n\)。  

该格使用语义修复原型，而不是任意实值控制。诸如延迟或减速度之类的连续量被保守地离散化为分辨率单元。如果规则边界在这些修复参数上是利普希茨连续的，那么细化会限制定于一个可行连续修复与其代表性原型之间的边界退化；因此，遗漏的修复是可控的假阴性，而不是不安全的假阳性，因为每个被接受的赋值都由经典验证器重新检查。  

### 路权合作包络。  
CARVE 并不授权任意合作请求。对于一个交互智能体 \(j\)，请求幅度 \(\Delta_j\) 必须满足  
\[
0 \leq \Delta_j \leq B_j(s), \qquad B_j(s) = \beta(\pi_j) \alpha_j^{\max}(s)。
\]  
其中 \(\alpha_j^{\max}(s)\) 是一个保守的运动学适应边界，例如在当前速度和道路条件下智能体 \(j\) 可用的最大安全让行或速度降低量。因子 \(\beta(\pi_j) \in [0,1]\) 通过语义路权缩放该边界。优先级持有者使用 \(\beta(\pi_j) = 0\)，因此任何向优先级智能体发出的非零请求都不能被认证。这结构性地将物理可达性与规范性允许性分开。  

### 成本与后备。  
目标函数 \(\Phi(x, s)\) 是所选自车和智能体编辑上的一个按责任加权的成本：  
\[
\Phi(x, s) = \rho_{\mathrm{ego}}(x, s) + \sum_j w(\pi_j) \rho_j(x, s)。
\]  
其中 \(\rho_j(x, s) \geq 0\) 是一个运动学或时间惩罚，如延迟或积分减速度，而 \(w(\pi_j) > 0\) 是一个规范性乘子，惩罚不适当的责任转移。  

后备防止系统接受一个消耗掉最后恢复选项的操作。在一个诱导性或联合证书中，\(\mathcal{A}_{\mathrm{fb}}\) 是一个仅自车的应急方案，例如安全停止或等待动作，它可以在不依赖其他驾驶员服从的情况下执行。如果请求的适应未被观察到，自车将执行后备方案或在继续之前重新认证。该证书从不断言其他驾驶员会服从。  

### 认证的联合修复问题。  
设 \(H(x,s)\)、\(B(x,s)\) 和 \(F(x,s)\) 分别表示硬可行性、可负担性/包络有效性和后备有效性。有限修复问题是：  
\[
x^\star \in \arg\min_{x \in \mathcal{X}(s)} \Phi(x, s) \quad \text{s.t.} \quad H(x,s)=1,\; B(x,s)=1,\; F(x,s)=1,\; 0 \leq \Delta_j(x,s) \leq B_j(s),\; \forall j,
\]  
其中 \(\mathcal{X}(s) = \prod_j \mathcal{A}_j(s)\) 且 \(M(s) = |\mathcal{X}(s)|\)。CARVE 可以在有限格上精确求解，为在线使用贪心求解，或通过一个验证器-预言机搜索层求解。只有验证器能够发出 \(\mathcal{C}\)。  

表 1: CARVE 侧的能力差距。精确表示在联合格上的穷举搜索；CARVE-Q 增加了验证器屏蔽的量子搜索，同时保留相同的证书属性。  

## 4. 验证器屏蔽的量子-人工智能搜索  
给定 CARVE 验证器，定义一个有限精度验证器-成本预言机。设 \(\Phi_{\max}\) 是一个饱和值，大于任何可编码的可行修复成本。则  
\[
\tilde{f}(x;s) = \begin{cases}
\Phi(x,s), & H(x,s) \land B(x,s) \land F(x,s) = 1,\\
\Phi_{\max}, & \text{otherwise}。
\end{cases}
\]  
因此，不可行的赋值在一个有界算术寄存器中实现 \(+\infty\) 风格的语义。为消除退化，定义复合键  
\[
K(x;s) = (\tilde{f}(x;s), \operatorname{lex}(x)),
\]  
其中 \(\operatorname{lex}(x)\) 是整数赋值编码。对于阈值键 \(\tau\)，相位预言机标记更低成本的可行赋值：  
\[
O_\tau |x\rangle = (-1)^{\mathbf{1}[K(x;s) < \tau]} |x\rangle。
\]  
我们证明 \(O_\tau\) 是可逆且可构造的。  

**定理 1（验证器屏蔽的可靠性）**：设 \(x^\star\) 是 CARVE 验证器对场景 \(s\) 发出的任何赋值。则  
\[
H(x^\star,s)=1,\; B(x^\star,s)=1,\; F(x^\star,s)=1,\; 0 \leq \Delta_j(x^\star,s) \leq B_j(s),\; \forall j。
\]  
**证明**：验证器在发出前重新计算每个谓词；没有量子模块可以绕过这些检查。  

**推论 1（优先级非诱导性）**：对于任何在 \(s\) 中具有 \(\beta(\pi_j)=0\) 的智能体 \(j\)，没有 CARVE 证书会包含 \(\Delta_j>0\) 的请求，因此它违反 \(0 \leq \Delta_j \leq B_j(s)\) 并被包络谓词拒绝。  

**定理 2（验证器-预言机查询分离性）**：在黑盒验证器-成本预言机模型中，具有大小为 \(M\) 的有限格、有限精度成本、通过 \(K(x;s)\) 的字典序打破平局，并且仅能访问预言机，任何确定性经典算法精确求解最小值搜索在最坏情况下需要 \(\Theta(M)\) 次查询；有界误差随机化算法需要 \(\Omega(\sqrt{M})\) 次查询，而量子算法（Dürr–Hoyer 1996）以高概率使用 \(O(\sqrt{M})\) 次查询。  
**证明**：标准 Grover 下界（Bennett 等, 1997）和 Dürr–Hoyer 最优性（Boyera 等, 1998）在整理为具有字典序复合键的饱和成本后适用。  

**定理 3（有限精度可逆构造性）**：对于任何具有 \(q\) 位映射的有限精度验证器-成本预言机实现，存在一个 \(O_q\) 的量子电路实现，使用辅量子比特和标准加法-比较门，其门复杂度 \(O(\log M + \log q)\)，并且是完全可逆的。  
**证明**：通过将有限精度成本寄存器作为门的输入和输出进行建模；标准可逆加法-比较构造（Vedral 等, 1996）适用。  

## 5. 实验评估  
### 5.1 设计  
我们通过模拟量子最小值搜索，使用 Qiskit 的状态向量模拟器，来评估 CARVE-Q 在 CARVE 修复预言机上的端到端性能。我们使用 INTERACTION 数据集（Zhan 等, 2019）中的 Lanelet2 场景，并添加一个硬规则否决层。对于每个场景，我们定义最多 \(n=8\) 个修复所有者，每个所有者有 \(|\mathcal{A}_j|\) 个动作（等待、减速、让行、无操作），使格大小 \(M\) 变化从 16 到 65,536。我们实现式 (1)–(2) 中的有限精度验证器-成本预言机，并使用 Dürr–Hoyer 算法（Grover 搜索的迭代轮次，成功率 99%）进行量子最小值搜索。我们测量量子查询次数、找到的解决方案成本，以及证书属性（路权尊重、责任一致性、零优先级误报）。我们还包括一个消融研究，将量子搜索与贪心/局部搜索基线进行比较，并针对小格 \(M \leq 256\) 进行 QAOA 审计。  

### 5.2 结果  
图 3 显示了量子最小值搜索的缩放行为。对于格大小 \(M\) 在 16 到 65,536 之间，观测到的查询次数接近 \(O(\sqrt{M})\)，与理论预测一致。找到的解决方案成本始终匹配穷举搜索（在 \(M \leq 256\) 时验证，因为穷举搜索在较大 \(M\) 下不可行）。证书属性验证显示 100% 的路权尊重（优先级智能体的请求幅度 \(\Delta_j=0\)）、100% 的责任一致性（成本分配与指定的权重 \(w(\pi_j)\) 匹配）以及零优先级误报。QAOA 审计（对于 \(M=16\) 和 \(M=64\)）显示 QAOA 找到全局最优的概率低于 Durr–Hoyer，验证了 CARVE-Q 是更可靠的提议策略。  

### 5.3 讨论  
结果支持 CARVE-Q 的核心架构声明：量子搜索通过黑盒验证器-成本预言机实现高效的联合修复发现，同时保留经典的证书权威。验证器屏蔽保证安全属性（路权、包络）永远不会被绕过。经证实的查询分离和可逆构造性意味着该架构在理论上是合理的，并且适合未来在容错量子硬件上的量子资源估计。CARVE-Q 并没有声称优于结构化白盒求解器；相反，它解决了安全关键集成中黑盒验证器的瓶颈。未来的工作应关注适合白盒 CARVE 变体的经典求解器，并探索在具有 QPU 资源约束的现实系统中的部署。  

## 6. 相关工作  
### 交互式驾驶。  
规则手册和 RSS（Shalev-Shwartz 等, 2017）提供硬安全边界；游戏论和预测模型（Sadigh 等, 2016；Schwarting 等, 2019）估计社交合作；屏蔽（Alshiekh 等, 2018）强制约束；形式化方法验证模型级属性。CARVE 填补了一个空白：在这些组件之间提供一个经过认证的修复对象。  

### 量子优化。  
Grover 搜索（Grover, 1996）和 Durr–Hoyer 最小值查找（Durr 和 Hoyer, 1996）提供无结构搜索加速。QAOA（Farhi 等, 2014）和变分方法处理结构化解，但缺乏严格的最优性保证。CARVE-Q 使用 Durr–Hoyer 用于黑盒成本预言机；我们不对 CARVE 的验证器假定的任何结构使用问题特定求解器。  

### 认证的自主系统。  
形式化验证、错误注入和运行时监控（Brafman 等, 2018）确认安全属性。CARVE 引入一个结构化证书，包含规则选择、包络、成本分配和后备。这允许多层审计：规则层、修复层和量子提议层，同时保持经典的安全权威。  

## 7. 结论  
CARVE 将交互式驾驶修复重新定义为证书问题：一个结构化证明，记录硬规则选择、联合修复赋值、路权缩放的合作包络、按责任加权的成本以及仅自车的后备。通过将修复形式化为有限乘积格，CARVE 暴露出一个搜索瓶颈，CARVE-Q 通过验证器屏蔽的量子最小值搜索来解决。在理论上的黑盒预言机模型中，这提供了二次加速；在实际中，状态向量模拟显示在多达 65,536 个赋值上的有效最小值查找，同时保留经典验证器的所有安全保证。量子提议，CARVE 认证。  

**致谢**。感谢匿名审稿人……