4 papers
The quantum smooth label cover problem is undecidable
Eric Culf, Kieran Mastel, Connor Paddock +1
We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a…
The Clifford theory of the n-qubit Clifford group
Kieran Mastel
The n-qubit Pauli group and its normalizer the n-qubit Clifford group have applications in quantum error correction and device characterization. Recent applications have made use o…
RE-completeness of entangled constraint satisfaction problems
Eric Culf, Kieran Mastel
Constraint satisfaction problems (CSPs) are a natural class of decision problems where one must decide whether there is an assignment to variables that satisfies a given formula. S…
Two prover perfect zero knowledge for MIP*
Kieran Mastel, William Slofstra
The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursiv…