Clocks in Feynman's computer and Kitaev's local Hamiltonian: Bias, gaps, idling, and pulse tuning

We present a collection of results about the clock in Feynman's computer construction and Kitaev's local Hamiltonian problem. First, by analyzing the spectra of quantum walks on a line with varying end-point terms, we find a better lower bound on the gap of the Feynman Hamiltonian, which translates into a less strict promise gap requirement for the quantum-Merlin-Arthur–complete local Hamiltonian problem. We also translate this result into the language of adiabatic quantum computation. Second, introducing an idling clock construction with a large state space but fast Cesaro mixing, we provide a way for achieving an arbitrarily high success probability of computation with Feynman's computer with only a logarithmic increase in the number of clock qubits. Finally, we tune and thus improve the costs (locality and gap scaling) of implementing a (pulse) clock with a single excitation.

Figure 1

Quantum walks on a line of length $N$. (a) The quantum walk on a line (hopping) Hamiltonian $H_N^{\mathrm{walk}}$ [Eq. (8)] is the negative of the adjacency matrix. (b) The Laplacian walk $H_N^{\mathrm{L}}$ [Eq. (9)] includes a self-loop on each vertex for each outgoing edge. (c) A more general version $H_N^{(L,R)}$ [Eq. (21)] parametrized by a pair $L,R$ includes end-point projectors (loops) $-L|0\rangle \langle 0|$ and $-R|N\rangle \langle N|$.

Figure 2

Special cases of walks with end-point projectors appearing in the proof of the promise gap lower bound. (a) The walk $H_N^{(1,0)}$ appears in cases (ii) and (iii) of the 1D invariant subspaces. (b) In the 2D invariant subspaces, we get two copies of the walk $H_N^{(1,0)}$, connected by a perturbation (58).

Figure 3

Schedule for universal quantum computation by adiabatic preparation using Kitaev's propagation Hamiltonian, and projectors on the initial and final states of the clock register. The gap is constant for the first and third sections, while in the middle section it becomes $\mathrm{\Theta }(N^{-2}+x^2)$ around $t=\frac{1}{2}(T_1+T_2)+x$.

Figure 4

Legal clock states for an $N=4$ domain-wall clock with a $C=3$ idling chain. A state is labeled by a string made from its $N$ unary bits (black), extra $C$ unary bits (blue), and $C$ idling bits (red). Each line is a projector onto the antisymmetric combination of the clock states at the vertices. The graph is a line (the original clock, first four vertices), connected to the idling part: a line connected to a square, to a cube, and so on.

Figure 5

The (progression of) allowed clock states of a single-qutrit surfer cycle. Site 1 is to the right of the vertical line and site $L$ is to the left of it.

Figure 6

Synchronizing multiple cogs. (a) Cog 1 simply progresses through its first revolution. (b) Cog 1 simply progresses through its second revolution. (c) When the first cog has finished two revolutions, its transition is coupled to a progression of the second cog. (d) Note that cog 2 could also be in its second revolution. (e) When the second cog has finished two revolutions and the first cog has finished two revolutions, they transition together and cog 3 progresses as well.