CESGA researches algorithm partitioning to help design the programming of future quantum computers
Quantum computers are still small and error-prone, but the scientific community is already preparing for a scenario with large, sophisticated machines or networks of small, well-connected (or, in quantum jargon, entangled) machines. Partitioning quantum algorithms, which chops up instructions to make them manageable for today’s machines, is one of the ways to compensate for the technology’s current limitations. CESGA researchers are contributing to the advancement of these techniques to broaden the scope of quantum computing in the future
In recent years, the term algorithm has crossed the threshold of mathematics, computer science, and other academic and scientific disciplines to seep into the language of the street increasingly. The ubiquity of social networks and now also of artificial intelligence has led to talk of the algorithm as a kind of abstract entity called upon to govern our lives.
Guillermo Díaz
This is despite the fact that many people who mention it in their conversations would not know how to define it. In general terms, it is any method of solving a problem by means of a sequence of well-defined, ordered, and finite steps. In the field of computing, it could be said to be the instructions given to a computer so that it can execute a task, such as solving a problem. If we relate it to a concept closer to our day-to-day practice, a computer program is nothing more than the concrete implementation of one or more algorithms through a programming language that the computer can understand and run.
“In their early days, classical computers were the size of an entire room and we passed instructions to them with punched cards. Today, you can have all that computing power in your pocket and programmers do not need to think about what each bit of the machine does but can work on the programs in a more natural way,” explains Guillermo Díaz Camacho, a researcher at the Galicia Supercomputing Center (CESGA).
Quantum computers are very incipient, they are still at that point equivalent to punched cards and machines that occupy an entire room, so they are still being worked on at a very fundamental and labor-intensive level. In fact, bridging all the distances involved in talking about frontier science and disruptive technologies, one could use the term rudimentary. “Quantum algorithms still resemble those punched cards, with instructions that are more like a circuit with wires and electronic components, hence it is common to refer to them as quantum circuits,” says Díaz Camacho.
CESGA’s Department of Applications and Projects, to which this researcher belongs, seeks to contribute to the design of algorithms adapted to this context so that programmers can work more naturally on quantum computers, thus allowing these machines to tackle increasingly large and applied problems in the future. “It’s what we would call basic research, it’s closer to helping other researchers than industry,” he expounds.
Partitioning algorithms
Large companies such as IBM and Google have quantum computers (QPUs, or quantum processing units) with a few hundred qubits (the basic unit of quantum computing, analogous to the bit in classical computing). In contrast, one of the most powerful publicly accessible quantum computers in Europe, CESGA’s QMIO, only has 32 qubits. “While these sizes represent significant progress, it is estimated that thousands, or even millions, of qubits will be required to solve problems of real industrial relevance,” says Díaz Camacho.
As long as these dimensions cannot be achieved on a single machine, we have to be creative. The transitional solution is to interconnect small quantum computers so they can work together, which requires chopping the algorithms so that they can be executed across multiple machines. This complex task, which is the focus of CESGA’s project, is called quantum algorithm partitioning.
“It’s about having many small, manageable QPUs that communicate with each other to combine their memory and computing power. To achieve this, we need to break down the algorithm we want to run into smaller pieces that can be executed either sequentially or separately on different computers. Essentially, we divide the workload that a single QPU cannot handle into smaller, more manageable pieces,” explains the CESGA researcher.
Cutting and knitting
Even in classical computing, separating an algorithm into pieces is not as simple as running a piece here and a piece there, because everything is very interconnected. Entanglement, a purely quantum phenomenon that differentiates quantum computers from classical ones, makes it even more complicated when it comes to partitioning quantum algorithms. Without entanglement between qubits, there is no quantum computing power, either between qubits on a single machine or between qubits on several interconnected machines. “The problem is that, in practice, creating entanglement is tricky. Quantum computers are usually very isolated and protected so that the cubits do not suffer errors, but making them talk to each other is the opposite of isolating them!” says Díaz Camacho to give an idea of the complexity involved.
To overcome this limitation, Díaz Camacho’s team employs a technique that simulates quantum entanglement. “Currently, there are very few methods to physically connect multiple QPUs in a way that allows them to be entangled and combine their capacity. Ideally, future hardware will enable this, but for now, we have to use techniques that simulate entanglement. It’s not as simple as splitting the algorithm in half and running each part on a different QPU. Instead, you need to perform a series of distinct operations on each QPU so that, on average, the result resembles what you would get if they were truly entangled,” he explains.
To achieve this, it is necessary to draw on the computing power of classical supercomputers. “The job of simulating that the QPUs are entangled is done by a classical computer, which talks to the quantum computers to coordinate them, sending small pieces of the algorithm or circuit to each one. It is a laborious process, but it is less dependent on current hardware because it is easier to connect CPUs to QPUs than to connect two QPUs to each other,” says Díaz Camacho.
This technique of partitioning quantum algorithms is so new that there is still no consensus in the scientific community on what to call it, whether circuit cutting or circuit knitting. The term cutting refers to breaking algorithms into smaller pieces, while knitting evokes the idea of combining those pieces and putting them back together (or entangling them) into a larger unit. Regardless of the terminology, this cutting and knitting process is at the core of CESGA’s project: breaking down large quantum circuits into subcircuits that can run on smaller quantum computers, and then using classical simulation to weave the results back together into the final target outcome.
Although industrial applicability is still a distant horizon, the researchers of this project, part of the Plan Complementario de Comumicaciones Cuánticas (PCCC), focus on two types of prototype problems that, in the long term, could lead to significant practical solutions: combinatorial optimization and condensed matter. The former encompasses a wide range of problems, from comparing molecules and protein folding –which could benefit the pharmaceutical, food, or biotechnology industries– to issues like traffic prediction, route calculation, and managing the demand of electrical grids. “The study of condensed matter is more aligned with my background as a physicist, as it aims to understand the microscopic properties of materials such as superconductors,” says Díaz Camacho. The latter, for instance, have the ability to conduct electricity without resistance, enabling energy to be transported without losses.
The quantum future
“You have to keep your eyes open because every week something comes along that can change the paradigm and force us back to the drawing board to redesign things from scratch. It’s partly frustrating, partly exciting,” admits Guillermo Díaz Camacho. In this dynamic and uncertain landscape, predicting the future is challenging, but he ventures a forecast: “In the next five years, we will likely see much more mature and professional circuit partitioning software. This will speed up development work by eliminating the need for everyone to start from scratch,” he explains.
“I also think we will start to see QPUs connected with real entanglement, albeit still on a small scale, which could increase interest in these techniques,” adding that major competitors such as Google and IBM are already referencing these kinds of tools and hardware in their near-future plans.
In his opinion, the advancement of quantum technologies requires a large number of experts familiar with both the state-of-the-art and the real-world challenges that science and industry aim to address. “From CESGA, we want to work in that space, even though we have only been working on the project for a short time,” he notes.
