Search

Quantum algorithms for Hamiltonian simulation and linear differential equations more generally have provided promising exponential speed-ups over classical computers on a set of problems with high real-world interest. However, extending this to a nonlinear problem has proven challenging, with exponential lower bounds having been demonstrated for the time scaling. We provide a quantum algorithm matching these bounds. Specifically, we find that for a non-linear differential equation of the form $\frac{d|u\rangle}{dt} = A|u\rangle + B|u\rangle^{\otimes2}$ for evolution of time $T$, error tolerance $\epsilon$ and $c$ dependent on the strength of the nonlinearity, the number of queries to the differential operators that approaches the scaling of the quantum lower bound of $e^{o(T\|B\|)}$ queries in the limit of strong non-linearity. Finally, we introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case, as well as a randomized classical algorithm based on path integration that acts as a true analogue to the quantum algorithm in that it scales comparably to the quantum algorithm in cases where sign problems are absent.

Let $H$ be a fixed undirected graph on $k$ vertices. The $H$-hitting set problem asks for deleting a minimum number of vertices from a given graph $G$ in such a way that the resulting graph has no copies of $H$ as a subgraph. This problem is a special case of the hypergraph vertex cover problem on $k$-uniform hypergraphs, and thus admits an efficient $k$-factor approximation algorithm. The purpose of this article is to investigate the question that for which graphs $H$ this trivial approximation factor $k$ can be improved.