<p>Don't forget that even though the fan-in is unbounded, the number of gates is polynomially bounded in the number of variables <span class="math-container">$n$</span> (in the definition of <span class="math-container">$\mathsf{AC}$</span> for instance) .</p>

CC BY-SA 4.0
2019-10-27T05:07:53.980Z
2019-10-27T05:07:53.980Z
Bjørn Kjos-Hanssen
<p>The fan-in of any real-world classical gate is bounded by <span class="math-container">$B := 2^{2^{1000000}}$</span> because if you tried to store <span class="math-container">$B$</span>-many distinct bits of information in the observable universe you would run out of space before you ran out of bits.</p>

<p>This does not mean that there cannot be practical uses for it, as there are plausibly real-world circuits that are well approximated by the unbounded model. This is not dissimilar to the fact that we talk about space as if it was structured like <span class="math-container">$\mathbb{R}$</span> in physics.</p>

<p>There are other ways that this model can be useful in applications as well. <a href="https://cstheory.stackexchange.com/questions/33720/is-unbounded-quantum-fanout-operation-experimentally-feasible">This answer</a> raises the question</p>

<blockquote>
  <p>Is there a realistic quantum architecture which is effectively equivalent to the quantum circuit with unbounded fan-out?</p>
</blockquote>

<p>and claims that the answer is <em>yes</em>. Here, even though the actual circuit cannot be built, something else that is computably equivalent can be. I'm not knowledgeable of quantum algorithms, but it seems obvious to me that there are plausible scenarios where you'd rather work with the circuit model than whatever the real-world model is.</p>

CC BY-SA 4.0
2019-05-29T20:27:32.383Z
2019-05-29T20:27:32.383Z
Stella Biderman
<p>Does the unbounded fan-in circuit model apply in "practical" settings? In other words, are there real-world realisable computers with unbounded fan-in gates?</p>

<p>As I understand, standard silicon ASICs are made of so-called cells where the number of input signals in the largest cells is small (e.g. never exceeds a fan-in of 100).</p>

CC BY-SA 4.0
2019-10-28T19:21:18.070Z
Related question: https://cstheory.stackexchange.com/questions/3624/practical-consequences-of-parity-notin-ac0
Hermann Gruber
CC BY-SA 4.0
2019-10-28T19:22:23.293Z
@Sasho: consider turning your comment into an answer.
Hermann Gruber
CC BY-SA 4.0
2019-05-29T23:29:50.567Z
If you are talking about things like the circuit class $\mathsf{AC}^0$, then I don't think the point of this class is to capture something about the real world. You can see it as a toy model in which to develop lower bound techniques. Also, $\mathsf{AC}^0$ lower bounds were originally motivated by oracle separation results in complexity theory.
Sasho Nikolov
CC BY-SA 4.0
2019-06-04T17:50:38.187Z
AC0 can be seen also as boolean circuits of arbitrary depth but such as alternation between OR and AND is bounded on every input-to-output path.

Alternation between gate is related somehow (but I don't know more actually) to powerconsumption and speed of stabilisation of circuits. So I would say that actually it could be intersting. 
In practice, I doubt any circuits designer use results from circuits complexity.
C.P.
<cc.complexity-theory><circuit-complexity><circuits>
Is the unbounded fan-in model realistic?
Randomblue
# Is the unbounded fan-in model realistic?

(Asked by: username_0 on 2019-05-26)

Does the unbounded fan-in circuit model apply in "practical" settings? In other words, are there real-world realisable computers with unbounded fan-in gates?

As I understand, standard silicon ASICs are made of so-called cells where the number of input signals in the largest cells is small (e.g. never exceeds a fan-in of 100).

**Tags:** cc.complexity-theory, circuit-complexity, circuits

> **Comments:**
> **username_2**: If you are talking about things like the circuit class $\mathsf{AC}^0$, then I don't think the point of this class is to capture something about the real world. You can see it as a toy model in which to develop lower bound techniques. Also, $\mathsf{AC}^0$ lower bounds were originally motivated by oracle separation results in complexity theory.  
> **username_3**: AC0 can be seen also as boolean circuits of arbitrary depth but such as alternation between OR and AND is bounded on every input-to-output path.  Alternation between gate is related somehow (but I don't know more actually) to powerconsumption and speed of stabilisation of circuits. So I would say that actually it could be intersting.  In practice, I doubt any circuits designer use results from circuits complexity.  
> **username_1**: Related question: https://cstheory.stackexchange.com/questions/3624/practical-consequences-of-parity-notin-ac0  
> **username_1**: @Sasho: consider turning your comment into an answer.  

---

## 2 answers

### Answer by username_4 on 2019-10-27. Score: 1

Don't forget that even though the fan-in is unbounded, the number of gates is polynomially bounded in the number of variables $n$ (in the definition of $\mathsf{AC}$ for instance) .


---

### Answer by username_5 on 2019-05-29. Score: 0

The fan-in of any real-world classical gate is bounded by $B := 2^{2^{1000000}}$ because if you tried to store $B$-many distinct bits of information in the observable universe you would run out of space before you ran out of bits.

This does not mean that there cannot be practical uses for it, as there are plausibly real-world circuits that are well approximated by the unbounded model. This is not dissimilar to the fact that we talk about space as if it was structured like $\mathbb{R}$ in physics.

There are other ways that this model can be useful in applications as well. [This answer](https://cstheory.stackexchange.com/questions/33720/is-unbounded-quantum-fanout-operation-experimentally-feasible) raises the question

> Is there a realistic quantum architecture which is effectively equivalent to the quantum circuit with unbounded fan-out?

and claims that the answer is *yes*. Here, even though the actual circuit cannot be built, something else that is computably equivalent can be. I'm not knowledgeable of quantum algorithms, but it seems obvious to me that there are plausible scenarios where you'd rather work with the circuit model than whatever the real-world model is.


---

