Universal Quantum Computation with Little Entanglement

We show that universal quantum computation can be achieved in the standard pure-state circuit model while the entanglement entropy of every bipartition is small in each step of the computation. The entanglement entropy required for large-scale quantum computation even tends to zero. Moreover we show that the same conclusion applies to many entanglement measures commonly used in the literature. This includes e.g., the geometric measure, localizable entanglement, multipartite concurrence, squashed entanglement, witness-based measures, and more generally any entanglement measure which is continuous in a certain natural sense. These results demonstrate that many entanglement measures are unsuitable tools to assess the power of quantum computers.

Figure 1

Quantum computation in an $ϵ$ neighborhood of $|0{⟩}^n$. A quantum circuit composed of $T$ gates starts with the input $|0{⟩}^n$ and traces out some path $|0{⟩}^n\to |{\psi }_1⟩\to \cdots \to |{\psi }_T⟩$ in the $n$-qubit Hilbert space $\mathcal{H}$. In principle the $|{\psi }_i⟩$ may be highly entangled. Here we consider quantum computations ${\mathrm{QC}}_{ϵ}$ where the state of the computer is required to be $ϵ$ close to $|0{⟩}^n$ at all times. We show that a ${\mathrm{QC}}_{ϵ}$ still has universal quantum computing power, for any $ϵ=1/\mathrm{poly}(n)$. Every entanglement measure $E$ which is sufficiently continuous will take on small values throughout the computation. Using this approach one shows that universal quantum computation is possible with vanishingly small amounts of entanglement; the argument applies to entanglement entropy and many other entanglement measures.