In this seminar, I will introduce "normaliser circuits", a family of
quantum operations that play a relevant role in quantum algorithms:
prominent examples of normaliser gates are quantum Fourier transforms
(QFT)---sometimes said to be "the source of various exponential quantum
speedups"---, subroutines that generate highly entangled states and
adaptive measurements.
Recently we have investigated the computational power of normaliser
circuits and found that, in spite of their apparent quantumness, they can
be efficiently simulated in a classical computer. Thus, a quantum computer
operating within this set of gates can not offer exponential quantum
speed-ups over classical computation, regardless e.g. the number of QFT it
uses. Our result generalises a well-known theorem of Gottesman and Knill,
valid for qubits, to systems that do not decompose as products of small
subsystems.
Format:
I will introduce some elements of group theory needed to understand our
theorem and the main tool we developed to prove it: a stabiliser formalism
for high dimensions. The latter may be of independent interest in quantum
error correction and fault tolerant quantum computing. I will also explain
the relation of these results with Shor's algorithm.