Efficient quantum circuit for singular-value thresholding

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/\varepsilon \right)\right]$ qubits and $O\left[\text{poly}{log}_2\left(1/\varepsilon \right)\right]$ quantum gates in terms of error $O\left(\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.

Figure 1

Overview of the quantum circuit for solving the transformed SVT. Wires with “/” represent the groups of qubits. The norms of the quantum states are omitted for convenience.

Figure 2

A quantum circuit of the unitary ${\mathbf{U}}_{\sigma ,\tau }$.

Figure 3

Quantum circuit for computing $y_k=1-\tau z_k$. The black strip on the right side of the rectangle represents a unitary operation, and the black strip on the left represents the inverse of the corresponding unitary operation.

Figure 4

A quantum circuit of one Newton iteration for computing $g\left(z_k^{\left(i\right)}\right)$.

Figure 5

A quantum circuit for computing $z_k^{\left(s\right)}$ with $s$ iterations.

Figure 6

A quantum circuit for computing the initial state $z_k^{\left(0\right)}$. $X$ is presented as initial $z_k^{\left(0\right)}$, which follows the IEEE 754 floating-point format.

Figure 7

Quantum circuit of the unitary ${\mathbf{R}}_y$.

Figure 8

Example quantum circuit for solving the SVT. ${\mathbf{U}}^{†}$ represents the inverse of all the operations before of ${\mathbf{R}}_y$. Each simplified unitary $e^{i\mathbf{A}{t}_0/2^j}\left(j=1,2,3\right)$ in the figure represents the operation $e^{i\mathbf{A}{t}_0/2^j}\otimes {\mathbf{I}}_n$.

Figure 9

Singular-value distributions of the 120 matrices.

Figure 10

Probability and fidelity based on the solutions obtained by Taylor's method and our method. (a) Probability. (b) Fidelity.

Figure 11

Probability and fidelity with the rank of input matrices. (a) Probability. (b) Fidelity.

Figure 12

(a) Fidelity with different input matrices and different $\tau$. (b) Probability with different input matrices and different $\tau$. (c) The difference of the probabilities in terms of our method and the normal method with different input matrices and different $\tau$.