Newest QuICS Fellow Expands Research Beyond the Intersection of Computer Science and Physics

It’s rare that scientists spend their careers toiling away on a narrow set of questions, and Xiaodi Wu—the newest Fellow at the Joint Center for Quantum Information and Computer Science (QuICS) and an assistant professor in the UMD Department of Computer Science—is no exception. Wu has spent his early research career picking his way through many topics in computer science and physics, and he hasn’t satisfied his curiosity yet.

“I want to try new stuff, so that means I always have new topics show up in my research,” Wu says. “But I don't forget about my old stuff.”

Wu grew up in China, and, as a high school student, competed in the National Olympiad in Informatics, an annual computer programming competition. There, he honed his coding skills and solidified an interest in computation. Eventually that interest broadened to include the more theoretical aspects of computer science, including its basis in physics and math.

“I was thinking I had learned enough coding, and I wanted to try something new,” Wu says. “The natural sciences were a big attraction.”

After learning about quantum information and computation while he was a math and physics major at Tsinghua University in Beijing, Wu sought out a graduate program that taught the field from a computer science perspective. He decided on the University of Michigan in Ann Arbor and immediately began working with Yaoyun Shi, a computer scientist with broad interests in quantum information and computation.

Undeterred by the shock of moving from Beijing to Ann Arbor—“I kinda enjoy the college town life,” he says—Wu came up to speed quickly, and spent his first summer simplifying the proof of a major result in quantum complexity theory. That result, which showed that the power of a particular model of quantum computing was equivalent to that of an ordinary computer with a reasonable amount of memory, piqued Wu’s interest in complexity theory. But although his Ph.D. thesis was largely filled with his work on complexity theory, Wu soon heard the siren call of another topic.

Many students and postdocs in Shi’s group were studying device-independent cryptography—the ultra-paranoid attempt to prove the security of things like random number generators, even when the device’s creator can’t be trusted. Quantum physics, via entanglement and other unintuitive features, offers a new set of tools for certifying that these devices are performing as advertised.

“I think cryptography might be among the first practical applications of quantum information and computation,” Wu says.

Wu sought to shed as many assumptions as possible and reduce the first steps of creating truly random numbers to mere physical law. The result was a proof that a weak source of randomness could, in fact, seed a procedure for generating more randomness, albeit in a less than efficient way.

After finishing graduate school, Wu spent just two years in his first postdoctoral appointment, quickly moving on to a faculty position at the University of Oregon in Eugene. Once there, he took advantage of the local expertise to embark on another new project: developing a framework for the nascent field of quantum programming languages.

Each summer, Oregon computer science professor Zena Ariola organizes the Oregon Programming Languages Summer School, a two-week workshop that dives into the theoretical underpinnings of programming languages. Many sessions over the past decade have included the topic of verification—a suite of techniques that help ensure a computer program is doing what the programmer expects. Wu became interested in porting those principles over to quantum programs, which are still confined largely to the minds of research scientists.

The problem is that basic operations, such as copying a value from one variable to another, aren’t allowed by the rules of quantum physics.

“First you need to invent or figure out what the right mechanism would be to prove the correctness of a quantum program,” Wu says.

With one of his undergraduate mentors and another collaborator, Wu proposed using invariants—statements that are true whenever a program reaches a certain point in its code—and they published a paper that both defined appropriate invariants for quantum programs and did some early work on generating and using them in practice.

Although Wu still maintains an active interest in many of the areas he’s tackled before, he says he’s excited to come to QuICS and start something new. He hopes to link up with quantum algorithm experts, like QuICS Fellows Andrew Childs and Stephen Jordan, and try his hand at creating the software that future quantum hardware will run.

“I just want to have the taste of designing algorithms,” he says. “They are something I haven't really touched on.”

Wu, who also has an appointment in the University of Maryland Institute for Advanced Computer Studies (UMIACS), is also excited to begin advising graduate students, and plans to teach a class on complexity theory in the fall. He welcomes inquiries from students interested in his areas of expertise.

About QuICS
QuICS is a partnership between the University of Maryland and the National Institute of Standards and Technology. Faculty and students in QuICS receive technical and administrative support from UMIACS.

—Story by Chris Cesare