Identifying the Potential—and Limitations—of Quantum Computers

There’s a lot of hype about quantum computers these days and their potential to change the world, from revolutionizing fields like drug discovery and finance, to breaking all current forms of cyber security, and more. But behind the hype are researchers working to sort out the true power of this rapidly emerging technology. “While we're in the early stages of developing practical quantum computers, we want to ask what sorts of problems we expect them to be useful for,” said Columbia graduate student Natalie Parham.

Parham, a third-year PhD student working with theoretical computer scientist Henry Yuen, recently received a Google Fellowship, which will support two years of her research on identifying the power, and potential limitations, of quantum computers. 

In this Q&A, she shares more about her theoretical quantum computing research, what drew her to the field in the first place, and the value of community and role models in challenging spaces.  

Can you summarize what you work on?

At the highest level, I want to understand the power and limitations of quantum computers. There are a ton of exciting potential applications for quantum computers but at the moment, there are relatively few techniques for developing the algorithms needed for these applications and even fewer for proving that they offer some advantage over what we can already do with our classical or “normal” computers. 

Let’s say you come up with a quantum algorithm for adding two numbers quickly—we agree that quantum computers can be used to add. But we already have some pretty good, and much cheaper, calculators that do that! Ideally, we should focus our efforts on problems that we know our classical computers can’t already solve well. This requires proving the limitations of classical computation. I also focus on understanding the limitations of quantum computing—in other words, what are quantum computers not useful for? Answering this question is important for steering research toward the promising applications for quantum computers.

I’ve spent a lot of my research efforts so far focused on near-term quantum devices, particularly quantum algorithms that can only run for some fixed amount of time—say 100 seconds. These algorithms are relevant to existing quantum devices, which can only run for short periods before noise and errors start to add up. Even with this severe restriction on the runtime of quantum computers, we still know that they can not be simulated with our classical computers. I find these restricted models of quantum computation interesting because they’re much simpler than full-fledged quantum computers, which makes them easier objects to reason about. But they’re still surprisingly powerful. 

I am also interested in developing tools to help researchers develop quantum algorithms. It is not like coding on a classical computer, and it requires a deep knowledge of quantum mechanical theory. It’s also difficult to verify that a quantum circuit is actually doing what you want it to. I’m trying to make algorithm development overall easier.

What drew you to this field in the first place?

I really enjoyed my computer science theory class as an undergraduate at the University of California, Berkeley. It had a small section on quantum computing, which I followed up with in a dedicated class. Before this course, I admit I had a pop-science view of technology, with some misconceptions, such as thinking quantum computers could allow one to teleport. I found quantum computing much less intuitive than my classical computer science courses, which intrigued me. This struggle in developing my intuition for quantum computing was very frustrating, but a fun kind of frustrating. Similar to how I feel now when I’m hooked on a research problem. So much is unknown about this new piece of technology we are just starting to understand that you can really explore unique directions. It feels good to be a part of that. 

What have been some highlights from your time so far at Columbia?

In terms of research, I recently published a paper with fellow students Shivam Nadimpalli and Francisca Vasconcelos and my advisor Henry Yuen that was a lot of fun, to me at least. Essentially, we proved that a large class of functions can not be computed by quantum circuits whose runtime is fixed. The type of circuits we considered even allow for a “quantum-AND” gate that acts on all of the qubits at the same time. Existing techniques for proving limitations often break down for these “global” gates.

Last fall, I was also a teaching assistant (TA) for Columbia’s Introduction to Quantum Computing course. I got a lot of joy from teaching and helping students understand complicated topics. It’s very complimentary to research, and I felt like I built a nice little community during my office hours. I think it’d be fun to try teaching or co-teaching a course in the future. 

How do you spend your free time in New York? 

My main hobby is skateboarding. It’s similar to research in a way—you try at something for a really long time, and then you figure out a solution or you land the new trick. That’s such a good feeling.

It’s also been a great place to find community here in New York, especially with women, which I think is really cool. 

You are a woman skateboarder and a woman quantum scientist—do you have any thoughts about being a woman in these spaces?

I feel like I belong at Columbia, especially in the Computer Science Theory Group. It’s a really welcoming place, and it doesn’t feel like there’s any one dominating personality, but that wasn’t the case when I was an undergrad. I often felt self-conscious of the questions I asked and my actions, worried about reinforcing negative biases against women. I would have loved to have had more women classmates and teachers. 

As a TA last year, seeing the growing engagement from female students was inspiring. Many of them sought out my office hours, and it was rewarding to know that my presence helped them feel more excited and welcome. Research is hard, especially when you are just starting out. You need a certain level of confidence, which I believe requires community and relatable role models to help you visualize where you can go. That sense of community is really important, whether in research or in skateboarding.