Abstract

A central challenge in quantum computing is to discern which types of problems allow for quantum algorithms that substantially outperform classical ones. Underlying this challenge is an even more fundamental question: what general characteristics of computational problems make them more (or less) amenable to quantum methods? In this talk I will present my personal attempts to make progress on this fundamental question.

I will introduce a new framework of quantum computation where the symmetries of the problem in consideration play a key role. This framework was developed with the view to elucidate the role of symmetries on quantum speedups, and forms a natural quantum extension of symmetric threshold circuits—a common core where multiple notions of symmetry in classical computation converge. I aim to motivate our computational model and show how it can go beyond the capabilities of its classical counterpart. Several open problems will be presented, which I hope can pave the way for future progress on my earlier question.

This talk is based on joint work with Tom Gur and Sergii Strelchuk.