# Quantum Computing - Relationship between Hamiltonian and Unitary model

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.

• 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. – Peter Shor Jul 6 '14 at 1:25
• 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 – vzn Jul 6 '14 at 15:58
• 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. – user340082710 Jul 8 '14 at 15:47
• 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). – user340082710 Jul 8 '14 at 15:49
• 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? – Robin Kothari Jul 10 '14 at 0:27