Quantum Simulations with Polariton Graphs
Prof Pavlos Lagoudakis
Skolkovo Institute of Science and Technology, Russian Federation
Department of Physics & Astronomy, University of Southampton, UK
Finding the ground state of physical systems is the natural quantum analogue of classical constraint satisfaction problems that are mapped into various optimization problems in technology and life sciences. Most of these problems belong to the non-deterministic polynomial time (NP)-complete or NP-hard complexity classes and cannot be solved efficiently using classical digital computers. By calculating the ground state energies of a physical system of a given complexity class one can solve any problem in the same complexity class according to the Cook-Levin theorem [1-3]. It has been established that quantum generalisation of constraint satisfaction problems is provided by the k-local Hamiltonian problem , which is quantum Merlin-Arthur (QMA)-complete for k≥2 , where QMA is the quantum analogue of NP. For QMA-complete (NP-complete) problems there are no classical or quantum polynomial-time algorithms to solve them. One way to tackle such computationally intractable problems is to construct a controllable quantum system - a quantum simulator -- for which the calculation of the ground state provides the solution for one and thus all of the NP-complete or NP-hard problems. Apart from potentially solving classical NP-complete or NP-hard problems a major motivation for constructing a quantum simulator for the k-local Hamiltonian problem is in simulating quantum mechanics in large condensed-matter, cosmological, high-energy, atomic, and other systems described in terms of k-local Hamiltonians with restricted types of interactions. Here, I will present recent advances on quantum simulations of 1-D Ising chains and 2-D frustrated classical magnetism utilising polariton graphs.
 S. Cook, Proc. of the Third Ann. ACM Symp. on Theory of Computing, 151, (1971).
 L. Levin, Problems of Information Transmission (in Russian), 9, 115, (1973).
 M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
 A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi, Graduate Studies in Mathematics, AMS, vol. 47, 2002.
 J. Kempe, A. Kitaev, and O. Regev, SIAM J. Comput., 35,1070 (2006).