Simulating high-accuracy nuclear motion Hamiltonians in discrete variable representation using Walsh–Hadamard QROM with fault-tolerant quantum computers
Ákos Nagy
joint with: Michał Szczepanik and Emil Żak
Rovibrational Hamiltonians
- A few atoms with rotational and vibrational degrees of freedom.
- Applications:
- Spectroscopy
- Chemical reaction modelling (ultracold physics, biochemistry, catalysis)
- Astrophysics
- Atmospheric sciences
- Problem: the dimension of the Hilbert space grows exponentially with the size of the system. Hence, memory requirements also grow exponentially.
- Our methods:
- We use Born–Oppenheimer Hamiltonians with exact kinetic energy part expressed in internal coordinates of the system.
- Discrete variable representation: Shifts complexities into encoding the Potential Energy Surfaces (PES) at quadrature grid points of the system. Switching to this representation is classically hard, but quantumly cheap!
- Walsh–Hadamard encoding: Improves the efficiency of the PES encoding, compared to SOTA methods.
- Example: The quantum volume required for computing the rovibrational spectrum of water can be reduced by a factor of $\approx 10^5$ compared to other quantum algorithms.
Discrete variable representation
- Many-body QM system with Hamiltoinian $\hat{H} = \hat{K} + \hat{V}$, where $\hat{K} = \sum g_{ij} \hat{P}_i \hat{P}_j$ is the kinetic term and $V : \mathbb{R}^D \rightarrow \mathbb{R}$ is the potential. $D$ is the number of degrees of freedom (large).
- Block encoding $\hat{H}$ on a quantum computer: Discrete variable representation (DVR) yield a simple encoding of $\hat{K}$, while keeping $\hat{V}$ diagonal: $\hat{V} | q > = V(\bar{q}) | q >$.
- Block encode $\hat{V}$: use QROM + position operator
\begin{align}
\mathrm{QROM}: | q > &\mapsto | q > | V(\bar{q}) >, \\
\mathrm{position}: | y > &\mapsto y | y >,
\end{align}
and then $| q > \mapsto | q > | V(\bar{q}) > \mapsto V(\bar{q}) | q > | V(\bar{q}) > \mapsto V(\bar{q}) | q >$.
- Typically the QROM is "costly", while the position operator is "cheap". The standard method for QROM is the "Select-SWAP" method (Low et al, '18).
- Our approach is based on the a Walsh–Hadamard Transform (somewhat similar to the recent Xanadu paper, Alonso-Linaj et al, December '25).
QROMs (continued)
- Cliffords: $H$, $S$, $CX$.
- Magic: Toffoli or $T$. These are more (but not infinitely more) costly, than Cliffords.
- Resources:
- Cost = $C + F \cdot M$, where $1 \ll F \leqslant 300$
- Number of ancillas.
- We constructed QROMs for certain nuclear motion Hamiltonians that outperformed other SOTA implementation in both of those metric.
- Our approach is based on the a Walsh–Hadamard Transform.
QROMs (state-of-the-art)
- The best-known and most commonly used QROM implementation is called the Select–Swap method.
- This design is sequential in the nonzero values of $f$.
- Thus, it is useful when the $f$ is sparse.
- The Select–Swap QROM is, in fact, a family of implementations, parametrized by $1 \leqslant \lambda$. Increasing $\lambda$ decreases the number of Toffolis and the overall circuit depht, but increases the number of ancillas.
- Resources:
- Toffoli count $\approx \tfrac{N_f}{\lambda} + 2 d \lambda$.
- Clifford count $\approx d N_f$.
- Number of ancillas = $\lambda d$.
- The Toffoli count is minimized for $\lambda \approx \sqrt{\tfrac{N_f}{2 d}}$.
- This is Toffoli-optimal, but comes at the cost of $\approx \sqrt{d N_f}$ ancillas. When $N_f = 2^n$ and $n \approx 100$, this comparable to the number of fermions on Earth.
- No proof for efficiency when Cliffords are accounted for!
Walsh–Hadamard QROM
- Our method uses the Walsh–Hadamard transform of the input data:
\begin{equation}
wh(f) (z) := \sum\limits_{x \in \mathbb{F}_2^n} (- 1)^{x \cdot z} f(x).
\end{equation}
- This design is sequential in the nonzero values of $wh(f)$.
- Thus, it is useful when the $wh(f)$ is sparse!
- Resources:
- Toffoli count $= O \left( d W_f \right)$.
- Clifford count $= O \left( d W_f \right)$.
- Number of ancillas = $O(d)$.
- High level idea of the construction:
- The parities $(- 1)^{x \cdot z}$ can be computed with $O(1)$ $CX$ gates on the key registers.
- Controlled by the parity, a $wh(f)(z)$ adder/subtractor acts on the value register (costs $O(d)$ Toffolis and $CX$ gates).
Walsh–Hadamard QROM (continued)
- Nontrivial observation: $wh(f)$ is sparse, or sparsely approximatable, if $f$ is smooth enough.
- Such functions arise, for example, as Potential Energy Surfaces (PES) that need to encoded when simulating nuclear motion Hamiltonians:
Encoding analytic functions
(More recent work with my undergrad, Arjun Dixit (U of T).)
- Recall: we want $U_{F, n}$ such that: $U_{F, n} | x >_n | z >_d = | x >_n | z + F(\bar{x}) >_d$.
- When the function $F : [0, 1] \rightarrow \mathbb{R}$ is analytic, one can use Taylor expansion: For $(x, y) \in \mathbb{F}_2^k \times \mathbb{F}_2^{n - k}$
\begin{equation}
F \left( \bar{x} + 2^{- k} \bar{y} \right) = \sum\limits_{q = 0}^p \frac{F^{(q)} (\bar{x})}{q!} \frac{\bar{y}^q}{2^{qk}} + O_F \left( 2^{- (p + 1) k} \right).
\end{equation}
- Observe: For each $x$ we need the QROM of a polynomial function, which is cheaper, when the degree is not too large.
- Combining the Select-SWAP method (to control on $x$) with the WH-QROM (or other polynomial expansion based QROMs), we get cheap implementations.
- Example Theorem: On $n$ qubits, choosing $k_n$, so that $\tfrac{k_n^2}{\log_2 (k_n)} = n$, the Tofolli cost of $U_{F, n}$, up to $O(2^{- n})$ error in $F$, is $2^{2 k_n + o(k_n)}$, while using $O \left( poly(n) \right)$ ancillas and $O \left( poly(n) 2^{2 k_n} \right)$ Cliffords. The Tofolli cost can be reduced to $2^{k_n + o(k_n)}$ by using (many) ancillas.
- Example Corollary: "smooth" states can be prepared with $O_\psi \left( n 2^{k_n} \right)$ Tofolli gates.
Thank you for your attention!