Fifth-year Rice CS Ph.D. student Zhiwei Zhang and his advisor, University Professor Moshe Vardi, have used a mathematical approach to tackle a quantum problem. The results could eventually mean a big leap forward for the field of quantum computing.
Zhang’s paper on perfect matching problems caught the attention of the Max Planck Institute for the Science of Light, who awarded it the Quantum-Graph Best-Paper Award for 2023.
Zhang will be presenting his work, which takes a mathematical approach to quantum problems, at the upcoming International Joint Conference on Artificial Intelligence (IJCAI ’23), to be held in Macao.
Graph Theory And Quantum Computers
So what is graph theory and what does it have to do with quantum computing? Graph theory is a branch of mathematics that specializes in showing real-world relationships between objects as graphs. Each graph has nodes (points) and edges (the lines between those points).
You can see elements of graph theory at work every day, each time you use a computer. The friend recommendations of social media are generated by graph algorithms, and people interacting with a computer program are sort of traversing a state graph; they go from point to point, unlocking features as they move.
The Max Planck Institute discovered that the components of a quantum computer, quantum circuits, could be modeled using graphs. They’ve been trying to apply graph theory to construct those models, but doing this computationally proved highly challenging, and gets more time-consuming as the graph gets larger and more complicated. However, Zhang appears to have found a solution that could make generating quantum circuits a whole lot simpler in the future.
An ‘Elegant’ Approach
Zhang's paper deals with a specific element of graph theory: the perfect-matching problem. In a graph, a perfect matching exists if there is a set of edges such that each node touches exactly one edge in the set. Determining how many perfect matchings exist in a graphical model can be difficult even with small graphs, and gets harder the larger your model becomes.
Until recently, physicists trying to build graph models of quantum circuits tried to enumerate every perfect matching within a graph using brute force computing, which made the process laborious. Zhang, however, saw a way to circumvent that via mathematics.
Boolean logic is used in everyday items all around us, from our laptop at the cafe to the switch routing trains along their route. The Google searches you do everyday? Boolean logic. It’s a programming language that can only hold one of two possible values: true or false. In binary computer code, 1 represents true and 0 represents false. Or 1 can represent “on” with 0 representing “off.”
Code written in this language tells any piece of technology with an electrical circuit how and when to function.
Zhang used this language, coupled with satisfiability — or SAT — solvers, to constrain the vast number of perfect matches in a quantum graph down to variables that could be quickly and easily expressed.
SAT solvers are designed to take a large number of true/false Boolean possibilities and compute the best possible solution or set of solutions. In the real world, a SAT solver might be used in shipping company software that helps decide what packages to put on what trucks. Given the large number of potential solutions, it would be incredibly time-consuming for a human to compute the possibilities on their own, but a SAT solver handles problems like that all the time.
Zhang’s idea was to use the strength of SAT solvers on the problem of perfect matchings in a quantum graph. By using Boolean constraints — putting everything in terms of true/false or 1/0 — the problem can then be fed into a SAT solver, which can crunch the huge number of possible perfect matches in far less time than it would take a human to compute by hand.
Since graphs can serve as models of a quantum circuit, figuring out the structure of a graph quickly and efficiently can aid in building new circuits for new, more efficient quantum computers. According to Zhang, the larger the graph gets, the more possibilities, the better this solution works:
“One of the power sources of Boolean logic is that the representative power of Boolean logic also grows with respect to the number of variables…if we have 100 variables we could represent that problem with 2^100 scenarios. That’s why Boolean logic is able to absorb the size of the problem that the quantum inspired problem has.”
The Max Planck Institute, who viewed this as a continuous optimization problem instead of a logical one, described Zhang’s solution as “beautiful” and “elegant” in their message awarding his paper.
New Quantum Circuits In The Blink Of An Eye?
Eventually, Zhang hopes his work will help automatically generate new quantum circuits, thus making it much easier to build quantum components and quantum computers. “We believe we provide a reliable and useful toolkit for people in other research communities,” he said of this solution.
If successful, we could end up using classical computing via Boolean logic to build new quantum circuits quickly. “Our work can be viewed somehow like biology, where they use computers to find the structures of proteins,” said Zhang. “We’re using computers, classic computers, to find the structure of quantum circuits.”
Zhang is a fifth-year Ph.D. student in computer science at Rice University advised by University Professor Moshe Vardi and co-advised by Noah Harding Assistant Professor Anastasios Kyrillidis. His research on constrained optimization has been published in top AI venues such as AI Journal, IJCAI and AAAI.
You can view the full paper here: https://arxiv.org/abs/2301.09833