## Who wants to be a summer student?

Lately I’ve been getting emails from undergrads with stellar-looking résumés who want to be my summer students. My initial reaction was: “who, me? I’m barely more than a summer student myself!” But today a light bulb went off: “hey, if these ambitious whippersnappers *really* want to do my research for me, why shouldn’t I let them do it — thereby freeing up my own time for more important priorities like blogging?”

I’ve therefore decided to list three project ideas. If you’re an undergrad or grad student who wants to tackle one of them this summer at the University of Waterloo, email me (scott at scottaaronson dot com). Tell me about yourself and what you want to do, and attach a CV. I’ll pick up to two students. Deadline: Feb. 21 or until positions are filled.

Scott Aaronson is an equal opportunity employer. He doesn’t have his own funding, so if you can bring your own, great; if not, he’ll try to scrounge some from under Mike Lazaridis’s couch. If the projects listed below don’t interest you — or if you’re more interested in physics, engineering, or information theory than in quantum complexity — there are many, many potential supervisors at both the Institute for Quantum Computing and the Perimeter Institute who’d probably be a better match for you.

**Project #1: The Learnability of Quantum States.** For this project, you’d first read and understand my paper of the same name, ideally before the summer started. You’d then implement my quantum state reconstruction algorithm in Matlab, Mathematica, or any other environment of your choice, and study its performance with realistic physical systems. This is a crucial first step if experimentalists are ever going to be convinced to try my quantum state learning approach. (The fact that I *proved* it works is completely irrelevant to them…) There’s also plenty of scope for new theoretical ideas if you swing that way. The eventual goal would be to publish the results somewhere like *Physical Review Letters*. This project is highly recommended.

**Project #2: Multiple Quantum Proofs.** Today we believe that there are mathematical truths that you could efficiently verify if given a small quantum state, but that you couldn’t efficiently verify if given a short classical string. But what if you were given *two* quantum states, which were guaranteed to be unentangled with each other? Would that let you verify even more truths than you could with a single quantum state? The answer is, we have no idea! Nor do we know whether three quantum proofs are more powerful than two, etc. When it comes to the power of multiple quantum proofs, even the most embarrassingly simple questions are open. In this project, you’d work with me to try and sort out the mess. This project is only for students who are confident of their ability to do original research in theoretical computer science.

**Project #3: Insert Your Own Project.** Wow me. Dazzle me. Give me a *specific, detailed* idea for a research project in quantum complexity theory or a related area, and convince me that you’re ferocious enough to get somewhere with it in one summer. I’ll try to help where I can.

Comment #1 February 8th, 2007 at 10:45 am

Before I send some ugrads your way, I need to know,

how much Quantum Computing do they need to know ahead of time?

Or Quantum Mechanics?

More generally- what should their background be?

bill gasarch

Comment #2 February 8th, 2007 at 12:07 pm

I’m looking for the most qualified students I can get, whether from physics, math, or CS. If your students are interested, tell them to send me their resumes. They’ll already be facing some stiff competition from students who do have QM backgrounds (in addition to CS) — but they could compensate by (for example) being extraordinary in classical complexity theory.

Comment #3 February 8th, 2007 at 2:21 pm

Do you know of any people who are offering similar possibilities in mathematics? After reading this advertisement I’ve done 1-hour googling for pure-mathematics-oriented summer programs but I found nothing.

Additionally, I’d like to share my opinion that You’re doing really Good Thing :-).

(Actually, I found few cool things but all of them were reserved for U.S. citizens. There was also very nice looking summerschool near me, in Germany, but it was in 2006. At least they made videos (some big names were lecturing, including Y.Manin).)

Comment #4 February 8th, 2007 at 2:37 pm

sirix: In the US, there’s a whole program called Research Experiences for Undergraduates (REU) — see this page for a list of opportunities in math. I just perused the offerings, and some of them do indeed say that they’re reserved for US residents —

