電路寬度的定義是什麼

我們在大多數情況下都會考慮電路的大小和深度，但最近我讀了一些考慮電路“寬度”的論文，所以我想知道電路寬度的定義是什麼？我搜尋了一些定義，但似乎沒有明確定義，您能否提供一個連結或電路寬度的正式定義（您可以以姚氏亂碼電路為例）？

電路的寬度在某種意義上與您似乎已經熟悉的電路*深度的概念有關。*要理解這些概念，以電路圖的形式考慮電路的圖形表示非常有幫助。我在這裡畫了一個這樣的圖表的例子：

電路的深度鬆散地說是我們可以將電路劃分成的層數，因此層中的所有門 $ i $ 如果我們有層中所有門的輸出，則可以評估 $ 0,\ldots,i-1 $ . 上圖是一個三層的電路，即電路的深度為三。

另一方面，電路的寬度是具有最多柵極的層中的柵極數量。所以在範例圖中，寬度也是三，因為頂層有三個門。

在安全計算領域（包括 Yao 電路），電路的寬度通常很有趣，因為它說明了電路評估的可並行性。即，具有寬層的電路可以更好地並行化。

來自單向函式的自適應安全亂碼電路：

請注意，如果我們將電路視為表示圖靈機或 RAM 計算，則電路的寬度 w 對應於計算的輸入大小 n、輸出大小 m 和空間複雜度 s的最大值。

空間複雜度表示需要多少空間（記憶體，通常是主記憶體，因此是 RAM）才能執行算法並包括輸入的大小。

基本上 with 是算法狀態的最大大小，其中第一個狀態是輸入，最終狀態是算法的輸出。

通常這些類型的測量由比特數或字節數表示，但它也可以與其他單位一起使用，例如塊。

引用自：https://crypto.stackexchange.com/questions/38095