Quantum Speedup in Dissecting Roots and Solving Nonlinear Algebraic Equations

• URL: http://arxiv.org/abs/2503.06609v1
• Date: Sun, 09 Mar 2025 13:27:11 GMT
• Title: Quantum Speedup in Dissecting Roots and Solving Nonlinear Algebraic Equations
• Authors: Nhat A. Nghiem,
• Abstract summary: It is shown that quantum computer can detect the existence of root of a function almost exponentially more efficient than the classical counterpart.<n>Various applications and implications are discussed, including a quantum algorithm for solving dense linear systems.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It is shown that quantum computer can detect the existence of root of a function almost exponentially more efficient than the classical counterpart. It is also shown that a quantum computer can produce quantum state corresponding to the solution of nonlinear algebraic equations quadratically faster than the best known classical approach. Various applications and implications are discussed, including a quantum algorithm for solving dense linear systems with quadratic speedup, determining equilibrium states, simulating the dynamics of nonlinear coupled oscillators, estimating Lyapunov exponent, an improved quantum partial differential equation solver, and a quantum-enhanced collision detector for robotic motion planning. This provides further evidence of quantum advantage without requiring coherent quantum access to classical data, delivering meaningful real-world applications.

Related papers

• Variational quantum and neural quantum states algorithms for the linear complementarity problem [1.2796203864160849]
  Variational quantum algorithms (VQAs) are promising hybrid quantum-classical methods. We present a novel application of the variational quantum linear solver (VQLS) and its classical neural quantum states-based counterpart, the variational neural linear solver (VNLS) We demonstrate using the VNLS that our solver accurately simulates the dynamics of rigid spherical bodies during collision events.
  arXiv  Detail & Related papers  (2025-04-10T22:03:14Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Phase-space negativity as a computational resource for quantum kernel methods [2.5499055723658097]
  Quantum kernel methods are a proposal for achieving quantum computational advantage in machine learning. We provide sufficient conditions for the efficient classical estimation of quantum kernel functions for bosonic systems. Our results underpin the role of the negativity in phase-space quasi-probability distributions as an essential resource in quantum machine learning.
  arXiv  Detail & Related papers  (2024-05-20T21:18:53Z)
• Efficient estimation of trainability for variational quantum circuits [43.028111013960206]
  We find an efficient method to compute the cost function and its variance for a wide class of variational quantum circuits. This method can be used to certify trainability for variational quantum circuits and explore design strategies that can overcome the barren plateau problem.
  arXiv  Detail & Related papers  (2023-02-09T14:05:18Z)
• A theory of quantum differential equation solvers: limitations and fast-forwarding [19.080267236745623]
  We show that quantum algorithms suffer from computational overheads due to two types of non-quantumness'' We then show that ODEs in the absence of both types of non-quantumness'' are equivalent to quantum dynamics. We show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency.
  arXiv  Detail & Related papers  (2022-11-09T22:50:14Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Quantum advantage for differential equation analysis [13.39145467249857]
  We show how the output of quantum differential equation solving can serve as the input for quantum machine learning. These quantum algorithms provide an exponential advantage over existing classical Monte Carlo methods.
  arXiv  Detail & Related papers  (2020-10-29T17:19:04Z)
• Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices [0.0]
  We introduce a quantum solver of contracted eigenvalue equations, the quantum analogue of classical methods for the energies. We demonstrate the algorithm though computations on both a quantum simulator and two IBM quantum processing units.
  arXiv  Detail & Related papers  (2020-04-23T18:35:26Z)
• Quantum computation of molecular response properties [12.66895275733527]
  We propose an algorithm for computing linear and nonlinear molecular response properties on quantum computers. On the other hand, we introduce a variational hybrid quantum-classical variant of the proposed algorithm, which is more practical for near-term quantum devices.
  arXiv  Detail & Related papers  (2020-01-10T12:49:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.