Publications
2024
- Alternative Method for Estimating Betti NumbersNhat A NghiemarXiv preprint arXiv:2403.04686, 2024
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.
- Quantum Algorithm For Solving Nonlinear Algebraic EquationsNhat A Nghiem, and Tzu-Chieh WeiarXiv preprint arXiv:2404.03810, 2024
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.
- Quantum algorithm for computing distances between subspacesNhat A NghiemPhysics Letters A, 2024
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.
- Improved Quantum Power Method and Numerical Integration Using Quantum Singular Value TransformationNhat A Nghiem, Hiroki Sukeno, Shuyu Zhang, and 1 more authorarXiv preprint arXiv:2407.11744, 2024
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
- Subtleties in the trainability of quantum machine learning modelsSupanut Thanasilp, Samson Wang, Nhat Anh Nghiem, and 2 more authorsQuantum Machine Intelligence, 2023
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.
- An improved method for quantum matrix multiplicationNhat A Nghiem, and Tzu-Chieh WeiQuantum Information Processing, 2023
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.
- Constant-time quantum algorithm for homology detection in closed curvesNhat Anh Nghiem Vu, Xianfeng David Gu, and Tzu-Chieh WeiSciPost Physics, 2023
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.
- Quantum Algorithm for Estimating Betti Numbers Using a Cohomology ApproachNhat A Nghiem, Xianfeng David Gu, and Tzu-Chieh WeiarXiv preprint arXiv:2309.10800, 2023
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.
- Quantum algorithm for estimating largest eigenvaluesNhat A Nghiem, and Tzu-Chieh WeiPhysics Letters A, 2023
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.
- Improved Quantum Algorithms for Eigenvalues Finding and Gradient DescentNhat A Nghiem, and Tzu-Chieh WeiarXiv preprint arXiv:2312.14786, 2023
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
- Heat pulse propagation and nonlocal phonon heat transport in one-dimensional harmonic chainsPhilip B Allen, and Nhat A NghiemPhysical Review B, 2022
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
- Unified framework for quantum classificationNhat A Nghiem, Samuel Yen-Chi Chen, and Tzu-Chieh WeiPhysical Review Research, 2021
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.