Variational algorithms for linear algebra

Abstract

Quantum algorithms have been developed for efficiently solving linear algebra tasks. However, they generally require deep circuits and hence universal fault-tolerant quantum computers. In this work, we propose variational algorithms for linear algebra tasks that are compatible with noisy intermediate-scale quantum devices. We show that the solutions of linear systems of equations and matrix-vector multiplications can be translated as the ground states of the constructed Hamiltonians. Based on the variational quantum algorithms, we introduce Hamiltonian morphing together with an adaptive ansatz for efficiently finding the ground state, and show the solution verification. Our algorithms are especially suitable for linear algebra problems with sparse matrices, and have wide applications in machine learning and optimisation problems. The algorithm for matrix multiplications can be also used for Hamiltonian simulation and open system simulation. We evaluate the cost and effectiveness of our algorithm through numerical simulations for solving linear systems of equations. We implement the algorithm on the IBM quantum cloud device with a high solution fidelity of 99.95%.

15 pages

References in corpus (11)

• Quantum algorithm for solving linear systems of equations
• Simulated Quantum Computation of Molecular Energies
• Variational Quantum Linear Solver
• Noise Resilience of Variational Quantum Compiling
• Variational Quantum State Eigensolver
• Mitigating realistic noise in practical noisy intermediate-scale quantum devices
• Quantum simulation with hybrid tensor networks
• Variational Quantum Singular Value Decomposition
• Near-term quantum algorithms for linear systems of equations
• Perturbative quantum simulation
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm

Cited by in corpus (88)

• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• The Variational Quantum Eigensolver: a review of methods and best practices
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Robust data encodings for quantum classifiers
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Variational Quantum Linear Solver
• Solving nonlinear differential equations with differentiable quantum circuits
• Trainability of Dissipative Perceptron-Based Quantum Neural Networks
• Large gradients via correlation in random parameterized quantum circuits
• Variational Quantum State Eigensolver
• Higher Order Derivatives of Quantum Neural Networks with Barren Plateaus
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Evaluating the noise resilience of variational quantum algorithms
• Minimizing estimation runtime on noisy quantum computers
• Towards a Larger Molecular Simulation on the Quantum Computer: Up to 28 Qubits Systems Accelerated by Point Group Symmetry
• On the practical usefulness of the Hardware Efficient Ansatz
• NISQ Computers: A Path to Quantum Supremacy
• Experimental quantum state measurement with classical shadows
• Subtleties in the trainability of quantum machine learning models
• Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets
• Toward Practical Quantum Embedding Simulation of Realistic Chemical Systems on Near-term Quantum Computers
• Calculating transition amplitudes by variational quantum deflation
• Overlapped grouping measurement: A unified framework for measuring quantum states
• Dynamical mean field theory algorithm and experiment on quantum computers
• Quantum unary approach to option pricing
• Robust resource-efficient quantum variational ansatz through evolutionary algorithm
• Quantum Kernel Methods for Solving Differential Equations
• Practical Quantum Computing: solving the wave equation using a quantum approach
• Can Error Mitigation Improve Trainability of Noisy Variational Quantum Algorithms?
• A variational quantum eigensolver for dynamic correlation functions
• Mitigating Barren Plateaus with Transfer-learning-inspired Parameter Initializations
• Application of a variational hybrid quantum-classical algorithm to heat conduction equation
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• Variational Quantum Evolution Equation Solver
• A semi-agnostic ansatz with variable structure for quantum machine learning
• Operator Sampling for Shot-frugal Optimization in Variational Algorithms
• A brief introduction to quantum algorithms
• Variational Quantum Linear Solver with Dynamic Ansatz
• Engineered dissipation to mitigate barren plateaus
• Variational Quantum-Based Simulation of Waveguide Modes
• Towards a variational Jordan-Lee-Preskill quantum algorithm
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Variational Quantum Simulation of Partial Differential Equations: Applications in Colloidal Transport
• Depth analysis of variational quantum algorithms for heat equation
• Enabling Large-Scale and High-Precision Fluid Simulations on Near-Term Quantum Computers
• A hybrid quantum-classical framework for computational fluid dynamics
• Quantum Error Mitigation Relying on Permutation Filtering
• Quantum algorithms for scientific computing
• Variational quantum algorithms for Poisson equations based on the decomposition of sparse Hamiltonians
• Ensemble-learning error mitigation for variational quantum shallow-circuit classifiers
• Complexity of quantum state verification in the quantum linear systems problem
• Variational quantum Gibbs state preparation with a truncated Taylor series
• Variational Quantum Cloning: Improving Practicality for Quantum Cryptanalysis
• Quantum gradient descent algorithms for nonequilibrium steady states and linear algebraic systems
• Computationally Efficient Quantum Expectation with Extended Bell Measurements
• Beyond unital noise in variational quantum algorithms: noise-induced barren plateaus and limit sets
• Hybrid quantum-classical algorithms for solving quantum chemistry in Hamiltonian-wavefunction space
• Experimental Quantum Learning of a Spectral Decomposition
• Highly optimized quantum circuits synthesized via data-flow engines
• Dissipative variational quantum algorithms for Gibbs state preparation
• Variational Quantum Algorithms for Trace Distance and Fidelity Estimation
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
• Characterization of variational quantum algorithms using free fermions
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• Sequential optimal selection of a single-qubit gate and its relation to barren plateau in parameterized quantum circuits
• Variational quantum algorithm for generalized eigenvalue problems and its application to the finite element method
• Emergence of noise-induced barren plateaus in arbitrary layered noise models
• Variational Quantum Support Vector Machine based on $\Gamma$ matrix expansion and Variational Universal-Quantum-State Generator
• Qsun: an open-source platform towards practical quantum machine learning applications
• Quantum Algorithms for Geologic Fracture Networks
• Optimal Parameter Configurations for Sequential Optimization of Variational Quantum Eigensolver
• Can Noise on Qubits Be Learned in Quantum Neural Network? A Case Study on QuantumFlow
• Adaptive shot allocation for fast convergence in variational quantum algorithms
• Near Term Algorithms for Linear Systems of Equations
• Maximising Quantum-Computing Expressive Power through Randomised Circuits
• Variational quantum simulation of long-range interacting systems
• Quantum algorithms for Schrieffer-Wolff transformation
• Improved resource-tunable near-term quantum algorithms for transition probabilities, with applications in physics and variational quantum linear algebra
• Photonic variational quantum eigensolver using entanglement measurements
• Exploiting subspace constraints and ab initio variational methods for quantum chemistry
• The Accuracy vs. Sampling Overhead Trade-off in Quantum Error Mitigation Using Monte Carlo-Based Channel Inversion
• Comprehensive Library of Variational LSE Solvers
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Warm-Start Variational Quantum Policy Iteration
• Notes on Quantum Computing for Thermal Science
• Variational quantum algorithms with invariant probabilistic error cancellation on noisy quantum processors
• Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems