Concentration for Random Product Formulas

Quantum simulation has wide applications in quantum chemistry and physics. Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation. Among them, a simple and powerful technique, called qDRIFT, is known to generate random product formulas for which the average quantum channel approximates the ideal evolution. qDRIFT achieves a gate count that does not explicitly depend on the number of terms in the Hamiltonian, which contrasts with Suzuki formulas. This work aims to understand the origin of this speedup by comprehensively analyzing a single realization of the random product formula produced by qDRIFT. The main results prove that a typical realization of the randomized product formula approximates the ideal unitary evolution up to a small diamond-norm error. The gate complexity is already independent of the number of terms in the Hamiltonian, but it depends on the system size and the sum of the interaction strengths in the Hamiltonian. Remarkably, the same random evolution starting from an arbitrary, but fixed, input state yields a much shorter circuit suitable for that input state. In contrast, in deterministic settings, such an improvement usually requires initial state knowledge. The proofs depend on concentration inequalities for vector and matrix martingales, and the framework is applicable to other randomized product formulas. Our bounds are saturated by certain commuting Hamiltonians.

Popular Summary

Digital quantum simulation is a promising application of quantum computers. Given some Hamiltonian that describes the dynamical evolution of a molecule or material, the goal is to approximate the dynamics by a sequence of (quantum) logic gates. Physicists have long studied approximations where the gates are chosen according to deterministic rules. Recently, researchers have proposed new approximations based on (classically) randomized rules. For some simulation regimes, randomized rules outperform deterministic rules. This phenomenon has been mysterious because of the interplay between randomness from classical and quantum sources.

This paper studies the performance of a single randomly constructed sequence of quantum logic gates, as opposed to an ensemble average over many such sequences. It uncovers several novel insights. (1) A single gate sequence can accurately model the evolution of all quantum states under the Hamiltonian dynamics, but the sequence length depends on the size of the quantum system being simulated. (2) A single gate sequence can accurately model the evolution of a single quantum state; the sequence length is independent of the size of the system but quadratic in the required accuracy. (3) A single gate sequence can accurately model a specific measurement of the evolution of a single quantum state; the sequence length grows linearly with the accuracy.

The paper also introduces new mathematical methods, from the field high-dimensional probability, into the literature on quantum information science. These methods may have wider implications for quantum-computing applications.

Figure 1

Pictorial summary of the main results. (Left) To sample a product formula that works for all $n$-qubit input states and observables with high probability, the number of gates is larger than sampling a product formula that works for a fixed, yet arbitrary, input state (center). Resampling fresh product formulas every time (right) produces an average channel that requires even fewer gates; this is the original qDRIFT guarantee [17].

Figure 2

Illustration of concentration effects for random walks (and their averages) on the unitary group. The expectation $\mathbb{E}[V_N\cdots V_1]$ of a random product formula is not unitary, but it may be very close to the ideal evolution. A sampled random product formula $V_N\cdots V_1$ is unitary, but its distance from the ideal evolution is about $\mathcal{O}(\sqrt{n{t}^2{\lambda }^2/N})$. The average of the random product formulas results in an error of $\mathcal{O}\left(t^2{\lambda }^2/N\right)$.

Figure 3

Numerical experiments for simulating 1D Heisenberg model under different gate count $N$. In All input states (left), we consider $ϵ={∥U-V_N\dots V_1∥}_{\mathrm{\infty }}$, which considers the error over all input states and observables. In Fixed input state (right), we consider $ϵ={∥U|\psi ⟩-V_N\dots V_1|\psi ⟩∥}_{{\ell }_2}$, which considers the error over all observables. The input state $|\psi ⟩$ is chosen to be the tensor product of single-qubit Haar-random states. For both All input state and Fixed input state, we give an additional plot showing how the error $ϵ$ increases as the system size $n$ increases for a fixed number of gates $N=160$. The $y$-axis is normalized using the average error for system size $n=4$ over $50$ independent runs. Bounds in Theorems 1 and 2 show that the relative error ${ϵ}_n/{ϵ}_{n=4}$ scales as $\sqrt{n/4}$ for All input state and stays as constant $1$ for Fixed input state, which are shown as the dotted lines. The shaded regions are the standard deviation over $50$ independent runs.

Figure 4

Illustration of the worst-case input for a product formula simulating evolution of a simple Hamiltonian. The Hamiltonian $H=1/n\sum _{k=1}^n{Z}_k$ produces a time evolution that factorizes into single qubit unitaries $U$ (left). A product formula with fewer than $n/2$ single-site terms (right) is too small to address all qubits; at least $n/2$ of them must remain untouched. These errors accumulate for a GHZ state comprised of these untouched qubits. If $n$ is large, even small evolution times {$U=\exp [-i(\pi /n)Z]$} can accumulate and lead to a maximal approximation error [$⟨\mathrm{GHZ}(+),\mathrm{GHZ}(-)⟩=0$].

Figure 5

Illustration of the probabilistic proof for the commuting Hamiltonian given in Eq. (16). We consider all the $2^n$ computational basis states as the starting state. The probability for one of the starting state to incur at least an error $ϵ$ is exponentially smaller than the probability for the maximum of the $2^n$ starting states to incur error $>ϵ$. However the failure probability is exponential suppressed by increasing the gate count $N$. Hence one need only to set $N=n/{ϵ}^2$.