February 25, 2009

How to Think Like A Quantum Computer Programmer

Matt Hastings writes in an understandable way about adiabatic quantum computer algorithms. The last half of this article describes the question and answer analysis that Matt Hastings uses to try and create a useful algorithm for quantum computing. Adiabatic Quantum Computers are the kind of computer that Dwave systems of vancouver is trying to make. Dwave systems is at 128 qubits now and could be at 2048 by the end of the 2009.

This summary goes over two brief introductory paragraphs of how quantum computers and the sub-type of adiabatic quantum computers work. Next the question and answer analysis is provided with minimal math. You still need to know something about computer algorithms and how fast computers can solve problems. Some pointers exponential time means problems rapidly become to big to solve. Polynomial time means that useful problems can be solved in reasonable time.

How General Quantum Computing Works
There are many proposals for doing quantum computing. But basically all of them involve the following sequence of steps: you initialize a system to some quantum state, you evolve it under some Hamiltonian (which may be time-dependent), and then you measure something to get your answer. If you think about the usual gate model of quantum computing, you can imagine producing the effect of each of those 2-qubit gates by acting for a short time with a Hamiltonian that acts just on those two qubits (in fact, that is how it would actually have to be done in practice). If you think about measurement based quantum computing, there are in fact many measurement steps in between, not just one at the end, but all of those intervening measurement steps could be modeled by Hamiltonian dynamics in some larger Hilbert space. So, everything in quantum computing is just create a state, evolve, and then measure.

How Adiabatic Quantum Computing Works a Little Differently

Adiabatic quantum computing is a special case of this. In adiabatic quantum computing you again evolve the system under a time-dependent Hamiltonian, H(t) , but you have two further constraints. First, your initial state is the ground state of H(0). Next, the Hamiltonian changes very slowly in time, so that for all times your H(t) quantum state remains close to the ground state of H(t) .

It has also been shown by Aharonov et. al. that such a linear interpolation (adjusting the simple Adiabatic formula with a function) is computationally as powerful as the gate model.

Questions and Answers from the Analysis: Thinking like a Quantum Computing Programmer
Question: Can we make adiabatic quantum computation with a large spectral gap (of order 1)?
Partial Answer: Immediately, we realize that this will imply that we follow a “long path” in parameter space if we want to do anything useful.

Answer: Everything that can be done with an order unity spectral gap in one dimension can be done on a classical computer in polynomial time.

Answer: We need to have a polynomially long path, and we need to work in more than one dimension.

Question: Are there any interesting algorithms based on such a long path. Is there any reason to believe that this will allow us to get nontrivial results?

Partials Answer: not only is it possible, but that this possibility in fact already is well known [topological quantum computeing]

Question: Topological quantum computing can be realized as adiabatic evolution: add some terms to the Hamiltonian which favor producing defects, and then slowly change those terms to drag the defects, and braid them. However, topological quantum computing relies on a highly degenerate ground state. Is it possible to do this “long path” adiabatic quantum computing with a unique ground state and a spectral gap of order 1?

Answer: Don’t know. Maybe. I thought for a short time about whether one could at least come up with a Grover algorithm [Faster than Classical Database searching] that worked this way, but didn’t get anywhere. Perhaps instead of linearly interpolating one could imagine changing in a position-dependent way. Maybe one could choose some long random path in parameter space.

Topological quantum computers for beginners

Topological approaches to fault tolerance seem especially promising.

So more stable and more fault tolerant than other kinds of quantum computers.

Topological quantum computing at wikipedia

A topological quantum computer is a theoretical quantum computer that employs two-dimensional quasiparticles called anyons, whose world lines cross over one another to form braids in a three-dimensional spacetime (i.e., one temporal plus two spatial dimensions). These braids form the logic gates that make up the computer. The advantage of a quantum computer based on quantum braids over using trapped quantum particles is that the former is much more stable.

blog comments powered by Disqus