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 many-body system give rise to ground states that are interesting from three viewpoints. First, their relationship to optimization problems, second, their non-classical 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 many-body 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, pp1048-1070 (2016)
- Quantum 3-SAT Is QMA1-Complete David Gosset and Daniel Nagaj SIAM J. Comput. 45-3, pp. 1080-1128 (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. 243-255. (2017)
- The Feynman-Kitaev 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 pair-flip model: a very entangled translationally invariant spin chain Libor Caha, Daniel Nagaj arXiv:1805.07168
