Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
arXiv:2401.08550 · doi:10.22331/q-2025-09-11-1857
Abstract
Many promising quantum applications depend on the efficient quantum simulation of an exponentially large sparse Hamiltonian, a task known as sparse Hamiltonian simulation, which is fundamentally important in quantum computation. Although several theoretically appealing quantum algorithms have been proposed for this task, they typically require a black-box query model of the sparse Hamiltonian, rendering them impractical for near-term implementation on quantum devices. In this paper, we propose a technique named Hamiltonian embedding. This technique simulates a desired sparse Hamiltonian by embedding it into the evolution of a larger and more structured quantum system, allowing for more efficient simulation through hardware-efficient operations. We conduct a systematic study of this new technique and demonstrate significant savings in computational resources for implementing prominent quantum applications. As a result, we can now experimentally realize quantum walks on complicated graphs (e.g., binary trees, glued-tree graphs), quantum spatial search, and the simulation of real-space Schrödinger equations on current trapped-ion and neutral-atom platforms. Given the fundamental role of Hamiltonian evolution in the design of quantum algorithms, our technique markedly expands the horizon of implementable quantum advantages in the NISQ era.
68 pages, 10 figures, an accompanying GitHub repository is at https://github.com/jiaqileng/hamiltonian-embedding
References in corpus (70)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Circuit Quantum Electrodynamics: Coherent Coupling of a Single Photon to a Cooper Pair Box
- Quantum algorithm for solving linear systems of equations
- Quantum computational advantage using photons
- Logical quantum processor based on reconfigurable atom arrays
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Quantum random access memory
- Programmable Quantum Simulations of Spin Systems with Trapped Ions
- Exponential algorithmic speedup by quantum walk
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Realizing quantum Ising models in tunable two-dimensional arrays of single Rydberg atoms
- Simulating Hamiltonian dynamics with a truncated Taylor series
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Spatial search by quantum walk
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Schrieffer-Wolff transformation for quantum many-body systems
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Perfect Transfer of Arbitrary States in Quantum Spin Networks
- Benchmarking an 11-qubit quantum computer
- Quantum computing with neutral atoms
- A Theory of Trotter Error
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Strongly Correlated Quantum Walks in Optical Lattices
- On the relationship between continuous- and discrete-time quantum walk
- tket : A Retargetable Compiler for NISQ Devices
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms
- Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Mirror Inversion of Quantum States in Linear Registers
- Low Depth Quantum Simulation of Electronic Structure
- Experimental Implementation of the Quantum Random-Walk Algorithm
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Exponential improvement in precision for simulating sparse Hamiltonians
- Parametrically Activated Entangling Gates Using Transmon Qubits
- Variational Quantum Linear Solver
- Faster quantum walk algorithm for the two dimensional spatial search
- Variational algorithms for linear algebra
- Faster quantum simulation by randomization
- Observing the space- and time-dependent growth of correlations in dynamically tuned synthetic Ising antiferromagnets
- Resource-efficient digital quantum simulation of -level systems for photonic, vibrational, and spin- Hamiltonians
- Localization phenomena in interacting Rydberg lattice gases with position disorder
- Experimental Quantum Fast Hitting on Hexagonal Graphs
- Time-dependent Hamiltonian simulation with -norm scaling
- Universal Quantum Hamiltonians
- Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice
- Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
- Perturbative Gadgets at Arbitrary Orders
- A randomized quantum algorithm for statistical phase estimation
- Domain wall encoding of discrete variables for quantum annealing and QAOA
- Simulating sparse Hamiltonians with star decompositions
- Time-dependent unbounded Hamiltonian simulation with vector norm scaling
- Bounding the costs of quantum simulation of many-body physics in real space
- Block-encoding structured matrices for data input in quantum computing
- Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer
- Realization of quantum signal processing on a noisy quantum computer
- Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
- Quantum simulation of real-space dynamics
- Localization and criticality in antiblockaded 2D Rydberg atom arrays
- Quantum spatial search in two-dimensional waveguide arrays
- Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
- Circuit complexity of quantum access models for encoding classical data
- Quantum computer-aided design: digital quantum simulation of quantum processors
- On quantum algorithms for the Schrödinger equation in the semi-classical regime
- On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
- Variational quantum iterative power algorithms for global optimization
- Quantum algorithms for escaping from saddle points
- Improving Schrödinger Equation Implementations with Gray Code for Adiabatic Quantum Computers
- On connectivity-dependent resource requirements for digital quantum simulation of -level particles