The C&O department has 36 faculty members and 60 graduate students. We are intensely research oriented and hold a strong international reputation in each of our six major areas:
- Algebraic combinatorics
- Combinatorial optimization
- Continuous optimization
- Cryptography
- Graph theory
- Quantum computing
Read more about the department's research to learn of our contributions to the world of mathematics!
News
Chasing a dream
“While working as an instructional support assistant (ISA), I remember the first time a professor asked for a volunteer to teach a lecture while he was at a conference,” remembers Josué Kurke. “My hand shot up. I donned a professorial kind of jacket with the elbow patches and went all out. Over time, I’ve realized that I feel most at home in front of a classroom. I want to spend my career talking to people about math.”
Recent graduate student awarded first in Faculty of Mathematics Doctoral Prize competition
Stefan Sremac wins the 2019 Huawei Prize for Best Research Paper
This award recognizes the impact of Stefan's paper, Maximum determinant positive definite Toeplitz completions, with a prize of $4,000.
Events
Tutte Colloquium -David Gosset-Triply efficient shadow tomography
| Speaker: | David Gosset |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: Given copies of a quantum state, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision. We say that such a protocol is triply efficient if it is sample efficient, time efficient, and uses measurements that entangle a constant number of copies of the state at a time. A natural family of shadow tomography protocols based on random single-copy Clifford measurements can be understood as arising from fractional colorings of a graph G that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of G with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all -qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample-efficient schemes are provably impossible using only single-copy measurements. This is joint work with Robbie King, Robin Kothari, and Ryan Babbush.