How VQE is scalable if the dimension of the Pauli basis of the given Hamiltonian grows exponentially with the number of qubits?

Question

For a given Hamiltonian operator $H$, It's possible to approximate its smallest eigenvalue using VQE. Any Hamiltonian is a Hermitian operator. Therefore, for a system with $n$ qubits, the set $S$ of all combinations of $n$-qubits Pauli tensor-products is a basis for all possible $2^n \times 2^n$ Hamiltonians. The dimension $|S|$ of this basis is $2^n \cdot 2^n = 2^{2n}$, and therefore it grows exponentially with the number of qubits.

Let $A$ be the subset of $S$ that is being used to express a given Hamiltonian. Let $m$ be the cardinality of $A$: $m = |A|$. In each iteration of the VQE we run the Ansatz circuit $m$ times - Each time followed by a measurement scheme defined by the Pauli string $A_i$. Put aside the constant shots factor.

How the VQE algorithm manages to scale efficiently, if $|S|$ grows exponentially with the number of qubits $n$? Of course that if $m$ is small enough, then $|S|$ is not a problem. But surely there are many Hamiltonians with large $m$ due to the exponentially growing $|S|$. Is the VQE useful only for Hamiltonians with small $m$? Is there something else maybe I haven't thought of?

Thanks!

Answer 1

VQE is not scalable if your Hamiltonian is decompose in such a way that it scales exponentially. As you stated, if you choose to decompose your Hamiltonian of size $2^n \times 2^n$ into Pauli basis then a general Hamiltonian will need $4^n$ elements. Thus, evaluating these $4^n$ is not efficient. However, many Hamiltonian of interest can be decomposed into Pauli basis efficiently, in $O(poly(n))$. For instance, in many chemistry applications, where you converting an electronic Hamiltonian into Pauli basis, you see a $O(poly(n))$ scaling. This is one reason why VQE is being applied there!

I should mention that you don't need to always decompose matrix into Pauli operators. Sometime it's best to decompose using different basis. For instance, you can decompose the following matrix $A$

then decomposing this into Pauli basis will scale exponentially, $2^n$ elements! However, if you use another basis set, says $S = \{I, \sigma_+, \sigma_- \}$ then one can show that you only need $O(n)$ elements. To be exact, using the basis set $S$, you can decompose the above matrix $A$ in $2m+1$ elements. To see how to do this, see Variational quantum algorithm for the Poisson equation. The gist is see how $A_n$ grow recursively.