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}$.

arXiv comment28+16 pages, 6 figures

References in corpus (23)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Supervised learning with quantum enhanced feature spaces
• Quantum machine learning in feature Hilbert spaces
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum random access memory
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Variational ansatz-based quantum simulation of imaginary time evolution
• Benchmarking an 11-qubit quantum computer
• Variational quantum simulation of general processes
• A quantum linear system algorithm for dense matrices
• Genuine 12-qubit entanglement on a superconducting quantum processor
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Parallel Entangling Operations on a Universal Ion Trap Quantum Computer
• Quantum Algorithm for Linear Regression
• Quantum circuit optimizations for NISQ architectures
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Near-term quantum algorithms for linear systems of equations
• Quantum linear systems algorithms: a primer
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Randomized Row and Column Iterative Methods with a Quantum Computer

Cited by in corpus (7)

• Variational Quantum algorithm for Poisson equation
• The SWITCH test for discriminating quantum evolutions
• 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