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

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!

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.  • Thanks. So VQE is not scalable for any Hamiltonian, just for those that tend to decompose efficiently with the number of qubtis. However, regarding the example of a decomposition to the basis $S = \{I,\sigma_+,\sigma_-\}$ - How would we measure the observables in that case?