Meet a CQTian: Troy Lee

Troy Lee, a theoretical computer scientist, is CQT's newest Principal Investigator.

Who are you?

I'm Troy Lee. I'm from the US. I was born in Texas and grew up in Hawaii.

What do you do?

I work in theoretical computer science. I work on computational complexity, which looks at what kinds of problems computers can solve efficiently and what problems they can't solve efficiently, and how this depends on the resources they have. Resources can include randomisation, that is the ability to flip coins, or even being quantum.

The quantum is a clue to why you're here, at the Centre for Quantum technologies?

Yes, the main novelty of a quantum computer compared to classical ones is that the states of the computer can be in superposition. Initially, you might think that, oh, this means you can do massively parallel things, but that's not what the quantum world allows. When a measurement is made, you don't get the answer to all these parallel paths, you just get one answer, at random. You have to be quite clever to figure out how to make use of this superposition to compute things that you can't do classically. It is a very interesting puzzle to work on.

How did you get interested in this?

When I was younger, I wanted to do physics. When I was at University, I realised that I didn't have so much physical intuition when it came to things like electricity and magnetism, and quantum mechanics, and really I was just relying on the math. Then I became interested in the math itself and switched to mathematics. Doing quantum information is nice because it combines both things.

But if you hadn't gone into maths, you might have run away to the circus...? You gave a juggling performance at CQT once.

When he's not doing research, Troy enjoys practicing circus skills.

Yeah, I kept that in mind as a back-up career! I like to do gymnastics. I like circus arts – some juggling, unicycle, handstands, slackline, all those kinds of things. The unicycling club here in Singapore is a cool group. They get together to play unicycle hockey.

How did you get started with circus skills?

I started juggling a lot during my PhD. When you're stuck on a problem, you don't know when you are going to make progress. There is not something definite you can do, you just try different things and maybe they don't work. With juggling, as long as you keep practicing, you're going to keep progressing. I found that can kind of prevent frustration: when you are stuck in one aspect of your life, you can still progress in another.

The gymnastics and unicycling are things I only started when I came to Singapore.

Can you give us an example of your research?

Well, here's a simple problem I can explain. It comes about from comparing different techniques for computing lower bounds in communication complexity. I heard this problem from fellow CQTian Hartmut Klauck and worked on it last summer with an intern.

Say you have a matrix with ones on the diagonal and zeros everywhere else. This is called the identity matrix. It has the property that the only vector it maps to the all zero vector is the all zero vector. The problem is to start filling in the zero entries of the matrix so that many vectors are mapped to the zero vector. That would be easy, you could just fill the whole matrix with ones. So to make it interesting we add another constraint: if you make the (i,j) entry nonzero, then the (j,i) entry must remain zero. Such a matrix is called a 'fooling set' and is important in communication complexity. The goal was to fill in the entries, respecting this constraint, to map as many vectors to zero as possible.

Did you solve this problem?

Actually, my intern did! The construction is very nice, quite simple mathematics. The values that we used to fill in the matrix are all binomial coefficients.

The student is an undergraduate who came for the summer from Egypt. I was super excited when she got the proof, more excited than she was. Now she's applying for grad school, and at that stage, having a publication under your belt will really help. The paper is now on the arXiv (arXiv:1310.7321), and we've submitted it to a journal.

I vividly remember the first time I proved something, and the euphoria lasted for days. Of course, over time as you prove more things, that feeling becomes more familiar and less exciting...unless you really have a breakthrough! It's nice when you start working with students, then you can again experience that joy through seeing their first results.

You were appointed a PI at CQT earlier this year and won an NRF Fellowship in 2013. Congratulations! What is changing for you?

There is definitely more administrative work now! I've hired some postdocs, and I am still searching for PhD students.

One research direction I'm expanding is looking at the power of semidefinite programming. This is a powerful algorithmic technique that can efficiently solve some quite challenging problems. And we still haven't ruled out an approach using semidefinite programming to solve NP-hard problems. There is an interesting connection between the size of semidefinite programmes – which is related to how quickly they can be solved –and a model of quantum communication complexity. You can actually show lower bounds on the power of semidefinite programming by studying quantum communication complexity. That's pretty interesting.