# Complexity of Variational Quantum Eigensolvers

I am doing research surrounding VQE and am a bit confused about the complexity and its comparison to classical systems. My brief research has yielded me that classical eigenvalue solving is $$O(n^3)$$. For a given $$2^n$$ by $$2^n$$ Hamiltonian, I understand why the quantum side of the algorithm would be faster, assuming we have $$O(\text{Poly}(N))$$ Pauli Strings in our decomposition and short enough Pauli Strings. My question on complexity relates to the time taken for decomposition. I've found the Frobenius Inner Product Method, PauliDecomposer used by Qiskit, and other methods for general Pauli decomposition. All appear to be exponential in complexity. Given a generic Hamiltonian, is it possible to create quantum speedup (theoretically) given this exponential time taken for decomposition? Or do the applications of VQE only apply to physical systems where we form our Hamiltonian from physical devices like particles or graph nodes?

• If $n$ is a number of qubits, are you sure that classical eigenvalue algs scale as $O(n^3)$ and not $O((2^n)^3)$? Commented Apr 11 at 22:42

The decomposition of a Hamiltonian into Pauli strings is not always efficient. The general problem of decomposing a Hamiltonian expressed in an arbitrary basis into Pauli operators can be computationally challenging, often exhibiting exponential complexity with respect to the system size. The decomposition methods you mentioned, such as the Frobenius Inner Product Method and PauliDecomposer in Qiskit, are used to obtain this decomposition, but the complexity can grow significantly depending on the nature of the Hamiltonian.

This brings us to your query about whether there can be a theoretical quantum speedup given the potentially exponential time taken for the decomposition. Here, the nature of the Hamiltonian is crucial:

Physical Systems: For many physically relevant systems, such as molecules or spin networks, the Hamiltonian naturally exhibits a sparse or structured form. This sparsity or the presence of underlying physical symmetries can often be exploited to achieve a decomposition into Pauli strings that is more tractable (e.g., polynomially many terms). In these cases, VQE can offer a quantum speedup because the quantum state preparation and measurement steps are efficient, and the Hamiltonian decomposition is manageable.

Generic Hamiltonians: For a generic Hamiltonian without any specific structure or properties, the decomposition into a sum of Pauli strings could indeed become a bottleneck, potentially requiring exponential resources.