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:1711.08896 · Physical Review A

Efficient quantum circuit for singular-value thresholding

Bojia Duan, Jiabin Yuan, Ying Liu, Dan Li

Published Jul 10, 2018• 31 citations
arXivHTMLPDF

Abstract

A singular-value thresholding (SVT) operation is a fundamental core module of many mathematical models in computer vision and machine learning, particularly for many nuclear norm minimizing-based problems. A quantum SVT (QSVT) algorithm was proposed in Phys. Rev. A. 96, 032301 (2017) to solve an image-classification problem. This algorithm runs in $O\left[{log}_{2}\left(pq\right)\right]$, an exponential speed improvement over the classical algorithm, which runs in $O\left[\text{poly}\left(pq\right)\right]$. In this paper, we design a scalable quantum circuit for a QSVT. The quantum circuit is designed with $O\left[{log}_{2}\left(pq/\ensuremath{\varepsilon}\right)\right]$ qubits and $O\left[\text{poly}{log}_{2}\left(1/\ensuremath{\varepsilon}\right)\right]$ quantum gates in terms of error $O\left(\ensuremath{\varepsilon}\right)$. We also show that a high-probability and high-fidelity output can be obtained in one iteration of the quantum circuit. The quantum circuit for a QSVT implies a tempting possibility for experimental realization on a quantum computer. Finally, we propose a small-scale quantum circuit for a QSVT. We numerically simulate and demonstrate the performance of this circuit, verifying its capability to solve the intended SVT.

DOI
10.1103/physreva.98.012308

Related papers

Optimized quantum singular value thresholding algorithm based on a hybrid quantum computer

Yangyang Ge, Zhimin Wang, Wen Zheng +9 more

Quantum singular value thresholding (QSVT) algorithm, as a core module of many mathematical models, seeks the singular values of a sparse and low rank matrix exceeding a threshold and their associated singular vectors. The existing all-qubit QSVT algorithm demands lots of ancillary qubits, remaining a huge challenge for realization on near-term intermediate-scale quantum computers. In this paper, we propose a hybrid QSVT (HQSVT) algorithm utilizing both discrete variables (DVs) and continuous variables (CVs). In our algorithm, raw data vectors are encoded into a qubit system and the following data processing is fulfilled by hybrid quantum operations. Our algorithm requires O[log(MN)] qubits with O(1) qumodes and totally performs O(1) operations, which significantly reduces the space and runtime consumption.

Chinese Physics B•Dec 8, 2021•0 citations

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

András Gilyén, Yuan Su, Guang Hao Low +1 more

An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.

arXiv:1806.01838•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•645 citations

Unrolling SVT to Obtain Computationally Efficient SVT for N-Qubit Quantum State Tomography

Siva Shanmugam, Sheetal Kalyani

Quantum state tomography aims to estimate the state of a quantum mechanical system which is described by a trace one, Hermitian positive semidefinite complex matrix, given a set of measurements of the state. Existing works focus on estimating the density matrix that represents the state, using a compressive sensing approach, with fewer measurements than that required for a tomographically complete set, with the assumption that the true state has a low rank. One very popular method to estimate the state is the use of the Singular Value Thresholding (SVT) algorithm. In this work, we present a machine learning approach to estimate the quantum state of n-qubit systems by unrolling the iterations of SVT which we call Learned Quantum State Tomography (LQST). As merely unrolling SVT may not ensure that the output of the network meets the constraints required for a quantum state, we design and train a custom neural network whose architecture is inspired from the iterations of SVT with additional layers to meet the required constraints. We show that our proposed LQST with very few layers reconstructs the density matrix with much better fidelity than the SVT algorithm which takes many hundreds of iterations to converge. We also demonstrate the reconstruction of the quantum Bell state from an informationally incomplete set of noisy measurements.

arXiv:2212.08852•IEEE Transactions on Signal Processing•Jan 1, 2023•7 citations

A quantum hamiltonian simulation benchmark

Yulong Dong, K. Birgitta Whaley, Lin Lin

