Author name cluster

Daniel Nagaj

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

FOCS Conference 2014 Conference Paper

Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law

Dorit Aharonov
Aram W. Harrow
Zeph Landau
Daniel Nagaj
Mario Szegedy
Umesh V. Vazirani

We introduce a technique for applying quantum expanders in a distributed fashion, and use it to solve two basic questions: testing whether a bipartite quantum state shared by two parties is the maximally entangled state and disproving a generalized area law. In the process these two questions which appear completely unrelated turn out to be two sides of the same coin. Strikingly in both cases a constant amount of resources are used to verify a global property.

Details

FOCS Conference 2013 Conference Paper

Quantum 3-SAT Is QMA1-Complete

David Gosset
Daniel Nagaj

Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k ≥ 4 is QMA 1 -complete [4]. Quantum 3-SAT was known to be contained in QMA 1 [4], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA 1 -hard, and therefore complete for this complexity class.

Details