A toy theory of quantum speed-ups based on the stabilizer formalism
APA
Bermejo Vega, J. (2016). A toy theory of quantum speed-ups based on the stabilizer formalism. Perimeter Institute. https://pirsa.org/16110067
MLA
Bermejo Vega, Juani. A toy theory of quantum speed-ups based on the stabilizer formalism. Perimeter Institute, Nov. 09, 2016, https://pirsa.org/16110067
BibTex
@misc{ pirsa_PIRSA:16110067, doi = {10.48660/16110067}, url = {https://pirsa.org/16110067}, author = {Bermejo Vega, Juani}, keywords = {Other}, language = {en}, title = {A toy theory of quantum speed-ups based on the stabilizer formalism}, publisher = {Perimeter Institute}, year = {2016}, month = {nov}, note = {PIRSA:16110067 see, \url{https://pirsa.org}} }
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