Publications

2024

1. arxiv

   Alternative Method for Estimating Betti Numbers

   Nhat A Nghiem

   arXiv preprint arXiv:2403.04686, 2024

   Abs PDF

   Topological data analysis (TDA) is a fast-growing field that utilizes advanced tools from topology to analyze large-scale data. A central problem in topological data analysis is estimating the so-called Betti numbers of the underlying simplicial complex. While the difficulty of this problem has been established as NP-hard, previous works have showcased appealing quantum speedup. In this article, we provide an alternative method for estimating Betti numbers and normalized Betti numbers of given simplicial complex, based on some recent advances in quantum algorithm, specifically, quantum singular value transformation. Our method can be faster than the best-known classical method for finding Betti numbers, and interestingly, it can also find the Betti numbers of the complement graph to our original one. Comparing to the best known quantum algorithm, our method generally requires lower depth circuit, in trade-off for longer running time. Regarding normalized Betti numbers, our method could match the running time of best-known quantum method in the case of dense simplices.

2. arxiv

   Quantum Algorithm For Solving Nonlinear Algebraic Equations

   Nhat A Nghiem, and Tzu-Chieh Wei

   arXiv preprint arXiv:2404.03810, 2024

   Abs PDF

   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.

3. PhysLett

   Quantum algorithm for computing distances between subspaces

   Nhat A Nghiem

   Physics Letters A, 2024

   Abs PDF

   Geometry and topology have generated impacts far beyond their pure mathematical primitive, providing a solid foundation for many applicable tools. Typically, real-world data are represented as vectors, forming a linear subspace for a given data collection. Computing distances between different subspaces is generally a computationally challenging problem with both theoretical and applicable consequences, as, for example, the results can be used to classify data from different categories. Fueled by the fast-growing development of quantum algorithms, we consider such problems in the quantum context and provide a quantum algorithm for estimating two kinds of distance: Grassmann distance and ellipsoid distance. Under appropriate assumptions and conditions, the speedup of our quantum algorithm is exponential with respect to both the dimension of the given data and the number of data points. Some extensions regarding estimating different kinds of distance are then discussed as a corollary of our main quantum algorithmic method.

4. arxiv

   Improved Quantum Power Method and Numerical Integration Using Quantum Singular Value Transformation

   Nhat A Nghiem, Hiroki Sukeno, Shuyu Zhang, and 1 more author

   arXiv preprint arXiv:2407.11744, 2024

   Abs PDF

   Quantum singular value transformation (QSVT) is a framework that has been shown to unify many primitives in quantum algorithms. In this work, we leverage the QSVT framework in two directions. We first show that the QSVT framework can accelerate one recently introduced quantum power method, which substantially improves its running time. Additionally, we incorporate several elementary numerical integration techniques, such as the rectangular method, Monte Carlo method, and quadrature method, into the QSVT framework, which results in polynomial speedup with respect to the size or the number of points of the grid. Our results thus provide further examples to demonstrate the potential of the QSVT and how it may enhance quantum algorithmic tasks.

2023

1. QMI

   Subtleties in the trainability of quantum machine learning models

   Supanut Thanasilp, Samson Wang, Nhat Anh Nghiem, and 2 more authors

   Quantum Machine Intelligence, 2023

   Abs PDF

   A new paradigm for data science has emerged, with quantum data, quantum models, and quantum computational devices. This field, called quantum machine learning (QML), aims to achieve a speedup over traditional machine learning for data analysis. However, its success usually hinges on efficiently training the parameters in quantum neural networks, and the field of QML is still lacking theoretical scaling results for their trainability. Some trainability results have been proven for a closely related field called variational quantum algorithms (VQAs). While both fields involve training a parametrized quantum circuit, there are crucial differences that make the results for one setting not readily applicable to the other. In this work, we bridge the two frameworks and show that gradient scaling results for VQAs can also be applied to study the gradient scaling of QML models. Our results indicate that features deemed detrimental for VQA trainability can also lead to issues such as barren plateaus in QML. Consequently, our work has implications for several QML proposals in the literature. In addition, we provide theoretical and numerical evidence that QML models exhibit further trainability issues not present in VQAs, arising from the use of a training dataset. We refer to these as dataset-induced barren plateaus. These results are most relevant when dealing with classical data, as here the choice of embedding scheme (i.e., the map between classical data and quantum states) can greatly affect the gradient scaling.

2. QIP

   An improved method for quantum matrix multiplication

   Nhat A Nghiem, and Tzu-Chieh Wei

   Quantum Information Processing, 2023

   Abs PDF

   Following the celebrated quantum algorithm for solving linear equations (so-called HHL algorithm), Childs et al. (SIAM J Comput 46:1920–1950, 2017) provided an approach to solve a linear system of equations with exponentially improved dependence on precision. In this note, we aim to complement such a result for applying a matrix to some quantum state, based upon their Chebyshev polynomial approach. A few examples that motivate this application are included, and we further discuss an application of this improved matrix application algorithm explicitly with an efficient quantum procedure.

