<p>We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum circuits. However, what about classical probabilistic circuits? </p>

<p>It seems like if you had a "coin-flip" gate (takes no input/any input and produces 0 or 1, each with probability 1/2) and NAND, you could build any probabilistic circuit you want (up to some level of precision) with a rejection sampling procedure. The desired probabilistic circuit can be seen as a set of deterministic circuits, chosen according to some distribution; use rejection sampling to simulate that distribution and then apply the required deterministic circuit.</p>

<p>(by the same argument, any gate that produces a fixed, non-trivial probability distribution, plus NAND, would be universal).</p>

<p>Is this a question that has been looked into? Any results that I can cite?</p>

CC BY-SA 4.0
2019-03-11T15:16:23.907Z
Not sure what you mean by a "coin-flip gate ". Could you give us the truth table for such a gate ?
William Hird
CC BY-SA 4.0
2019-03-11T16:15:11.657Z
I don't know how to represent a probabilistic gate with a truth table. A "coin-flip gate" would be a 1/2 probability of an identity gate, and a 1/2 probability of a NOT gate
Sam Jaques
CC BY-SA 4.0
2019-03-17T19:28:38.503Z
Well Sam, here is your chance to become famous, invent a whole new form of truth table for the gate, it will be named the " Jaques Gate"    LOL
William Hird
CC BY-SA 4.0
2023-06-24T16:01:02.410Z
What makes you nervous about including a coin-flip gate in your definition of universal gates?  You could I think relatively easily define a class based on circuits comprising a polynomial number of {NAND, COIN-FLIP} gates, making sure to include the required uniformity conditions, and then show that your class, so defined, is equal to BPP.  This is the approach that Yao and Bernstein/Vazirani did in the '90's for BQP (but they were fuzzy about what kinds of gates they originally allowed).
Mark S
CC BY-SA 4.0
2023-06-25T21:22:39.327Z
The end result of this is in the introduction to my master's thesis: https://uwspace.uwaterloo.ca/handle/10012/14612. Ultimately I decided to represent computational states as vectors with $\ell_1$-norm equal to 1, and the gates as row-stochastic matrices. I haven't proven any complexity class results, though; that could be an interesting project.
Sam Jaques
CC BY-SA 4.0
2023-06-25T21:23:56.407Z
But, you can use the classic result that all row-stochastic matrices are a convex combination of permutations, and since (a) any convex combination can be obtained with the coin-flip gates; (b) any permutation can be obtained with NAND, then indeed this set is universal.
Sam Jaques
<quantum-computing><circuit-complexity><probabilistic-circuits>
Is there a universal gate set for classical probabilistic computing?
Sam Jaques
# Is there a universal gate set for classical probabilistic computing?

(Asked by: username_0 on 2019-03-11)

We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum circuits. However, what about classical probabilistic circuits?

It seems like if you had a "coin-flip" gate (takes no input/any input and produces 0 or 1, each with probability 1/2) and NAND, you could build any probabilistic circuit you want (up to some level of precision) with a rejection sampling procedure. The desired probabilistic circuit can be seen as a set of deterministic circuits, chosen according to some distribution; use rejection sampling to simulate that distribution and then apply the required deterministic circuit.

(by the same argument, any gate that produces a fixed, non-trivial probability distribution, plus NAND, would be universal).

Is this a question that has been looked into? Any results that I can cite?

**Tags:** quantum-computing, circuit-complexity, probabilistic-circuits

> **Comments:**
> **username_1**: Not sure what you mean by a "coin-flip gate ". Could you give us the truth table for such a gate ?  
> **username_0**: I don't know how to represent a probabilistic gate with a truth table. A "coin-flip gate" would be a 1/2 probability of an identity gate, and a 1/2 probability of a NOT gate  
> **username_1**: Well Sam, here is your chance to become famous, invent a whole new form of truth table for the gate, it will be named the " Jaques Gate"    LOL  
> **username_2**: What makes you nervous about including a coin-flip gate in your definition of universal gates?  You could I think relatively easily define a class based on circuits comprising a polynomial number of {NAND, COIN-FLIP} gates, making sure to include the required uniformity conditions, and then show that your class, so defined, is equal to BPP.  This is the approach that Yao and Bernstein/Vazirani did in the '90's for BQP (but they were fuzzy about what kinds of gates they originally allowed).  
> **username_0**: The end result of this is in the introduction to my master's thesis: https://uwspace.uwaterloo.ca/handle/10012/14612. Ultimately I decided to represent computational states as vectors with $\ell_1$-norm equal to 1, and the gates as row-stochastic matrices. I haven't proven any complexity class results, though; that could be an interesting project.  
> **username_0**: But, you can use the classic result that all row-stochastic matrices are a convex combination of permutations, and since (a) any convex combination can be obtained with the coin-flip gates; (b) any permutation can be obtained with NAND, then indeed this set is universal.  

---

## 0 answers

