Efficient quantum circuit for singular-value thresholding

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.