Cuffaro, Michael (2012) Is Entanglement Sufficient to Enable Quantum Speedup? [Preprint]
Abstract
According to the Gottesman-Knill theorem, any quantum algorithm utilising operations chosen exclusively from a particular restricted set are efficiently simulable by a classical computer. Since some of these algorithms involve entangled states, it is commonly concluded that entanglement is insufficient to enable quantum speedup. As I explain, however, the operations belonging to this set are precisely those which will never yield a violation of the Bell inequalities. Thus it should be no surprise that entangled quantum states which only undergo operations in this set are efficiently simulable classically. What the Gottesman-Knill theorem shows us is that it is possible to use an entangled state to less than its full potential. Nevertheless, there is a meaningful sense in which entanglement is sufficient for quantum speedup: an entangled quantum state provides sufficient physical resources to enable quantum speedup, whether or not one elects to use these resources fully.
Actions (login required)
![[img]](http://philsci-archive.pitt.edu/style/images/fileicons/application_pdf.png)
![[feed]](http://philsci-archive.pitt.edu/style/images/feed-icon-32x32.png){kind=icon}