butthat they make exceptions for international students who come with their own funding. I’m guessing that that’s a general rule.I see on your blog that you’re from Poland. Is there anything comparable to REU there,

orcan you get scholarship money to go abroad? I don’t know what undergrad summer research programs there are in Europe — if anyone can speak to that question, I’d be much obliged.Comment #5 February 8th, 2007 at 2:40 pm

(You should also ask your professors — they’ll probably know much more than I do.)

Comment #6 February 8th, 2007 at 9:38 pm

Hey, Scott, this is totally off-topic, but comments on the P/NP lecture post are closed: What’s up with these Orion guys?

Comment #7 February 8th, 2007 at 11:45 pm

Well, the two obvious questions about D-Wave are

(1) Should whatever it is that they’ve built really qualify as a “16-qubit quantum computer”?

(2) Supposing the answer is yes, is their proposal scalable? (Note that 16 qubits are still easily simulated classically.)

I haven’t studied their work enough to be able to comment intelligently on these questions — if you want a real discussion of them, I’ll have you turn you over to His Holiness the Pontiff.

I will say, however, that neither question can be answered by simply exhibiting a successful demo — to answer them, one needs to “pry open the black box” and actually understand how their machine works. (By contrast, if they were claiming a 16,000-qubit quantum computer, then a successful demo alone would be enough to convince the world that they had, if not a quantum computer, then certainly

somethingastonishing.)One final comment: even if D-Wave were as successful as anyone could hope, they would

notbe giving a general method to solve NP-complete problems in polynomial time — i.e., they would not be putting NP in BQP. They’d “merely” be building an adiabatic quantum computer, which could provide generic polynomial speedups together exponential speedups in various special cases. (Still a spectacular achievement of course.) To its credit, D-Wave has (I think) conceded as much.Comment #8 February 9th, 2007 at 12:30 am

Thanks, Scott! And thanks for the link. I thought “We’ve got a generalized add-on for solving all your NP-complete problems!” sounded a little too good to be true. 🙂

Comment #9 February 9th, 2007 at 6:05 am

Scott: There’s nothing like REU in Poland. I haven’t found anything similar in a whole Europe (but I was looking only for about hour), but there seem to be some interesting summerschools (like the one I pointed above) which would be perfectly fine for me, if not that I can’t find any happening this year.

My university is quite generous in giving me money for mathematical activities (conferences, IMC, etc.) but due to difference of costs of living in Poland and USA/Western Europe I don’t think they would cover anything more than travel.

BTW: In USA, what is the normal age of highschool student, undergraduate student and graduate student?

Comment #10 February 9th, 2007 at 6:26 am

I don’t know what about Poland, but Charles University in Prague where I studied, sends the students to participate to DIMACS REU program every year. Of course, that concerns combinatorics and related stuff, so if you’re interested in let’s say number theory, you should look for something else, but my impression is, that the opportunities heavily depend on the management and organization skills and interests of the department boss. So, sometimes it’s worth to have a larger area of interests, and look for something in a bit different branch of maths. I think, to participate to an undergrad program, you don’t need to be a well-known expert in the area (of course you should be interested, and attend seminars…, but if you’re a nerd, you can do that) – what is more worth about it is to get some research experience, anyway.

Comment #11 February 9th, 2007 at 9:08 am

BTW: In USA, what is the normal age of highschool student, undergraduate student and graduate student?High school: 14-18 or 15-18 (depends on whether the high school was preceded by “middle school” or “junior high”)

Undergrad: 18-22

Grad student: 22-?

My advice has always been to follow these guidelines as strictly as possible. 😉

Comment #12 February 9th, 2007 at 4:57 pm

Wait, there are people at the Perimeter Institute who will mentor undergraduates for summer research? Who would one contact for that??

Comment #13 February 9th, 2007 at 11:15 pm

Domenic: See this page.

Comment #14 February 14th, 2007 at 2:43 pm

Ah, many thanks! I was looking in the wrong place (under “Outreach” instead of “Positions”).