We construct families of translationally invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem. This is true even with the promise that each Hamiltonian is either gapped or gapless in the strongest sense: it is promised to either have continuous spectrum above the ground state in the thermodynamic limit, or its spectral gap is lower-bounded by a constant. Moreover, this constant can be taken equal to the operator norm of the local operator that generates the Hamiltonian (the local interaction strength). The result still holds true if one restricts to arbitrarily small quantum perturbations of classical Hamiltonians. The proof combines a robustness analysis of Robinson’s aperiodic tiling, together with tools from quantum information theory: the quantum phase estimation algorithm and the history state technique mapping Quantum Turing Machines to Hamiltonians.

Fibonacci anyons are attractive for use in topological quantum computation because any unitary transformation of their state space can be approximated arbitrarily accurately by braiding. However, there is no known braid that entangles two qubits without leaving the space spanned by the two qubits. In other words, there is no known ‘leakage-free’ entangling gate made by braiding. In this paper, we provide a remedy to this problem by supplementing braiding with measurement operations in order to produce an exact controlled rotation gate on two qubits.

In automata theory, quantum computation has been widely examined for finite statemachines, known as quantum finite automata (QFAs), and less attention has been given toQFAs augmented with counters or stacks. In this paper, we focus on such generalizations ofQFAs where the input head operates in one-way or realtime mode, and present some newresults regarding their superiority over their classical counterparts. Our first result isabout the nondeterministic acceptance mode: Each quantum model architecturallyintermediate between realtime finite state automaton and one-way pushdown automaton(one-way finite automaton, realtime and one-way finite automata with one-counter, andrealtime pushdown automaton) is superior to its classical counterpart. The second andthird results are about bounded error language recognition: for anyk > 0, QFAs with k blind counters outperform theirdeterministic counterparts; and, a one-way QFA with a single head recognizes an infinitefamily of languages, which can be recognized by one-way probabilistic finite automata withat least two heads. Lastly, we compare the nondeterminictic and deterministic acceptancemodes for classical finite automata with k blind counter(s), and we showthat for any k > 0, the nondeterministic models outperform thedeterministic ones.

Although it is known that quantum computers can solve certain computational problems exponentially faster than classical computers, only a small number of quantum algorithms have been developed so far. Designing such algorithms is complicated by the rather nonintuitive character of quantum physics. In this paper we present a genetic programming system that uses some new techniques to develop and improve quantum algorithms. We have used this system to develop two formerly unknown quantum algorithms. We also address a potential deficiency of the quantum decision tree model used to prove lower bounds on the query complexity of the parity problem.