Project Description

Q from IQIM logo

Andru Gheorghiu

“I am a computer scientist working primarily at the intersection of quantum cryptography and quantum complexity theory. I am attracted to the connections between complexity theory and physics and the way that their questions have a philosophical component to them. I find it interesting that complexity theory can say something about physics and situations that might happen in physics and inform us in creating new theories of understanding nature.”

Back to Directory


I am a computer scientist working primarily at the intersection of quantum cryptography and quantum complexity theory. I started working on blind-delegated quantum computing protocols that involve a client asking a quantum computer to solve a particular problem while keeping the algorithm secret from the computer. Part of my work is attempting to understand the kind of communication we would need to achieve this with a quantum computer and characterize what we could do with these types of protocols as well as how efficient they would be. I am also interested in the problem of verifying the correctness of quantum computations. Recently, protocols have been developed for both blind delegation and verification. I am currently trying to see whether these protocols can be made more efficient, in terms of the computational resources of the client, and I am also working to extend these protocols so that they may be composed with other protocols in a secure way.

My interest in complexity theory has led me to investigate more general questions pertaining to the potential applications that complexity theory might have in physics. Complexity theory is particularly interesting because it allows us to consider what we can and cannot solve efficiently using quantum computers, and it is the tool we use to answer questions pertaining to the hardness of problems under different models of computation. I have been looking at toy models of quantum gravity to try to argue that computing certain physical quantities, in these models, would be intractable even for quantum computers. So broadly speaking, I am just trying to see if we can use the tools of complexity theory to say something interesting about quantum gravity.

I have always been interested in both physics and computer science. I attended a computer programming high school, and the reason I got interested in physics was because of Stephen Hawking’s A Brief History of Time. This book changed my outlook on the world by making me aware of the fact that the universe is governed by the laws of physics and that we can express these laws in the language of mathematics. This allows us to make predictions about the behavior of physical systems and ultimately gain a greater understanding of our world. I found this very impressive and appealing, and I appreciated both that everything is governed by these laws and that we can understand them. In essence, I was impressed by what Eugene Wigner called “the unreasonable effectiveness of mathematics in the natural sciences.”

When I was younger, I read a lot of popular science articles, and I stumbled across quantum computing. I thought this was the perfect thing for me because it combined both physics and computer science by harnessing the strange laws of quantum mechanics in order to solve interesting problems more efficiently than we could with classical computers. My interests evolved to studying quantum cryptography in graduate school because that was the research topic of my advisor.

I was interested in the history of computer science as well, and I’ve always been more attracted to theory than practical things. I was reading up on complexity theory, and I found it very interesting that it originated with famous mathematicians who were trying to answer questions that were almost philosophical in nature, such as whether the creative process involved in deriving mathematical proofs can be fully automated and made efficient. The question at the heart of complexity theory is whether for problems with solutions that can be checked efficiently, we can also find a solution efficiently. I found it very interesting that this question, known as the P vs NP problem, has far reaching implications in almost all areas of science. On top of that, the P vs NP problem is also highly relevant to modern cryptography, since most cryptographic protocols used today hide information by encoding it as solutions to computationally hard problems. More recently, researchers have used complexity theory to study paradoxes arising in physics, such as the black hole information paradox. Given my interest in both computer science and physics, I am especially attracted to these connections between the two fields. I find it interesting that complexity theory can say something about physics and situations that might happen in physics and thus inform us in creating new theories for understanding nature.

I tend to read a lot of comic books, and am somewhat of a comic book geek.  The Dark Knight Returns by Frank Miller is probably my favorite comic.  I also play chess, and if I have some time, I might go to the gym or play some sports.  But most of my time outside of my research is spent watching movies and TV shows. I partly got into science because I used to watch and read a lot of science fiction as a kid, and I still watch many TV shows and movies that are science fiction or space related.  Stargate (all three series) is my favorite science fiction show.  I find space exploration and the Apollo program so interesting, and until recently, Apollo 13 was my favorite movie.  That was, however, until I went to the cinema five times to watch First Man, which is now my favorite movie of all time. I absolutely loved it.  It is definitely one of my dreams to eventually go to space. I don’t know if that will ever happen, but I can still hope.