Nhat Anh Nghiem

Given a loop or more generally 1-cycle r of size L on a closed two-dimensional manifold or surface, represented by a triangulated mesh, a question in computational topology asks whether or not it is homologous to zero. We frame and tackle this problem in the quantum setting. Given an oracle that one can use to query the inclusion of edges on a closed curve, we design a quantum algorithm for such a homology detection with a constant running time, with respect to the size or the number of edges on the loop r , requiring only a single usage of oracle. In contrast, classical algorithm requires Ω(L) oracle usage, followed by a linear time processing and can be improved to logarithmic by using a parallel algorithm. Our quantum algorithm can be extended to check whether two closed loops belong to the same homology class. Furthermore, it can be applied to a specific problem in the homotopy detection, namely, checking whether two curves are not homotopically equivalent on a closed two-dimensional manifold.

Topological data analysis has emerged as a powerful tool for analyzing large-scale data. An abstract simplicial complex, in principle, can be built from data points, and by using tools from homology, topological features could be identified. Given a simplex, an important feature is called Betti numbers, which roughly count the number of ‘holes’ in different dimensions. Calculating Betti numbers exactly can be #P-hard, and approximating them can be NP-hard, which rules out the possibility of any generic efficient algorithms and unconditional exponential quantum speedup. Here, we explore the specific setting of a triangulated manifold. In contrast to most known quantum algorithms to estimate Betti numbers, which rely on homology, we exploit the ‘dual’ approach by cohomology, combining the Hodge theory and de Rham cohomology, as well as recent development in quantum algorithm. This cohomology approach requires exponentially fewer qubits than those known homology-based approaches. Our proposed algorithm can calculate its r-th Betti number \beta_r up to some multiplicative error δwith running time \mathcalO\big( \log(c_r) \sqrtr \sqrtc_r / \beta_r 1/δ\big), where c_r is the number of r-simplex. It thus works best in the regime when the r-th Betti number is considerably smaller than the number of the r-simplices and is exponentially faster than previous homology methods in appropriate regime.

Nonlinear equations are challenging to solve due to their inherently nonlinear nature. As analytical solutions typically do not exist, numerical methods have been developed to tackle their solutions. In this article, we give a quantum algorithm for solving a system of nonlinear algebraic equations, in which each equation is a multivariate polynomial of known coefficients. Building upon the classical Newton method and some recent works on quantum algorithm plus block encoding from the quantum singular value transformation, we show how to invert the Jacobian matrix to execute Newton’s iterative method for solving nonlinear equations, where each contributing equation is a homogeneous polynomial of an even degree. A detailed analysis are then carried out to reveal that our method achieves polylogarithmic time in relative to the number of variables. Furthermore, the number of required qubits is logarithmic in the number of variables. In particular, we also show that our method can be modified with little effort to deal with polynomial of various types, thus implying the generality of our approach. Some examples coming from physical context, such as Gross-Pitaevski equation and Lotka-Volterra equations, involving nonlinear partial differential equations are provided to motivate the potential application, with a description on how to extend our algorithm with even less effort in such a scenario. Our work thus marks a further important step towards quantum advantage in nonlinear science, enabled by the framework of quantum singular value transformation.