A quantum computer that doesn't use entangled qubits has the same computational power as a classical one?

Question

Is the statement in the question correct? I would love to receive an explanation as to why it is or isn't.

I have a computer science degree background and I am a beginner learning the fundamental of QC from scratch.

Answer 1

Assuming you are talking about starting from a pure state, your statement is true. There are two steps to the proof:

• Show that a system without entanglement can implement any classical computation.

• Show that a system that remains separable can be simulated by a classical computation, proving that there are no calculations it can implement that a classical computer cannot.

The first is straightforward. Every classical computation can be written as a classical reversible computation. The Toffoli gate (controlled-controlled-not) is universal for classical reversible computation, so any circuit can be entirely decomposed in terms of that. But Quantum computers can implement the Toffoli gate, so they can implement any classical computation, and the state of the system at any intermediate point must be the same as in the classical computation, and therefore separable.

The second is also reasonably straightforward. If we know that every qubit remains separable, then we can hold in memory just the set of $N$ qubit states, comprising $N$ 2-element normalised complex vectors (as compared to the general case of a single $2^N$ element normalised complex vector). Whatever set of gates we use to describe the computation will act on some finite number of qubits, say $k$ at maximum (independent of $N$). So each computational step requires the action of a $2^k\times 2^k$ matrix, which we just have to apply to the appropriate set of $k$ separable states. We extract the separable states at the end, and continue. The total simulation time is $O(NM)$ for a sequence of $M$ gates on a classical computer.

Answer 2

The linked question in the comments is akin to "can we efficiently simulate a quantum computer without entanglement?", while the question of the OP is more akin to "if we handicap a quantum computer to not use entanglement, is such a quantum computer equivalent to a classical computer?"

@DaftWullie's great answer already shows that such a weakened quantum computer is equivalent up to a polynomial overhead to a classical "reversible" computer. That is, he mentions that the Toffoli ($\mathsf{CCNOT}$) gate is universal for classical reversible computation, much as a $\mathsf{NAND}$ gate is for classical irreversible computation. Because as we know all quantum gates are reversible, the OP's question can also be framed as "is reversible computation equivalent to irreversible computation?"

Clearly a $\mathsf{CCNOT}$ gate can efficiently realize a $\mathsf{NAND}$ gate; a little though shows that a $\mathsf{NAND}$ gate can efficiently realize a $\mathsf{CCNOT}$ gate. However there is some non-trivial overhead in converting an algorithm that uses irreversible computation to one that uses reversible computation.

For example, this Quanta magazine article describes how classical irreversible computation can recursively perform operations, whereas the requirement of quantum/reversible computation to not delete information has hampered many quantum algorithms' ability to do such recursion.

The Quanta article describes a breakthrough by Craig Gidney of using "tail call recursion" in reversible computation, which as I understand it would be applicable to many recursive processes; however, there may still be a non-zero overhead in making such computations.

---

Furthermore, there are some non-trivial applications of physical qubits that do not seem to absolutely require entanglement - these also don't have a counterpart in the classical world.

For example, the BB84 quantum key distribution protocol does not require the two parties Alice and Bob to share any entanglement. Wiesner's quantum money, from which BB84 was developed, also does not require such entanglement.

These topics are usually introduced in lectures in quantum information/quantum computation before introduction of Deutsch-Josza, Shor, etc. because they have no classical counterpart, and also do not have "spooky action at a distance" - i.e., entanglement.