With two recent publications in the Journal of the Association for Computing Machinery (JACM), quantum computer science researcher and Rice University assistant professor Nai-Hui Chia has hit his stride. Ironically, quantum computing is not the path he intended to take.
“I’ve been a fan of theoretical physicist Richard Feynman since junior high school; becoming a theoretical physicist was one of my childhood dreams,” said Chia. “But when I entered college, I was only admitted by the computer science department.
“I struggled a bit at the time because I am not a big fan of programming. Then I discovered and became fascinated by the potential impact of machine learning (ML) and artificial intelligence (AI) on real-world applications.”
Before his third year of college, Chia had settled on becoming a software engineer for ML or AI. Then he picked up a book about Feynman to read during a summer vacation.
Chia said, “While I was reading, I noticed the term ‘quantum computers’ in the book. Feynman had proposed the idea of using quantum computers to simulate quantum mechanisms. I was quite surprised by — and felt an immediate attraction to — the connection between quantum and computer science."
“That fall, I began studying papers and taking courses in the physics department. Exploring the possibility of using quantum computers to solve classically intractable problems dramatically changed my understanding of computer science. Rather than building a bigger, faster digital supercomputer using binaries, why not build a computer using a new mathematical model from quantum physics?”
His enthusiasm for studying quantum algorithms and quantum computer science was a good fit for the research team led by Sean Hallgren at The Pennsylvania State University. Chia felt fortunate to be mentored through his Ph.D. research by Hallgren, who had previously served as Head of the Quantum Information Technology group at Princeton’s NEC Laboratories and frequently published research cited by other quantum computer scientists.
Chia said, “I recognize the satisfaction other computer scientists and engineers derive from working on applications and infrastructure, projects they can easily talk about with their non-engineering friends and family. But what excites me, what motivates my research is understanding the power of quantum computers and how quantum computers might change the landscape of computer science.”
His recent publications in the JACM reflect two very different ways to approach that landscape: identifying the most efficient quantum depth and configuring quantum-inspired algorithms.
Large Quantum Depth
Chia said researchers already know that a fault-tolerant quantum computer — call it a ‘perfect quantum computer’ — can complete a variety of seemingly impossible applications in practice, such as breaking RSA cryptographic systems. But no perfect quantum computers exist at present.
“Near-term quantum computers are imperfect,” said Chia. “We only have quantum computers with hundreds of quantum bits (qubits) and each operation on these qubits is noisy, which means it has a certain probability of being an error. To reduce the noise, near-term quantum computers can only operate at a relatively small depth.”
Leveraging the power of these near-term quantum computers has become an important question for quantum computing. One idea is to use near-term quantum computers and classical digital computers together — but configuring them to work in tandem is tricky.
“Imagine the perfect quantum computer is an off-road vehicle (ORV) that can cross any type of terrain. However, you don’t have this magic ORV yet. You have a horse and a camel. The horse is good at running in the meadow. The camel is good for travelling in deserts. So, if you just use one of the animals for traveling, you might not be able to finish a trip that crosses both deserts and meadows. But if you have both and can ride them in suitable places, you might be able to make it!"
“We call this hybrid quantum-classical computing. It is like client-server infrastructure, where you run a program on your laptop or your phone. When your handheld device or laptop encounters a problem that is too big to solve locally, it calls up remote (quantum) computers for help,” said Chia.
If the hybrid conjecture holds true, then full quantum power could be available before the distant perfect quantum computer is built, which would mean a significantly faster ramp up to quantum computer solutions for real-world applications. However, quantum computer scientists are split over the value of such a shortcut.
Chia said, “Researchers like those in my team conject that the hybrid quantum-classical computer is equal in power to the ‘perfect’ fault-tolerant quantum computer. Other researchers, like Scott Aaronson in 2005, conject the computers are not equal and there will be a problem that can only be solved by a fault-tolerant quantum computer. In other words, perfect quantum computers are strictly more powerful.
“In our February 2023 JACM paper, On the need for large quantum depth, we proved Dr. Aaronson’s conjecture. We found a problem, solved the problem using perfect quantum computers, and showed that this problem could not be solved by any hybrid quantum-classical computers if the quantum computers do not have sufficiently large quantum depth. Our work also showed that quantum computers with different quantum depths have different computation power in the presence of classical computation,” Chia said.
Basically, increasing the depth of quantum computers can yield more power even in the presence of classical computation. Also, to gain full quantum power, computer scientists might still need to build a fault-tolerant quantum computer even though the hybrid model is a tempting detour because it is more readily accessible.
Quantum-inspired Algorithms
Before search engines, the local librarian may have been the ultimate recommendation guru. They knew what their clients read, listened to individual preferences, followed current trends of a broader group of readers and retained historical knowledge of previous publications. Using all these brain-powered resources, the librarian recommended other titles to their readers. Companies like Amazon and Netflix invested in quantum computers and quantum algorithms to replicate that personalized recommendation process for their customers.
Chia said, “Before 2018, there were many quantum algorithms for machine learning tasks claiming that they were exponentially faster than their classical counterparts. These quantum algorithms were used for recommendations, SVM, linear systems, etc. At that time, these algorithms were viewed as one of the potential killer applications of quantum computing and they were indeed exponentially faster than existing classical algorithms.
“In 2018, Ewin Tang — an 18-year-old graduate student at The University of Texas at Austin — found that given similar data access, she could build a classical algorithm for a recommendation system whose runtime is asymptotically as good as a quantum recommendation system. In other words, she showed that quantum algorithms for recommendation systems do not achieve exponential speedup; you could say her work ‘dequantized’ the recommendation system.”
Ironically, Tang’s research direction — producing quantum-style recommendation results with classical computers — was suggested by Aaronson, the same scientist who in 2005 conjectured a problem solvable only by quantum computing. Tang’s research approach began with data access.
“Before 2018, the quantum algorithms like those used in recommendation systems required special access to the data. Accessing that data with classical algorithms was rarely considered. Inspired by Tang’s ‘quantum-inspired’ algorithms, we first found that we could generalize the algorithms to low-rank linear systems and low-rank SDP (semi-definite program),” Chia said.
As shown in their October 2022 JACM paper, Chia’s research group discovered an algorithmic framework that can produce ‘quantum-inspired’ algorithms to dequantize more quantum algorithms including principal component analysis, clustering, support vector machines (SVMs), and other tools familiar to classical computer scientists.
“Using our framework, we came out with an algorithm that can quickly compute a very useful form of the given data matrix –a singular value decomposition,” said Chia.
“Most applications sit on top of a form and compute functions to present the data with nice properties. That is why we call our discovery a framework. If you can compute the form efficiently, you can compute all related applications fast.”