Fast quantum computation at arbitrarily low energy

One version of the energy-time uncertainty principle states that the minimum time $T_{\perp }$ for a quantum system to evolve from a given state to any orthogonal state is $h/\left(4\mathrm{\Delta }E\right)$, where $\mathrm{\Delta }E$ is the energy uncertainty. A related bound called the Margolus-Levitin theorem states that $T_{\perp }\ge h/\left(2\langle E\rangle \right)$, where $\langle E\rangle$ is the expectation value of energy and the ground energy is taken to be zero. Many subsequent works have interpreted $T_{\perp }$ as defining a minimal time for an elementary computational operation and correspondingly a fundamental limit on clock speed determined by a system's energy. Here we present local time-independent Hamiltonians in which computational clock speed becomes arbitrarily large relative to $\langle E\rangle$ and $\mathrm{\Delta }E$ as the number of computational steps goes to infinity. We argue that energy considerations alone are not sufficient to obtain an upper bound on computational speed, and that additional physical assumptions such as limits to information density and information transmission speed are necessary to obtain such a bound.

Figure 1

Circuit $U=U_G...U_1$ is padded by $G$ identity gates at the beginning and end. The initial wave packet has width of order $G$ and support on the initial identity gates. The wave packet then propagates rightward, ending with its support on the final segment of $G$ identity gates.

Figure 2

Here is an example of a quantum circuit, referred to henceforth as “the original circuit”. $\left|l_j\right.〉$ labels the state after the first $j$ layers of the circuit have been applied. We have assumed that all gates in the original circuit act on nearest neighbors in one dimension. This can always be achieved through the use of swap gates.

Figure 3

Original circuit has depth three and six qubits. Correspondingly we have a grid of three columns with six qubits each. The above sequence of steps implements the first layer of gates. Initially each column is in the state $\left|l_0\right.〉$, the input to the original circuit, which can be taken to be the all zeros state. After these steps are complete, the middle column contains state $\left|l_1\right.〉$. The paired $\times$ symbols indicate swap gates.

Figure 4

These steps implement the second layer of gates. After these steps are complete, the right column contains state $\left|l_2\right.〉$.

Figure 5

These steps implement the third layer of gates. After these steps are complete, the right column contains state $\left|l_3\right.〉$, which is the output of the original circuit.

Figure 6

Numbered circles represent clock qubits. The valid states of the clock are Hamming weight one strings. If the $x\text{th}$ clock qubit is 1, then this corresponds to the $x\mathrm{th}$ step in Figs. 3, 4, 5. The clock qubits are “snaked” among the computational qubits to ensure that the implementation of the $x\mathrm{th}$ step triggered by the $x\mathrm{th}$ clock qubit is spatially local, as is the hopping of the 1 from the $x\mathrm{th}$ clock qubit to the $(x+1)\mathrm{th}$ clock qubit.