3. Sci

   Constant-time quantum algorithm for homology detection in closed curves

   Nhat Anh Nghiem Vu, Xianfeng David Gu, and Tzu-Chieh Wei

   SciPost Physics, 2023

   Abs PDF

   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.

4. arxiv

   Quantum Algorithm for Estimating Betti Numbers Using a Cohomology Approach

   Nhat A Nghiem, Xianfeng David Gu, and Tzu-Chieh Wei

   arXiv preprint arXiv:2309.10800, 2023

   Abs PDF

   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.

5. PhysLett

   Quantum algorithm for estimating largest eigenvalues

   Nhat A Nghiem, and Tzu-Chieh Wei

   Physics Letters A, 2023

   Abs PDF

   Scientific computation involving numerical methods relies heavily on the manipulation of large matrices, including solving linear equations and finding eigenvalues and eigenvectors. Quantum algorithms have been developed to advance these computational tasks, and some have been shown to provide substantial speedup, such as factoring a large integer and solving linear equations. In this work, we leverage the techniques used in the Harrow-Hassidim-Llyod (HHL) algorithm for linear systems, the classical power, and the Krylov subsapce method to devise a simple quantum algorithm for estimating the largest eigenvalues in magnitude of a Hermitian matrix. Our quantum algorithm offers significant speedup with respect to the size of a given matrix over classical algorithms that solve the same problem.

6. arxiv

   Improved Quantum Algorithms for Eigenvalues Finding and Gradient Descent

   Nhat A Nghiem, and Tzu-Chieh Wei

   arXiv preprint arXiv:2312.14786, 2023

   Abs PDF

   Block encoding is a key ingredient in the recently developed quantum signal processing that forms a unifying framework for quantum algorithms. Initially showcased for simplifying and optimizing resource utilization in several problems, such as searching, amplitude estimation, and Hamiltonian simulation, the capabilities of the quantum signal processing go beyond these and offer untapped potential for devising new quantum algorithms. In this article, we utilize block encoding to substantially enhance two previously proposed quantum algorithms: largest eigenvalue estimation and quantum gradient descent. Unlike previous works that involve sophisticated procedures, our findings, using the unitary block encoding, demonstrate that even with elementary operations, these new quantum algorithms can eliminate major scaling factors present in their original counterparts. This yields much more efficient quantum algorithms capable of tackling complex computational problems with remarkable efficiency. Furthermore, we show how to extend our proposed method to different contexts, including matrix inversion and multiple eigenvalues estimation.

2022

1. PhysRev

   Heat pulse propagation and nonlocal phonon heat transport in one-dimensional harmonic chains

   Philip B Allen, and Nhat A Nghiem

   Physical Review B, 2022

   Abs PDF

   Phonons are the main heat carriers in semiconductor devices. In small devices, heat is not driven by a local temperature gradient, but by local points of heat input and removal. This complicates theoretical modeling. Study of the propagation of vibrational energy from an initial localized pulse provides insight into nonlocal phonon heat transport. We report simulations of pulse propagation in one dimension. The 1d case has tricky anomalies, but provides the simplest pictures of the evolution from initially ballistic toward longer time diffusive propagation. Our results show surprising details, such as diverse results from different definitions of atomistic local energy, and failure to exhibit pure diffusion at long times. Boltzmann phonon gas theory, including external energy insertion, is applied to this inherently time-dependent and nonlocal problem. The solution, using relaxation time approximation for impurity scattering, does not closely agree with the simulated results.

2021

1. PhysRev

   Unified framework for quantum classification

   Nhat A Nghiem, Samuel Yen-Chi Chen, and Tzu-Chieh Wei

   Physical Review Research, 2021

   Abs PDF

   Quantum machine learning is an emerging field that combines machine learning with advances in quantum technologies. Many works have suggested great possibilities of using near-term quantum hardware in supervised learning. Motivated by these developments, we present an embedding-based framework for supervised learning with trainable quantum circuits. We introduce both explicit and implicit approaches. The aim of these approaches is to map data from different classes to separated locations in the Hilbert space via a parametrized quantum circuit. We will show that the implicit approach is a generalization of a recently introduced strategy, so-called quantum metric learning. Furthermore, we discuss an intrinsic connection between the explicit approach and those previously proposed quantum classification models. The implicit and explicit approaches, together, provide a unified framework for quantum classification. The utility of our framework is demonstrated by our noise-free and noisy numerical simulations. Moreover, we have conducted classification testing with both implicit and explicit approaches using several IBM Q devices.