Skip to main content

Questions tagged [probabilistic-circuits]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
53 views

Is there a sharp phase change on error rate near the error correction threshold?

My rough intuition is that if we want to efficiently compute using noisy gates, the probability of success will exhibit threshold behavior as we cross the error correction threshold. Here is an ...
Geoffrey Irving's user avatar
4 votes
1 answer
117 views

NC0 randomnes vs. non-uniformity

In Ajtai and Ben-Or. A theorem on probabilistic constant depth Computations. STOC '84, 1984 Ajtai and Ben-Or show a non-uniform derandomization of BPAC0. Is there a similar relation known for ...
user68538's user avatar
2 votes
3 answers
147 views

Is the transducer version of BPP closed under complement?

Obviously, recognizing BPP languages is closed under complement. For primes and composite integers both recognizing primes/composites and generating primes/composites can be done in "BPP". Is this ...
botsina's user avatar
  • 101
2 votes
0 answers
95 views

Which computational framework lies behind the Chinese “Social Credit System”?

BACKGROUND The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
Tfovid's user avatar
  • 149
6 votes
0 answers
168 views

Is there a universal gate set for classical probabilistic computing?

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 ...
Sam Jaques's user avatar
1 vote
0 answers
111 views

Solving 0/1 integer programming and solving ACC-of-SYM circuits

I am referring to the proof of Theorem 1.4 in this STOC 2014 paper, https://arxiv.org/abs/1401.2444. In particular my question is about the argument that begins in the 8th line of page 9 where the ...
gradstudent's user avatar
  • 1,453
1 vote
0 answers
81 views

What is the average sensitivity of a quantum circuit with depth $d$ and size $s$?

We have some quantum circuit $C$ with $k$ ancillae and $n$ input bits of depth $d$ and size $s$, and we can define a function $f$ which, for any $x \in \{0, 1\}^n$, is the random variable which is the ...
Samuel Schlesinger's user avatar
4 votes
2 answers
148 views

Is there any notion of sensitivity for probabilistic Boolean functions?

Sensitivity is defined here. Denoting the neighbors of $x$ in the Boolean cube as $N(x)$, we define the sensitivity to be $s(f, x) = \sum_{y \in N(x)} I(f(x) \neq f(y))$, where $I$ is $1$ if the ...
Samuel Schlesinger's user avatar
49 votes
11 answers
3k views

What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

The question I am interested in is related to generating random permutations. Given a probabilistic pairwise swap gate as the basic building block, what is the most efficient way to produce a ...
Joe Fitzsimons's user avatar
4 votes
1 answer
314 views

On Defining Probabilistic/Nondeterministic Circuits

Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit. The standard way of defining probabilistic/nondeterministic circuits ...
Sadeq Dousti's user avatar
  • 16.5k