Computational power of symmetric Hamiltonians

The presence of symmetries, be they discrete or continuous, in a physical system typically leads to a reduction in the problem to be solved. Here we report that neither translational invariance nor rotational invariance reduce the computational complexity of simulating Hamiltonian dynamics; the problem is still bounded error, quantum polynomial time complete, and is believed to be hard on a classical computer. This is achieved by designing a system to implement a universal quantum interface, a device which enables control of an arbitrary computation through the control of a fixed number of spins, and using it as a building block to entirely remove the need for control, except in the system initialization. Finally, it is shown that cooling such Hamiltonians to their ground states in the presence of random magnetic fields solves a Quantum-Merlin-Arthur-complete problem.

Figure 1

(Color online) The basic scenario of a universal quantum interface. At each site, there are two qubit systems, $a$ and $q$. All of the $a$'s are initialized as $|0⟩$. A ${|1⟩}^a$ is input at site 1, and its arrival at site $N$ is monitored. The hopping Hamiltonian is such that as the excitation moves between site $i$ and $i+1$, a unitary $U_{i,i+1}$ is enacted on the computational qubits $q$. Thus, upon arrival at site $N$, the unitary $U_{N-1,N}\cdots U_{1,2}$ has been implemented. Furthermore, this transfer is efficient.

Figure 2

(Color online) Schematic of the Hamiltonian’s mechanism. At each site, there is a label to specify if that site is a computational qubit or program qutrit. One location in the program bus is marked as the active region, and that value is stored in the read-head qubit $r_i$. The read head applies a unitary to each computational qubit consecutively, controlled off its value. When it reaches the active program region, it exchanges its data with the next step in the program.

Figure 3

(Color online) (a) Schematic depiction of a 1D array of 31-dimensional spins(s). The black regions denote the nearest-neighbor interactions of the Hamiltonian. (b) The same system made rotationally invariant by encoding the states of the spin in logical states on a block of qubits. The logical spins, and the periodic Hamiltonian interactions are depicted. To make the system translationally invariant requires the inclusion of terms (gray) where the interactions do not align with the logical qubits of the state. (c) To regain translational invariance in the Hamiltonian, we introduce a flag state $\left(f\right)$ before each block of logical qubits, denoting the start of that block. Note that in the case of $Z$-rotational invariance, not only do we use the flag state $|11⟩$, but between each qubit in $s$ we add an extra qubit on the $|0⟩$ state.

Figure 4

(Color online) The rotationally invariant state that flags, and the Hamiltonian that detects the flag, at the start of the block of 10 qubits encoding a logical spin within a decoherence free subsystem. Section $A$ makes sure that when the Hamiltonian and herald state are offset by a single qubit, the overlap is 0. Section $B$, where the states $P_3$ are repeated eight times, handles a relative shift of an even number of qubits. Section $C$ does the same for an odd number of qubits, and the states $P_3$ are repeated nine times. The difference in the number of repetitions of $P_3$ handles an edge effect that arises otherwise.