Awesome

Numerical renormalisation/simulation is all about data structures and variational methods: (1) we need to store a classical description of the system's quantum state (the "data structure"); and (2) we need to be able to vary over the class of states representable with the given data structure (this is the "variational method").

There are some well-known data structures out there to simulate condensed matter systems, eg. matrix product states and PEPS. The variational methods for these data structures are the density matrix renormalisation group and relatives. However, one recently proposed data structure, the MERA class described by Guifre Vidal in cond-mat/0512165, has, until recently, been lacking an associated variational procedure. Such variational methods are highly desirable as the MERA class is expected, on physical grounds, to model well the physics of critical quantum systems.

This timely paper is the first to implement a variational method over the MERA class of data structures (which is a classically simulatable quantum circuit). They essentially pick a unitary matrix in the quantum circuit representing the system's state and optimise this while holding the rest fixed (this is a quadratic problem). They sweep through the circuit and repeat. They obtain the ground state by applying e^{-\beta H} to the data structure in infinitesimal pieces, optimising the fidelity after each application.

There are some curious peculiarities of their results: the accuracy they obtain for the ground-state energy of a noncritical system is roughly 10^(-5) which is fairly poor in comparison with the DMRG applied to the same system (which is apparently 10^(-9)). The case of the critical system is a bit worse: they obtain accuracies of 10^(-3), which is comparable to CORE. (Mind you, the computational resources required to obtain these results are less than DMRG.) Additionally, they seem to be getting caught in local minima; increasing the natural refinement parameter for the MERA class doesn't improve the results. This is in contrast to the situation for MPS, where increasing the refinement parameter will typically improve the results.

I'm not sure I agree with the author's explanation of why this occurs: they suggest that adding in constraints to enforce translation invariance will improve the results. However, adding constraints to an optimisation problem can only decrease the objective?

This is an interesting paper, and is well worth a look. Whether the accuracy problems are an artefact of the optimisation method, or of the MERA class itself only time will tell...

Quantum expanders, introduced by Ben-Aroya and Ta-Shma in quant-ph/0702129 and the present author in cond-mat/0701055, are CP maps F which possess two conflicting properties: (i) when applied to any quantum state they inexorably move it closer to the completely mixed state (as measured in Hilbert-Schmidt norm); and (ii) there exists a Kraus-decomposition of F such that F can be written in terms of a constant number (in terms of N, the Hilbert space dimension) of Kraus elements. Clearly one can achieve property (i) by choosing F to be the completely depolarising map D, but this comes at the expense of property (ii) as D requires at least N^2 Kraus elements. Optimising property (ii) obviously restricts how much entropy the map can introduce into a system, and hence, how much the map can mix up an arbitrary quantum state. What is surprising, therefore, is that quantum expanders exist. This was shown in quant-ph/0702129 using maps built from representations of the nonabelian group PGL(2, q). The reason for the name "quantum expander" is that they are one possible generalisation to the quantum domain of expander graphs.

Classically it is known that a random d-regular graph is, with high probability, an expander graph. (For a discussion of this see the excellent article of Hoory et. al. Bull. AMS 43(4), 439 (2006)). So the natural question arises: quantumly, are random CP maps quantum expanders? That is, if M = O(1) Kraus operators are chosen independently from Haar measure on U(N) will the resulting unital map F constructed from these operators be, with high probability, a quantum expander? In this impressive paper the author shows, using a variety of techniques, that the answer is yes.

There are roughly three important ideas underlying the proof: (i) a generalisation of the trace method to apply to CP maps; (ii) an efficient recursive procedure, based on the Schwinger-Dyson equations as employed in lattice gauge theory, to evaluate integrals of traces over U(N)\times U(N) \times ... \times U(N); and (iii) a careful counting argument to prove the convergence of the resulting power series. The trace method is the approach employed to show the corresponding classical result, but the quantum generalisation is far from trivial. Interestingly the quantum result the author proves is as "strong" as the corresponding best classical result (cs/0405020) which requires a huge amount of effort to show.

We now have several constructions of quantum expanders. Given the major role classical expanders play in many areas of computer science it seems plausible that these extremal maps will find many applications. So far quantum expanders have been applied to study the entropy-difference problem and to construct extremal translation-invariant states of chains of spins (these states have essentially the largest entropy growth for a given correlation length). The major outstanding problem now is to see if we can do anything else with quantum expanders.