Seyed Sajjad Nezhadi

I am a Computer Science Ph.D. student at QuiCS and the University of Maryland, advised by Matthew Coudron.

Before that I did an undergraduate degree in Math and CS at the University of Toronto, where I was advised by Henry Yuen.

 -  CV  -   - 

profile photo

Sajjad - سجاد


I am broadly interested in the theory of quantum computing and computational complexity theory.

project image

Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy

Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen
Symposium on Theory of Computing STOC, 2022
Quantum Information Processing QIP (Plenary talk), 2022
Tsirelson Memorial Workshop, 2022

We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy. We prove that deciding whether the quantum value of a two-player nonlocal game is exactly equal to 1 is complete for Π2. This shows that exactly computing the quantum value is strictly harder than approximating it, and also strictly harder than computing the commuting operator value (either exactly or approximately). We explain how results about the complexity of nonlocal games all follow in a unified manner from a technique known as compression. At the core of our result is a new gapless compression theorem that holds for both quantum and commuting operator strategies. Our compression theorem yields as a byproduct an alternative proof of Slofstra’s result that the set of quantum correlations is not closed.

project image

Synchronous Values of Games

J. William Helton, Hamoon Mousavi, Seyed Sajjad Nezhadi, Vern I. Paulsen, Travis B. Russell
Tsirelson Memorial Workshop, 2022


We investigate the synchronous values of graph colouring games, XOR games, and products of games. We show the optimal strategy for a synchronous game need not be synchronous. We derive a formula for the synchronous value of an XOR game as an optimization problem over a spectrahedron and show that the synchronous quantum bias of the XOR of two XOR games is not multiplicative. Finally, we give an example of a game whos repeated product synchronous value is increasing.

project image

On the complexity of zero gap MIP*

Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen
International Colloquium on Automata, Languages, and Programming ICALP, 2020
Theory of Quantum Computation TQC, 2020

arxiv - slides

We characterize the complexity of exactly computing the maximum winning probability of entangled non-local games and show it to be strictly harder than the halting problem. In particular, we show that the class of zero-gap entangled multiprover interactive proofs, \(MIP_0^*\), is equal to \(\Pi_2\), a class within the second level of arithmetical hierarchy from computability theory.

project image

A generalization of CHSH and the algebraic structure of optimal strategies

David Cui, Arthur Mehta, Hamoon Mousavi, Seyed Sajjad Nezhadi
Quantum 4, 346, 2020
Quantum Information Processing QIP, 2020


We introduce a family of games that generalize CHSH, viewing it as a linear constraint system game. These provide the first example of non-local games that self-test non-Pauli operators and states other than the maximally entangled state. We also introduce the Glued Magic Square game that is not a self-test for any strategy. Our results suggest a richer landscape of self-testing phenomena than previously considered.

Website from Jon Barron via Leonid Keselman's Jekyll fork.