12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Robin Kothari Aug 28 '10 at 16:00
  • $\begingroup$ 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) $\endgroup$ – Deyaa Aug 28 '10 at 16:19
  • 3
    $\begingroup$ I think this should be a community wiki, assuming it is in scope at all. $\endgroup$ – Lev Reyzin Aug 28 '10 at 20:13
  • 2
    $\begingroup$ @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 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). $\endgroup$ – Jukka Suomela Aug 28 '10 at 23:58
  • 3
    $\begingroup$ @Deyaa, I think trying to answer Joe Fitzsimmons and Jukka Suomela's questions will help you craft a better question. $\endgroup$ – Suresh Venkat Aug 30 '10 at 4:10
24
$\begingroup$

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.)

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. :-) $\endgroup$ – Ross Snider Aug 30 '10 at 16:37
  • $\begingroup$ I didn't know there were such things as quantum random walks ! nice idea ! $\endgroup$ – Suresh Venkat Aug 30 '10 at 21:31
  • 2
    $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons Aug 30 '10 at 21:52
10
$\begingroup$

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 and Dave Bacon 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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ simulations like what? $\endgroup$ – Deyaa Aug 29 '10 at 11:27
  • $\begingroup$ 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. $\endgroup$ – M. Alaggan Aug 29 '10 at 17:53
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.