Checking out SciRate there’s been a fair bit of good quant-ph action over the last week. For instance you might want to check out the following papers:
- Guillaume Aubrun, A remark on the paper “Randomizing quantum states: Constructions and applications”. (10 scites)
- Huw Price, Toy Models for Retrocausality. (7 scites)
- Keisuke Fujii, Katsuji Yamamoto, Fault-tolerant quantum computation in concatenation of verified cluster states. (5 scites)
- Shesha Raghunathan, Todd Brun, Continuous monitoring can improve indistinguishability of a single-photon source. (5 scites)
- Paulo E. M. F. Mendonca, Alexei Gilchrist, Andrew C. Doherty, Optimal tracking for single qubit states. (5 scites)
Unfortunately the world is cruel and the law of the land clearly states that there can only ever be one Weakly Abstract (that is until I decide to do things differently of course). The paper that caught my eye this week was The computational difficulty of finding MPS ground states by Schuch, Cirac, and Verstraete:
The computational difficulty of finding MPS ground states
Authors: Norbert Schuch, Ignacio Cirac, Frank Verstraete
We determine the computational difficulty of finding ground states of one-dimensional (1D) Hamiltonians which are known to be Matrix Product States (MPS). Therefore, we construct a class of 1D frustration free Hamiltonians with unique MPS ground states and a polynomial gap above, for which finding the ground state is at least as hard as factoring. By lifting the requirement of a unique ground state, we obtain a class for which finding the ground state solves an NP-complete problem. Therefore, for these Hamiltonians it is not even possible to certify that the ground state has been found. Our results thus imply that in order to prove convergence of variational methods over MPS, as the Density Matrix Renormalization Group, one has to put more requirements than just MPS ground states and a polynomial spectral gap.
Where to begin, where to begin. Well, once upone a time there was a classical algorithm called the Density Matrix Renormalization Group (DMRG). Now DMRG is an algorithm that varies over Matrix Product States (MPS) in order to determine which MPS describe the low energy structure of some Hamiltonian. Typically, DMRG works very well in 1D systems. When I say "works well" I mean that the DMRG algorithm converges on a MPS that is a good approximation to the ground state of the Hamiltonian. Indeed, Hastings proved that if a 1D Hamiltonian has a local structure and is "gapped" then it’s ground state can always be approximated by an MPS.
The key question is how hard is it to find the right MPS to describe the ground state of a given Hamiltonian. Jens Eisert demonstrated in 2006 that performing DMRG on 1D frustrated systems while trying to optimize multiple local sites at once is an NP hard problem. Eisert pointed out that if one optimizes DMRG locally then it is possible to get stuck in local minima, whereas if a more global optimization is performed the problem becomes computationally intractable. Eisert’s results suggest that it can be difficult to make DMRG converge to the correct answer even in somewhat simple systems. Unfortunately his approach doesn’t say much about the typical behaviour of DMRG as it depended on arguments about specific systems (those which are frustrated) and also it is restricted to particular optimization methods.
In this week’s Weakly Abstract paper Schuch, Cirac, and Verstraete have taken a more general approach to this problem. In particular they have leveraged recent results of Kitaev and Aharonov et al on the QMA completeness of the LOCAL HAMILTONIAN problem to the problem of finding MPS descriptions of the ground states of 1D systems.
Importantly, they use techniques from the study of the LOCAL HAMILTONIAN problem to construct classes of Hamiltonians with the following properties:
- There is a class of 1D local frustration-free Hamiltonians of length L, a gap of order 1/poly(L), with a unique MPS of size poly(L) describing the ground state and MPS describing the low-energy states where finding the MPS corresponding to the ground state is in NPcoNP. Notably, this class of problems includes factoring which is thought to be hard.
- There is a class of 1D local Hamiltonians of length L, a gap of order 1/poly(L), the ground state is an eigenstate of every local term and where the ground state manifold is spanned by MPS for which finding the ground state is NP-complete. (Note that finding the ground state of some classical 2D systems has long been known to be NP-complete)
They argue (quite well!) that existence of the above two classes demonstrates that it is very unlikely that one can find a certifiable version of DMRG. That is, a version of DMRG where one can efficiently check whether a particular solution is indeed the correct solution.
It should be emphasized that there are lots of classes of Hamiltonians for which DMRG will converge to the correct answer, as is often the case with these sort of NPish results. It’s just that we can’t say really which ones converge and we can’t write an algorithm that can generally check this quickly for 1D systems.
One of the more interesting aspects of this paper, which I’d like to think a lot more about, is how they used the techniques developed for QMA-completeness proofs of the LOCAL HAMILTONIAN problem of Kitaev and co to find NP-hard ground states. They suggest in the paper that there may be other classes of Hamiltonians with more NP trickery happening in their low-energy eigenstates waiting to be found by using these techniques…