In this paper, we study quantum computing with twists. Twists are yet another form of defects in a lattice. They arise from dislocations in the lattice and can be used to encode and process quantum information. Surface codes with twists are also called dislocation codes. Hastings and Geller showed that dislocation codes could provide gains in space-time complexity of quantum computation. In this paper, we undertake a detailed study of generalized dislocation codes. We develop the theory of qubit dislocation codes over arbitrary four-valent and bicolorable lattices. We give a construction to introduce twists in such lattices and also study the structure of logical operators. We then study dislocation codes over odd prime dimensions in square lattices. Using the theory developed, we present protocols for implementing a universal gate set in qubit dislocation codes. We also show how to implement the generalized Clifford group in qudit dislocation codes in odd prime dimensions.
We give two quantum algorithms for computing (twisted) Kloosterman sums attached to a finite field F of q elements. The first algorithm computes a quantum state containing, as its coefficients with respect to the standard basis, all Kloosterman sums for F twisted by a given multiplicative character, and runs in time polynomial in logq. The second algorithm computes a single Kloosterman sum to a prescribed precision, and runs in time quasi-linear in q.
We introduce a theory of twisted simplicial distributions on simplicial principal bundles, which allow us to capture Bell's non-locality, and the more general notion of quantum contextuality. We leverage the classical theory of simplicial principal bundles, as well as structures on categories of such bundles, to provide powerful computational tools for analyzing twisted distributions in terms of both direct constructions in simplicial sets and techniques from homological algebra. We use these techniques to analyze our key examples: quantum distributions and operator-theoretic polytopes used in the classical simulation of quantum computation.