How to derive quantum advantages for VQAs, if the underlying classical optimization is hard to solve?

Question

This is probably a dumb question but here it goes:

Variational Quantum Algorithms (VQAs) are the leading proposal to derive quantum advantage use NISQ devices. VQAs employ classical optimization algorithms as part of the VQA algorithm.

Classical optimization algorithms can be very expensive to implement for quantum mechanical problems. For example, the Hamiltonian matrix has size that scales exponentially with the number of qubits. So how can we really derive quantum advantage in this case if the underlying classical optimization problem is hard to solve to begin with?

Answer 1

In VQA, there are two subroutines: one is quantum and the other is classical.

The quantum subroutine deals with exponentially large Hilbert space. Think of an $n$-qubit quantum circuit that evolves a $2^n$-dimensional quantum state. In this subroutine, we estimate the expected energy of a Hamiltonian. So, roughly speaking, to estimate the expected energy of a Hamiltonian we need $n$ qubits and many samples from a quantum computer.

The classical subroutine does not deal with $2^n$-dimensional states or Hamiltonians. Instead, it takes the estimates from the quantum subroutine and uses them to drive the classical optimization process. The optimization is happening on the parameter space of a circuit whose dimension is polynomial in the number of qubits.

For example, we can have $2^{100}\times 2^{100}$ dimensional Hamiltonian and a 100-qubit quantum circuit that only has one parameter $\theta$. Using a quantum computer, we estimate necessary quantities such as energy. Then we use these estimates to find the best parameter $\theta$. So classical subroutine only deals with one dimension.

Answer 2

VQAs have something very peculiar. Let me explain.

At heart they are randomized alorithms with nothing interesting in the first place. As a matter of fact there have been only a few studies on their performance (see https://arxiv.org/abs/2209.10615 and https://arxiv.org/abs/2009.10095) but no study I know of has shown satisfactory evidence that VQAs can do something better than classical optimization algorithms.

The problem is ineritely on the difficulty to train them as shown by Bittel et. al. https://arxiv.org/abs/2101.07267. This is of course a "worse case" result and for practical problem instances one can try to argue that its not as important (similar argument can hold for deep neural nets - and we know they work).

The "peculiarity" comes from the fact that the quantum part of the VQA can play a huge role in the outcome of the computation depending on the initial state $|\Psi_0\rangle$. In the magical world of theoretical computer science, people often study the behaviour of various algorithms (e.g. in the Turing machine model of computation) under the assumption that somebody gives us a "very convenient" input string. Combinatorial optimization problems that can be solved using such algorithms with such convenient input strings $f(n)$ form classes such as NP/$f(n)$.Such an experiment can be done for the case of any quantum alorithm, see for example the class of decision problems BQP/poly($n$). It is not hard to conjecture the behaviour of VQAs if we do this mental exercise in order to discover if VQAs can offer "quantum advantage" (I conjecture they can).

In practice thouh this means nothing since usually we have no such "convenient" quantum input (equivalent of string) state $|\tilde \Psi\rangle$ while even if we did there is no way to guarantee this state can be prepared in poly time. As such, and again for "all practical purposes", it seems hard to obtain practical, real world problem quantum advantage using VQAs.