Abstract Hamiltonian simulation is one of the most important problems in quantum computation, and quantum singular value transformation (QSVT) is an efficient way to simulate a general class of Hamiltonians. However, the QSVT circuit typically involves multiple ancilla qubits and multi-qubit control gates. In order to simulate a certain class of n -qubit random Hamiltonians, we propose a drastically simplified quantum circuit that we refer to as the minimal QSVT circuit, which uses only one ancilla qubit and no multi-qubit controlled gates. We formulate a simple metric called the quantum unitary evolution score (QUES), which is a scalable quantum benchmark and can be verified without any need for classical computation. Under the globally depolarized noise model, we demonstrate that QUES is directly related to the circuit fidelity, and the potential classical hardness of an associated quantum circuit sampling problem. Under the same assumption, theoretical analysis suggests there exists an ‘optimal’ simulation time t opt ≈ 4.81, at which even a noisy quantum device may be sufficient to demonstrate the potential classical hardness.

arXiv:2108.03747•npj Quantum Information•Nov 9, 2022•24 citations

Quantum algorithm for support matrix machines

Bojia Duan, Jiabin Yuan, Ying Liu +1 more

We propose a quantum algorithm for support matrix machines (SMMs) that efficiently addresses an image classification problem by introducing a least-squares reformulation. This algorithm consists of two core subroutines: a quantum matrix inversion (Harrow-Hassidim-Lloyd, HHL) algorithm and a quantum singular value thresholding (QSVT) algorithm. The two algorithms can be implemented on a universal quantum computer with complexity $O\left[log\left(npq\right)\right]$ and $O\left[log\left(pq\right)\right]$, respectively, where $n$ is the number of the training data and $pq$ is the size of the feature space. By iterating the algorithms, we can find the parameters for the SMM classfication model. Our analysis shows that both HHL and QSVT algorithms achieve an exponential increase of speed over their classical counterparts.

Physical Review A•Sep 1, 2017•65 citations

An Exact Quantum Principal Component Analysis Algorithm Based on Quantum Singular Value Threshold

Chen He, Jiazhen Li, Weiqi Liu

Quantum principal component analysis (qPCA) is the quantum version of principal component analysis (PCA). In this paper, based on the quantum singular value threshold (qSVT), we propose an exact quantum principal component analysis algorithm, which screens the data components through the threshold, rather than output all components of data. Compared with other improved qPCA algorithms, our proposed algorithm does not require to adjust the parameters to obtain estimated results. Instead, it yields exact results directly, and the quantum circuit designed is simpler because almost half of the quantum gates are reduced. We implemented our qPCA algorithm on the IBM quantum computing platform: IBM Quantum Experience, and the experimental results verified correctness of our algorithm.

