2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 30 at 16:59
  • $\begingroup$ Not quite. With $2^n$ classical bits, you can represent an integer or some fractions, but not a general $n$ qubit quantum state. $\endgroup$
    – MonteNero
    Jul 31 at 22:43
  • $\begingroup$ @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. $\endgroup$ Aug 2 at 21:59
  • $\begingroup$ @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. $\endgroup$
    – MonteNero
    Aug 3 at 0:16
  • $\begingroup$ @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. $\endgroup$ Aug 3 at 0:24

1 Answer 1

2
$\begingroup$

First, it is useful to realize that quantum computation can be simulated on a classical computer, and any classical computation can be represented as a circuit.

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$.

Now, even more peculiarly, certain quantum computation can be efficiently simulated classically even in the presence of entanglement. This is due to the Gottesman–Knill theorem. The theorem states that some highly entangled circuits can be simulated efficiently on a classical computer.

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.

$\endgroup$
3
  • 1
    $\begingroup$ +1. It’s far from straightforward whether or how much entanglement is necessary for a computational speedup. I liked Looking Glass’s video on this. $\endgroup$
    – Mark S
    Aug 1 at 0:15
  • 1
    $\begingroup$ Although, a corollary of the Gottesman-Knill theorem is that entanglement is not sufficient for any speedup, it’s getting clearer that it is at least necessary, perhaps.. $\endgroup$
    – Mark S
    Aug 1 at 1:17
  • $\begingroup$ @MarkS thanks for the interesting link! I will definitely check it out. There is an interesting paper by Jozsa about the role of entanglement arxiv.org/abs/quant-ph/0201143 $\endgroup$
    – MonteNero
    Aug 1 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.