
P R O J E C T SASPRO
LHQC SASPRO (Marie Curie individual fellowship)
Title: Local Hamiltonians in Quantum Complexity
Duration: 01/09/2015  31/12/2018
Principal Investigator: Daniel Nagaj
Project Description:
What does nature allow us to compute and why are some physics problems computationally more difficult than others? These questions on the boundary of theoretical physics and computer science have their root at the microscopic level. Local interactions in a quantum manybody system give rise to ground states that are interesting from three viewpoints. First, their relationship to optimization problems, second, their nonclassical correlations, and third, the possibilities of approximation. In this project, our first and basic goal is the understanding of the computational hardness (or simplicity) of simulation for these systems, developing quantum information theory for Hamiltonian systems. Second, we will utilize and generalize the area law for ground states of gapped local Hamiltonians as a computational tool, aiming at applications in manybody physics numerical methods. Third, we will explore the robustness of these results in presence of noise and various approximations, bringing light to the hottest topic in quantum complexity theory: the quantum PCP conjecture.
Researchers: Daniel Nagaj
Publications:

Quantum proofs can be verified using only single qubit measurements
Tomoyuki Morimae, Daniel Nagaj, Norbert Schuch
Phys. Rev. A 93, 022326 (2016)

An adaptive attack on Wiesner's quantum money
Daniel Nagaj, Or Sattath, Aharon Brodutch, and Dominique Unruh
Quantum Information & Computation, Vol.16 No.11&12, pp10481070 (2016)

Quantum 3SAT Is QMA1Complete
David Gosset and Daniel Nagaj
SIAM J. Comput. 453, pp. 10801128 (2016)

Exact Quantum Query Complexity of EXACTnk,l
Andris Ambainis, Jānis Iraids, Daniel Nagaj
In: Steffen B., Baier C., van den Brand M., Eder J., Hinchey M., Margaria T. (eds) SOFSEM 2017: Theory and Practice of Computer Science. SOFSEM 2017. Lecture Notes in Computer Science, vol 10139. Springer, Cham, 2017. S. 243255. (2017)

The FeynmanKitaev computer's clock: bias, gaps, idling and pulse tuning
Daniel Nagaj, Libor Caha, Zeph Landau
Physical Review A, Vol. 97, No. 6, 062306 (2018)

Shorter unentangled proofs for Ground State Connectivity
Daniel Nagaj, Libor Caha, Martin Schwarz
Quantum Information Processing 17:174 (2018)

The pairflip model: a very entangled translationally invariant spin chain
Libor Caha, Daniel Nagaj
arXiv:1805.07168

