What exactly makes VQE faster than classical optimization?

Question

I have been trying to understand Variational Quantum Eigensolver (VQE), particularly from the non-linear binary programming perspective. But after reading a few resources I'm still confused about where exactly the algorithm promise a speed-up over classical one. The key steps where quantum properties provide advantages seem to be:

1. Ansatz preparation $|\psi(\theta)\rangle = U(\theta)|\psi_0\rangle$, where classically this would involve applying matrices of size $2^N$.
2. Computing the expectation $\langle \psi(\theta)|H|\psi(\theta)\rangle$.

Is this essentially correct?

I think I can accept step 1. but for step 2. how does quantum computer computes $\langle \psi(\theta)|H|\psi(\theta)\rangle$ quickly in practice?

I read from several places, e.g. Why exactly are variational algorithms considered promising? that this is done by making repeated measurements to find the approximated distribution of bitstrings in $|\psi(\theta)\rangle$, then compute the expectation value of $H$ classically. The important point seems to be that if $H$ is bounded by some $C$, then the number of samples required to estimate $\langle \psi(\theta)|H|\psi(\theta)\rangle$ to $\epsilon > 0$ precision seems to be $O(C^2/\epsilon^2)$, which grows polynomially with problem size if $C$ does (see e.g. 4.3.3 remark in https://qiskit.org/textbook/ch-applications/qaoa.html#:~:text=QAOA%20(Quantum%20Approximate%20Optimization%20Algorithm,(%20%CE%B2%20%2C%20%CE%B3%20)%20%E2%9F%A9%20). On the other hand, even to simulate the sampling process classically we need to store distribution $|\psi(\theta)\rangle$ which requires $2^N$ space and also another $2^N$ loop to simulate sampling process (dividing $[0,1]$ into $2^N$ subintervals and do a uniform distribution or something?).

But if we are only going to measure $|\psi(\theta)\rangle$ w.r.t. $Z$-basis then compute the expectation value of $H$ classically, then why many resources such as https://arxiv.org/pdf/2111.05176.pdf seems to suggest the importance of having $H$ in a form that is `directly measurable on quantum computer' (see page 7)? This apparently restricts $H$ to the form $H = \sum w_a P_a$ where $P_a \in \{I, X, Y, Z\}^{\otimes N}$, instead of $H$ being any bounded functions $\{0,1\}^N\rightarrow \mathbb{R}$ which should be allowed if we are just going to compute the expectation value classically.

Answer 1

How does quantum computer computes ⟨ψ(θ)|H|ψ(θ)⟩ quickly in practice?

It does if $H$ have a efficient (scales polynomial) decomposition into linear combination of unitaries. In particular, for VQE we want to decomposed it into Pauli string $P_a \in \{I,X,Y,Z\}^{\otimes N}$ as you mentioned in your question. That is, we assumed that $H$ can be written as $$ H = \sum_{a=1}^{O( Poly(N) )} w_a P_a $$ The value $O( Poly(N) )$ determines the number of circuits you have to run on the quantum computer. So that is why you need $H$ to be decomposed efficiently for you to have any speedup in VQE.

So if $dim(H) = 2^N \times 2^N$, then classically the evaluation of $\langle \psi | H | \psi \rangle $ would requires $O( 2^{2N})$ operations naively. But if $H$ is assumed to have an efficient decomposition into Pauli strings, and WOLOG suppose $H = \sum_{a=1}^N w_a P_a $. Then naively we have to perform $N$ circuits on the quantum computer. Furthermore, we are assuming these circuits (ansatz) is not too long. That is, their depth is also scale as $O(poly(N))$. This is usually not a big deal for chemistry application of VQE since there are techniques that can guarantee your circuit (ansatz) scales polynomially. For instance, the popular Unitary Coupled Clustered Single Double (UCCSD) does that, and it is sufficient for many problems of interest. So far we have $N$ circuits to be executed on the quantum computer and each circuit have $O(poly(N))$ operations. Thus overall, we have $O(poly(N))$

What about the number of measurements? You noticed the $O(1/\epsilon^2)$ number of measurements. That is, each of the $N$ circuits in question have to be perform $O(1/\epsilon^2)$ times. This is straightly derived statically. Think of it as flipping a coin. So to get a precision of $\epsilon = 0.0001$ you would need about $O(10^6)$ measurements. But this is still just a constant. It doesn't scale with the problem size.

So all in all, on the quantum computer you can evaluate $\langle \psi | H | \psi \rangle$ in order of $O(poly(N))$ assuming that $H$ is efficiently decomposeable into Pauli strings and the circuit to create $|\psi \rangle$ (ansatz) is not too deep (polynomial depth).

So each iteration of VQE is efficient, and assuming that everything works fine during your optimization and all, you can find the minimum eigenvalue of $H$ within $O(poly(N))$.

---

Note that VQE is heuristic. We are not guarantee that we will actually reach the global minimum. There are many problems arise in the optimization procedure.

Also I mentioned that UCCSD ansatz is very well received for chemistry type problem because of its polynomially scaling and its ability to attack many problems, it is not practical for near-term devices. This is because polynomial can still be very large. You don't expect near-term device can run circuit that has depth of tens of thousands which is what you would run into if you are trying to use UCCSD for large chemical systems. This leads to a lot of work in finding the right circuit for each specific problem of interest so that these circuits can solve the problem you are interesting in but also have minimal depth.

There are also a lot of work recently trying to reduce the number of measurements in VQE. The number of measurements is directly related to the number of Pauli strings in your decomposition. But commuting Pauli string can be measured together. For instance, look at the paper "$O(N^3)$ Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians" for start. And as you noted, $O(1/\epsilon^2)$ number of repeating each circuit is quite bad. It would be nice to reduce this. There are ways to do this. Look at $\alpha-VQE$ by Riverlane, and the work of the Zapata group in "Minimizing estimation runtime on noisy quantum computer".