•Oct 2, 2020•2 citations
A singular-value thresholding (SVT) operation is a fundamental core module of many mathematical models in computer vision and machine learning, particularly for many nuclear norm minimizing-based problems. A quantum SVT (QSVT) algorithm was proposed in Phys. Rev. A. 96, 032301 (2017) to solve an image-classification problem. This algorithm runs in O[log2(pq)]O\left[{log}_{2}\left(pq\right)\right]O[log2​(pq)], an exponential speed improvement over the classical algorithm, which runs in O[poly(pq)]O\left[\text{poly}\left(pq\right)\right]O[poly(pq)]. In this paper, we design a scalable quantum circuit for a QSVT. The quantum circuit is designed with O[log2(pq/\ensuremathε)]O\left[{log}_{2}\left(pq/\ensuremath{\varepsilon}\right)\right]O[log2​(pq/\ensuremathε)] qubits and O[polylog2(1/\ensuremathε)]O\left[\text{poly}{log}_{2}\left(1/\ensuremath{\varepsilon}\right)\right]O[polylog2​(1/\ensuremathε)] quantum gates in terms of error O(\ensuremathε)O\left(\ensuremath{\varepsilon}\right)O(\ensuremathε). We also show that a high-probability and high-fidelity output can be obtained in one iteration of the quantum circuit. The quantum circuit for a QSVT implies a tempting possibility for experimental realization on a quantum computer. Finally, we propose a small-scale quantum circuit for a QSVT. We numerically simulate and demonstrate the performance of this circuit, verifying its capability to solve the intended SVT.
Quantum singular value thresholding (QSVT) algorithm, as a core module of many mathematical models, seeks the singular values of a sparse and low rank matrix exceeding a threshold and their associated singular vectors. The existing all-qubit QSVT algorithm demands lots of ancillary qubits, remaining a huge challenge for realization on near-term intermediate-scale quantum computers. In this paper, we propose a hybrid QSVT (HQSVT) algorithm utilizing both discrete variables (DVs) and continuous variables (CVs). In our algorithm, raw data vectors are encoded into a qubit system and the following data processing is fulfilled by hybrid quantum operations. Our algorithm requires O[log(MN)] qubits with O(1) qumodes and totally performs O(1) operations, which significantly reduces the space and runtime consumption.
An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.
Quantum state tomography aims to estimate the state of a quantum mechanical system which is described by a trace one, Hermitian positive semidefinite complex matrix, given a set of measurements of the state. Existing works focus on estimating the density matrix that represents the state, using a compressive sensing approach, with fewer measurements than that required for a tomographically complete set, with the assumption that the true state has a low rank. One very popular method to estimate the state is the use of the Singular Value Thresholding (SVT) algorithm. In this work, we present a machine learning approach to estimate the quantum state of n-qubit systems by unrolling the iterations of SVT which we call Learned Quantum State Tomography (LQST). As merely unrolling SVT may not ensure that the output of the network meets the constraints required for a quantum state, we design and train a custom neural network whose architecture is inspired from the iterations of SVT with additional layers to meet the required constraints. We show that our proposed LQST with very few layers reconstructs the density matrix with much better fidelity than the SVT algorithm which takes many hundreds of iterations to converge. We also demonstrate the reconstruction of the quantum Bell state from an informationally incomplete set of noisy measurements.
Abstract Hamiltonian simulation is one of the most important problems in quantum computation, and quantum singular value transformation (QSVT) is an efficient way to simulate a general class of Hamiltonians. However, the QSVT circuit typically involves multiple ancilla qubits and multi-qubit control gates. In order to simulate a certain class of n -qubit random Hamiltonians, we propose a drastically simplified quantum circuit that we refer to as the minimal QSVT circuit, which uses only one ancilla qubit and no multi-qubit controlled gates. We formulate a simple metric called the quantum unitary evolution score (QUES), which is a scalable quantum benchmark and can be verified without any need for classical computation. Under the globally depolarized noise model, we demonstrate that QUES is directly related to the circuit fidelity, and the potential classical hardness of an associated quantum circuit sampling problem. Under the same assumption, theoretical analysis suggests there exists an ‘optimal’ simulation time t opt ≈ 4.81, at which even a noisy quantum device may be sufficient to demonstrate the potential classical hardness.
We propose a quantum algorithm for support matrix machines (SMMs) that efficiently addresses an image classification problem by introducing a least-squares reformulation. This algorithm consists of two core subroutines: a quantum matrix inversion (Harrow-Hassidim-Lloyd, HHL) algorithm and a quantum singular value thresholding (QSVT) algorithm. The two algorithms can be implemented on a universal quantum computer with complexity O[log(npq)]O\left[log\left(npq\right)\right]O[log(npq)] and O[log(pq)]O\left[log\left(pq\right)\right]O[log(pq)], respectively, where nnn is the number of the training data and pqpqpq is the size of the feature space. By iterating the algorithms, we can find the parameters for the SMM classfication model. Our analysis shows that both HHL and QSVT algorithms achieve an exponential increase of speed over their classical counterparts.
Quantum principal component analysis (qPCA) is the quantum version of principal component analysis (PCA). In this paper, based on the quantum singular value threshold (qSVT), we propose an exact quantum principal component analysis algorithm, which screens the data components through the threshold, rather than output all components of data. Compared with other improved qPCA algorithms, our proposed algorithm does not require to adjust the parameters to obtain estimated results. Instead, it yields exact results directly, and the quantum circuit designed is simpler because almost half of the quantum gates are reduced. We implemented our qPCA algorithm on the IBM quantum computing platform: IBM Quantum Experience, and the experimental results verified correctness of our algorithm.