Here's a good article in this month's Scientific American: How Noise Can Help Quantum Entanglement.
Decoherence is the largest obstacle in the physical implementation of quantum computers, so steps towards overcoming the current problems with it are important.
Friday, November 6, 2009
Tuesday, November 3, 2009
On SlideShare- Cove: A Practical Quantum Computer Programming Framework
Here's the slide share presentation of the final draft of my dissertation on Cove.
Saturday, October 31, 2009
Ramping up work on Cove again
I really have not spent too much time working on Cove (my quantum computing framework) for a few months while I wrapped up my dissertation and took some time off. I'll be starting to ramp up work on Cove again in the coming weeks. My initial target will be reducing the memory requirements of the simulation so that I can carry out larger ones. (Efficient simulation has never been a goal.) After that I plan to continue the factoring example, followed by work on some papers.
Wednesday, October 21, 2009
Limit on rate of quantum computing
Levitin and Toffoli recently published a paper in Physics Review Letters titled "The fundamental limit on the rate of quantum dynamics: the unified bound is tight" [1]. The title is a pretty academic sounding, but the final sentence of the abstract sums it up perfectly: "These results establish the fundamental quantum limit on the rate of operation of any information-processing system." Hitting this limit will take decades if Moore's law keeps up however. There is a great summary on the paper here and you can find the entire paper on arXiv here [1].
It is impressive that this limit has been established, but there is still a lot of work ahead to reach this limit. Nonetheless we should be able to do impressive things regardless of this limit. Turing started establishing what we could compute in the 1930's [2], but that hasn't had a noticeable impact to the average person on what computing technology can accomplish. Think of all the possible improvements in algorithms as well. While there may be a limit on the speed of computation, algorithms may lend short cuts that render the limit a mute point. In quantum algorithms especially, we have quite a ways to go with only a handful of practical ones at present. Furthermore, these existing quantum algorithms have shown that previously hard problems can be made practical via quantum computation.
The name Toffoli will ring a bell to those familiar with quantum computing. The Toffoli gate, or controlled controlled not, is one of the fundamental gates. Furthermore the reversible equivalent of any classical computation can be constructed using Toffoli gates [3].
References
[1] L. B. Levitin and T. Toffoli, "The fundamental limit on the rate of quantum dynamics: the unified bound is tight," Physics Review Letters, vol. 103, 13Oct2009 2009.
[2] A. Turing, "On Computable Numbers, with an Application to Entscheid-ungsproblem," Proc. London Math Society, vol. 42, pp. 230-265, 1936.
[3] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 1 ed. Cambridge, UK: Cambridge University Press, 2000.
It is impressive that this limit has been established, but there is still a lot of work ahead to reach this limit. Nonetheless we should be able to do impressive things regardless of this limit. Turing started establishing what we could compute in the 1930's [2], but that hasn't had a noticeable impact to the average person on what computing technology can accomplish. Think of all the possible improvements in algorithms as well. While there may be a limit on the speed of computation, algorithms may lend short cuts that render the limit a mute point. In quantum algorithms especially, we have quite a ways to go with only a handful of practical ones at present. Furthermore, these existing quantum algorithms have shown that previously hard problems can be made practical via quantum computation.
The name Toffoli will ring a bell to those familiar with quantum computing. The Toffoli gate, or controlled controlled not, is one of the fundamental gates. Furthermore the reversible equivalent of any classical computation can be constructed using Toffoli gates [3].
References
[1] L. B. Levitin and T. Toffoli, "The fundamental limit on the rate of quantum dynamics: the unified bound is tight," Physics Review Letters, vol. 103, 13Oct2009 2009.
[2] A. Turing, "On Computable Numbers, with an Application to Entscheid-ungsproblem," Proc. London Math Society, vol. 42, pp. 230-265, 1936.
[3] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 1 ed. Cambridge, UK: Cambridge University Press, 2000.
A quantum crypto network in China
This sounds impressive: Field experiment on a robust hierarchical metropolitan quantum cryptography network. Like a lot of things in quantum information, the leap between the lab and practical real world use is a big one. What I found most interesting about this is the use of quantum routers.
As the article states, routers are needed because of the no-cloning theorem. The no-cloning theorem states that you cannot copy the state of an arbitrary quantum system. In other words you cannot do a copy and paste. You can transfer it, essentially a cut and paste, via teleportation. You cannot do the copy and paste because to copy the system you basically end up doing a measurement, which alters the state of the system.
As the article states, routers are needed because of the no-cloning theorem. The no-cloning theorem states that you cannot copy the state of an arbitrary quantum system. In other words you cannot do a copy and paste. You can transfer it, essentially a cut and paste, via teleportation. You cannot do the copy and paste because to copy the system you basically end up doing a measurement, which alters the state of the system.
Thursday, October 15, 2009
Another step forward: Quantum algorithm for solving linear systems of equations
Harrow, Hassidim, and Lloyd have recently published a paper titled "Quantum algorithm for solving linear systems of equations" [1]. You can find the paper here on ArXiv and there is a pretty good summary article here from MIT news. (Lloyd is pretty big in the pop sci world of quantum computing too, he's written Programming the Universe and a recent Scientific American article for instance.)
As the title says, they outline a quantum algorithm for solving linear systems of equations. In other words given:
The algorithm solves for the vector x, when matrix A and b are known. So why is this useful? Linear systems of equations show up all the time. Some diverse examples include: oil exploration, electrical networks, and flight crew scheduling [2] just to name a few. Of course, as they point out even in the abstract, they aren't actually solving for x, but "...an
approximation of the expectation value of some operator associated with x..." [1]. Another highlight is that this algorithm is an exponential speed up over the best known classical value! I recommend the MIT article from above if you want a general overview, or the entire paper (obviously) for all the details.
This is another important step forward we've had recently in addition to the steps forward in physical implementations I've written about here and here. Up until now there are really only two practical quantum algorithms, and they get cited quite a bit: Shor's algorithm for factoring [3] and Grover's fast database search [4]. Both of these where developed in the mid 1990s. Furthermore both of these algorithms have pretty narrow applications, while linear systems of equations are everywhere. We'll see how things pan out, but it could arguably be considered the most important development to date in the currently sparse universe of quantum algorithms.
References
[1] A. W. Harrow, A. Hassidim, and S. Lloyd, "Quantum algorithm for solving linear systems of equations," Phys. Rev. Lett, vol. 15, p. 15, 07Oct2009 2009.
[2] D. C. Lay, Linear Algebra and Its Applications, 1 ed. Reading, MA: Addison-Wesley, 1997.
[3] P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM Journal on Computing, vol. 26, p. 25, October 1997 1997.
[4] L. K. Grover, "A fast quantum mechanical algorithm for database search," Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219, 1996.
As the title says, they outline a quantum algorithm for solving linear systems of equations. In other words given:
The algorithm solves for the vector x, when matrix A and b are known. So why is this useful? Linear systems of equations show up all the time. Some diverse examples include: oil exploration, electrical networks, and flight crew scheduling [2] just to name a few. Of course, as they point out even in the abstract, they aren't actually solving for x, but "...anapproximation of the expectation value of some operator associated with x..." [1]. Another highlight is that this algorithm is an exponential speed up over the best known classical value! I recommend the MIT article from above if you want a general overview, or the entire paper (obviously) for all the details.
This is another important step forward we've had recently in addition to the steps forward in physical implementations I've written about here and here. Up until now there are really only two practical quantum algorithms, and they get cited quite a bit: Shor's algorithm for factoring [3] and Grover's fast database search [4]. Both of these where developed in the mid 1990s. Furthermore both of these algorithms have pretty narrow applications, while linear systems of equations are everywhere. We'll see how things pan out, but it could arguably be considered the most important development to date in the currently sparse universe of quantum algorithms.
References
[1] A. W. Harrow, A. Hassidim, and S. Lloyd, "Quantum algorithm for solving linear systems of equations," Phys. Rev. Lett, vol. 15, p. 15, 07Oct2009 2009.
[2] D. C. Lay, Linear Algebra and Its Applications, 1 ed. Reading, MA: Addison-Wesley, 1997.
[3] P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM Journal on Computing, vol. 26, p. 25, October 1997 1997.
[4] L. K. Grover, "A fast quantum mechanical algorithm for database search," Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219, 1996.
Tuesday, October 6, 2009
Why I Chose to Study Quantum Computing
One of the biggest questions facing doctoral students is: what area will you do your research in? Your choices may vary depending on the school and program. At the very least your research area will play a large role on who serves on your committee. I went to Colorado Tech University's Institute for Advance Studies (CTU IAS) where we were given quite a bit of leeway in the area selected. This post is based on my Doctorate experience at Colorado Tech.
Switching topics can lengthen the time to finish your dissertation, so it is best if you can choose one and stick with it. Obviously this cannot always be the case, but this needs to be kept in mind. Another thing that may lengthen the doctoral process is picking a project that is too ambitious or too much work for a dissertation. If you think about it the end result you need to finish is a dissertation that you've successfully defended and had your committee sign off on. There aren't any more points for doing three times as much work. So with that in mind scope should be limited for your dissertation. Your dissertation can be just the first step and the subsequent steps can be areas for future work.
As is probably obvious from this blog, I selected quantum computing programming as my research area. My focus wasn't so narrow at first, I had originally selected the more general topic of quantum computing. As I read more and more I always kept an eye on the software side of things. My physics background was limited, and I had none in quantum computing. So I had enough work cut out on the general quantum computing side of things. My day job was writing software, so I did feel that I had a perspective that others in the field might not have. Thus my choice evolved into quantum computer programming as I progressed through the literature.
As the tittle of this post says, why quantum computing? Here is a list of the motivating reasons behind the reason I selected quantum computer programming (in no particular order, and not formalized when I did the selection):
Switching topics can lengthen the time to finish your dissertation, so it is best if you can choose one and stick with it. Obviously this cannot always be the case, but this needs to be kept in mind. Another thing that may lengthen the doctoral process is picking a project that is too ambitious or too much work for a dissertation. If you think about it the end result you need to finish is a dissertation that you've successfully defended and had your committee sign off on. There aren't any more points for doing three times as much work. So with that in mind scope should be limited for your dissertation. Your dissertation can be just the first step and the subsequent steps can be areas for future work.
As is probably obvious from this blog, I selected quantum computing programming as my research area. My focus wasn't so narrow at first, I had originally selected the more general topic of quantum computing. As I read more and more I always kept an eye on the software side of things. My physics background was limited, and I had none in quantum computing. So I had enough work cut out on the general quantum computing side of things. My day job was writing software, so I did feel that I had a perspective that others in the field might not have. Thus my choice evolved into quantum computer programming as I progressed through the literature.
As the tittle of this post says, why quantum computing? Here is a list of the motivating reasons behind the reason I selected quantum computer programming (in no particular order, and not formalized when I did the selection):
- Interesting subject. I wanted to pick something I was truly interested in. Without the passion for the subject I wouldn't have been able to sacrifice weekends, evenings, time with friends and family, etc. It was the true interest in the subject that allowed me to spend so much time on it.
- Bleeding edge. I wanted to pick something bleeding edge in computer science, as the body of work is much less- which means there are more places to select from for doctoral work. I figured since quantum computers were probably 15+ years out when I started (2006), this met the criteria. I suppose this could also be listed as selection of an "un-matured" area in Computer Science.
- Ground breaking area. Since quantum computers operate fundamentally different than classical (existing) computers this pretty much sealed the deal on this one. How much more ground breaking can you get then something that works differently than every other computer built?
- "Wow" factor. While it shouldn't really be listed as a criteria for selection of a research area if you want to be formal, it didn't hurt. As any doctoral student is at various points in the process, I became frustrated and stumped. I bring this point up because I was able to sit back and say to myself, "hey this is programming photons (or electrons, etc), this is cool stuff!" I don't think I would've been able to give myself that motivating kick quite as much if I had selected another subject area.
Subscribe to:
Posts (Atom)
