Advances in optimal Hamiltonian simulation

Presenting Author: Guang Hao Low, Microsoft Research
Contributing Author(s): Isaac Chuang

The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian \(\hat{H}\), and the quantum circuit \(\hat{U}\) that encodes its description. In the quest to better approximate time-evolution \(e^{-i\hat{H}t}\) with error \(\epsilon\), we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits \(\hat{U}\) for generalized measurement. This allows us to define a uniform spectral amplification problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring \(\hat{U}\) into \(n=1,2,3\) unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian and recent 'quantum signal processing' and 'Qubitization' techniques, specializing these results allow us simulate time-evolution by \(d\)-sparse Hamiltonians using \(\mathcal{O}\left(t(d \|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/\epsilon)}\right)\) queries given the norms \(\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}\). Up to logarithmic factors, this is a strict polynomial improvement upon prior art.

Read this article online: https://arxiv.org/abs/1610.06546, https://arxiv.org/abs/1707.05391

(Session 4 : Thursday from 3:45pm-4:15pm)


SQuInT Chief Organizer
Akimasa Miyake, Assistant Professor

SQuInT Co-Organizer
Mark M. Wilde, Assistant Professor LSU

SQuInT Administrator
Gloria Cordova
505 277-1850

SQuInT Founder
Ivan Deutsch, Regents' Professor

Tweet About SQuInT 2018!