111. Mathematical Colloquium

Mario Szegedy

Aliyun Quantum Laboratory

THE ART AND CRAFT OF QUANTUM CIRCUIT DESIGN

Abstract

Quantum circuits are ``machine level'' instruction sets for algorithms run on quantum computers. Is there a science of designing them? Are there general principles, programming paradigms that we can follow? In the talk we answer with yes to these questions.

About the speaker

Mario Szegedy (born October 23, 1960, Budapest) has received his Ph.D. in computer science in 1989 from the University of Chicago. He worked in Bell Laboratories from 1991 to 1999, and after spending a year in the Princeton Institute for Advanced Studies he became a professor of computer science at Rutgers University. He has joined Aliyun Quantum Laboratory in January 2018, and currently he is on unpaid leave from Rutgers.

Szegedy's research areas include computational complexity theory and quantum computing. In computational complexity he is known for characterizing inapproximability of combinatorial optimization problems. He was part of a group of researchers who have pioneered the idea of applying probabilistic verification in proving conditional hardness of approximation. Another major result of his was inventing data streaming algorithms for devices with limited storage. In quantum computing his research areas include quantum algorithms, quantum query complexity and quantum walks. There is a quantum walk operator named after him.

Szegedy was awarded the Gödel Prize twice, in 2001 and 2005, for his works on probabilistically checkable proofs and on the space complexity of approximating the frequency moments in streamed data.