Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1908.00719 · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics

Quantum Higher Order Singular Value Decomposition

Lejia Gu, Xiaoqiang Wang, Guofeng Zhang

Published Oct 1, 2019• 9 citations
arXivHTMLPDF

Abstract

Higher order singular value decomposition (HOSVD) is an important tool for analyzing big data in multilinear algebra and machine learning. In this paper, we present a quantum algorithm for higher order singular value decomposition. Our method allows one to decompose a tensor into a core tensor containing tensor singular values and some unitary matrices by quantum computers. Compared to the classical HOSVD algorithm, our quantum algorithm provides an exponential speedup.

DOI
10.1109/smc.2019.8914525

Related papers

Multilinear singular value decomposition for two qubits

Pak Shen Choong, Hishamuddin B Zainuddin, I. S. Rakhimov

Schmidt decomposition has been used in the local unitary (LU) classification of bipartite quantum states for some time. In order to generalize the LU classification of bipartite quantum states into multipartite quantum states, higher order singular value decomposition (HOSVD) is introduced but specific examples have not been explicitly worked out. In this pedagogical paper, we would like to work out such details in two qubits since the LU classification of two qubits is well known. We first demonstrate the method of HOSVD in two-qubit systems and discuss its properties. In terms of the LU classification of two-qubit states, some subtle differences in the stabilizer groups of entanglement classes are noticed when Schmidt decomposition is substituted by HOSVD. To reconcile the differences between the two, further studies are needed.

•Jan 1, 2016•1 citation

An Improvement in Quantum Fourier Transform

László Gyöngyösi, Sándor Imre

Singular Value Decomposition (SVD) is one of the most useful techniques for analyzing data in linear algebra. SVD decomposes a rectangular real or complex matrix into two orthogonal matrices and one diagonal matrix. In this work we introduce a new approach to improve the preciseness of the standard Quantum Fourier Transform. The presented Quantum-SVD algorithm is based on the singular value decomposition mechanism. While the complexity of the proposed scheme is the same as the standard Quantum Fourier Transform, the precision of the Quantum-SVD approach is some orders higher. The Quantum-SVD approach also exploits the benefits of quantum searching.

arXiv:1207.4464•Jul 18, 2012•4 citations

Quantum tensor singular value decomposition with applications to recommendation systems

Xiaoqiang Wang, Lejia Gu, Joseph H. W. Lee +1 more

In this paper, we present a quantum singular value decomposition algorithm for third-order tensors inspired by the classical algorithm of tensor singular value decomposition (t-svd) and then extend it to order-$p$ tensors. It can be proved that the quantum version of the t-svd for a third-order tensor $\mathcal{A} \in \mathbb{R}^{N\times N \times N}$ achieves the complexity of $\mathcal{O}(N{\rm polylog}(N))$, an exponential speedup compared with its classical counterpart. As an application, we propose a quantum algorithm for recommendation systems which incorporates the contextual situation of users to the personalized recommendation. We provide recommendations varying with contexts by measuring the output quantum state corresponding to an approximation of this user's preferences. This algorithm runs in expected time $\mathcal{O}(N{\rm polylog}(N){\rm poly}(k)),$ if every frontal slice of the preference tensor has a good rank-$k$ approximation. At last, we provide a quantum algorithm for tensor completion based on a different truncation method which is tested to have a good performance in dynamic video completion.

arXiv:1910.01262•Oct 3, 2019•2 citations

Tensor Decompositions with Applications to Local Unitary and Stochastic Local Operations and Classical Communication Equivalence of Multipartite Pure States

Luke Oeding, Ian Tan

