Combining the best of quantum computing and classical computing

Ilya Safro of Clemson University is working to create algorithms that combine the best of quantum computing and classical computing, a hybrid that could put quantum hardware a step closer to solving real-life problems.

No one yet knows whether it will be possible to solve practical problems with quantum computers, a technology that for certain problems would be exponentially faster than current systems. But small quantum devices are becoming available, and Safro’s algorithms are aimed at putting them to work in fields ranging from defense and national security to engineering and natural sciences.

With his research, Safro and his team are joining a worldwide race to find ways of using quantum devices to solve problems faster and more efficiently than on classical computers. The idea is to take the advantages of classical computers, such as their large memories  and combine them with the power of small quantum devices.

“We hope that we can introduce a family of hybrid quantum-classical algorithms that will accelerate the solution of computationally hard optimization problems,” said Safro, an associate professor of computer science. “By nature of these optimization problems, it is very likely that if we will be able to demonstrate it on one practical problem, then a whole class of other optimization problems will benefit from it.”

The Safro team has received $1.03 million for four years of research from the Defense Advanced Research Projects Agency. Safro, the principal investigator, is collaborating on the project with Argonne National Laboratory.

Yuri Alexeev of Argonne National Laboratory is a co-investigator on the project.  Joey Xiaoyuan Liu and Ruslan Shaydulin, who are Ph.D. students in Safro’s lab, are also working on the research.

Amy Apon, the C. Tycho Howle Director of the School of Computing, said that Safro’s funding is well deserved.

“Dr. Safro is an accomplished researcher with deep experience in computational science and creating algorithms,” she said. “His knowledge, experience and passion make him uniquely qualified to lead this project.”

As many as six graduate students and several undergraduates will have an opportunity to work on the project, giving them practical experience in the field of quantum computing.

“It is hard to overestimate the need of quantum computing in the future,” Safro said. “All major companies either have their quantum computing teams or are building ones or exploring their opportunities in using quantum computing. While we cannot immediately use it for practical problems, I see learning quantum computing as a long-term investment in many disciplines that will become more and more important.”

Anand Gramopadhye, dean of the College of Engineering, Computing and Applied Sciences, said that Safro’s project underscores the quality of research in the School of Computing. 

“Dr. Safro is helping open new frontiers in cutting-edge technology,” Gramopadhye said. “The amount of the award is a testament to his hard work and innovative approach. I wholeheartedly congratulate him on securing funding for his new project.”

Safro recently sat down to answer series of questions for IDEAS Monthly about quantum computing and his research:

 

I think that the general public has a pretty limited understanding of what quantum computing is. What is your best layperson’s definition for quantum computing?

Major advances in quantum physics that were introduced in the 1920’s, along with Richard Feynman’s incredible intuition in the early 1980’s gave birth to quantum computing.  Feynman asked a “simple” question: Is it possible to simulate any physical system, including particles as tiny as electrons, with a classical computer? Because of the limitations of classical computers, a fully correct simulation of quantum mechanics becomes intractable. Then, the idea was, “All right, if there is a physical system that we cannot simulate on a classical machine, let’s use it to design a much more powerful type of a computation.”

Quantum computing is a qualitatively new way of thinking, designing, and understanding the computational process, hardware development, and underlying computational complexity. It bridges the laws of probability and quantum physics with our computational problems and suggests ways to tackle them qualitatively better.

 

You have a front-row seat to one of the hottest technologies on the planet. What are your highest hopes for quantum computing? What are some of the practical problems it could solve?

Currently, no practical problem has been demonstrated to be solved on a quantum computer more efficiently than on a classical device. There is a worldwide race for finding such problems. It is very likely that such a demonstration will begin with absolutely impractical problems with no immediate applications. However, the quantum supremacy that we hear about in the news is not necessarily the ultimate goal of this race. For example, if we could find a problem that can be solved on a quantum computer “just” 1,000 times faster than on a cost-comparable classical computer, and there is evidence that such an approach can scale, it will already be practical enough to demonstrate the quantum advantage. 

