7
$\begingroup$

From a few VQE tutorials online I see that they normally start with something like:

VQE is a way of getting a good estimate for the upper bound of the ground state of a quantum system's Hamiltonian. The Hamiltonian is known.

Then they proceed to show you a single qubit Hamiltonian as a 2x2 matrix, and go through the VQE algorithm to get the ground state energy (the smaller of the two eigenvalues).

Cool, but as devil's advocate, I could have just pulled out my high school maths to analytically get the smaller of the two eigenvalues. And with larger matrices, a classical computer will do the job well (which afaik is not a hard problem).

My question then is at what point does a Hamiltonian's matrix representation become so large, that even though we know it, we'd go to the trouble of probing the quantum system itself rather than solving for the eigenvalues on a classical computer? And how does that relate to the current and near future statuses of classical and quantum computing?

Please feel free to completely sidestep my question and nudge me back on track if I'm off-paradigm or started from the wrong premise.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

The computational advantage of using quantum computers can be reached if the classical resources (memory; number of operations), required to solve a particular problem, grow exponentially in a certain parameter, while the quantum resources (memory; number of operations; number of measurements) grow polynomially in the same parameter.

Finding the lowest eigenvalue of an arbitrary matrix may very well NOT be a problem which you can solve on a quantum computer with an exponential improvement over the classical methods. (Please someone correct me if I'm wrong.)

However, if you are interested in finding the lowest eigenvalue of a Hamiltonian representing some physical system, there is a good chance that using quantum computers (in general) and VQE (in particular) may give you some advantage.

Consider, as an example, a Hamiltonian describing a system of $n$ particles. The Hilbert space size in this case grows with the number of particles as $N=O(\operatorname{exp}(n))$. For any reasonable encoding, the number of qubits required to encode the state of such a system in a quantum computer grows as $O(\operatorname{poly}(n))$. If you want to use VQE, the other parameters you are concerned with are:

  • The number of Pauli operators in the expansion of the Hamiltonian — grows as $O(\operatorname{poly}(n))$ for local interactions.
  • The number of gates required to prepare an ansatz state — grows as $O(\operatorname{poly}(n))$ for many known cases (e.g. look up UCCSD for quantum chemistry: one, two).

Therefore, in this case all the quantum resources grow polynomially in $n$:

Memory; number of gates; number of measurements $=O(\operatorname{poly}(n))$.

In the classical case, one would have to generally deal with vectors and matrices in $N = O(\operatorname{exp(n)})$ dimensions. Therefore, in this case we clearly have an improvement in memory and, quite likely, in the number of operations (asymptotically) as well.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks although I'm a bit confused as you start with the paragraph in bold saying that getting the lowest eigenvalue of an arbitrary matrix is not more efficient on a quantum computer. In the next paragraph "find the lowest eigenvalue of a Hamiltonian representing some physical system", that's essentially the same thing. Remember that I'm starting from the premise that the Hamiltonian must be known for VQE. And from the link I shared, classically we can find a good approximation in polynomial time. $\endgroup$
    – Alexander Soare
    Commented May 22, 2020 at 9:48
  • 2
    $\begingroup$ This is NOT the same thing, that's the whole point. A matrix representing a Hamiltonian of some physical system is typically largely constrained (in the sense that it has many additional properties), as compared to an arbitrary matrix of the same size. It is especially true in the case of multiparticle systems with local interactions - such Hamiltonians are typically extremely sparse (meaning that the number of nonzero entries in each row/column scales as $O(\operatorname{poly}(n))$, while the size of the matrix scales as $O(\operatorname{exp}(n))$). $\endgroup$
    – mavzolej
    Commented May 22, 2020 at 13:11
  • 1
    $\begingroup$ Using your terminology: for an arbitrary $N\times N$ matrix (where $N=O(\operatorname{exp}(n))$ in my notations from above), the classical resources required to find the lowest eigenvalue on this matrix scale as $O(\operatorname{poly}(N))$. However, in certain cases the quantum resources scale as $O(\operatorname{poly}(\log(N))$. $\endgroup$
    – mavzolej
    Commented May 22, 2020 at 13:19
  • 3
    $\begingroup$ I meant "in certain cases" ALL the quantum resources scale as $O(\operatorname{poly}(\log(N)))$. As of your last remark: not really. The class of Hamiltonian matrices representing local multiparticle interactions is, in fact, extremely wide (nearly all known physical systems). There's quite some evidence that most of them can be efficiently (in the sense discussed above) simulated on quantum computers. At the same time, it is likely that one will never be able to efficiently simulate an arbitrary quantum system on a classical computer. See a good intro. $\endgroup$
    – mavzolej
    Commented May 22, 2020 at 14:51
  • 1
    $\begingroup$ Original paper, a detailed example, an experimental implementation, some complexity analysis, a generalization for thermal states, a generalization for excited states # 1, a generalization for excited states # 2. Also look up stuff on QAOA, a variant of VQE for classically hard problems. $\endgroup$
    – mavzolej
    Commented Jun 5, 2020 at 16:40

Your Answer

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

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