An idea that I’ve been toying with for a while now is to write a weekly post on my favourite quant-ph arXiv paper which has been released in the last week. I’ve decided after literally minutes of consultation with my office mates that this new regular post should be called "Weakly Abstract".
I expect that the Weakly Abstract will appear on Mondays, though this first week is going to be an exception because I traveled a couple of thousand kilometers yesterday.
I’m not really sure what format the "Weakly Abstract" is going to take. I plan to experiment with a few different styles over the coming weeks. Ideally I’d just like this post to be a bit of an open forum for people to discuss the offerings from the previous week or so on the quant-ph arXiv. I’ll probably get the discussion started by pointing to my favourite paper, or the most scited paper on SciRate each week and then people can take it from there.
I doubt that I’ll always take this super-seriously and I’d like it if people keep the discussion as light and humorous as possible. Be polite but don’t worry too much about keeping the tone too professional, I want this thread to be relatively accessible to all but, of course, if you want to throw down some serious math be my guest. In short, a chatty and jokey atmosphere is highly encouraged.
Oh, and if anyone has any suggestions for papers they’d like discussed can feel free to email me or to let me know in the comments.
So, here goes…
For the first Weakly Abstract I’d like you all to point your browsers towards "Hamiltonian Quantum Cellular Automata in 1D" by Daniel Nagaj and Pawel Wocjan (arXiv:0802.0886):
Hamiltonian Quantum Cellular Automata in 1D
Authors: Daniel Nagaj, Pawel Wocjan
(Submitted on 6 Feb 2008)
We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of 10-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process. We only require the ability to prepare an initial computational basis state which encodes both the quantum circuit and its input. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time polynomially long in the size of the quantum circuit has passed, the result of the computation is obtained with high probability by measuring a few qudits in the computational basis.
This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless BPP=BQP).
I really like this paper. It is well written and with 11 scitations, Nagaj and Wocjan’s paper is currently the most scited paper of last week on SciRate.
The key point of this paper is that the authors constructively prove that it is possible to perform efficient quantum computations by time evolving relatively simple, separable, low dimensional initial states by a fixed time-independent 1D nearest neighbour translationally invariant Hamiltonian and measuring in a fixed basis. As is pointed out in the second paragraph of the abstract, this result sets up a compelling dichotomy – either BPP=BQP (that is classical computers can simulate quantum computers) or the folklore belief in the condensed matter physics that the time evolution of all low-dimensional 1D translationally invariant nearest neighbour systems can be simulated classically is wrong.
A similar, yet more complex, construction that proves the basically the same concept was presented in an earlier paper by Vollbrecht and Cirac (arXiv:0704.3432v2) which I also highly recommend.
In Nagaj and Wocjan’s constructions all of the control required for the computation is programmed into the initial state of the computer. In a sense, all of the description complexity of any "circuit" that is implemented is pushed into the initial state of the system. The compelling point is that this can always be done for efficient quantum algorithms with a separable input that is in a computational basis state. All of the superposition and entanglement that is normally associated with the "power" of a quantum computation is performed via the time evolution by the one, simple, time-independent entangling Hamiltonian (and for efficient algorithms the amount of time you have to wait for an answer isn’t very long).
This result seemed really surprising to me at first, but I guess in a lot of ways it isn’t really that dissimilar to the 1-way model of quantum computing. In the 1-way model all of the quantumish part of a computation is thrown into the initial state (normally thought of as a 2D cluster state). The circuit complexity is pushed into the measurement stage of the computation (albeit with a bit of feed-forward control).
Wheras in the model of Nagaj and Wocjan’s the complexity of the circuit happens, mostly, in the initial state. Though there is of course the tricky point of having to wait enough time for the computation to be able to give the correct result, this is essentially something that can’t be sped up.
In summary, I think this paper is tops because it gives us a real target for resolving the problem of quantum versus classical computation. If we can demonstrate a method for simulating the time evolution of the Hamiltonians involved in Nagaj and Wocjan’s constructions then BQP=BPP (and I’m out of a job). Though it should be noted that a recent paper by Schuch et al (arXiv:0801.2078v1) suggests that given current simulation methods in computational physics this is very unlikely.
These results, to me, gives one of the more compelling arguments for pushing ahead with development quantum computers. While we now know that simulating the static properties of generic quantum systems (like finding the ground state) is really hard both classically and quantumly, all of this recent work is suggesting that when it comes to simulating dynamics we may be able to use quantum computers to do a lot more than we ever can with classical devices.