Abstract. We introduce a broad lemma, one consequence of which is the higher order singular value decomposition (HOSVD) of tensors (L. De Lathauwer, B. De Moor, and J. Vandewalle, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1253–1278). By an analogous application of the lemma, we find a complex orthogonal version of the HOSVD. Kraus’s algorithm (B. Kraus, Phys. Rev. Lett., 104 (2010), 020504) used the HOSVD to compute normal forms of almost all [Formula: see text]-qubit pure states under the action of the local unitary group. Taking advantage of the double cover [Formula: see text], we produce similar algorithms (distinguished by the parity of [Formula: see text]) that compute normal forms for almost all [Formula: see text]-qubit pure states under the action of the group of stochastic local operations and classical communication.

arXiv:2402.12542•SIAM Journal on Applied Algebra and Geometry•Jan 3, 2025•0 citations

QUANTUM SINGULAR VALUE DECOMPOSITION BASED APPROXIMATION ALGORITHM

László Gyöngyösi, Sándor Imre

Singular Value Decomposition (SVD) is one of the most useful techniques for analyzing data in linear algebra. SVD decomposes a rectangular real or complex matrix into two orthogonal matrices and one diagonal matrix. The proposed Quantum-SVD algorithm interpolates the non-uniform angles in the Fourier domain. The error of the Quantum-SVD approach is some orders lower than the error given by ordinary Quantum Fourier Transformation. Our Quantum-SVD algorithm is a fundamentally novel approach for the computation of the Quantum Fourier Transformation (QFT) of non-uniform states. The presented Quantum-SVD algorithm is based on the singular value decomposition mechanism, and the computation of Quantum Fourier Transformation of non-uniform angles of a quantum system. The Quantum-SVD approach provides advantages in terms of computational structure, being based on QFT and multiplications.

Journal of Circuits Systems and Computers•Sep 15, 2010•3 citations

Quantum tensor singular value decomposition*

Xiaoqiang Wang, Lejia Gu, Heung-wing Lee +1 more

Abstract Tensors are increasingly ubiquitous in various areas of applied mathematics and computing, and tensor decompositions are of practical significance and benefit many applications in data completion, image processing, computer vision, collaborative filtering, etc. Recently, Kilmer and Martin propose a new tensor factorization strategy, tensor singular value decomposition (t-svd), which extends the matrix singular value decomposition to tensors. However, computing t-svd for high dimensional tensors costs much computation and thus cannot efficiently handle large scale datasets. Motivated by advantage of quantum computation, in this paper, we present a quantum algorithm of t-svd for third-order tensors and then extend it to order-p tensors. We prove that our quantum t-svd algorithm for a third-order N dimensional tensor runs in time  N polylog ( N ) if we do not recover classical information from the quantum output state. Moreover, we apply our quantum t-svd algorithm to context-aware multidimensional recommendation systems, where we just need to extract partial classical information from the quantum output state, thus achieving low time complexity.

