PaperlayerView exact revision on arXiv

Source-linked AI summary

A Theory of Nested Cascading in Directed Logic

Ihar Babushkin, Oliver Melchert, Ayhan Demircan, Uwe Morgner

arXiv:2610.02930v1physics.opticscs.CCcs.ET

TL;DR

Earlier nested-cascading work covered only a few examples and left its proof and scaling unclear. This paper gives a rigorous general construction for Boolean formulas and finds power-law scaling with an exponent close to 3/2, with linear scaling in important cases.

  • Problem

    The nested-cascading proposal had been checked only on a few examples, without proof or truth tables, and its extension to larger gate counts was unclear.

    Source: Formulating the procedure · p. 3

  • Method

    The paper specifies an unambiguous procedure and proves it by induction, directly verifying 72 configurations; AND and OR suffice once negated variables are available.

    Source: INTRODUCTION · p. 2, CONCLUSIONS AND DISCUSSION · p. 10

  • Results

    A power-law exponent close to 3/2 describes worst-case and typical DL-element scaling relative to Boolean formulas; conjunctive and disjunctive normal forms scale linearly with formulas and circuits.

    Source: CONCLUSIONS AND DISCUSSION · p. 10

  • Takeaways & Limitations

    Nested cascading reflects formula/tree complexity, which can be exponentially larger than the complexity of the corresponding optimal Boolean circuit.

    Source: CONCLUSIONS AND DISCUSSION · p. 10

    Because sharing and reuse are unavailable, the adder’s Boolean-formula and optical-element counts are exponential in n, even though optical-element growth is polynomial in formula size.

    Source: Adder circuit · p. 9

Abstract

from arXiv · show

In directed logic (DL), electronically controlled optical elements serve as photonic gates. Such electro-optical elements are of mixed nature: they have two inputs--electronic and optical--but only one, optical, output. This makes cascading such gates without repeated conversion between optical and electronic representations cumbersome. This problem can be largely overcome using the nested cascading scheme proposed by Shamir and Hardy [Opt. Express, 17, 150 (2007)]. Although promising as a solution to the cascading problem, the Shamir-Hardy scheme has so far been proved or implemented only for a few simplest cases. Here, we develop a general rigorous theory of nested cascading, valid for an arbitrary number of gates. We propose a variant of the algorithm which easily extendable to large number of gates, and rigorously prove its validity. Furthermore, we analyze how nested cascading scales with the size of the corresponding Boolean formula. We show that good (linear) scalability is guaranteed in many important cases, while the average scaling with respect to the corresponding Boolean formulas is only moderately polynomial, with an exponent of approximately 3/2. Yet, the worst-case scaling remains exponential with respect to more general Boolean circuits allowing sharing and reuse of intermediate results.

INTRODUCTION

Directed logic uses electronically controlled optical networks for logical operations, but their mixed electronic and optical inputs make cascading cumbersome. The paper gives a rigorous nested-cascading theory and analyzes its scaling with Boolean formulas.

INTRODUCTION

  • Electronic computing's energy use and data-transfer bottleneck motivate optical logic, but directed-logic gates' mixed electronic and optical inputs make cascading awkward.The electronic signal controls the optical path, while the gate output is optical.Source: INTRODUCTION · p. 1
  • Shamir and Hardy proposed recursively replacing a gate with a circuit implementing it, but the design was cumbersome and lacked proof for arbitrary gate counts.The proposal had been checked only on a few configurations.Source: INTRODUCTION · p. 2
  • The paper develops a rigorous, general nested-cascading procedure; with variable negations available, AND and OR alone represent any Boolean formula.The authors therefore focus on AND and OR gates.Source: INTRODUCTION · p. 2
  • For Boolean formulas, typical and worst-case gate counts scale with a power-law exponent near 3/2, while many important cases scale linearly.The paper frames scalability in terms of the corresponding Boolean expression.Source: INTRODUCTION · p. 2

Formulating the procedure

The procedure maps AND/OR formulas to directed-logic circuits by recursively nesting gates with a fixed channel-connection rule. The resulting circuit is run with a prescribed input and yields the formula and its negation on its first two outputs.

