Quantum-classical algorithms for skewed linear systems with an optimized Hadamard test

The solving of linear systems provides a rich area to investigate the use of nearer-term, noisy, intermediate-scale quantum computers. In this work, we discuss hybrid quantum-classical algorithms for heavily skewed linear systems for overdetermined and underdetermined cases. Our input model is such that the columns or rows of the matrix defining the linear system are given via quantum circuits of polylogarithmic depth and the number of circuits is much smaller than their Hilbert space dimension. Our algorithms have polylogarithmic dependence on the dimension and polynomial dependence in other natural quantities. In addition, we present an algorithm for the special case of a factorized linear system with run time polylogarithmic in the respective dimensions. At the core of these algorithms is the Hadamard test and in the second part of this paper, we consider the optimization of the circuit depth of this test. Given an $n$-qubit and $d$-depth quantum circuit $\mathcal{C}$, we can approximate $\langle 0|\mathcal{C}|0\rangle$ using $(n+s)$ qubits and $O\left({log}_{2}s+d{log}_2(n/s)+d\right)$-depth quantum circuits, where $s\le n$. In comparison, the standard implementation requires $n+1$ qubits and $O\left(dn\right)$ depth. Lattice geometries underlie recent quantum supremacy experiments with superconducting devices. We also optimize the Hadamard test for an $(l_1\times l_2)$ lattice with $l_1\times l_2=n$ and can approximate $\langle 0|\mathcal{C}|0\rangle$ with $(n+1)$ qubits and $O\left(d\left(l_1+l_2\right)\right)$-depth circuits. In comparison, the standard depth is $O\left(d{n}^2\right)$ in this setting. Both of our optimization methods are asymptotically tight in the case of one-depth quantum circuits $\mathcal{C}$.

Figure 1

An example for snakelike order on $4\times 4$ lattice.

Figure 2

Circuit for Hadamard test, $Pr\left(0\right)=\left(1+\mathrm{Re}\langle 0|\mathit{U}|0\rangle \right)/2$ when $j=0$, and $Pr\left(0\right)=\left(1-\mathrm{Im}\langle 0|\mathit{U}|0\rangle \right)/2$ when $j=1$. Here $H$ is Hadamard gate and $S$ is phase gate.

Figure 3

The circuit for Control-$\mathcal{C}$ with $s-1$ ancillas. The circuit of the left-top dashed box perform the copy operation, the right-top box perform the uncompute operation, the red dashed box is the circuit $\mathcal{C}$, and the box in gray is to target gates with one control qubit, $\alpha ,\beta \in \mathbb{C}$ and ${\left|\alpha \right|}^2+{\left|\beta \right|}^2=1$.

Figure 4

(a) $2\times 2$ lattice in snake order and a permutation $\sigma =(1,3,2,4)$. (b) A depth-1, 4 qubit CNOT circuit. (c) The same circuit as in (b) with qubits 2 and 3 swapped.

Figure 5

(Ref. [64]) Implementation of Toffoli gate with one borrowed ancilla qubit.

Figure 6

(Ref. [64]) Converting a Control-$\mathbf{R}\left(\theta \right)$ to CNOTs $+$ one-qubit gates, where $\mathbf{R}\left(\theta \right)=e^{i\varphi }\mathbf{R}\left(a\right)X\mathbf{R}\left(b\right)X\mathbf{R}\left(c\right)$, and $\mathbf{R}\left(a\right)\mathbf{R}\left(b\right)\mathbf{R}\left(c\right)=\mathbf{I}$, where $X$ is Pauli-$X$.