Daniel Nagaj

According to our database, Daniel Nagaj authored at least 16 papers between 2009 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Quantum 2-SAT on low dimensional systems is QMA₁-complete: Direct embeddings and black-box simulation.

Dorian Rudolph, Sevag Gharibian, Daniel Nagaj

CoRR, 2024

2018

Shorter unentangled proofs for ground state connectivity.

Libor Caha, Daniel Nagaj, Martin Schwarz

Quantum Inf. Process., 2018

2017

Exact Quantum Query Complexity of \text EXACT_k, l^n.

Andris Ambainis, Janis Iraids, Daniel Nagaj

Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

2016

Quantum 3-SAT Is QMA₁-Complete.

David Gosset, Daniel Nagaj

SIAM J. Comput., 2016

An adaptive attack on Wiesner's quantum money.

Daniel Nagaj, Or Sattath, Aharon Brodutch, Dominique Unruh

Quantum Inf. Comput., 2016

Exact quantum query complexity of EXACT_{k, l}ⁿ.

Andris Ambainis, Janis Iraids, Daniel Nagaj

CoRR, 2016

2015

Momentum switches.

Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, Zak Webb

Quantum Inf. Comput., 2015

Perturbative gadgets without strong interactions.

Yudong Cao, Daniel Nagaj

Quantum Inf. Comput., 2015

Quantum proofs can be verified using only single qubit measurements.

Tomoyuki Morimae, Daniel Nagaj, Norbert Schuch

CoRR, 2015

2014

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

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

The local Hamiltonian problem on a line with eight states is QMA-complete.

Sean Hallgren, Daniel Nagaj, Sandeep Narayanaswami

Quantum Inf. Comput., 2013

The SAT-UNSAT transition in the adversarial SAT problem.

Marco Bardoscia, Daniel Nagaj, Antonello Scardicchio

CoRR, 2013

Quantum 3-SAT Is QMA1-Complete.

David Gosset, Daniel Nagaj

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems.

Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, Harumichi Nishimura

Quantum Inf. Comput., 2012

2010

Efficient circuits for quantum walks.

Chen-Fu Chiang, Daniel Nagaj, Pawel Wocjan

Quantum Inf. Comput., 2010

2009

Fast amplification of QMA.

Daniel Nagaj, Pawel Wocjan, Yong Zhang

Quantum Inf. Comput., 2009