<p>I posted some quantum complexity theory project ideas at <a href="http://scottaaronson.com/blog/?p=471">http://scottaaronson.com/blog/?p=471</a></p>

<p>(But beware, most of these are problems that have been open for years!  My suggestion for an undergraduate project would be to break off a chunk of one of the problems.)</p>

CC BY-SA 2.5
2010-10-27T20:41:55.737Z
2010-10-27T20:41:55.737Z
Scott Aaronson
<p>One project I would suggest is this: Try to develop a quantum algorithm based on quantum random walk for linear programming. For the project you should first learn some basic facts about quantum random walks and how they are algorithmically useful, second about randomized simplex type algorithms and third trying to combine the two. Part 3 is very ambitious and I do not know if anything fruitful can be said at all, but parts 1 and 2 are already nice for an undergraduate project.  </p>

CC BY-SA 2.5
2010-08-30T16:37:33.413Z
That's a really nice suggestion. There are in fact a good number of algorithms that might benefit from specialized random walks. LT/Raptor error correcting codes are based on a random walk for example. Up vote from me. And it's nice to see you on here, Gil. :-)
Ross Snider
CC BY-SA 2.5
2010-08-30T21:31:03.617Z
I didn't know there were such things as quantum random walks ! nice idea !
Suresh Venkat
CC BY-SA 2.5
2010-08-30T21:52:10.103Z
Suresh: Yes, there are. They turn out to be quite an important approach to quantum algorithms. 

The thing about algorithms projects, though, is that it is trivial to get a square root speed-up, and very very hard to get anything better. Perhaps another idea would be to look at trying to get polynomial time algorithms down to log time, as in the recent algorithm for solving linear systems of equations.
Joe Fitzsimons
CC BY-SA 2.5
2010-08-30T12:09:55.387Z
2010-08-30T12:09:55.387Z
Gil Kalai
<p>DWaves results with image search are a little odd. There is not currently strong evidence that DWave's devices cannot be efficiently simulated. This has been discussed in great detail on a number of blogs (for <a href="http://scottaaronson.com/blog" rel="noreferrer">Scott Aaronson</a> and <a href="http://dabacon.org/pontiff" rel="noreferrer">Dave Bacon</a> have both covered DWave numerous times).</p>

<p>Now, leaving that aside, there are a huge number of potential projects, depending in what aspect of quantum computing you are interested in. It also depends on the level of your knowledge about quantum mechanics and physics. Architecture type questions often become quite physicsy, since experimental limitations play a big part in determining what problems are worth looking at. Algorithms and communications complexity are much more CS oriented areas.</p>

<p>There are a number of different models of quantum computation, and there is steeper barriers to entry for some rather than others. Adiabatic and topological quantum computing tend to be somewhat harder to get into than the circuit model and the measurement based model of computation.</p>

<p>One problem I have had success with a summer student working on was approximating fault-tolerance thresholds for various error-correction codes by simulation. This is something that has a relatively low barrier to entry. Another idea is to look at quantum cellular automata schemes for special purpose tasks (encoding, measurement, state preparation). </p>

<p>You mentioned machine learning, so perhaps you may want to look at using evolutionary programming to evolve quantum circuits for various simple problems. I have played around with this a few times, and it seems you can get some quite nice behaviour (for example, evolving search rules).</p>

<p>I could go on listing random ideas that might make a suitable project, but if you could give more of an idea as to what area you are interested in, I think you will get better answers. A fundamental question might simply be are you interested in a coding project, one on hardware design, one on pure theory, etc.? Depending on which way you want to go, there will be a range of different possibilities.</p>

CC BY-SA 2.5
2010-08-30T03:25:50.410Z
2010-08-30T03:25:50.410Z
Joe Fitzsimons
<p>I suggest something like providing current quantum computing development tools (such as libquantum) with the capability of taking advantage of CUDA-enabled GPUs to accelerate the simulations. Quantum computing is more or less about linear algebra, i.e. matrix and vector operations, which was what GPUs was designed for in the first place.</p>

CC BY-SA 2.5
2010-08-29T11:27:02.560Z
simulations like what?
Deyaa
CC BY-SA 2.5
2010-08-29T17:53:43.267Z
Quantum computing development tools allows you to simulate quantum algorithms and protocols, including Shor's algorithm, Grover's search, quantum teleportation, error correcting codes, and algorithms you created and want to test for yourself.
Mohammad Alaggan
CC BY-SA 2.5
2010-08-29T00:23:12.840Z
2010-08-29T00:23:12.840Z
Mohammad Alaggan
<p>Quantum computing themed languages such as QCL have been created for thesis projects. In fact any quantum computing based languages I've seen implemented on the web have been done for thesis projects. You could also try to code up a quantum emulator. In the book "Quantum Computing for Computer Scientists" they provide programming drills that collectively add up to such an emulator.</p>

CC BY-SA 2.5
2010-09-05T03:35:40.650Z
2010-09-05T03:35:40.650Z
Vincent Russo
<p>I don't know how helpful this will be, but maybe it will offer some guidance.</p>

