Daniel Nagaj

21 papers A* 2A 1B 1Journal 16Unranked 1
YearRankTypeTitle / Venue / Authors
2025 A conf
Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript{1}-Complete: Direct Embeddings and Black-Box Simulation.
ITCS
Dorian Rudolph, Sevag Gharibian, Daniel Nagaj
2025 — conf
Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes.
TQC
Ricardo Rivera Cardoso, Alex Meiburg, Daniel Nagaj
2025 J jnl
Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes.
CoRR
Ricardo Rivera Cardoso, Alex Meiburg, Daniel Nagaj
2024 J jnl
Quantum 2-SAT on low dimensional systems is QMA
CoRR
Dorian Rudolph, Sevag Gharibian, Daniel Nagaj
2018 J jnl
Shorter unentangled proofs for ground state connectivity.
Quantum Inf. Process.
Libor Caha, Daniel Nagaj, Martin Schwarz
2017 B conf
Exact Quantum Query Complexity of \text EXACT_k, l^n.
SOFSEM
Andris Ambainis, Janis Iraids, Daniel Nagaj
2016 J jnl
An adaptive attack on Wiesner's quantum money.
Quantum Inf. Comput.
Daniel Nagaj, Or Sattath, Aharon Brodutch, Dominique Unruh
2016 J jnl
Exact quantum query complexity of EXACT
CoRR
Andris Ambainis, Janis Iraids, Daniel Nagaj
2016 J jnl
Quantum 3-SAT Is QMA
SIAM J. Comput.
David Gosset, Daniel Nagaj
2015 J jnl
Momentum switches.
Quantum Inf. Comput.
Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, Zak Webb
2015 J jnl
Perturbative gadgets without strong interactions.
Quantum Inf. Comput.
Yudong Cao, Daniel Nagaj
2015 J jnl
Quantum proofs can be verified using only single qubit measurements.
CoRR
Tomoyuki Morimae, Daniel Nagaj, Norbert Schuch
2014 J jnl
An adaptive attack on Wiesner's quantum money.
CoRR
Aharon Brodutch, Daniel Nagaj, Or Sattath, Dominique Unruh
2014 A* conf
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law.
FOCS
Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani
2013 A* conf
Quantum 3-SAT Is QMA1-Complete.
FOCS
David Gosset, Daniel Nagaj
2013 J jnl
Quantum 3-SAT is QMA1-complete.
CoRR
David Gosset, Daniel Nagaj
2013 J jnl
The SAT-UNSAT transition in the adversarial SAT problem.
CoRR
Marco Bardoscia, Daniel Nagaj, Antonello Scardicchio
2013 J jnl
The local Hamiltonian problem on a line with eight states is QMA-complete.
Quantum Inf. Comput.
Sean Hallgren, Daniel Nagaj, Sandeep Narayanaswami
2012 J jnl
Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems.
Quantum Inf. Comput.
Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, Harumichi Nishimura
2010 J jnl
Efficient circuits for quantum walks.
Quantum Inf. Comput.
Chen-Fu Chiang, Daniel Nagaj, Pawel Wocjan
2009 J jnl
Fast amplification of QMA.
Quantum Inf. Comput.
Daniel Nagaj, Pawel Wocjan, Yong Zhang