IBM Quantum Research Points Toward Quantum Speedup in Tackling Complex, Useful Calculations

Insider Brief

• IBM Quantum researchers report that near-term quantum computers may be able to use algorithms to solve complex problems faster than classical devices.
• The team showed that their approach, if it scales, could address computational bottlenecks in machine learning, for example.
• IBM’s 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 made strides in extracting value from near-term quantum processors while laying the groundwork for fault-tolerant quantum-centric supercomputers.

IBM’s recent research, published in Nature, showed that quantum computers maybe able to churn through extremely important, widely-used computer algorithms faster than classical computers. This speedup, if it continues to hold at larger scales, could address 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 to solve useful sampling problems rather than merely difficult ones.

In the blog post, team members Sarah Sheldon and David Layden write: “Quantum computers can’t just solve difficult problems to be valuable — they also need to solve useful problems. And according to new work, quantum may provide a speedup for instances of one extremely important, widely-used computer algorithm, called the Metropolis-Hastings algorithm.”

According to the IBM researcher’ blog post, the Markov chain Monte Carlo (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, known as sampling. The focus of IBM’s work was to find an algorithm that could run on near-term quantum devices, guarantee the correct answer and provide value for real-world applications. The team chose the challenging problem of sampling the Boltzmann distribution of the classical Ising model.

The Ising model assigns energy values to a set of binary numbers, or bitstrings. Using the Boltzmann distribution, probabilities for each bitstring are calculated based on temperature, with low energy states having higher probabilities. However, calculating these probabilities efficiently requires determining the partition function, which is exponentially time-consuming as the size of the bitstrings increases.

Sampling from the Boltzmann distribution has numerous practical applications, including calculating magnetic properties of materials and facilitating the training process in deep learning for machine learning applications. However, current methods, such as the Markov chain Monte Carlo (MCMC) 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 into qubit values and evolving the qubits based on the Ising model’s properties, quantum computers can make intelligent jumps to accelerate the process. The acceptance probabilities for these jumps are calculated using classical computers, creating a feedback loop between quantum and classical computation.

The researchers report they conducted simulations for an ideal quantum computer and found an average-case speedup ranging from cubic to quartic, depending on the problem’s size. To validate their findings, they also implemented the algorithm on a 27-qubit IBM Quantum Falcon processor. The quantum version demonstrated a speedup compared to classical-only methods, producing the correct answer for the specific problems tested, according to the post.

This research highlights the potential of quantum computing in solving complex problems, even with the limitations of current noisy quantum processors. While the ultimate goal is to develop fault-tolerant, universal quantum computers, these incremental advancements provide valuable insights and useful speedups 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 broaden. By tackling challenges in sampling from complicated probability distributions, researchers pave the way for advancements in various fields, including materials science, machine learning, and other areas that depend on efficient sampling techniques.

The researchers write: “This work demonstrates how we hope the future of quantum computing will play out. Of course, our ultimate goal is a fault-tolerant, universal quantum computer capable of solving a variety of problems. But as we work toward that goal, we can continue looking for useful speedups along the way. Our quantum Markov chain Monte Carlo is a perfect example of this. Even with a noisy quantum computer, it can deliver the correct answer. And as the scale, quality, and speed of our processors increase, so too will the speed at which they can solve this problem.”