Efficient algorithm for generating Pauli coordinates for an arbitrary linear operator

• URL: http://arxiv.org/abs/2011.08942v1
• Date: Tue, 17 Nov 2020 20:57:39 GMT
• Title: Efficient algorithm for generating Pauli coordinates for an arbitrary linear operator
• Authors: Daniel Gunlycke, Mark C. Palenik, Alex R. Emmert, and Sean A. Fischer
• Abstract summary: We present an efficient algorithm that for our particular basis only involves $mathcal O(mathrm N2logmathrm N)$ operations. Because this algorithm requires fewer than $mathcal O(mathrm N3)$ operations, for large $mathrm N$, it could be used as a preprocessing step for quantum computing algorithms.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Several linear algebra routines for quantum computing use a basis of tensor products of identity and Pauli operators to describe linear operators, and obtaining the coordinates for any given linear operator from its matrix representation requires a basis transformation, which for an $\mathrm N\times\mathrm N$ matrix generally involves $\mathcal O(\mathrm N^4)$ arithmetic operations. Herein, we present an efficient algorithm that for our particular basis transformation only involves $\mathcal O(\mathrm N^2\log_2\mathrm N)$ operations. Because this algorithm requires fewer than $\mathcal O(\mathrm N^3)$ operations, for large $\mathrm N$, it could be used as a preprocessing step for quantum computing algorithms for certain applications. As a demonstration, we apply our algorithm to a Hamiltonian describing a system of relativistic interacting spin-zero bosons and calculate the ground-state energy using the variational quantum eigensolver algorithm on a quantum computer.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
  We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it. Each row of the matrix is encoded as a pure state of some quantum system. The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
  We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix. This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup. We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
  arXiv  Detail & Related papers  (2023-11-07T22:52:56Z)
• Fast quantum algorithm for differential equations [0.5895819801677125]
  We present a quantum algorithm with numerical complexity that is polylogarithmic in $N$ but is independent of $kappa$ for a large class of PDEs. Our algorithm generates a quantum state that enables extracting features of the solution.
  arXiv  Detail & Related papers  (2023-06-20T18:01:07Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
  We propose a class of randomized quantum algorithms for the task of sampling from matrix functions. Our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures.
  arXiv  Detail & Related papers  (2023-02-03T17:22:49Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
  We study problems involving the solution of matrix equations, for which there currently exists no efficient, general quantum procedure. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware.
  arXiv  Detail & Related papers  (2021-12-05T15:42:32Z)
• A quantum algorithm for computing the Carmichael function [0.0]
  Quantum computers can solve many number theory problems efficiently. This paper presents an algorithm that computes the Carmichael function for any integer $N$ with a probability as close to 1 as desired.
  arXiv  Detail & Related papers  (2021-11-03T19:30:27Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.