6
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ Not sure what you mean by a "coin-flip gate ". Could you give us the truth table for such a gate ? $\endgroup$
    – William Hird
    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$
    – William Hird
    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

0

Reset to default

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.