15
$\begingroup$

When developing algorithms in quantum computing, I've noticed that there are two primary models in which this is done. Some algorithms - such as for the Hamiltonian NAND tree problem (Farhi, Goldstone, Guttman) - work by designing a Hamiltonian and some initial state, and then letting the system evolve according to the Schrödinger equation for some time $t$ before performing a measurement.

Other algorithms - such as Shor's Algorithm for factoring - work by designing a sequence of Unitary transformations (analogous to gates) and applying these transformations one at a time to some initial state before performing a measurement.

My question is, as a novice in quantum computing, what is the relationship between the Hamiltonian model and the Unitary transformation model? Some algorithms, like for the NAND tree problem, have since been adapted to work with a sequence of Unitary transformations (Childs, Cleve, Jordan, Yonge-Mallo). Can every algorithm in one model be transformed into a corresponding algorithm in the other? For example, given a sequence of Unitary transformations to solve a particular problem, is it possible to design a Hamiltonian and solve the problem in that model instead? What about the other direction? If so, what is the relationship between the time in which the system must evolve and the number of unitary transformations (gates) required to solve the problem?

I have found several other problems for which this seems to be the case, but no clear cut argument or proof that would indicate that this is always possible or even true. Perhaps it's because I don't know what this problem is called, so I am unsure what to search for.

$\endgroup$
  • 3
    $\begingroup$ Every polynomial-time algorithm in one corresponds to a polynomial-time algorithm in the other, but it's not clear the degree of the polynomial will be the same. Hopefully somebody will come up with references. These results were proved in the early days of quantum computation, and there should be better proofs of these theorems now. $\endgroup$ – Peter Shor Jul 6 '14 at 1:25
  • $\begingroup$ does this relate to what is known as the Heisenberg vs Schroedinger picture of QM which relates to how the operators are defined? also if it isnt covered in Nielsen & Chuang then that would seem to be a major oversight! the NAND tree paper uses "hamiltonian oracles" which seem to be introduced by Farhi/Gutmann 1998. here is a nice survey article on Hamiltonian oracles by Mochon 2007 $\endgroup$ – vzn Jul 6 '14 at 15:58
  • $\begingroup$ The book link you provided is actually the textbook we used in my undergraduate course in Quantum Information Processing. The book is really geared towards the Unitary approach (within the context of oracles as well), but not so much in the context of Hamiltonians. My undergrad course was focused from a cs perspective and not a physics perspective, which is why I am most familiar with the Unitary model. $\endgroup$ – user340082710 Jul 8 '14 at 15:47
  • $\begingroup$ The paper you provided as well is a good reference in general, but I don't believe it addresses my question either. Lastly, I've taken a look at the Heisenberg vs Schroedinger picture of QM, and it does look related, but I believe my question is different (though I could be wrong - It was a hard to follow the Wikipedia entries). $\endgroup$ – user340082710 Jul 8 '14 at 15:49
  • $\begingroup$ I think there are different ways to interpret your question and instead of answering all interpretations, I'd like to ask you the following: Could you be more precise about the version of the Hamiltonian model you have in mind? What is the measure of complexity in this model? (i.e., what is it that counts how difficult it is to solve a problem in the Hamiltonian model?) How is the input to the problem given? Is it given explicitly or do you have to query the input via an oracle? $\endgroup$ – Robin Kothari Jul 10 '14 at 0:27
9
$\begingroup$

To show that Hamiltonian evolution can simulate the circuit model, one can use the paper Universal computation by multi-particle quantum walk, which shows that a very specific kind of Hamiltonian evolution (multi-particle quantum walks) is BQP complete, and thus can simulate the circuit model.

Here is a survey paper on simulating quantum evolution on a quantum computer. One can use the techniques in this paper to simulate the Hamiltonian evolution model of quantum computers. To do this, one needs to use "Trotterization", which substantially decreases the efficiency of the simulation (although it only introduces a polynomial blowup in computation time).

$\endgroup$
  • $\begingroup$ Thanks! These references look quite good and should be able to give me an idea of how this is done. $\endgroup$ – user340082710 Jul 10 '14 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.