PRL Quantum speedups are demonstrable compared to any classical computation!
For decades, scientists have been trying to unravel the mystery of how quantum computers are more powerful than classical computers. The origins of this quest can be traced back to Albert Einstein, who referred to quantum mechanical entanglement as "spooky action at a distance".
Now, a team of scientists led by William Fefferman, an assistant professor in the Department of Computer Science at the University of Chicago, has published a breakthrough paper in Physical Review Letters: they have discovered a computational problem in which entanglement directly leads to quantum computations that are vastly faster than any efficient classical algorithm! .
"Complexity Phase Transitions Generated by Entanglement."
Fefferman, along with lead PhD student Soumik Ghosh, IBM researcher Abhinav Deshpande (Fefferman's co-advisor while at the University of Maryland), University of Maryland postdoc Dominik Hangleiter, and University of Maryland/NIST researcher Alexey Gorshkov, in their paper for the first time raise a question and make two points:
- demonstrable speedups in quantum computing compared to any classical computer;
- Entanglement is responsible for the speedup in this particular problem.
Since the early 1990s, there has been theoretical evidence that quantum computers can solve problems that are too difficult for today's classical computers.
One specific example that scientists have been working on is the Shor algorithm, which posits that quantum computers can handle incredibly large numbers (e.g., 10 billion) and quickly decompose them into prime factors. The foundation of modern cryptography that we use on the Internet is based on this intractable problem; therefore, if large quantum computers were to be built, the foundation of cryptography as we know it would be undermined.
However, the Shor algorithm is still only a theoretical result: because a large enough and perfect enough quantum computer has not yet been built.
Now that we are in the NISQ era, some companies have designed certain types of quantum computers, but one of their distinguishing features is that they are a bit 'noisy,'" Ghosh says. Today's quantum computers are believed to be only slightly more powerful than our best classical computers, so sharpening the line between the two is becoming increasingly important."
In the same way that classical computers are made up of bits, quantum computers are made up of individual components called 'quantum bits'. As Ghosh explains, today's quantum bits are so noisy that they are too imperfect and inefficient: a quantum computer would need hundreds of thousands of noise-free quantum bits to solve the nearly impossible problems facing modern computers.
While research institutions like the University of Chicago are making great strides toward building large-scale quantum computers capable of testing these theories, we don't currently have the equipment to do so.
There is still a lot that scientists don't understand about the basic foundations of quantum computing, making it difficult to make progress in this area. From a first principles perspective, we need to answer certain questions:
- Why is quantum computing so powerful?
- Why does Shor's algorithm work?
- What quantum properties lead to these speedups?
After years of research trying to better understand these questions, this work gives an example of a quantum system in which entanglement can be identified as the definitive answer.
Fefferman explains, "Entanglement is a fundamental property of quantum systems, and we think it is very different from anything that happens in the classical world. Moreover, there has always been an intuition that entanglement is one of the fundamental reasons for quantum acceleration."
"It is an important factor in the power of quantum computers, but it is not entirely clear that entanglement is the only reason. This is exactly what our paper tries to address."
Entanglement is a complex and largely misunderstood phenomenon that scientists have been trying to understand for the past hundred years. Albert Einstein, for example, struggled with entanglement and died while trying to give a classical explanation.
Essentially, if two entangled quantum particles are separated by a certain distance, it doesn't matter how far away, what happens to one of the particles affects the behavior of the other at the same time. In the abstract, if you have a large number of particles (or quantum bits, the basic unit of quantum information) and you want to understand the state of the entire system, the concept of entanglement means that you won't get any real information by looking at just one quantum bit - you have to look at the interactions between all of them to get a sense of the state of the subset within the system.
The problem posed by the research team in their paper isn't as useful as Shor's algorithm, but it can be described mathematically and has implications for quantum theory. The point is that entanglement is the root cause of faster computation.
We can talk about the same computational problem with a little bit of entanglement, then a little more, and so on," Fefferman says. What's exciting is that when this entanglement reaches a certain threshold, we go from a simple problem for classical computers to a provable puzzle. Entanglement seems to be the reason for the increased difficulty and quantum acceleration. In the past, we have never been able to prove this in a problem like the Shor algorithm."
The authors consider a particular type of quantum state, called a k-regular graph state, and modify it somewhat to isolate entanglement as the main causal factor in the difficulty of classical simulations.
The complement of the lattice graph is an intuitive proof of the resourcefulness of the MBQC (Measurement-Based Quantum Computing) state.
This study is the first step in pinpointing the quantum speedup.
"The next step is to try to generalize this model to more practical quantum computing systems," the research team said.
"We hope to understand what leads to speedups in the types of quantum computers that people design in real life, as well as the types of processes that run using those computers."
Reference link:
[1] https://cs.uchicago.edu/news/uchicago-scientists-make-new-discovery-proving-entanglement-is-responsible-for-computational- hardness-in-quantum-systems/
[2]https://thequantuminsider.com/2023/07/28/uchicago-scientists-show-entanglement-is-responsible-for-computational-hardness-in- quantum-systems/
[3]https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.131.030601
*** Translated with www.DeepL.com/Translator (free version) ***
