2 citations · 4 across the 4 of their papers we have counts for
5 papers
Quantum Perfect Matchings
David Cui, Laura Mančinska, Seyed Sajjad Nezhadi +1
We investigate quantum and nonsignaling generalizations of perfect matchings in graphs using nonlocal games. Specifically, we introduce nonlocal games that test for -perfect mat…
Provably Overwhelming Transformer Models with Designed Inputs
Lev Stambler, Seyed Sajjad Nezhadi, Matthew Coudron
We develop an algorithm which, given a trained transformer model as input, as well as a string of tokens of length and an integer , can genera…
Hamiltonians whose low-energy states require T gates
Nolan J. Coble, Matthew Coudron, Jon Nelson +1
The recent resolution of the NLTS Conjecture [ABN22] establishes a prerequisite to the Quantum PCP (QPCP) Conjecture through a novel use of newly-constructed QLDPC codes [LZ22]. Ev…
Local Hamiltonians with no low-energy stabilizer states
Nolan J. Coble, Matthew Coudron, Jon Nelson +1
The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [GL22] posits the existence of a family of local Hamiltonians where all states of lo…
On the complexity of zero gap MIP*
Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen
The class is the set of languages decidable by multiprover interactive proofs with quantum entangled provers. It was recently shown by Ji, Natarajan, Vidick, Wrigh…