Formulating the procedure

  • The gate replacement leaves the last input and output unused and connects the remaining channels in order, preserving a consistent nesting rule.This variant is not fully topologically equivalent to Hardy and Shamir’s, though differences are presumed confined to paths never traversed.Source: Formulating the procedure · pp. 4–5, Figure 3 · p. 4
  • Build the root gate, then recursively replace controlled two-port elements with three-port gates as each tree branch is refined.At each step, connect the first two outputs in order and leave the last channel hanging as a new channel.Source: Formulating the procedure · p. 4
  • First convert the formula to a binary tree, arranging chains such as a ∧ b ∧ c as a ∧ (b ∧ c), not (a ∧ b) ∧ c.The latter configuration is disallowed by the procedure.Source: Formulating the procedure · p. 4
  • After setting each operator according to its Boolean variable, apply input vector (1, 0, 0, . . . , 0) to the circuit.The signal is nonzero in the first channel and zero in all others.Source: Formulating the procedure · p. 4
  • The first two outputs carry the negation of the formula and the formula, respectively; all remaining outputs are zero.A circuit for L = (a∧b)∨c illustrates the construction, with a more complex example also given.Source: Formulating the procedure · p. 5, Figure 4 · p. 5

Universality proof by induction

The proof establishes both that the nesting algorithm evaluates Boolean expressions and that it preserves correctness when a variable is refined into a subexpression. It uses direct verification for the base case and induction for arbitrary nesting depth.

Universality proof by induction

  • The proof separates circuit mapping from refinement mapping: the circuit must evaluate each expression, and nesting must implement replacing a variable with a subexpression.The first two outputs represent the formula and its negation, while all other outputs are zero.Source: Universality proof by induction · p. 5
  • For the base case, direct checks of all single- and two-gate configurations verify both hypotheses.Table I and Appendix A give the output expressions, circuits, and channel values for these cases.Source: Universality proof by induction · p. 6, Table I · p. 6
  • Assuming both hypotheses through depth n, replacing a variable with a depth-1 subexpression preserves correct evaluation and refinement mapping at depth n + 1.The construction replaces the controlled two-port device and its inverse with the subexpression’s three-port DL realization.Source: Universality proof by induction · pp. 5–6

SCALABILITY OF THE PROCEDURE

The section evaluates optical-element growth relative to Boolean-formula size, distinguishing formulas from circuits that share intermediate results. The nested construction can avoid repeated growth in shallow cases by placing continuation in the non-duplicating slot.

SCALABILITY OF THE PROCEDURE

  • General Boolean circuits can share and reuse intermediate results, unlike formulas, so the analysis measures optical elements against the corresponding formula size.The section notes that reuse in general circuits requires converting an optical signal back into an electronic representation.Source: SCALABILITY OF THE PROCEDURE · pp. 7–8
  • At each expansion, adding gates to the duplicating slot risks doubling device size, but depth-1 expressions can be arranged for constant overhead.Right-branching fan-in-2 forms put the continuation in the non-duplicating slot and leave the duplicating slot only at terminal variables.Source: SCALABILITY OF THE PROCEDURE · p. 7
  • Figure 7 gives an example circuit for a six-variable Boolean formula using the optimal right-branching form whenever possible.The caption specifies that the main output channels contain L and its complement, while all other output channels contain zeros.Source: Figure 7 · p. 8

Conjunctive and disjunctive normal forms

For conjunctive normal forms, each OR clause has favorable scaling, and the nested construction preserves linear scaling across the form. The same reasoning applies to disjunctive normal forms.

Conjunctive and disjunctive normal forms

Fully nested binary trees

Fully nested alternating binary trees duplicate a subcircuit at every level, yet their optical-element growth follows a power law rather than the naively expected exponential scaling. An analytical scaling is reported as close to the numerical result.

Fully nested binary trees

  • Numerical results for fully nested alternating trees through depth n = 7 show power-law scaling rather than the naively expected exponential growth.At each level, one subcircuit is duplicated because both gate inputs are nontrivial subexpressions.Source: Fully nested binary trees · pp. 8–9
  • For a depth-2 tree, duplication makes the lower-level element count grow by a factor of three instead of two, providing an analytical route to the power law.Source: Fully nested binary trees · p. 9
  • The analytical scaling is reported as quite close to the numerically obtained power law.The numerical comparison considers trees through depth n = 7.Source: Fully nested binary trees · p. 9

Adder circuit

The section describes the ripple-carry adder’s sum and carry computation, then compares the nested DL gate count with the corresponding Boolean formula. For n ≤ 7, the observed gate-count scaling is a power law, but the comparison depends on representing the adder as a formula without reuse.

