Quantum Entanglement Identified as Key to Quantum Computing Speedup, Reveals University of Chicago Study

A team of scientists led by Assistant Professor William Fefferman from the University of Chicago’s Department of Computer Science have made a significant discovery in the field of quantum computing. They have identified a computational problem where quantum entanglement, a phenomenon famously described by Albert Einstein as “spooky action at a distance”, is directly responsible for a significant speedup in quantum computation compared to any efficient classical algorithm. This discovery was published in a paper titled “Complexity phase transitions generated by entanglement”.

The team, which includes Ph.D. student Soumik Ghosh, IBM researcher Abhinav Deshpande, University of Maryland postdoc Dominik Hangleiter and University of Maryland/NIST researcher Alexey Gorshkov, have demonstrated that there is a provable quantum speedup over any classical computer, and that entanglement is causing the speedup in this particular problem. This discovery is a significant step forward in understanding the power of quantum computing.

Theoretical Evidence and Practical Challenges

Since the early 90’s, there has been theoretical evidence that quantum computers can solve problems that are too difficult for today’s classical computers. One specific example is Shor’s algorithm, which suggests that quantum computers can quickly break incredibly large numbers into their prime factors. This is a difficult problem for classical computers to solve and forms the basis of modern cryptography. However, Shor’s algorithm is still a theoretical result because large enough and perfect enough quantum computers have not yet been built.

Currently, we are in the era of NISQ — which stands for noisy intermediate scale quantum computing. Some companies have designed certain types of quantum computers, but they are a bit noisy. Today’s quantum computers are believed to be just slightly more powerful than our best classical computers. A quantum computer would need hundreds of thousands of noiseless qubits to solve the near-impossible problems facing modern computers. While progress is being made toward building large scale quantum computers, we don’t currently have devices capable of doing so.

The Role of Entanglement in Quantum Computing

Entanglement is a fundamental property of quantum systems. There’s always been an intuition that entanglement is one of the root causes of quantum speedups. It’s an important contributor to the power of quantum computers, but it wasn’t totally clear that entanglement was the sole cause. The team’s paper addresses this issue.

Entanglement is a complex and largely misunderstood phenomenon that scientists have been trying to understand for the last hundred years. If you have two entangled quantum particles that are separated by a distance, what happens to one particle can simultaneously affect the behavior of the other particle. If you have a large number of particles– or qubits as the basic unit of quantum information– and you want to understand the state of this entire system, the idea of entanglement implies you won’t get any real information by looking at just one qubit; you have to look at the interactions between all of the qubits to understand the state of subsets within the system.

The Impact of Entanglement on Computational Speed

The problem the team presented in the paper is not useful in the same sense that Shor’s algorithm is, but it can be mathematically described and is meaningful to quantum theory. The key point is that entanglement can be seen to be the root cause of the computational speedup.

Fefferman explains that when the entanglement reaches a certain threshold, we go from an easy problem for a classical computer to a provably hard problem. Entanglement seems to be causing the increased difficulty and quantum speedup. This is the first time that entanglement has been shown to cause a speedup in a problem like Shor’s algorithm.

Future Steps in Quantum Computing Research

This research is part of the first steps in the broader context of pinpointing quantum speedups. The next step, according to Ghosh, is trying to generalize this model to more practical systems of quantum computation. The aim is to understand what is causing speedups for the types of quantum computers that people are designing in real life and the type of processes that will be run using those computers.

“Right now we are in the era of NISQ — which stands for noisy intermediate scale quantum computing,” said Ghosh. “Some companies have designed certain types of quantum computers, but one defining feature is that they are a bit noisy. Today’s quantum computers are believed to be just slightly more powerful than our best classical computers, so it’s becoming more significant to sharpen that boundary between the two.”

“Entanglement is a fundamental property of quantum systems, and it’s a property that we think is very different from anything that happens in the classical world,” Fefferman explained. “Furthermore, there’s always been an intuition that entanglement is one of the root causes of these quantum speedups. It’s an important contributor to the power of quantum computers, but it wasn’t totally clear that entanglement was the sole cause. That’s what our paper is trying to address.”

“We can talk about the same computational problem with a little bit of entanglement, and then a little bit more, and so on,” said Fefferman. “The exciting part is that when this entanglement reaches a certain threshold, we go from an easy problem for a classical computer to a provably hard problem. Entanglement seems to be causing the increased difficulty and quantum speedup. We’ve never been able to show that in a problem like Shor’s algorithm.”

Quick Summary

A team of scientists led by Assistant Professor William Fefferman from the University of Chicago’s Department of Computer Science have discovered a computational problem where quantum entanglement directly causes a significant speedup in quantum computing over classical algorithms. This research is a crucial step in understanding the power of quantum computing and the role of entanglement, potentially paving the way for more practical applications of quantum computers.

• A team of scientists led by Assistant Professor William Fefferman from the University of Chicago’s Department of Computer Science, including Ph.D. student Soumik Ghosh, IBM researcher Abhinav Deshpande, University of Maryland postdoc Dominik Hangleiter and University of Maryland/NIST researcher Alexey Gorshkov, have published a paper in the Physical Review Letters.
• The paper, titled “Complexity phase transitions generated by entanglement”, presents a computational problem where quantum entanglement is directly responsible for a significant quantum computational speedup over any efficient classical algorithm.
• Quantum computers are believed to be slightly more powerful than classical computers, but current quantum computers are noisy and imperfect, requiring hundreds of thousands of noiseless qubits to solve complex problems.
• The team’s research provides an example of a quantum system where entanglement can be identified as the clear cause of quantum speedups, a question that has puzzled scientists for decades.
• The next step in the research is to generalise this model to more practical systems of quantum computation, to understand what causes speedups for the types of quantum computers being designed in real life.

Read More from UChicago.