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?

  • $\begingroup$ Not sure what you mean by a "coin-flip gate ". Could you give us the truth table for such a gate ? $\endgroup$ Mar 11, 2019 at 15:16
  • 1
    $\begingroup$ 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 $\endgroup$
    – Sam Jaques
    Mar 11, 2019 at 16:15
  • 1
    $\begingroup$ 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 $\endgroup$ Mar 17, 2019 at 19:28
  • $\begingroup$ 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). $\endgroup$
    – Mark S
    Jun 24 at 16:01
  • $\begingroup$ The end result of this is in the introduction to my master's thesis: 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. $\endgroup$
    – Sam Jaques
    Jun 25 at 21:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.