We also expect that these technologies will advance classical algorithms and hardware because they will be required to effectively run quantum devices and not to be a bottleneck of significantly faster computational systems. From healthcare and AI to modeling in chemistry and business analytics, scientists are exploring countless applications and their potential of being advanced with quantum devices. There exists an enormous number of practical algorithms (called heuristics) that successfully tackle applied problems even when theory does not provide us with a tool that is helpful to achieve a provably correct solution with a reasonable quality/resources’ tradeoff. Demonstrating a quantum supremacy on a real physical device that will provably guarantee a qualitatively better tradeoff and advantage over the theory and heuristics will be considered a breakthrough in the history of computing.   

We explore this direction for combinatorial optimization and machine learning problems using hybrid quantum-classical algorithms. At this point, nobody knows what are the practical problems that could be solved on quantum computers substantially faster than on classical computers. Our applications are relevant not only to the national security and defense areas. These are broadly defined problems with applications in natural sciences, engineering, social sciences, and many more.

 

I’ve seen a lot in the popular press about the power of quantum computers, but the sense I’m getting is that there are some limitations. In the simplest possible terms, could you help us understand those limitations?

 Leaving apart the search for a “killer app” that will demonstrate quantum supremacy, there are several limitations to quantum computers. For example:

1)     There is no physically implemented concept of a storage space and random-access memory with fast access on existing quantum computers. There are doubts that we will see something like that in the near future.

2)     Basic information units on quantum machines (qubits), are more powerful than their classical counterparts (bits), but their amount in quantum hardware is significantly smaller.

3)     In order to ensure the cooperative work of qubits, they have to be effectively connected with each other, which is expressed in such factors as the number of connections, bandwidth, latency, and measurement quality. Sparsely connected quantum architectures will be able to solve smaller problems even with a large number of qubits. Leaving aside all other issues, the existing quantum devices with thousands of qubits provide a bad connectivity. The existing quantum devices with only tens of qubits are connected better but can handle small problems.

4)     Existing quantum devices are extremely noisy, which means that they are highly sensitive to unwanted physical disturbance. A lot of work has to be done in quantum error correction. It’s a huge challenge in this field.

5)     Because of the physical limitations in the development and maintenance of hardware, most likely these quantum computers will be available as additional computational units that accelerate and improve certain tasks in classical computers. For example, they will be available through clouds or connected to supercomputers like the Palmetto Cluster.

 

My understanding is that your work brings together the best of classical computing and quantum computing. Could you help us understand that?

Yes, we work on hybrid quantum-classical algorithms. We use the memory and other abilities of a classical computer to look at the entire data, and we use the power of a small quantum device to efficiently solve parts of a big problem. In particular, we are trying to advance two fields:

1)     Even if we assume that there will be progress in quantum error correction, the quantum hardware will stabilize, and devices will be robust, the lack of a large number of  qubits cooperating with each other won’t disappear, which is a major problem. In other words, a problem we will be able to solve with a quantum device will remain small in comparison to the overall size of the real-world problems. Our goal is to develop methods to break down the entire problem into smaller problems on a classical machine and solve them on small quantum devices, and then effectively compose them back into one solution of a big problem.

2)     Running quantum devices requires complex parametrization. In order to get the best performance of a washer, we need to set up its input parameters, such as load size, intensity, temperature and time. The quantum computer is a much more sensitive and complicated physical device whose input parameters to run it correctly are way more complex. In fact, finding them is a hard computational problem by itself which has to be solved on a classical computer.

 

How did you come up with the idea for this research?

 I have been working on multi-scale computational methodology since my Ph.D. at the Weizmann Institute of Science. The multiscale methodology is an extremely powerful approach to tackle large-scale computational, simulation and optimization problems that led to breakthroughs in multiple domains. No matter how big our supercomputers are, we will always have important problems that will require more powerful machines. This is precisely the case when the multi-scale methods help. The quantum computers are expected to remain smaller than many practical problems.

 

What makes your approach unique?

 The uniqueness of our approach is that we tackle optimization problems at multiple scales of problem coarseness, which allows us first to learn a geometry of the problem and then use it to break the problem down into smaller pieces for quantum devices. This is a very effective approach. For example, when we solve optimization problems related to artificial intelligence, it helps to avoid the classical data over- and under-fitting obstacles.