Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup

• URL: http://arxiv.org/abs/2412.19090v2
• Date: Wed, 01 Jan 2025 02:54:42 GMT
• Title: Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup
• Authors: Zi-Ming Li, Yu-xi Liu,
• Abstract summary: Gram-Schmidt process is widely used to solve Vector set normalization and matrix QR decomposition. Existing methods have problems of high complexity, scaling $O(N3)$ in the system dimension $N$. We propose quantum algorithms to solve these two problems based on the idea of Gram-Schmidt process and quantum phase estimation.
• Score: 4.913177281640608
• License:
• Abstract: Vector set orthogonal normalization and matrix QR decomposition are fundamental problems in matrix analysis with important applications in many fields. We know that Gram-Schmidt process is a widely used method to solve these two problems. However, the existing methods, including Gram-Schmidt process have problems of high complexity, scaling $O(N^3)$ in the system dimension $N$, which leads to difficulties when calculating large-scale or ill-conditioned problems. With the development of quantum information processing, a series of quantum algorithms have been proposed, providing advantages and speedups over classical algorithms in many fields. In this paper, we propose quantum algorithms to solve these two problems based on the idea of Gram-Schmidt process and quantum phase estimation. The complexity of proposed quantum algorithms is also theoretically and numerically analyzed. We find that our algorithms provide polynomial acceleration over the best-known classical and quantum algorithms on these two problems, scaling $O(N^2\mathrm{poly}(\log N))$ in the dimension $N$ of the system.

Related papers

• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  We propose a quantum algorithm inspired by the classical multi-row iteration method. Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
  arXiv  Detail & Related papers  (2024-09-06T03:32:02Z)
• A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
  We propose a quantum-classical hybrid algorithm with Ising model (HAWI) to address the Learning-With-Errors (LWE) problem. We identify the low-energy levels of the Hamiltonian to extract the solution, making it suitable for implementation on current noisy intermediate-scale quantum (NISQ) devices. Our algorithm is iterations, and its time complexity depends on the specific quantum algorithm employed to find the Hamiltonian's low-energy levels.
  arXiv  Detail & Related papers  (2024-08-15T05:11:35Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
  We propose two quantum algorithms for solving quantum linear systems of equations with coherent superposition. The two quantum algorithms can both compute the rank and general solution by one measurement. Our analysis indicates that the proposed algorithms are mainly suitable for conducting attacks against lightweight symmetric ciphers.
  arXiv  Detail & Related papers  (2024-05-11T03:03:14Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  We present a complete analysis of the quantum solvability of the noisy binary linear problem (NBLP) We show that the cost of solving the NBLP can be in the problem size, at the expense of an exponentially increasing logical qubits.
  arXiv  Detail & Related papers  (2021-09-23T07:46:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• A Grand Unification of Quantum Algorithms [0.0]
  A number of quantum algorithms were recently tied together by a technique known as the quantum singular value transformation. This paper provides a tutorial through these developments, first illustrating how quantum signal processing may be generalized to the quantum eigenvalue transform. We then employ QSVT to construct intuitive quantum algorithms for search, phase estimation, and Hamiltonian simulation.
  arXiv  Detail & Related papers  (2021-05-06T17:46:33Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer. We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
  arXiv  Detail & Related papers  (2020-09-02T22:46:47Z)

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.