IBM Quantum Research Points to Quantum Acceleration in Handling Complex, Useful Computations

Insider Summary

• IBM Quantum researchers report that short-term quantum computers may be able to use algorithms to solve complex problems faster than classical devices.
• The team demonstrated that their approach, when scalable, could overcome computational bottlenecks in machine learning, for example.
• The IBM research team published its findings in Nature.

In a significant step towards making quantum computing practical and useful, IBM Quantum researchers report that they have taken steps in extracting value from short-term quantum processors while laying the foundation for a fault-tolerant, quantum-centric supercomputer.

IBM’s latest research, published in Natural, suggesting that quantum computers may be able to crunch critical and widely used computer algorithms faster than classical computers. This acceleration, if continued at a larger scale, could overcome the computational bottlenecks associated with sampling problems in machine learning, statistical physics, and optimization. It also highlights the practical value of the algorithm and its potential for solving useful sampling problems rather than just hard problems.

In a blog post, team members Sarah Sheldon and David Layden wrote: “Quantum computers can not only solve difficult problems to be valuable — they also need to solve useful problems. And according to the new work, quantum could provide acceleration for an example of one very important and widely used computer algorithm, called the Metropolis-Hastings algorithm.”

According to IBM researchers blog posts, the Markov Monte Carlo chain (MCMC), of which the Metropolis-Hastings algorithm is a well-known example, is an algorithm that allows researchers to select random representative items from a large set, which is known as sampling. The focus of IBM’s work is to find algorithms that can run on short-term quantum devices, guarantee the right answers, and deliver value for real-world applications. The team chose the challenging problem of sampling the Boltzmann distribution from the classic Ising model.

The Ising model assigns energy values ​​to sets of binary numbers, or bitstrings. Using the Boltzmann distribution, the probability for each bitstring is calculated based on the temperature, with lower energy states having a higher probability. However, calculating these probabilities efficiently requires determining the partition function, which takes exponential time as the bitstring size increases.

Sampling from the Boltzmann distribution has many practical applications, including calculating the magnetic properties of materials and facilitating the training process in deep learning for machine learning applications. However, current methods, such as the Markov Monte Carlo (MCMC) chain technique, have computational bottlenecks that limit their effectiveness, according to the post.

The integration of quantum computing into this problem-solving approach offers a promising solution. By converting bitstrings to qubit values ​​and expanding the qubits based on the properties of the Ising model, quantum computers can make intelligent leaps to speed up the process. The acceptance probability for this jump is calculated using a classical computer, creating a feedback loop between quantum and classical computing.

The researchers report that they performed simulations for an ideal quantum computer and found average case accelerations ranging from cubic to quartic, depending on the size of the problem. To validate their findings, they also implemented the algorithm on a 27-qubit IBM Quantum Falcon processor. The quantum version demonstrates speed up compared to the classical method alone, yielding the correct answer for the specific problem tested, according to the post.

This research highlights the potential of quantum computing in solving complex problems, even with the limitations of today’s noisy quantum processors. While the ultimate goal is to develop a fault-tolerant universal quantum computer, these additional advances provide valuable insights and useful acceleration along the way, the researchers write.

There is a lot of work ahead, according to the researchers. As IBM Quantum continues to improve the scale, quality, and speed of their processors, the applications for quantum computing are expected to expand even more. By overcoming the challenges of sampling from complex probability distributions, researchers are paving the way for advances in a variety of fields, including materials science, machine learning, and other fields that depend on efficient sampling techniques.

The researchers write: “This work shows how we hope the future of quantum computing will play out. Of course, our ultimate goal is a universal, fault-tolerant quantum computer capable of solving a wide range of problems. But as we work towards that goal, we can continue to find useful acceleration along the way. Our Markov quantum chain, Monte Carlo, is a perfect example of this. Even with a noisy quantum computer, it can give the right answer. And as the scale, quality, and speed of our processors improves, so can their speed solve these problems.”