A Theory of Nested Cascading in Directed Logic

技术摘要：定向逻辑中的嵌套级联理论

问题陈述
定向逻辑（Directed Logic, DL）利用电子控制的光学元件（光子门）来执行逻辑运算。这些逻辑门具有两个输入端——一个电子控制信号和一个光学数据信号——但只有一个光学输出端。虽然 DL 在一旦电子状态设定后，能够提供实现“以光速处理”的潜力，从而具备速度和能效方面的优势，但一个根本性的局限性阻碍了其可扩展性：即级联问题。由于输出是纯光学的，而控制输入是电子的，将一个逻辑门的输出连接到另一个逻辑门的输入需要将光学信号转换回电子领域。这种转换过程缓慢且耗能，抵消了 DL 的主要优势。

Shamir 和 Hardy 此前的研究提出了一种“嵌套级联”方案，旨在通过递归地将逻辑门的控制变量替换为整个 DL 子电路来绕过这一限制。然而，该方法仅在少数简单案例中得到了演示，缺乏针对任意复杂度的严谨理论证明，也未提供将其扩展到大量逻辑门的清晰算法。此外，该方法相对于布尔公式规模的可扩展性也未得到分析。

方法论
作者开发了一种适用于任意数量逻辑门的通用、严谨的嵌套级联理论。其方法论包括：

1. 算法重构： 作者提出了一种专为可扩展性设计的 Shamir-Hardy 算法变体。他们定义了一个将任何布尔公式（由 AND 和 OR 门组成）转换为 DL 电路的严格程序：

   • 将布尔公式转换为每个逻辑门具有 2 个输入端的二叉树。
   • 应用特定的排序规则：每个逻辑门的最后一个输入和输出通道将被闲置，而其余两个通道则按保序方式进行连接。
   • 构造过程是递归进行的。为了实现一个逻辑门 $a \land b$（或 $a \lor b$），作者使用代表子表达式的 3 端口 DL 电路（$P_a, P_a^{-1}$）替换 2 端口控制元件，并按保序方式连接前两个输出。

2. 基于归纳法的严谨证明： 论文通过两个归纳假设提供了算法有效性的数学证明：

   • (H1) 电路映射： 证明对于任何布尔表达式 $L$，构建的 DL 电路会在第一个光学输出通道评估 $L$，并在第二个通道评估其非 $\bar{L}$，其余通道输出为零。
   • (H2) 精炼映射： 证明将变量递归替换为子表达式的过程会保持电路的逻辑正确性。
   • 基准情况（$n=1$）通过对所有单门和双门配置进行直接枚举得到了验证。

3. 可扩展性分析： 作者分析了光学元件数量（$N_{opt}$）相对于布尔公式中逻辑门数量（$N_{bool}$）的缩放关系。他们区分了布尔公式（中间结果仅使用一次的树结构）和布尔电路（允许共享中间结果的有向无环图 DAG）。由于 DL 在不进行电子转换的情况下无法共享中间光学结果，因此分析侧重于从布尔公式到 DL 电路的映射。

核心结果

• 普适性： 作者严谨地证明了任何由 AND 和 OR 门组成的布尔公式都可以实现为嵌套 DL 电路。该电路在第一个通道输出逻辑结果，在第二个通道输出其非逻辑。
• 可扩展性发现：
  • 线性缩放： 对于特定类别的公式，如合取范式（CNF）和析取范式（DNF），光学元件的数量随逻辑门数量呈线性缩放（$N_{opt} \sim N_{bool}$）。这是通过排列树结构以最小化“倍增槽”中的重复来实现的。
  • 幂律缩放： 对于完全嵌套的二叉树（布尔公式最典型的结构）和进位传递加法器（当作为公式处理时），其缩放遵循幂律而非指数律。数值模拟和解析推导表明，$N_{opt} \sim N_{bool}^{3/2}$。
  • 典型情况与最坏情况： $N_{bool}^{3/2}$ 的缩放既代表了随机布尔公式的典型情况，也代表了公式的最坏情况。
  • 指数背景： 作者指出，虽然 DL 电路的大小随布尔公式的规模呈多项式级增长，但布尔公式本身可能比最优的布尔电路（允许共享）要大得多（呈指数级）。因此，DL 实现方案相对于公式是多项式级的，但相对于最优电路可能是指数级的。

意义与主张
本文声称填补了原始 Shamir-Hardy 提案留下的理论空白。通过提供通用的算法和严谨的归纳证明，作者确立了嵌套级联是实现定向光学中任意布尔逻辑的可行方法，且无需中间电子转换。

这项工作的意义在于证明了在标准递归倍增中担心的“指数爆炸”在一般情况下并不会发生。相反，其复杂度以幂律（$N^{3/2}$）增长，这对于许多应用来说是一个可控的开销。作者得出结论，DL 逻辑的主要困难不在于嵌套过程中变量的重复，而在于无法共享和复用中间结果这一基本特性（这是电子电路中具备的功能，但在纯光学级联中并不具备）。他们认为，需要进行共享的节点是涉及光-电转换或非线性机制的混合架构的自然边界。