Simulating Sparse Hamiltonians with Star Decompositions

DOI10.1007/978-3-642-18073-6_8MaRDI QIDQ3070979zbMATH OpenOpenAlexFDO

Authors Andrew M. Childs, Robin Kothari

Publication date 28 January 2011

Published in Theory of Quantum Computation, Communication, and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.3683

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: We present an efficient algorithm for simulating the time evolution due to a sparse Hamiltonian. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian H acts for time t, this algorithm uses (d^2(d+log* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log* N)||Ht||)^{1+o(1)}. To achieve this, we decompose a general sparse Hamiltonian into a small sum of Hamiltonians whose graphs of non-zero entries have the property that every connected component is a star, and efficiently simulate each of these pieces.

Recommendations

• Efficient quantum algorithms for simulating sparse Hamiltonians
• Hamiltonian sparsification and gap-simulation
• Limitations on the simulation of non-sparse Hamiltonians
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• scientific article; zbMATH DE number 6131346
• Optimized spatial matrix representations of quantum Hamiltonians
• Randomized algorithms for Hamiltonian simulation

Cited in

(21)

• A generalized circuit for the Hamiltonian dynamics through the truncated series
• Quantum algorithm design: techniques and applications
• A Quantum Implementation Model for Artificial Neural Networks
• Limitations on the simulation of non-sparse Hamiltonians
• Product formulas for exponentials of commutators
• Bounding the costs of quantum simulation of many-body physics in real space
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Black-box Hamiltonian simulation and unitary implementation
• Optimization of quantum Hamiltonian evolution: from two projection operators to local Hamiltonians
• On the gap of Hamiltonians for the adiabatic simulation of quantum circuits
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Quantum algorithms for Hamiltonian simulation
• Simulating arbitrary pair-interactions by a given Hamiltonian: graph-theoretical bounds on the time-complexity
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• Obtaining a linear combination of the principal components of a matrix on quantum computers
• Multiple network alignment on quantum computers
• Quantum spin dynamics with pairwise-tunable, long-range interactions
• Context-aware quantum simulation of a matrix stored in quantum memory
• Hamiltonian sparsification and gap-simulation
• Algorithm for quantum simulation
• Divide and conquer approach to quantum Hamiltonian simulation

This page was built for publication: Simulating Sparse Hamiltonians with Star Decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3070979)