What are the biggest obstacles currently preventing us from solving real world problems defined in terms of quantum simulation?

Question

Quantum simulation (also referred to as Hamiltonian simulation) is defined as follows:

In the Hamiltonian simulation problem, given a Hamiltonian $H$ ($2^n \times 2^n$ hermitian matrix acting on $n$ qubits), a time $t$ and maximum simulation error $\epsilon$, the goal is to find an algorithm that approximates $U$ such that $||U - e^{-iHt}|| \leq \epsilon$, where $e^{-iHt}$ is the ideal evolution and $||\cdot||$ is the spectral norm.

One of possible applications of quantum simulation is of course simulation of quantum systems, but I'm sure, that there are many others possible. I've read about some possible approaches to this problem (like Trotterization), but I haven't come accros any practical solutions obtained thanks to these methods (probably because of my laziness :) ).

My question is - what is preventing us from solving real world problems, defined in terms of Hamiltonian simulation, on currently available quantum computers? Is this just the number of qubits available? Or maybe, it would be at least theoretically possible to create some hybrid solutions, by inventing new algorithms operating on currently available architectures, to get some results that are beyond the reach of classical algorithms?

Answer 1

What is preventing us from solving real world problems, defined in terms of Hamiltonian simulation, on currently available quantum computers?

Short answer: it depends on the "real world problem" considered, but one or several of qubit number, coherence time or gate errors.

The real answer is really problem-dependant.

Disclaimer: I am not an expert of VQE, please double or triple-check the claims I am making in the following paragraph.

For VQE and quantum chemistry applications we are mostly limited by the number of qubits available and gate errors. Quantum chemistry problems and VQE are one of the main area of research for useful problem solvable on NISQ computers, mainly because they only use Pauli gates that have some very desirable properties. One of them is the possibility to estimate $\langle \psi \vert U \vert \psi \rangle$ with direct measurements instead of indirect ones. See Methodology for replacing indirect measurements with direct measurements for more information on this.

In general, any problem that can be efficiently formulated with Pauli operators is interesting for NISQ quantum computers, thanks to the properties of Pauli operators to be able to replace a costly indirect measurement (Hadamard-test for example) with a direct measurement. For problems that are in this category, I would say that the limiting factors can be gate errors or the number of available qubits.

A few research papers have analysed the cost of simulating more complex Hamiltonians. Here are the two I am aware of:

1. Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target. The authors have used an automatic oracle synthesis tool but they write that

   In the current state of our investigations, we believe that, even with hand-coding, these numbers could only be improved upon by a factor of 5, or perhaps at most a factor of 10.

   The overall number of gates and circuit are depicted at pages 41 and 42. The paper is really detailed and it seems like every implementation steps have been explained.

2. Disclaimer: I am the main author of this paper.

   Practical Quantum Computing: solving the wave equation using a quantum approach. Here the Hamiltonian is given as an Hermitian matrix and is simulated using Trotter-Suzuki formula.

The overall results from the 2 papers above is: oracles are super-costly, mostly because of the heavy use of arithmetic subroutines. Moreover the repetition imposed by the Hamiltonian simulation algorithm to ensure a given precision $\epsilon$ is one of the reason why the number of gates is so high.

So for this kind on application, the number of qubits may or may not be a limitation depending on the problem, but the number of gates is huge and so gate errors and coherence time are the real bottleneck here.

Note also that the execution time starts to be an issue for the two previous algorithms. Even if you could execute gates in 1ns (which is absolutely not the case on current hardware, CNOTs are closer to 100-400ns), executing $10^{20}$ gates would require $10^{11}$ seconds, i.e. more than 3000 years.

Conclusion: Hamiltonian simulation is costly and depending on your specific problem you will be limited by either the number of qubits or thegate errors.

PS: I did not had the time to read the paper yet, but you might be interested in Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware.