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


Quantum Perfect Matching Games
David Cui, Laura Mančinska, Seyed Sajjad Nezhadi, David E. Roberson
In Preparation
We define the notion of a quantum perfect matching (aswell as fractional matching and Xperfect matching) by defining quantum matching games inspired by the homomorphism game. We prove complexity results aswell as characterization theorems relating these properties to classical properties of graphs aswell as study how these are related to the other quantum graph properties.


The recursive compression method for proving undecidability results
Andrew Marks, Seyed Sajjad Nezhadi, Henry Yuen
In Preparation
We discuss a technique called recursive compression for proving undecidability results. The technique was used [JNV+22] in the breakthrough MIP* = RE result and further developed [MNY22] to prove the Π2hardness of the exact quantum value problem. Independently, similar ideas to recursive compression has been used by [DRS10] to prove undecidability results about Wang tilings.
We formulate a general recursive compression lemma which abstracts the technique in all these
above applications. We also prove a converse and generalizations of the recursive compression lemma.


Hamiltonians whose lowenergy states require Ω(n) T gates
Nolan J. Coble, Matthew Coudron, Jon Nelson, Seyed Sajjad Nezhadi
In Submission
arxiv
In this work we focus on a specific and natural prerequisite to both NLSS and the QPCP Conjecture, namely, the existence of local Hamiltonians whose lowenergy states all require ω(log n) T gates to prepare. In fact, we prove a stronger result which is not necessarily implied by either conjecture: we construct local Hamiltonians whose lowenergy states require Ω(n) Tgates. We further show that our procedure can be applied to the NLTS Hamiltonians to yield local Hamiltonians whose lowenergy states require both Ω(log n)depth and Ω(n) T gates to prepare. Our results utilize a connection between Tcount and stabilizer groups, which was recently applied in the context of learning low Tcount states.


Local Hamiltonians with no lowenergy stabilizer states
Nolan J. Coble, Matthew Coudron, Jon Nelson, Seyed Sajjad Nezhadi
Theory of Quantum Computation TQC (2023)
arxiv
We describe families of local Hamiltonians whose lowenergy space contains no stabilizer (Clifford) states via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe, resulting in a family of local Hamiltonians whose lowenergy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS.


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)
arxiv
We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy. We prove that deciding whether the quantum value of a twoplayer 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.


Synchronous Values of Games
J. William Helton, Hamoon Mousavi, Seyed Sajjad Nezhadi, Vern I. Paulsen, Travis B. Russell
Annales Henri Poincaré, 141 (2024)
Tsirelson Memorial Workshop (2022)
arxiv
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.


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 nonlocal games and show it to be strictly harder than the halting problem. In particular, we show that the class of zerogap entangled multiprover interactive proofs, \(MIP_0^*\), is equal to \(\Pi_2\), a class within the second level of arithmetical hierarchy from computability theory.


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)
arxiv
We introduce a family of games that generalize CHSH, viewing it as a linear constraint system game. These provide the first example of nonlocal games that selftest nonPauli operators and states other than the maximally entangled state. We also introduce the Glued Magic Square game that is not a selftest for any strategy. Our results suggest a richer landscape of selftesting phenomena than previously considered.

