# Can there be an equivalent classical circuit for a quantum circuit?

It is known that any classical circuit or algorithm can be implemented on a quantum computer using universal quantum gates. My question is, can there be a circuit with classical statistics which are equivalent to that of measurement probabilities of computational basis states in a quantum circuit?

I understand my question might point to the simulability of quantum circuits classically as knowledge of the probabilities of the computational basis states can lead to the full reconstruction of the quantum states. In contrast to this, I was curious if there could be classical (or stochastic) circuits with equivalent transition probabilities.

• You can encode a general state of $n$ qubits using $2^n$ classical bits. So, in principle, you can simulate any quantum circuit using a classical circuit. Jul 30 at 16:59
• Not quite. With $2^n$ classical bits, you can represent an integer or some fractions, but not a general $n$ qubit quantum state. Jul 31 at 22:43
• @MonteNero Yes, I should have clarified, I just meant that the scaling goes as $2^n$, if you want to represent a real number with the precision afforded by $p$ bits then you'd need $2p\cdot 2^n$ bits to represent an $n$ qubit state. Aug 2 at 21:59
• @FreeAssange, again not quite. If you use $p$ bits for precision (and I suppose you actually meant bits for mantissa and exponent) then you don't count sign bits. So with $2p2^n$ you still can't represent an arbitrary $n$-qubit quantum state. Aug 3 at 0:16
• @MonteNero Umm, no, I meant $p$ bits to represent a real number including everything -- the mantissa (including the sign-bit) and the exponent. The point being you need $2^n$ complex numbers to represent a general $n-$qubit state. If you can represent a real number using $p$ bits then you can represent a general $n-$qubit state using $2p\cdot 2^n$ bits. Aug 3 at 0:24

Interestingly, if a quantum circuit does not have entanglement, it can be simulated efficiently on a classical computer. Due to the absence of entanglement, each qubit in a quantum circuit is independent of any other qubit. Hence each qubit's state can be represented by a 2d complex vector. Mathematically, for a quantum circuit $$U$$ with no entanglement and an $$n$$-qubit product state $$|\psi\rangle = |\psi_1\rangle \otimes \cdots \otimes |\psi_n\rangle$$, we can write: $$U|\psi\rangle = U_1 |\psi_1\rangle\otimes \cdots \otimes U_n |\psi_n\rangle,$$ where $$U_i$$ are $$2\times2$$ complex unitary matrices such that $$U_1\otimes \cdots \otimes U_n = U$$. Such computation can be done in polynomial time on a classical computer because we just need to do $$n$$ matrix multiplications. Moreover, it can be done in parallel, and it will take constant time in $$n$$.
In general, we can represent an $$n$$-qubit quantum state by a $$2^n$$ complex unit vector. Of course, generally, we have an exponential overhead when trying to simulate an $$n$$-qubit quantum system. So while simulating quantum circuits is possible, the classical circuit will take exponentially many resources.