<p>In Spring 2009 Sasha Razborov taught a course on quantum computing.  <a href="http://people.cs.uchicago.edu/~razborov/teaching/spring09.html" rel="nofollow">The course website</a> contains some "project" ideas, as well as references to a few seminal quantum papers.  </p>

<p>The "projects" on the page are really just "more involved homework problems", so they are probably not suitable in and of themselves for a senior thesis, nor will they take 11 months.  However, those problems and/or some of the references might spark some good ideas for you.</p>

CC BY-SA 2.5
2010-08-29T23:08:18.500Z
2010-08-29T23:08:18.500Z
Joshua Grochow
<p>I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?</p>

CC BY-SA 2.5
2010-08-28T16:00:25.693Z
It would help if you could give an example of the type of project you would consider appropriate given the time you have for this project and the intended difficulty. Like is reading a paper in detail acceptable as a project?
Robin Kothari
CC BY-SA 2.5
2010-08-28T16:19:53.930Z
Example: combining (or inventing new ones) machine learning techniques with quantum computing to solve a hard problem
Google used machine learning algorithms and D-wave quantum computer to do much faster image searching.
Time, I've: 11 month
difficulty: medium (Undergraduate)
Deyaa
CC BY-SA 2.5
2010-08-28T18:17:00.010Z
D-Wave!  Have your lecturers recommended their technology to you?
Charles Stewart
CC BY-SA 2.5
2010-08-28T18:42:59.863Z
I just showing an example in Google case !
I don't have any lecturer and my supervisor has no idea about quantum computing. I self study this field so I can't get an idea alone
Deyaa
CC BY-SA 2.5
2010-08-28T20:13:56.040Z
I think this should be a community wiki, assuming it is in scope at all.
Lev Reyzin
CC BY-SA 2.5
2010-08-28T21:06:01.347Z
I don't understand the down vote on this question. Although usually I would suggest that Deyaa browse this site and others and "quantize" questions until he finds a quantum computing question he thinks is interesting, specifically asking for an unexplored area of subject X doesn't seem particularly off topic to me.
Ross Snider
CC BY-SA 2.5
2010-08-28T22:33:41.130Z
I agree. I don't understand the downvote either. seems like a reasonable question.
Suresh Venkat
CC BY-SA 2.5
2010-08-28T23:58:26.033Z
@Ross: I downvoted it, simply because the question was unclear, very open-ended, subjective, and certainly not something with a clear "correct answer" (see also http://cstheory.stackexchange.com/faq). With more careful explanations and in the "community wiki" mode it would have most likely avoided my downvote. Apologies if this seems unnecessarily harsh, but I do think that people should pay more attention to the formulation of their questions (and use the CW flag correctly, especially as nobody else can fix it currently).
Jukka Suomela
CC BY-SA 2.5
2010-08-30T03:20:54.503Z
It might help for the purposes of the beta if a higher-reputation user could edit the question to address the points Jukka raises above, or sets it to community wiki.  With some editing, the question can be brought into line with the FAQ.
Anand Kulkarni
CC BY-SA 2.5
2010-08-30T04:09:20.263Z
unfortunately we don't have any moderators who can set the CW bit. as for re-editing the question, Jukka's comment doesn't suggest what changes need to be made.
Suresh Venkat
CC BY-SA 2.5
2010-08-30T04:10:19.973Z
@Deyaa, I think trying to answer Joe Fitzsimmons and Jukka Suomela's questions will help you craft a better question.
Suresh Venkat
<quantum-computing><soft-question>
Quantum computing project ideas
Deyaa
# Quantum computing project ideas

(Asked by: username_0 on 2010-08-28)

I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?

**Tags:** quantum-computing, soft-question
> **Comments:**
> **username_1**: It would help if you could give an example of the type of project you would consider appropriate given the time you have for this project and the intended difficulty. Like is reading a paper in detail acceptable as a project?  
> **username_0**: Example: combining (or inventing new ones) machine learning techniques with quantum computing to solve a hard problem Google used machine learning algorithms and D-wave quantum computer to do much faster image searching. Time, I've: 11 month difficulty: medium (Undergraduate)  
> **username_2**: D-Wave!  Have your lecturers recommended their technology to you?  
> **username_0**: I just showing an example in Google case ! I don't have any lecturer and my supervisor has no idea about quantum computing. I self study this field so I can't get an idea alone  
> **username_3**: I think this should be a community wiki, assuming it is in scope at all.  
> **username_4**: I don't understand the down vote on this question. Although usually I would suggest that Deyaa browse this site and others and "quantize" questions until he finds a quantum computing question he thinks is interesting, specifically asking for an unexplored area of subject X doesn't seem particularly off topic to me.  
> **username_5**: I agree. I don't understand the downvote either. seems like a reasonable question.  
> **username_6**: @Ross: I downvoted it, simply because the question was unclear, very open-ended, subjective, and certainly not something with a clear "correct answer" (see also http://cstheory.stackexchange.com/faq). With more careful explanations and in the "community wiki" mode it would have most likely avoided my downvote. Apologies if this seems unnecessarily harsh, but I do think that people should pay more attention to the formulation of their questions (and use the CW flag correctly, especially as nobody else can fix it currently).  
> **username_7**: It might help for the purposes of the beta if a higher-reputation user could edit the question to address the points Jukka raises above, or sets it to community wiki.  With some editing, the question can be brought into line with the FAQ.  
> **username_5**: unfortunately we don't have any moderators who can set the CW bit. as for re-editing the question, Jukka's comment doesn't suggest what changes need to be made.  
> **username_5**: @Deyaa, I think trying to answer Joe Fitzsimmons and Jukka Suomela's questions will help you craft a better question.  

---

## 6 answers

### Answer by username_8 on 2010-10-27. Score: 29

I posted some quantum complexity theory project ideas at <http://scottaaronson.com/blog/?p=471>

(But beware, most of these are problems that have been open for years! My suggestion for an undergraduate project would be to break off a chunk of one of the problems.)


---

### Answer by username_9 on 2010-08-30. Score: 17

One project I would suggest is this: Try to develop a quantum algorithm based on quantum random walk for linear programming. For the project you should first learn some basic facts about quantum random walks and how they are algorithmically useful, second about randomized simplex type algorithms and third trying to combine the two. Part 3 is very ambitious and I do not know if anything fruitful can be said at all, but parts 1 and 2 are already nice for an undergraduate project.

> **Comments:**
> **username_4**: That's a really nice suggestion. There are in fact a good number of algorithms that might benefit from specialized random walks. LT/Raptor error correcting codes are based on a random walk for example. Up vote from me. And it's nice to see you on here, Gil. :-)  
> **username_5**: I didn't know there were such things as quantum random walks ! nice idea !  
> **username_10**: Suresh: Yes, there are. They turn out to be quite an important approach to quantum algorithms.   The thing about algorithms projects, though, is that it is trivial to get a square root speed-up, and very very hard to get anything better. Perhaps another idea would be to look at trying to get polynomial time algorithms down to log time, as in the recent algorithm for solving linear systems of equations.  

---

### Answer by username_10 on 2010-08-30. Score: 12

DWaves results with image search are a little odd. There is not currently strong evidence that DWave's devices cannot be efficiently simulated. This has been discussed in great detail on a number of blogs (for [Scott Aaronson](http://scottaaronson.com/blog) and [Dave Bacon](http://dabacon.org/pontiff) have both covered DWave numerous times).

Now, leaving that aside, there are a huge number of potential projects, depending in what aspect of quantum computing you are interested in. It also depends on the level of your knowledge about quantum mechanics and physics. Architecture type questions often become quite physicsy, since experimental limitations play a big part in determining what problems are worth looking at. Algorithms and communications complexity are much more CS oriented areas.

There are a number of different models of quantum computation, and there is steeper barriers to entry for some rather than others. Adiabatic and topological quantum computing tend to be somewhat harder to get into than the circuit model and the measurement based model of computation.

One problem I have had success with a summer student working on was approximating fault-tolerance thresholds for various error-correction codes by simulation. This is something that has a relatively low barrier to entry. Another idea is to look at quantum cellular automata schemes for special purpose tasks (encoding, measurement, state preparation).

You mentioned machine learning, so perhaps you may want to look at using evolutionary programming to evolve quantum circuits for various simple problems. I have played around with this a few times, and it seems you can get some quite nice behaviour (for example, evolving search rules).

I could go on listing random ideas that might make a suitable project, but if you could give more of an idea as to what area you are interested in, I think you will get better answers. A fundamental question might simply be are you interested in a coding project, one on hardware design, one on pure theory, etc.? Depending on which way you want to go, there will be a range of different possibilities.


---

### Answer by username_11 on 2010-08-29. Score: 4

I suggest something like providing current quantum computing development tools (such as libquantum) with the capability of taking advantage of CUDA-enabled GPUs to accelerate the simulations. Quantum computing is more or less about linear algebra, i.e. matrix and vector operations, which was what GPUs was designed for in the first place.

> **Comments:**
> **username_0**: simulations like what?  
> **username_11**: Quantum computing development tools allows you to simulate quantum algorithms and protocols, including Shor's algorithm, Grover's search, quantum teleportation, error correcting codes, and algorithms you created and want to test for yourself.  

---

### Answer by username_12 on 2010-09-05. Score: 3

Quantum computing themed languages such as QCL have been created for thesis projects. In fact any quantum computing based languages I've seen implemented on the web have been done for thesis projects. You could also try to code up a quantum emulator. In the book "Quantum Computing for Computer Scientists" they provide programming drills that collectively add up to such an emulator.


---

### Answer by username_13 on 2010-08-29. Score: 2

I don't know how helpful this will be, but maybe it will offer some guidance.

In Spring 2009 Sasha Razborov taught a course on quantum computing. [The course website](http://people.cs.uchicago.edu/~razborov/teaching/spring09.html) contains some "project" ideas, as well as references to a few seminal quantum papers.

The "projects" on the page are really just "more involved homework problems", so they are probably not suitable in and of themselves for a senior thesis, nor will they take 11 months. However, those problems and/or some of the references might spark some good ideas for you.


---

