Black-box Hamiltonian simulation and unitary implementation
arXiv:0910.4157 · doi:10.26421/QIC12.1-2
Abstract
We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D^4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N x N unitary operation use O(N^2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(sqrt{N}) queries, which is optimal.
19 pages, 3 figures, minor corrections
References in corpus (5)
Cited by in corpus (32)
- Quantum Chemistry in the Age of Quantum Computing
- Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
- Near-optimal ground state preparation
- Faster quantum simulation by randomization
- Black-box quantum state preparation without arithmetic
- Simulating sparse Hamiltonians with star decompositions
- Quantum algorithm for calculating molecular vibronic spectra
- Provably accurate simulation of gauge theories and bosonic systems
- Resilience of quantum random access memory to generic noise
- Time-dependent unbounded Hamiltonian simulation with vector norm scaling
- Time-marching based quantum solvers for time-dependent linear differential equations
- Bayesian Deep Learning on a Quantum Computer
- Compilation by stochastic Hamiltonian sparsification
- Introduction to Quantum Algorithms for Physics and Chemistry
- Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
- Double sparse quantum state preparation
- Quantum Algorithm for Solving the Advection Equation using Hamiltonian Simulation
- Fast Black-Box Quantum State Preparation
- qSWIFT: High-order randomized compiler for Hamiltonian simulation
- Optimally controlled quantum discrimination and estimation
- New Developments in Quantum Algorithms
- Multi-nucleon structure and dynamics via quantum computing
- Simulation of linear non-Hermitian boundary-value problems with quantum singular value transformation
- Hybrid algorithms to solve linear systems of equations with limited qubit resources
- Quantum algorithms for powering stable Hermitian matrices
- Decoherence on Staggered Quantum Walks
- Toward simulating quantum field theories with controlled phonon-ion dynamics: A hybrid analog-digital approach
- Ladder Operator Block-Encoding
- Low Depth Phase Oracle Using a Parallel Piecewise Circuit
- Optimizing Quantum Walk Search on a Reduced Uniform Complete Multi-Partite Graph
- Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm
- Controlling quantum chaos via Parrondo strategies on noisy intermediate-scale quantum hardware