Journal of Physics Communications•Jun 22, 2021•4 citations
Higher order singular value decomposition (HOSVD) is an important tool for analyzing big data in multilinear algebra and machine learning. In this paper, we present a quantum algorithm for higher order singular value decomposition. Our method allows one to decompose a tensor into a core tensor containing tensor singular values and some unitary matrices by quantum computers. Compared to the classical HOSVD algorithm, our quantum algorithm provides an exponential speedup.
Schmidt decomposition has been used in the local unitary (LU) classification of bipartite quantum states for some time. In order to generalize the LU classification of bipartite quantum states into multipartite quantum states, higher order singular value decomposition (HOSVD) is introduced but specific examples have not been explicitly worked out. In this pedagogical paper, we would like to work out such details in two qubits since the LU classification of two qubits is well known. We first demonstrate the method of HOSVD in two-qubit systems and discuss its properties. In terms of the LU classification of two-qubit states, some subtle differences in the stabilizer groups of entanglement classes are noticed when Schmidt decomposition is substituted by HOSVD. To reconcile the differences between the two, further studies are needed.
Singular Value Decomposition (SVD) is one of the most useful techniques for analyzing data in linear algebra. SVD decomposes a rectangular real or complex matrix into two orthogonal matrices and one diagonal matrix. In this work we introduce a new approach to improve the preciseness of the standard Quantum Fourier Transform. The presented Quantum-SVD algorithm is based on the singular value decomposition mechanism. While the complexity of the proposed scheme is the same as the standard Quantum Fourier Transform, the precision of the Quantum-SVD approach is some orders higher. The Quantum-SVD approach also exploits the benefits of quantum searching.
In this paper, we present a quantum singular value decomposition algorithm for third-order tensors inspired by the classical algorithm of tensor singular value decomposition (t-svd) and then extend it to order-ppp tensors. It can be proved that the quantum version of the t-svd for a third-order tensor A∈RN×N×N\mathcal{A} \in \mathbb{R}^{N\times N \times N}A∈RN×N×N achieves the complexity of O(Npolylog(N))\mathcal{O}(N{\rm polylog}(N))O(Npolylog(N)), an exponential speedup compared with its classical counterpart. As an application, we propose a quantum algorithm for recommendation systems which incorporates the contextual situation of users to the personalized recommendation. We provide recommendations varying with contexts by measuring the output quantum state corresponding to an approximation of this user's preferences. This algorithm runs in expected time O(Npolylog(N)poly(k)),\mathcal{O}(N{\rm polylog}(N){\rm poly}(k)),O(Npolylog(N)poly(k)), if every frontal slice of the preference tensor has a good rank-kkk approximation. At last, we provide a quantum algorithm for tensor completion based on a different truncation method which is tested to have a good performance in dynamic video completion.
Abstract. We introduce a broad lemma, one consequence of which is the higher order singular value decomposition (HOSVD) of tensors (L. De Lathauwer, B. De Moor, and J. Vandewalle, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1253–1278). By an analogous application of the lemma, we find a complex orthogonal version of the HOSVD. Kraus’s algorithm (B. Kraus, Phys. Rev. Lett., 104 (2010), 020504) used the HOSVD to compute normal forms of almost all [Formula: see text]-qubit pure states under the action of the local unitary group. Taking advantage of the double cover [Formula: see text], we produce similar algorithms (distinguished by the parity of [Formula: see text]) that compute normal forms for almost all [Formula: see text]-qubit pure states under the action of the group of stochastic local operations and classical communication.
Singular Value Decomposition (SVD) is one of the most useful techniques for analyzing data in linear algebra. SVD decomposes a rectangular real or complex matrix into two orthogonal matrices and one diagonal matrix. The proposed Quantum-SVD algorithm interpolates the non-uniform angles in the Fourier domain. The error of the Quantum-SVD approach is some orders lower than the error given by ordinary Quantum Fourier Transformation. Our Quantum-SVD algorithm is a fundamentally novel approach for the computation of the Quantum Fourier Transformation (QFT) of non-uniform states. The presented Quantum-SVD algorithm is based on the singular value decomposition mechanism, and the computation of Quantum Fourier Transformation of non-uniform angles of a quantum system. The Quantum-SVD approach provides advantages in terms of computational structure, being based on QFT and multiplications.
Abstract Tensors are increasingly ubiquitous in various areas of applied mathematics and computing, and tensor decompositions are of practical significance and benefit many applications in data completion, image processing, computer vision, collaborative filtering, etc. Recently, Kilmer and Martin propose a new tensor factorization strategy, tensor singular value decomposition (t-svd), which extends the matrix singular value decomposition to tensors. However, computing t-svd for high dimensional tensors costs much computation and thus cannot efficiently handle large scale datasets. Motivated by advantage of quantum computation, in this paper, we present a quantum algorithm of t-svd for third-order tensors and then extend it to order-p tensors. We prove that our quantum t-svd algorithm for a third-order N dimensional tensor runs in time  N polylog ( N ) if we do not recover classical information from the quantum output state. Moreover, we apply our quantum t-svd algorithm to context-aware multidimensional recommendation systems, where we just need to extract partial classical information from the quantum output state, thus achieving low time complexity.