Quanta magazine features recent work by John Preskill, Hsin-Yuan (Robert) Huang, IQIM graduate student Chi-Fang (Anthony) Chen, and DuBridge Postdoctoral Scholar Leo Zhou toward identifying a viable problem that confers a quantum advantage — something only a quantum computer can solve. Only then, scientists argue, will the technology be seen as essential. By studying the energy of certain quantum systems, they discovered a specific and useful question that is easy for a quantum machine to answer, but still difficult for a classical one. They’ve been looking for decades. “Part of the reason it’s challenging is because classical computers are pretty good at a lot of the things they do,” said John Preskill, a theoretical physicist at the California Institute of Technology.
“This is major progress on quantum algorithms theory,”said Sergey Bravyi, a theoretical physicist and computer scientist at IBM. “Their result is a quantum advantage for a problem with relevance to chemistry and material sciences.”
Carlos Arrojo for Quanta Magazine
Read the full Quanta article Physicists Finally Find a Problem That Only Quantum Computers Can Do
Read the full paper Local mimima in quantum systems Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou
Abstract: Finding ground states of quantum many-body systems is known to be hard for both classical and quantum computers. As a result, when Nature cools a quantum system in a low-temperature thermal bath, the ground state cannot always be found efficiently. Instead, Nature finds a local minimum of the energy. In this work, we study the problem of finding local minima in quantum systems under thermal perturbations. While local minima are much easier to find than ground states, we show that finding a local minimum is computationally hard for classical computers, even when the task is to output a single-qubit observable at any local minimum. In contrast, we prove that a quantum computer can always find a local minimum efficiently using a thermal gradient descent algorithm that mimics the cooling process in Nature. To establish the classical hardness of finding local minima, we consider a family of two-dimensional Hamiltonians such that any problem solvable by polynomial-time quantum algorithms can be reduced to finding ground states of these Hamiltonians. We prove that for such Hamiltonians, all local minima are global minima. Therefore, assuming quantum computation is more powerful than classical computation, finding local minima is classically hard and quantumly easy.
