Mgr. Daniel Nagaj, PhD

   Position: senior researcher IIA (part-time)
   E-mail: daniel.nagaj@savba.sk
   Tel. (+421 2) 20910709
   Office 108
   Personal webpage: http://quantum.physics.sk/people/nagaj/
   2002

List of publications

1. Ivana Miháliková, Matej Pivoluska, Martin Plesch, Martin Friák, Daniel Nagaj and Mojmír Šob:
   The Cost of Improving the Precision of the Variational Quantum Eigensolver for Quantum Chemistry
   Nanomaterials 12, 243 (2022) [arXiv:2111.04965]
2. Daniel Nagaj, Dominik Hangleiter, Jens Eisert, Martin Schwarz:
   Pinned QMA: The power of fixing a few qubits in proofs | pdf |
   Physical Review A 103, 012604 (2021) [arXiv:2001.03636]
3. Dominik Hangleiter, Ingo Roth, Daniel Nagaj, Jens Eisert:
   Easing the Monte Carlo sign problem | pdf |
   Science Advances 6, eabb8341 (2020) [arXiv:1906.02309]
4. Libor Caha, Daniel Nagaj, Martin Schwarz:
   Shorter unentangled proofs for Ground State Connectivity | pdf |
   Quantum Inf. Processing 17, 174 (2018) [arXiv:1712.07400]
5. Libor Caha, Zeph Landau, Daniel Nagaj:
   The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning | pdf |
   Phys. Rev. A 97, 062306 (2018) [arXiv:1712.07395]
6. Andris Ambainis, Jānis Iraids, Daniel Nagaj:
   Exact quantum query complexity of EXACT_k,lⁿ
   in Lecture Notes in Computer Science 10139, SOFSEM 2017 (Springer, Cham 2017), doi:https://doi.org/10.1007/978-3-319-51963-0_19 [arXiv:1608.02374]
7. Aharon Brodutch, Daniel Nagaj, Or Sattath, Dominique Unruh:
   An adaptive attack on Wiesner's quantum money based on interaction-free measurement | pdf |
   Quantum Information & Computation, Vol.16 No.11&12, pp1048-1070 (2016) [arXiv:1404.1507]
8. Tomoyuki Morimae, Daniel Nagaj, Norbert Schuch:
   Quantum proofs can be verified using only single qubit measurements | pdf |
   Phys. Rev. A 93, 022326 (2016) [arXiv:1510.06789]
9. Yudong Cao, Daniel Nagaj:
   Perturbative gadgets without strong interactions | pdf |
   Quantum Information & Computation 15, pp1197-1222 (2015) [arXiv:1408.5881]
10. Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, Zak Webb:
    Momentum switches | pdf |
    Quantum Information and Computation 15, 601-621 (2015) [arXiv:1406.4510]
11. Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mário Szegedy, Umesh Vazirani:
    Local tests of global entanglement and a counterexample to the generalized area law
    FOCS 2014, 246-255 (2014) [arXiv:1410.0951]
12. Marco Bardoscia, Daniel Nagaj, Antonello Scardicchio:
    Satisfiability-unsatisfiability transition in the adversarial satisfiability problem | pdf |
    Phys. Rev. E 89, 032128 (2014) [arXiv:1310.0967]
13. Sean Hallgren, Daniel Nagaj, Sandeep Narayanaswami:
    The Local Hamiltonian problem on a line with eight states is QMA-complete | pdf |
    Quantum Information & Computation, Vol.13, No.9&10, pp0721-0750 (2013), [arXiv:1312.1469]
14. David Gosset, Daniel Nagaj:
    Quantum 3-SAT is QMA1-complete
    2013 IEEE 54TH annual symposium on Foundations of Computer Science (FOCS 2013), pp. 756-765 (2013) [arXiv:1302.0290]
15. Sergey Bravyi, Libor Caha, Ramis Movassagh, Daniel Nagaj, Peter Shor:
    Criticality without frustration for quantum spin-1 chains | pdf |
    Phys. Rev. Lett. 109, 207202 (2012) [arXiv:1203.5801]
16. Rolando D. Somma, Daniel Nagaj, Maria Kieferova:
    Quantum Speedup by Quantum Annealing | pdf |
    Phys. Rev. Lett. 109, 050501 (2012) [arXiv:1202.6257]
