Tridiagonal matrix decomposition for Hamiltonian simulation on a quantum computer

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.

References in corpus (16)

• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• A Theory of Trotter Error
• Efficient quantum measurement of Pauli operators in the presence of finite sampling error
• Quantum Algorithm for Simulating the Wave Equation
• Mutually unbiased binary observable sets on N qubits
• Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas
• Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters
• Ordering of Trotterization: Impact on Errors in Quantum Simulation of Electronic Structure
• Practical Quantum Computing: solving the wave equation using a quantum approach
• Synthesizing efficient circuits for Hamiltonian simulation
• Fast Classical Simulation of Hamiltonian Dynamics by Simultaneous Diagonalization Using Clifford Transformation with Parallel Computation