Tridiagonal matrix decomposition for Hamiltonian simulation on a quantum computer
- URL: http://arxiv.org/abs/2310.00121v3
- Date: Tue, 21 May 2024 09:14:24 GMT
- Title: Tridiagonal matrix decomposition for Hamiltonian simulation on a quantum computer
- Authors: Boris Arseniev, Dmitry Guskov, Richik Sengupta, Jacob Biamonte, Igor Zacharov,
- Abstract summary: This work is the efficient procedure for representation of a tridiagonal matrix in the Pauli basis.
It allows one to construct a Hamiltonian evolution circuit without the use of oracles.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The construction of quantum circuits to simulate Hamiltonian evolution is central to many quantum algorithms. State-of-the-art circuits are based on oracles whose implementation is often omitted, and the complexity of the algorithm is estimated by counting oracle queries. However, in practical applications, an oracle implementation contributes a large constant factor to the overall complexity of the algorithm. The key finding of this work is the efficient procedure for representation of a tridiagonal matrix in the Pauli basis, which allows one to construct a Hamiltonian evolution circuit without the use of oracles. The procedure represents a general tridiagonal matrix $2^n \times 2^n$ by systematically determining all Pauli strings present in the decomposition, dividing them into commuting subsets. The efficiency is in the number of commuting subsets $O(n)$. The method is demonstrated using the one-dimensional wave equation, verifying numerically that the gate complexity as function of the number of qubits is lower than the oracle based approach for $n < 15$ and requires half the number of qubits. This method is applicable to other Hamiltonians based on the tridiagonal matrices.
Related papers
- Efficient Implementation of a Quantum Search Algorithm for Arbitrary N [0.0]
This paper presents an enhancement to Grover's search algorithm for instances where $N$ is not a power of 2.
By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases.
arXiv Detail & Related papers (2024-06-19T19:16:40Z) - A tree-approach Pauli decomposition algorithm with application to quantum computing [0.0]
We propose an algorithm with a parallel implementation that optimize this decomposition using a tree approach.
We also explain how some particular matrix structures can be exploited to reduce the number of operations.
arXiv Detail & Related papers (2024-03-18T10:38:06Z) - 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) - 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) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
Coherent control of quantum computations can be used to improve some quantum protocols and algorithms.
We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
arXiv Detail & Related papers (2022-02-10T18:59:52Z) - Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware.
We present an algorithm that compresses the Trotter steps into a single block of quantum gates.
This results in a fixed depth time evolution for certain classes of Hamiltonians.
arXiv Detail & Related papers (2021-08-06T19:38:01Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z) - 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) - Combinatorial optimization through variational quantum power method [0.0]
We present a variational quantum circuit method for the power iteration.
It can be used to find the eigenpairs of unitary matrices and so their associated Hamiltonians.
The circuit can be simulated on the near term quantum computers with ease.
arXiv Detail & Related papers (2020-07-02T10:34:16Z) - Circuit optimization of Hamiltonian simulation by simultaneous
diagonalization of Pauli clusters [1.0587959762260986]
Quantum circuits for exact time evolution of single Pauli operators are well known, and can be extended trivially to sums of commuting Paulis.
In this paper we reduce the circuit complexity of Hamiltonian simulation by partitioning the Pauli operators into mutually commuting clusters.
We show that the proposed approach can help to significantly reduce both the number of CNOT operations and circuit depth for Hamiltonians arising in quantum chemistry.
arXiv Detail & Related papers (2020-03-30T16:29:40Z)
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.