17. Daniel Nagaj :
    Universal 2-local Hamiltonian Quantum Computing | pdf |
    Phys. Rev. A 85, 032330 (2012) [arXiv:1002.0420]
18. Maria Kieferova, Daniel Nagaj:
    Quantum Walks on Necklaces and Mixing | pdf |
    International Journal of Quantum Information, Vol.10, Issue 2, 1250025 (2012) [arXiv:1111.4433]
19. Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, Harumichi Nishimura:
    Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems | pdf |
    Quantum Information and Computation 12, 461-471 (2012) [arXiv:1111.5306v2]
20. Daniel Reitzner, Daniel Nagaj, Vladimír Bužek:
    Quantum walks
    Acta Physica Slovaca 61, No.6, 603-725 (2011)
21. Man-Hong Yung, Daniel Nagaj, James D. Whitfield, Alán Aspuru-Guzik:
    Simulation of Classical Thermal States on a Quantum Computer: A Renormalization Group Approach
    Phys. Rev. A 82, 060302 (2010) [arXiv:1005.0020]
22. Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Daniel Nagaj, Peter Shor:
    Quantum State Restoration and Single-Copy Tomography for Ground States of Hamiltonians
    Phys. Rev. Lett. 105, 190503 (2010) [arXiv:0912.3823]
23. Ramis Movassagh, Edward Farhi, Jeffrey Goldstone, Daniel Nagaj, Tobias J. Osborne, Peter W. Shor:
    Unfrustrated Qudit Chains and their Ground States
    Phys. Rev. A 82, 012318 (2010) [arXiv:1001.1006]
24. Daniel Nagaj:
    Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians
    J. Math. Phys. 51, 062201 (2010) [arXiv:0908.4219]
25. Chen-Fu Chiang, Daniel Nagaj, Pawel Wocjan:
    Efficient Circuits for Quantum Walks | pdf |
    Quantum Information and Computation 10, pp0420-0434 (2010) [arXiv:0903.3465]
26. Daniel Nagaj, Pawel Wocjan, Yong Zhang:
    Fast Amplification of QMA | pdf |
    QIC Vol.9 No.11&12 (2009), 1053-1068 [arXiv:0904.1549]
27. Pawel Wocjan, Chen-Fu Chiang, Anura Abeyesinghe, Daniel Nagaj:
    Quantum algorithm for approximating partition functions | pdf |
    Phys. Rev. A 80, 022340 (2009) [arXiv:0811.0596]
28. Daniel Nagaj, Pawel Wocjan:
    Hamiltonian Quantum Cellular Automata in 1D | pdf |
    Phys. Rev. A 78, 032311 (2008) [arXiv:0802.0886]
29. E. Farhi, J. Goldstone, S. Gutmann, D. Nagaj:
    How to Make the Quantum Adiabatic Algorithm Fail
    International Journal of Quantum Information, Vol. 6, No. 3 (2008), 503-516
30. D. Nagaj, E. Farhi, J. Goldstone, P. Shor, I. Sylvester:
    The Quantum Transverse Field Ising Model on an Infinite Tree from Matrix Product States
    Phys. Rev. B 77, 214431 (2008)
31. D. Nagaj, S. Mozes:
    A new construction for a QMA complete 3-local Hamiltonian
    J. Math. Phys. 48, 072104 (2007)
32. I. Kerenidis, D. Nagaj:
    On the Optimality of Quantum Encryption Schemes
    J. Math. Phys. 47, 092102 (2006)
33. D.Nagaj, P.Štelmachovič, V.Bužek, M.S.Kim,:
    Quantum homogenization for continuous variables: Realization with linear optical elements | pdf |
    Phys. Rev. A 66 , 62307 (2002)

Submitted

1. Dorian Rudolph, Sevag Gharibian, Daniel Nagaj:
   Quantum 2-SAT on low dimensional systems is QMA1-complete: Direct embeddings and black-box simulation
   [arXiv:2401.02368]

Unpublished

1. Daniel Nagaj:
   Local Hamiltonians in Quantum Computation | pdf |
   Ph.D. Thesis, MIT (2008) [0808.2117]