Adder circuit

  • Each sum bit depends on its input bits and incoming carry, and the carry is generated recursively as c_i+1 = (a_i ∧ b_i) ∨ (a_i ∧ c_i) ∨ (b_i ∧ c_i), with c_1 = 0.The section focuses on the final carry-out c_n+1.Source: Adder circuit · p. 9
  • For n ≤ 7, the adder’s numerically observed Nopt scaling follows a power law, with an exponent close to the fully nested tree’s and a smaller prefactor.The paper reports that Nopt for the adder is strictly smaller than Nopt for the full binary tree.Source: Adder circuit · p. 9
  • For the recursively expanded adder formula, both Nbool and Nopt are exponential in n, while Nopt grows polynomially with Nbool.A Boolean circuit that allows intermediate carry results to be shared would instead have Nbool ∼ n.Source: Adder circuit · p. 9

Scalings for worst and most typical cases

The full binary tree represents the paper’s typical Boolean formula shape, so its scaling is treated as close to both typical and worst-case. The reported DL-to-formula scaling does not account for channel-removal optimizations and may compare against formulas much larger than circuits with sharing.

Scalings for worst and most typical cases

  • The full binary tree is treated as both the most typical formula shape and a close proxy for worst-case Nopt(Nbool) scaling.The paper notes that most Boolean formulas are full binary trees, while other formulas are trees with some edges removed.Source: Scalings for worst and most typical… · p. 9
  • The scaling compares DL circuit size with Boolean formula size, which can be exponentially larger than circuit size when intermediate results can be shared.The authors also note that removing channels that do not affect the main channel c1 could reduce the circuit, but analyzing this optimization is beyond the paper’s scope.Source: Scalings for worst and most typical… · p. 9

CONCLUSIONS AND DISCUSSION

The paper gives a rigorous nested-cascading procedure for AND/OR Boolean formulas and analyzes its gate-count scaling. It reports power-law scaling relative to formulas, while noting that sharing and reuse in general Boolean circuits remain unavailable in pure optical DL.

CONCLUSIONS AND DISCUSSION

  • The authors provide an unambiguous cascading procedure and rigorous correctness proof for fan-in-2 AND/OR formulas under specified composition rules.Their inductive proof directly tests 72 elementary and two-gate configurations.Source: CONCLUSIONS AND DISCUSSION · p. 10
  • Pure optical DL circuits cannot share or reuse intermediate results, whereas Boolean formulas also lack sharing and can be exponentially larger than corresponding optimal circuits.The nested construction therefore reflects formula-tree complexity rather than the complexity of more general Boolean circuits.Source: CONCLUSIONS AND DISCUSSION · p. 10
  • The nested DL construction has power-law scaling with an exponent close to 3/2 relative to Boolean formulas; CNFs and DNFs scale linearly with both their formulas and corresponding circuits.The paper also reports similar scaling for algorithms such as addition.Source: CONCLUSIONS AND DISCUSSION · p. 10
  • The authors identify points where sharing and reuse become necessary as natural places to use mixed architectures, including optical-to-electronic back-conversion or nonlinear mechanisms.The proposed alternatives include optical nonlinearities and other nonlinear mechanisms.Source: CONCLUSIONS AND DISCUSSION · p. 10

Appendix A: truth tables and graphical representations of 1- and 2-operator Boolean formulas

Appendix A presents truth tables and graphical realizations for one- and two-operator AND/OR formulas. It identifies one configuration, (a ∧ b) ∧ c, whose truth table does not match the intended composition.

Appendix A: truth tables and graphical representations of 1- and 2-operator Boolean formulas

  • Figures 9–16 collect truth tables and graphical representations for one- and two-operator Boolean formulas; (a ∧ b) ∨ c is shown earlier in Fig. 6.The appendix uses the same figure denotations as Fig. 6.Source: Appendix A · p. 11
  • Figure 9 presents direct circuits and corresponding outputs for the one-gate operations a ∧ b and a ∨ b.The figure gives graphical realizations above the output channels.Source: Figure 9 · p. 11
  • Figure 10 shows the direct circuit and corresponding outputs for a ∨ (b ∧ c).Source: Figure 10
  • Figures 11 and 12 show the direct circuits and outputs for (a ∨ b) ∧ c and a ∧ (b ∨ c).Source: Figure 11 · p. 12, Figure 12 · p. 12
  • Figure 13 shows a direct circuit and outputs for a ∧ (b ∧ c), while Figure 14’s attempted circuit for (a ∧ b) ∧ c is the only case whose truth table misses the intended composition.Source: Figure 13 · p. 13, Figure 14
  • Figures 15 and 16 show direct circuits and corresponding outputs for a ∨ (b ∨ c) and (a ∨ b) ∨ c.Source: Figure 15 · p. 14, Figure 16
Loading 2610.02930v1…