5 papers
Operator solutions of linear systems and small cancellation
William Slofstra, Lu-Ming Zhang
We show that if a graph has minimum vertex degree at least d and girth at least g, where (d, g) is (3, 6) or (4, 4), then the incidence system of the graph has a (possibly infinite…
Positivity is undecidable in tensor products of free algebras
Arthur Mehta, William Slofstra, Yuming Zhao
It is well known that an element of the algebra of noncommutative *-polynomials is positive in all *-representations if and only if it is a sum of squares. This provides an effecti…
The NPA hierarchy does not always attain the commuting operator value
Marco Fanizza, Larissa Kroell, Arthur Mehta +4
We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. Specifically, there is a computable mapping from T…
The membership problem for constant-sized quantum correlations is undecidable
Honghao Fu, Carl A. Miller, William Slofstra
When two spatially separated parties make measurements on an unknown entangled quantum state, what correlations can they achieve? How difficult is it to determine whether a given c…
Satisfiability problems and algebras of boolean constraint system games
Connor Paddock, William Slofstra
Mermin and Peres showed that there are boolean constraint systems (BCSs) which are not satisfiable, but which are satisfiable with quantum observables. This has led to a burgeoning…