Skip to content

qDRIFT

Rough overview (in words)

qDRIFT (the quantum stochastic drift protocol) [1] assumes a Pauli access model and approximates the Hamiltonian simulation channel (as opposed to the unitary) by randomly sampling a term from the Hamiltonian (according to the coefficient magnitudes) and then evolving under the chosen term. This process is repeated for a number of steps. Because it approximates the channel, rather than the unitary, it can be more difficult to use qDRIFT as a coherent subroutine in other algorithms (see caveats below).

The error in qDRIFT depends on the 1-norm of Hamiltonian coefficients. Its main advantage is that it does not explicitly depend on the number of terms in the Hamiltonian and has small constant overheads. This may make it well suited to systems with rapidly decaying interaction strengths, dominated by a few large terms. However, its time and error dependence is asymptotically worse than other methods. This seems to originate from its randomized nature [2]. qDRIFT can also be extended to time-dependent Hamiltonian simulation, where it has the benefit of scaling as \(\int_0^t \nrm{H(t')} dt'\), rather than as \(t \max_{t'} \nrm{H(t')}\) common to some other Hamiltonian simulation algorithms [3]. We will restrict our discussion below to the time-independent case.

Rough overview (in math)

Given a Hamiltonian in the Pauli decomposition \(H = \sum_i h_i H_i\) (with \(\nrm{H_i}=1\)), qDRIFT provides a stochastic channel \(\mathcal{N}\) which when applied for \(N\) steps, approximates the Hamiltonian simulation channel

\[\begin{equation} \nrm{\mathcal{N}^N - e^{iHt} (\cdot)e^{-iHt}}_{\diamond} \le \epsilon \end{equation}\]

to within diamond-norm error \(\epsilon\).

qDRIFT proceeds by randomly sampling a term according to its importance

\[\begin{align} X_k \stackrel{i.i.d.}{\sim} \quad \frac{\mathrm{sign}(h_i) H_i}{p_i} \quad \text{where} \quad p_i = \frac{|h_i|}{\nrm{H}_1} \end{align}\]

and \(\nrm{H}_1: = \sum_i |h_i|\) is the sum of the strengths. Each step of qDRIFT then evolves the randomly sampled term \(X_k\) for a short period of time \(t/N\), where \(N\) is a free parameter determining the number of qDRIFT steps, which controls the error in the simulation. This implements the following quantum channel

\[\begin{align} \mathcal{N}[\rho]: = \mathbb{E}[e^{i(t/N)X_k}\rho e^{-i(t/N)X_k}]. \end{align}\]

As discussed above, this channel is repeated for \(N\) steps, in order to approximate the Hamiltonian simulation channel.

Dominant resource cost (gates/qubits)

For an \(n\)-qubit Hamiltonian, qDRIFT acts on \(n\) register qubits, and no additional ancilla qubits are required.

In order to simulate the Hamiltonian evolution channel to within diamond-norm error \(\epsilon\), we require

\[\begin{align} N = \mathcal{O}\left( \frac{\nrm{H}_1^2 t^2}{\epsilon} \right) \end{align}\]

steps of qDRIFT [1, 2]. While the diamond-norm is a different error metric to the spectral norm used in other articles in this section, both provide upper bounds on the error in an observable measured with respect to the time-evolved state [1]. For unitary channels, the diamond norm is effectively equal to the spectral norm (see, e.g., discussion in [4], up to constant factors).

The gate complexity is the number of steps multiplied by the individual costs of the elementary evolution \(e^{i(t/N)X_k}\), which scales linearly with the locality of the Pauli operator \(X_k\). When using qDRIFT to time evolve a state (e.g., for the purpose of measuring an observable), it is important to average the results over a sufficient number of independently sampled qDRIFT circuits [1].

Caveats

The qDRIFT algorithm has a quadratic dependence on time and linear dependence on the error \(\epsilon\), while other Hamiltonian simulation methods can achieve linear time dependence and logarithmic error dependence. A higher-order variant of qDRIFT was recently developed which improves the error dependence [5]. It is currently unclear how to design higher-order variants of qDRIFT that improve the time dependence, which appears to result from the randomized nature of the algorithm [2].

As discussed above, qDRIFT approximates the time evolution channel, rather than the unitary \(e^{iHt}\). As a result, it can be difficult to incorporate as a subroutine in algorithms that seek to manipulate the unitary directly—for example, measuring \(\mathrm{Tr}\left(U(t) \rho \right)\). Tasks of this form feature in some approaches for phase estimation [6], motivating alternate, qDRIFT-inspired approaches, in order to exploit qDRIFT-like benefits [7].

Example use cases

Bibliography

  1. Earl Campbell. Random compiler for fast hamiltonian simulation. Physical Review Letters, 8 2019. arXiv: https://arxiv.org/abs/1811.08017. doi:10.1103/physrevlett.123.070503.

  2. Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp. Concentration for random product formulas. PRX Quantum, 10 2021. arXiv: https://arxiv.org/abs/2008.11751. doi:10.1103/prxquantum.2.040305.

  3. Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe. Time-dependent hamiltonian simulation with \(l^1\)-norm scaling. Quantum, 4:254, 2020. arXiv: https://arxiv.org/abs/1906.07115. doi:10.22331/q-2020-04-20-254.

  4. Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. arXiv: https://arxiv.org/abs/2302.14066, 2023.

  5. Kouhei Nakaji, Mohsen Bagherimehrab, and Alan Aspuru-Guzik. Qswift: high-order randomized compiler for hamiltonian simulation. arXiv: https://arxiv.org/abs/2302.14811, 2023.

  6. Lin Lin and Yu Tong. Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3:010318, 2 2022. arXiv: https://arxiv.org/abs/2102.11340. doi:10.1103/PRXQuantum.3.010318.

  7. Kianna Wan, Mario Berta, and Earl T. Campbell. Randomized quantum algorithm for statistical phase estimation. Physical Review Letters, 129:030503, 7 2022. arXiv: https://arxiv.org/abs/2110.12071. URL: https://link.aps.org/doi/10.1103/PhysRevLett.129.030503, doi:10.1103/PhysRevLett.129.030503.

  8. Yingkai Ouyang, David R. White, and Earl T. Campbell. Compilation by stochastic hamiltonian sparsification. Quantum, 4:235, 2 2020. arXiv: https://arxiv.org/abs/1910.06255. URL: https://doi.org/10.22331/q-2020-02-27-235, doi:10.22331/q-2020-02-27-235.

  9. Abhishek Rajput, Alessandro Roggero, and Nathan Wiebe. Hybridized methods for quantum simulation in the interaction picture. Quantum, 6:780, 2022. arXiv: https://arxiv.org/abs/2109.03308. doi:10.22331/q-2022-08-17-780.

  10. Matthew Hagan and Nathan Wiebe. Composite quantum simulations. arXiv: https://arxiv.org/abs/2206.06409, 2022.

  11. Oriel Kiss, Michele Grossi, and Alessandro Roggero. Importance sampling for stochastic quantum simulations. Quantum, 7:977, 4 2023. arXiv: https://arxiv.org/abs/2212.05952. URL: https://doi.org/10.22331/q-2023-04-13-977, doi:10.22331/q-2023-04-13-977.