How to understand Deutsch-Jozsa algorithm from an adiabatic perspective? - Quantum Computing Stack Exchange most recent 30 from quantumcomputing.stackexchange.com 2020-01-28T20:03:51Z https://quantumcomputing.stackexchange.com/feeds/question/5218 https://creativecommons.org/licenses/by-sa/4.0/rdf https://quantumcomputing.stackexchange.com/q/5218 2 How to understand Deutsch-Jozsa algorithm from an adiabatic perspective? nagenw https://quantumcomputing.stackexchange.com/users/5570 2019-01-17T15:50:29Z 2019-05-15T15:45:42Z <p>I'm trying to understand the Deutsch-Josza algorithm from an adiabatic perspective as presented in <a href="https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.90.015002" rel="nofollow noreferrer">Adiabatic quantum computing A: Review of modern physics, vol 90, (2018) pp 015002-1</a> (<a href="https://arxiv.org/abs/1611.04471" rel="nofollow noreferrer">arXiv version</a>). </p> <p>When explaining the unitary interpolation technique, the authors begin with:</p> <blockquote> <p>The initial Hamiltonian is chosen such that its ground state is the uniform superposition state [<span class="math-container">$|\phi\rangle = |+\rangle^{\otimes n}$</span>], i.e., <span class="math-container">$H(0) = w\sum^{n}_{i = 1}|-\rangle_i \langle-|$</span>, where <span class="math-container">$w$</span> is the energy scale.</p> </blockquote> <ul> <li>How can I calculate the ground state of <span class="math-container">$H(0)$</span>?</li> </ul> <p>Also, I have seen, but don't remember exactly where, an observation that <span class="math-container">$H(0)$</span> is introduced in a such a way that a penalty is provided for any state having a contribution of <span class="math-container">$|-\rangle$</span>. What does it mean?</p> <p>Then the paper goes on and states that:</p> <blockquote> <p>An adiabatic implementation requires a final Hamiltonian <span class="math-container">$H(1)$</span> such that its ground state is <span class="math-container">$|\Psi(1)\rangle = U|\Psi(0)\rangle$</span>, and that this can be accomplished via a unitary transformation of <span class="math-container">$H(0)$</span>, i.e. <span class="math-container">$H(1) = UH(0)U^\dagger$</span>.</p> </blockquote> <p>where <span class="math-container">$U$</span> is a diagonal matrix such that:</p> <p><span class="math-container">$$U = diag[(-1)^{f(0)}, \dots,(-1)^{f(2^n-1)}]$$</span></p> <p>At this point, I don't see why bother with this; since to arrive at the answer using adiabatic quantum computation I need to construct a unitary in such a way that I will already have the answer if <span class="math-container">$f$</span> is balanced or constant. Am I overlooking anything?</p> <hr> <p>Trying to workout an example, setting <span class="math-container">$n = 1$</span> and making <span class="math-container">$f(x) = 1$</span> (constant 1).</p> <p><span class="math-container">$$H(0) = w|-\rangle\langle-| = w\pmatrix{1 &amp; -1 \\ -1 &amp; 1}$$</span></p> <p>I will set <span class="math-container">$w = 1$</span> to get it out of the way. Then,</p> <p><span class="math-container">$$U = \pmatrix{-1 &amp; 0 \\ 0 &amp; -1}$$</span> <span class="math-container">$$H(1) = UH(0)U^\dagger = \pmatrix{-1 &amp; 0 \\ 0 &amp; -1}\pmatrix{1 &amp; -1 \\ -1 &amp; 1}\pmatrix{-1 &amp; 0 \\ 0 &amp; -1}$$</span> <span class="math-container">$$H(1) = \pmatrix{1 &amp; -1 \\ -1 &amp; 1}$$</span></p> <p>Meaning that the ground state of <span class="math-container">$H(1)$</span> is <span class="math-container">$|+\rangle$</span>.</p> <p>If now I do the function <span class="math-container">$f(x) = x$</span>, then <span class="math-container">$$U = \pmatrix{1 &amp; 0 \\ 0 &amp; -1}$$</span></p> <p>and </p> <p><span class="math-container">$$H(1) = \pmatrix{1 &amp; 1 \\ 1 &amp; 1}$$</span></p> <p>which, I suppose, has ground state <span class="math-container">$|-\rangle$</span>. And with this we can differentiate between a constant and a balanced function <span class="math-container">$f$</span>.</p> https://quantumcomputing.stackexchange.com/questions/5218/-/5220#5220 2 Answer by DaftWullie for How to understand Deutsch-Jozsa algorithm from an adiabatic perspective? DaftWullie https://quantumcomputing.stackexchange.com/users/1837 2019-01-18T07:36:48Z 2019-01-18T07:36:48Z <blockquote> <p>How can I calculate the ground state of <span class="math-container">$H(0)$</span>?</p> </blockquote> <p>The ground state means the eigenvector with lowest eigenvalue. Take your given example, <span class="math-container">$$H(1)=\left(\begin{array}{cc} 1 &amp; 1 \\ 1 &amp; 1 \end{array}\right).$$</span> You solve <span class="math-container">$\text{det}(H(1)-\lambda\mathbb{I})=0$</span> to find the eigenvalues. In this case, <span class="math-container">$\lambda=0,2$</span>. So you're interested in the smallest eigenvalue, 0. So, we solve for <span class="math-container">$H(1)|\lambda\rangle=0$</span>, which you'll find is satisfied for the state <span class="math-container">$|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}$</span>.</p> <p>To find the ground state of <span class="math-container">$H(0)$</span> in its general form, the easiest way is just to recognise what's going on. If I apply <span class="math-container">$$H(0)|+\rangle^{\otimes n}=0.$$</span> So, this is an eigenvector of 0 eigenvalue. Whenever I change a <span class="math-container">$|+\rangle$</span> into a <span class="math-container">$|-\rangle$</span>, the eigenvector relation is still satisfied, but the eigenvalue increases by <span class="math-container">$w$</span> each time. So there is an energy penalty of <span class="math-container">$w$</span> for having a <span class="math-container">$|-\rangle$</span> state. In this way, we can construct a complete basis, and find all the eigenvalues: <span class="math-container">$kw$</span>, repeated <span class="math-container">$\binom{n}{k}$</span> times for <span class="math-container">$k=0,1,\ldots ,n$</span>.</p> <blockquote> <p>At this point, I don't see why bother with this; since to arrive at the answer using adiabatic quantum computation I need to construct a unitary in such a way that I will already have the answer if f is balanced or constant. </p> </blockquote> <p>Well, Deutsch-Jozsa is very much defined in terms of an oracle, i.e. the unitary is something that is given directly to you, and you can't look inside it to see what's happening. <em>You do not construct the unitary <span class="math-container">$U$</span></em>. The question then is how long your algorithm needs to run for in order to find out if the function is constant or balanced. This is where the adiabatic part comes in; using the oracle in an adiabatic way, you can calculate how long it takes, and find it's a constant time.</p>