A toy theory of quantum speed-ups based on the stabilizer formalism

Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.

Recording Details

PIRSA Number: 


A central question in quantum computation is to identify which problems can be solved faster on a quantum computer. A Holy Grail of the field would be to have a theory of quantum speed-ups that delineates the physical mechanisms sustaining quantum speed-ups and helps in the design of new quantum algorithms. In this talk, we present such a toy theory for the study of a class of quantum algorithms for algebraic problems, including Shor’s celebrated factoring algorithm. Our theory is an extension of Gottesman’s stabilizer formalism based on elements of group and hypergroup theory. Using our methods, we develop classical simulation algorithms for Clifford-like circuits containing quantum Fourier transforms as well as new quantum algorithms for hidden symmetries and hyper-symmertry problems. During the talk, we will discuss the role of resources such as entanglement, interference and contextuality within our formalism and connect quantum speed-ups therein to the presence of precise algebraic structures.

Based on the following works:

[1] https://arxiv.org/abs/1210.3637

[2] https://arxiv.org/abs/1409.3208

[3] https://arxiv.org/abs/1409.4800

[4] https://arxiv.org/abs/1509.05806