Role of entanglement in quantum computation

Arun K. Pati, Sam Braunstein

Research output: Contribution to journalLiterature reviewpeer-review


Quantum computers are believed to surpass their classical counterparts in speed-up and efficiency. However, the origin of this speed-up in quantum algorithms is not yet fully understood. There are indications that entanglement plays an important role in quantum computation. Quantum algorithms that do not involve entanglement appear to require an exponential amount of resources and may be efficiently simulated on a classical computer. Here we discuss the role of entanglement in quantum computation. As an illustration, we consider Grover's algorithm and how entanglement arises in this case. We will show that even though entanglement is present throughout the computation, the change of entanglement per iteration is exponentially small for large databases.
Original languageEnglish
Pages (from-to)295-302
Number of pages8
JournalJournal of the Indian Institute of Science
Issue number3
Publication statusPublished - Jul 2009

Cite this