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?



1 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.

  • $\begingroup$ 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? $\endgroup$
    – Ohad
    Oct 27, 2022 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.