Dr. Ricardo Rivera Cardoso: Which problems can and can’t a quantum computer solve?

The talk, presented by Ricardo Rivera Cardoso, a PhD candidate in Hamiltonian complexity, addresses the question of which problems quantum computers can and cannot solve efficiently. It begins by formalizing the question, emphasizing the importance of efficiency (polynomial vs. exponential scaling) and worst-case analysis. The speaker introduces complexity theory concepts such as complexity classes (P, NP) and reductions, illustrating them with examples like sorting, matrix multiplication, and the shortest path problem. He then explains that while classical computers can solve problems in P efficiently, problems in NP (like Sudoku and integer factorization) are efficiently verifiable but not necessarily efficiently solvable. The talk discusses the relationship between classical and quantum computers, noting that quantum computers are believed to be more powerful but not omnipotent. It highlights Shor’s algorithm for integer factorization as a key quantum advantage. The speaker also addresses limitations of the complexity-theoretic framework, including approximation algorithms, average-case complexity, and the practical challenges of fault-tolerant quantum computing. The talk concludes by encouraging further study in this exciting field.