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

Abstract

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 skewed linear systems for over-determined and under-determined cases. Our input model is such that the columns or rows of the matrix defining the linear system are given via quantum circuits of poly-logarithmic depth and the number of circuits is much smaller than their Hilbert space dimension. Our algorithms have poly-logarithmic 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 poly-logarithmic 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 $⟨0|\mathcal{C}|0⟩$ using $(n+s)$ qubits and $O\left(\log s+d\log (n/s)+d\right)$-depth quantum circuits, where $s\le n$. In comparison, the standard implementation requires $n+1$ qubits and $O(dn)$ 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 $⟨0|\mathcal{C}|0⟩$ 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}$.

28+16 pages, 6 figures

References in corpus (4)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Simulating Hamiltonian dynamics with a truncated Taylor series

Cited by in corpus (6)

• Variational Quantum algorithm for Poisson equation
• Resource-Efficient Hadamard Test Tailored Variational Framework for Nonlinear Dynamics on Quantum Computers
• Simulating the Fermi-Hubbard model with long-range hopping on a quantum computer
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Finding eigenvectors with a quantum variational algorithm
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices