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/08/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:
  1. Andris Ambainis, Jānis Iraids, Daniel Nagaj: Exact quantum query complexity of EXACTk,ln, 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]
  2. Aharon Brodutch, Daniel Nagaj, Or Sattath, Dominique Unruh: An adaptive attack on Wiesner's quantum money based on interaction-free measurement, Quantum Information & Computation, Vol.16 No.11&12, pp1048-1070 (2016) [arXiv:1404.1507]
  3. Tomoyuki Morimae, Daniel Nagaj, Norbert Schuch: Quantum proofs can be verified using only single qubit measurements, Phys. Rev. A 93, 022326 (2016) [arXiv:1510.06789]