Over the past couple weeks, I’ve mostly been preparing for my summer project at IQC by getting familiar with the literature on quantum walks and, in particular, scattering on graphs. I didn’t know much about either so I found a couple review papers, as well as some key papers by Andrew Childs, the researcher at IQC that I’ll most likely be working with.
Quantum walks are the quantum mechanical version of classical random walks. Basically, by moving to quantum systems, you can exploit interference to get faster spreading, shorter mixing times, shorter hitting times, and all kinds of neat tricks that can be useful for developing efficient algorithms. It turns out quantum walks are universal for quantum computation, so if you can develop a quantum algorithm for some problem, you can do so using quantum walks. The hope is that particular problems will be easier to solve when thought of in terms of quantum walks than, say, quantum circuits or adiabatic computing.
Scattering on graphs are a particular type of quantum walk in which you take a finite graph, staple semi-infinite tails to it, send propagating quantum states down one tail, and measure the probability that they arrive at the other tails. This style of walk actually is what was used to prove that quantum walks are universal and so there’s plenty of interest in studying their features.
Today, I was mostly trying to assess what extra effects decoherence offers to quantum walks. While walks are traditionally treated as peaceful strolls through Hilbert space, considering decoherence is not only more realistic (given that any implementation of quantum computing will be subject to at least some environmental noise) but it can actually be useful. In particular, a little bit of decoherence allows for smoother spreading (quantum walks often propagate in a wave-like fashion due to interference effects) and shorter mixing times. Introducing decoherence also brings to the table one of my favorite quantum tricks, the quantum Zeno effect. The basic idea is that if you continually monitor a system (i.e. continually measure it), it can’t change its state due to wavefunction collapse (like a classical bully continually pinning a quantum nerd to the ground as he tries to get up and run away).
I’m particularly interested in quantum walks with decoherence because they’ve recently been the model for assessing the awesome efficiency of photosynthesis. This is part of a larger trend of quantum info people scouring biology to see whether any organisms are performing quantum computations or otherwise exploiting neat quantum tricks.
I also read a paper by USC’s Todd Brun and Martin Varbanov which looked at various tweaks you can perform to a graph with tails (as described above) and how those tweaks affect the S-matrix (a characterization of how propagating states will be reflected or transmitted when chucked at a graph). Dr. Childs mentioned that it might be interesting to look at the connection between graphs and their resulting S-matrices and this paper explores exactly some of those connections.
Related posts
Awesome. I look forward to regular progress reports!
Despite my above comments, I’ll try and make ‘em as readable as possible. Good practice for the day I forsake real science and exploit my PhD status to sell new-agey books explaining time, consciousness, and love in terms of quantum entanglement.
You might also want to check out some papers by Wisconsin physicists. I know Robert Joynt and Susan Coppersmith have done some work on quantum random walks and analyzed the effects of using bosons or fermions.
Discovering the phrase “Np-hard-core-boson” alone was worth scanning a few of their papers.
Thanks for the heads up! Looks like they’ve done some interesting numerical work on the graph isomorphism problem by juggling bosons and fermions, but dropped this line of research in the last five years.
The also have a recent paper that hasn’t made it to a journal yet arXiv:1002.3003
Good luck with the project!