Tell me more ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.
up vote 6 down vote favorite
4

Can anyone explain to me why we have had no major breakthroughs in the theory of quantum computation in the past 15 years?

Shor's algorithm set the standard, since then we've had Grover's algorithm and an improvement on the Deutsch–Jozsa algorithm. What quantum algorithms of practical value have been created since Grover's?

What makes it so hard to create a quantum algorithm?

Thanks.

share|improve this question
1  
If you are only interested in algorithms and not actual physics then you'd be better off asking this at the TCS site: cstheory.stackexchange.com Also, I don't agree with your sentiment of no breakthroughs. Maybe you don't find anything in your local newspapers but quantum algorithms is huge and thriving research area with nice progress. – Marek Mar 22 '11 at 14:39
6  
There has been considerable progress on quantum algorithms, although no breakthroughs on the scale of factoring or Grover's search algorithm. See this paper for a list, and a detailed survey of many of them. – Peter Shor Mar 22 '11 at 16:06
6  
Here is a link to the arXiv (free) version of the paper @Peter Shor gave in the comment above : arxiv.org/abs/0812.0380 – Frédéric Grosshans Mar 22 '11 at 16:16
4  
I can't improve on the comment by Shor/Grosshans, but I don't think it's fair to restrict "major breakthrough" to "algorithms" alone. Another "major breakthroughs" are discoveries of how to do quantum error correction. Without some way of doing error correction, nobody's ever going to be able to implement large-scale calculations. And I think there have been significant improvements (on the theory side) in error correction techniques in the last 15 years. – Anonymous Coward Mar 31 '11 at 18:45
1  
en.wikipedia.org/wiki/Timeline_of_quantum_computing What makes it hard? Why do you think there are so many big difficult and smaller easy programming languages at all? – Werner Schmitt Jun 16 '11 at 1:51
show 4 more comments

2 Answers

up vote 5 down vote

I would say Knill and Laflamme's work on Efficient Quantum Computation with just LINEAR optics was a pretty big breakthrough.

It allowed for renewed interest and thinking about the role of photons in quantum computation.

See--> http://www.nature.com/nature/journal/v409/n6816/abs/409046a0.html

share|improve this answer
up vote 1 down vote

Apart from the others already mentioned, one very recent example of a breakthrough that has both intrinsic and applied value is the June 2012 paper by Stephen Jordan, Keith Lee, John Preskill on Quantum algorithms for Quantum Field theories.

Intrinsic value - The paper has shown that simple quantum field theories can be simulated efficiently on a quantum computer, thus paving the way towards a quantum algorithm for simulating the Standard Model of particle physics. 'Such an algorithm would establish that, except for quantum-gravity effects, the standard quantum circuit model suffices to capture completely the computational power of our universe'

Possible applications - The ability to efficiently simulate field theories would give us the power to analyze systems that have evaded physicists for many years, ranging from very high-energy particle collisions and quantum many-body systems to the early universe itself.

References:

  1. The paper was published in Science
  2. Science-Mag perspectives on the paper can be found here.
  3. The full-text extended pre-print can be found on Arxiv.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.