# Questions tagged [circuits]

A computation model in which the computation is described via circuits of various logic gates.

15 questions
Filter by
Sorted by
Tagged with
5k views

### Universality of the Toffoli gate

Regarding the quantum Toffoli gate: is it classicaly universal, and if so, why? is it quantumly universal, and why?
1k views

### How to understand the SR Latch

I can't wrap my head around how the SR Latch works. Seemingly, you plug an input line from R, and another from S, and you are supposed to get results in $Q$ and $Q'$. However, both R and S require ...
249 views

### Creating a logical circuit

Task: Design a 2 bit comparator. Input: 2x 2 bit (I take it as 2 2-bit values, let them be unsigned for simplicity) Output: 1 if result input1>input2 is true, 0 otherwise Develop truth table and ...
880 views

### Given a Turing machine , How to construct a efficient boolean circuit?

The proof of $P\subseteq P_{\\poly}$, Let $M$ is a Turing machine with $T(n)$ is running time and goal here is to design a boolean circuit of size $O(T(n))$ (for more detail see Arora and Barak page ...
321 views

### What is the relation between arithmetic circuits and straight line programs?

One definition of arithmetic circuits is as follows: An arithmetic circuit $\Phi$ over the field $\mathbb F$ and the set of variables $X$ usually, $X = \{x_1, \dots , x_n\}$) is a directed acyclic ...
127 views

### Simple example of exponential gap between monotone and non-monotone circuits

Is there a simple example of a Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone circuit? ...
96 views

### Polynomial Identity Testing Evaluating a polynomial on a circuit

Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of ...
284 views

### Is it possible to make N-way Controlled-NOTs out of Toffoli gates, without extra work bits?

I'm working on exercise 4.29 of Nielsen and Chuang: Find a circuit containing O(n^2) Toffoli, CNOT, and single qubit gates which implements a $C^n(X)$ gate (for n >3), using no work qubits. As ...