Quantum Simulation

Given the fact that the Fourier Transform of a wave function is cheap in quantum computation, one can use this to efficiently design a system which will have the same ( discretely simulated) wave function as some real system.

Consider a system which obeys the Schroedinger equation

$$i{\partial \psi\over \partial t} = -{1\over 2}{\partial^2\psi\over \partial x^2} - V(x)\psi$$ (25)

We want to simulate this equation on a digital computer. To do so we divide the range of x values into a discrete set, with labels going from $0$ to $2^N-1$. We can always rescale the problem so that the label is also the value of $x$. We now convert the problem to its discrete approximation, where for example

$${\partial^2\psi(x)\over\partial x^2} ={1\over 2}(\psi(x+1)+\psi(x-1) -2\psi(x))$$ (26)

Using a symplectic integration, this problem can be solved by evolving with respect to the kinetic term for a time $\Delta t/2$ and then evolving via the potential for a time $\Delta t$ and then again with the kinetic term for a time $\Delta t/2$. The evolution of via the potential is trivial in configuration space, as it simply corresponds to multiplying the phase for each value of the wave-function at $x$ by $e^{iV(x)\Delta t}$. The evolution via the kinetic term is trivial in momentum space, as in momentum space the kinetic term is simply ${1\over 2} p^2 \tilde\psi(p)$, which gives a momentum space evolution of simply $e^{i{1\over 2 }p^2\Delta t/ 2}\tilde\psi(p)$. However in a classical simulation, the transition to the momentum frame costs $N2^N$ operations, and each of the multiplications cost $2^N$ operations. I.e., the simulation of the quantum system per time step costs a number operations proportional to some multiple of the number discrete points into which one has broken up the range of $x$ values.

However, one can design a quantum computer to calculate

$$V\vert x;0>=\vert x;V(x)>$$ (27)

One can then design a second computer designated by $T$ to calculate

$$T\vert x;W>= \vert x>T\vert W>=\vert x>e^{iW\Delta t/2}\vert W>=e^{iW\Delta t/2}\vert x;W>$$ (28)

for all $W$ and $x$. (Notice that this operation does not depend on the value of $x$. It operates solely on the second term.)

We now have the operation of taking the Fourier transform.

$$F\vert x;0> = \sum_k {1\over 2^{N/2}} e^{i2\pi kx 2^{-N}} \vert k;0>$$ (29)

and finally we can construct the computer $K2$ to calculate $k^2$.

$$K2\vert k;0>= \vert k;{1\over 2}k^2>$$ (30)

We can now put these together. One time step in the simulation will now be

$$\vert\psi(t+\Delta t)>= F^\dagger~ K2^\dagger~ T ~K2~ F ~V^\dagger~ T^2~ V ~F^\dagger~K2^\dagger ~U ~K2 ~F\vert\psi(t)>$$ (31)

This procedure in words is "take the Fourier transform, calculate ${k^2/2}$, phase shift for a time $\Delta t/2$ with $k^2/2$, undo the $k^2/2$ calculation, take the inverse Fourier transform back to position space, calculate $V(x)$, calculate twice using the phase shift over a time $\Delta t/2$, undo the $V(x)$ calculation, take the Fourier transform, calculate $k^2/2$, phase shift over $\Delta t/2$ using the $k^2$ result, undo the $k^2/2$ calculation, and undo the Fourier transform."

Each of these operations is efficient on a quantum computer, taking at most $N$ or $N^2$ ( rather than $2^N$) steps. Thus the quantum computer will be exponentially faster than a classical computer at calculating the evolution of this wave function.

However, what you are left with at the end is a system with a wave function

$$\vert\psi(t)>=\sum_x \psi(x,t)\vert x;0>$$ (32)

which is a digital approximation to the wave-function that the real system would have. You can now carry out experiments on this system, but as with the real system, each measurement will destroy the wave function. You cannot, in one running of the computer determine all the coefficients $\psi(x,t)$, for example. All you can do is for example measure the value of $x$ and the outcome of that measurement will be determined by the probability $\vert\psi(x,t)\vert^2$. I.e., what you have is simulation, not a calculation. On the other hand it is a simulation which is controlled by you, the person running the computer. You can decide which potential to use. You can then carry out experiments on a computer which you know has a given potential, and can see if it agrees with the same experiments carried out on the real system. Thus, if what you want is the $2^N$ coefficients of the wave function, i.e., the amplitudes $\psi(x,t)$, then the classical simulation is going to be as good as you can do. If on the other hand you are interested in the outcome of a few specific experiments, then a quantum computer allows you to simulate those experiments far more efficiently than doing the calculation on a classical computer.